- В этой теме 126 ответов, 8 участников, последнее обновление 17 лет, 1 месяц назад сделано
.
-
Сообщения
-
В шахматном программировании есть одна методика проверки корректности генератора ходов, называемая 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);
Perft(depth);
UnmakeMove(moves);
}
}
Если интересно, вот числа для чекерса:
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где-то сохранял эти данные, не могу найти
думается при такой постановке в шашки проблемы в генераторе вряд ли обнаружатся — основная их часть скорее всего будет при множественных дамочных взятиях, в частности — турецкий удар, а на глубине 14 вряд ли много таких позиций встретится.
А остальные совпадают?
Можно в качестве тестовой использовать какую-либо специальную позицию, в которой проявляются все тонкости шашечных правил.
Но по-моему и начальной вполне достаточно.
10 — 22450628
хмм… у меня — 22 450 647
Похоже что одинаковые взятия, но при разном порядке снятия шашек с доски — считаются за действительно разные взятия…
Аврора считает, что дамкой a1 можно сбить простые b2 и g7 4-мя способами.
10 — 22450628
хмм… у меня — 22 450 647
Похоже что одинаковые взятия, но при разном порядке снятия шашек с доски — считаются за действительно разные взятия…
Это у всех так.
Я конечно идиот, но я уже час мучаюсь, как бы их (одинаковые) исключить, и притом быстро
)))
Написал генератор (0x88) Сейчас передохну, и начну пробовать perfit.skoree vsego Avrora zapisivayet xod kak: a1xc3xh8 ili a1xd4xh8 … nu i tak dalee. Voobshe-to pravilno, ved dobav chernim eshe jdnu shahku na b6, i togda mozhno a1xd4xa7 😆
Kazhdy programmiruyet po svoemu
skoree vsego Avrora zapisivayet xod kak: a1xc3xh8 ili a1xd4xh8 … nu i tak dalee. Voobshe-to pravilno, ved dobav chernim eshe jdnu shahku na b6, i togda mozhno a1xd4xa7 😆
Kazhdy programmiruyet po svoemu
Зачем понапрасну раширять дерево перебора,
И смотреть четыре одинаковых хода?
А если позиции после этого хода нет в хеше?Function addmove(izot:byte;otkuda:byte;nap:shortint;var cap:capture;var mov:moves):Byte;
var kuda,kuda1,kolvz,nomMoves,i:byte;
Begin
kolvz:=0;
kuda:=otkuda+nap;
if (kuda and 136)=0 then
if pole[kuda]<0 then
Begin
kuda1:=kuda+nap;
if (kuda1 and 136)=0 then
if pole[kuda1]=0 then
if kuda1<112 then
Begin
// взятие
pole[kuda]:=-pole[kuda];
// поменям шашку противникак на нашу, чтоб не взять повторно.
cap[0]:=cap[0]+1;
cap[cap[0]]:=kuda;
kolvz:=kolvz+addmove(izot,kuda1,15,cap,mov);
kolvz:=kolvz+addmove(izot,kuda1,-15,cap,mov);
kolvz:=kolvz+addmove(izot,kuda1,17,cap,mov);
kolvz:=kolvz+addmove(izot,kuda1,-17,cap,mov);
pole[kuda]:=-pole[kuda];
if kolvz=0 then
Begin
kolvz:=1;
NomMoves:=mov.kolMoves+1;
mov.kolMoves:=NomMoves;
mov.moveOt[NomMoves]:=izot;
mov.moveKu[NomMoves]:=kuda1;
mov.dam[NomMoves]:=false;
mov.Vzatie:=true;
for i:=0 to cap[0] do mov.Cap[NomMoves]:=cap;
end;
cap[0]:=cap[0]-1;
end
Else
Begin
// взятие с превращением
pole[kuda]:=-pole[kuda];
cap[0]:=cap[0]+1;
cap[cap[0]]:=kuda;
kolvz:=kolvz+addmoveD(izot,kuda1,15,cap,mov);
kolvz:=kolvz+addmoveD(izot,kuda1,-15,cap,mov);
kolvz:=kolvz+addmoveD(izot,kuda1,17,cap,mov);
kolvz:=kolvz+addmoveD(izot,kuda1,-17,cap,mov);
pole[kuda]:=-pole[kuda];
if kolvz=0 then
Begin
kolvz:=1;
NomMoves:=mov.kolMoves+1;
mov.kolMoves:=NomMoves;
mov.moveOt[NomMoves]:=izot;
mov.moveKu[NomMoves]:=kuda1;
mov.dam[NomMoves]:=True;
mov.Vzatie:=true;
for i:=0 to cap[0] do mov.Cap[NomMoves]:=cap;
end;
cap[0]:=cap[0]-1;
end;
end;
addmove:=kolvz;
end;Вот такая вспомогательная функция получилась для генерации взятий простой… Или это очень неоптимально? (все переменные модуля компилятор хранит в регистрах)
ЗЫ. Прошу извинить за такое название переменных — но мне так удобней.// поменям шашку противникак на нашу, чтоб не взять повторно.
прикольно
if (kuda and 136)=0 then — так некрасиво (магические числа), смысл такой конструкции не очевиден
А так вроде нормально. Что ты видишь здесь неоптимального?
Как с генератором? Успел за вечер?
// поменям шашку противникак на нашу, чтоб не взять повторно.
прикольно
if (kuda and 136)=0 then — так некрасиво (магические числа), смысл не очевиден такой конструкции
А так вроде нормально. Что ты видишь здесь неоптимального?
Как с генератором? Успел за вечер?
Так этож 0x88
136!
За вечер не получилось — смог начать писать только в полночь…
К Двум часам ночи дописал, проверил на нескольких тестовых позиций.
Дальше писать уже не мог — хотелось спать
Сейчас нужно бежать на работу — нужно немного подправить генератор взятий дамки (работает вроде правильно (правда не уверен), но совсем кривой) и у меня вопрос по правилам — меня переклинило — шашка которой совершаем взятие тоже снимается только по окончании взятия? (может ли шашка в процессе взятия вернутся на изначальное место, либо пройти через него?)
Я перед генерацией взятий снимаю шашку (которая совершает взятия), а после ставлю обратно. Это правильно?
- Для ответа в этой теме необходимо авторизоваться.