Автор |
Сообщение |
Kallisto |
|
Тема сообщения: Re: Стандартная проверка корректности генератора ходов
Отправлено: Авг 23, 2006 - 11:10 PM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
Аврора считает, что дамкой a1 можно сбить простые b2 и g7 4-мя способами.
NS писал(а): AlexanderS писал(а): Kallisto писал(а): 10 - 22450628
хмм... у меня - 22 450 647
Похоже что одинаковые взятия, но при разном порядке снятия шашек с доски - считаются за действительно разные взятия...
Это у всех так. |
|
|
|
|
|
NS |
|
Тема сообщения: Re: Стандартная проверка корректности генератора ходов
Отправлено: Авг 23, 2006 - 09:08 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
AlexanderS писал(а): Kallisto писал(а): 10 - 22450628
хмм... у меня - 22 450 647
Похоже что одинаковые взятия, но при разном порядке снятия шашек с доски - считаются за действительно разные взятия... |
|
|
|
|
|
AlexanderS |
|
Тема сообщения:
Отправлено: Май 26, 2006 - 04:28 PM
|
|
Зарегистрирован: Авг 29, 2002
Сообщений: 845
Откуда : Якутск
|
|
Kallisto писал(а): А остальные совпадают?
До 10 совпадают, дальше у меня записей нет |
|
|
|
|
|
Kallisto |
|
Тема сообщения:
Отправлено: Май 26, 2006 - 06:55 AM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
А остальные совпадают?
Можно в качестве тестовой использовать какую-либо специальную позицию, в которой проявляются все тонкости шашечных правил.
Но по-моему и начальной вполне достаточно. |
|
|
|
|
|
AlexanderS |
|
Тема сообщения: Re: Стандартная проверка корректности генератора ходов
Отправлено: Май 25, 2006 - 10:44 PM
|
|
Зарегистрирован: Авг 29, 2002
Сообщений: 845
Откуда : Якутск
|
|
Kallisto писал(а): 10 - 22450628
хмм... у меня - 22 450 647 |
|
|
|
|
|
AlexanderS |
|
Тема сообщения: Re: Стандартная проверка корректности генератора ходов
Отправлено: Май 25, 2006 - 10:41 PM
|
|
Зарегистрирован: Авг 29, 2002
Сообщений: 845
Откуда : Якутск
|
|
где-то сохранял эти данные, не могу найти
думается при такой постановке в шашки проблемы в генераторе вряд ли обнаружатся - основная их часть скорее всего будет при множественных дамочных взятиях, в частности - турецкий удар, а на глубине 14 вряд ли много таких позиций встретится. |
|
|
|
|
|
Kallisto |
|
Тема сообщения: Стандартная проверка корректности генератора ходов
Отправлено: Май 25, 2006 - 06:07 PM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
В шахматном программировании есть одна методика проверки корректности генератора ходов, называемая Perft. Организуется полный перебор всех ходов, и подсчитывается число позиций на разных ярусах дерева перебора. Все корректные генераторы ходов должны выдавать одинаковые числа.
Вот эти числа для шашек, посчитанные Каллисто:
1 - 7
2 - 49
3 - 302
4 - 1469
5 - 7482
6 - 37986
7 - 190146
8 - 929905
9 - 4570667
10 - 22450628
11 - 110961169
12 - 545059387
13 - 2675994747
14 - 13138899366
Хотелось бы сверится с другими программами (может у меня еще остались ошибки в генераторе?). Организовать подсчет позиций для определенной глубины перебора очень легко. Вот примерный код на Си:
Код:
double PerftNodes = 0; // количество позиций может переполнить целочисленные переменные
void Perft(int depth)
{
Move moves[MAX_MOVES_CNT]; // массив для хранения ходов
int cnt = GenerateMoves(); // генерация ходов
if (depth == 1)
{
// достигли нужной глубины
// теперь можно посчитать позиции не делая ходов
PerftNodes += cnt;
return;
}
depth--;
for (int i = 0; i < cnt; i++) {
MakeMove(moves[i]);
Perft(depth);
UnmakeMove(moves[i]);
}
}
Если интересно, вот числа для чекерса:
1 - 7
2 - 49
3 - 302
4 - 1469
5 - 7361
6 - 36768
7 - 179740
8 - 845931
9 - 3963680
10 - 18391564
11 - 85242128
12 - 388623673
13 - 1766623630
14 - 7978439499 |
|
|
|
|
|
|