|
||
Идея нулевого хода заключается в том, что если мы пропускаем ход, а противник все равно не смог улучшить оценку, значит, эту ветку можно подрезать. Есть исключения это позиции цугцванга, в которых пропуск хода упускает победу или вообще ведет к поражению. Выигрыш в скорости получается, потому что мы перебираем на меньшую глубину. Это так называемый коэффициент редукции, который колеблется от 2 до 4. Нулевой ход следует вызывать один раз в ветке, иначе поиск вырождается. Не должно быть шаха в узле иначе следующим ходом противник побьет нашего короля. Ход не должен быть взятием, так как такие ветки нежелательно отсекать. Приведем код из Ифрита(Ifrit_b_2_5): Это за белых. За черных аналогично. // мы пропускаем свой ход и если даже при такой форе противник не находит // лучшего хода эту ветку можно подрезать // >3 потому что нужно оставить глубину на подрезку при нулевом ходе // нулевой ход начинает работать при максимальной глубине 6, начиная с глубины 3 (6-2=4>3)&&(depth > 2) if ((null_m == 0) && ((depth_max - depth) > 3 ) && (description_move != 2) && (check == 0)) { запоминаем состояние взятия на проходе taking_passage_yes_mem = bitboard->taking_passage_yes; taking_passage_x_mem = bitboard->taking_passage_x; taking_passage_y_mem = bitboard->taking_passage_y; bitboard->taking_passage_yes = 0; null_m=1;// два раза метод в одной ветке не вызываем depth_max_z= depth_max;// value=Black(check,bitboard,alpha,beta,depth_max_z,depth+4,nodes,pv_current,pv_best,((list_surplus_moves.move[1]>>6) & 63), three_moves,br,null_m); восстанавливаем состояние взятия на проходе bitboard->taking_passage_yes = taking_passage_yes_mem; bitboard->taking_passage_x = taking_passage_x_mem ; bitboard->taking_passage_y = taking_passage_y_mem ; //был ход черных, при котором они пытались найти минимальную оценку, т.е. улучшали бетту //теперь опять ход черных и если мы не смогли улучшить бету, т.е. наша оценка больше //или равна бете, значит, можно отсечь, т.к. ветка нам не интересна if(value>=beta) return beta ; null_m=0; } Посмотрим на то, как эффективно это у нас работает. NegaScout со всеми сортировками (хеш-таблица + сортировка взятий + киллер + централизация) 8/8 00:03 757.361 547.080 +0,12 e2e4 e7e5 Ng1f3 Ng8f6 d2d4 e5xd4 Qd1xd4 Bf8e7 9/9 00:14 7.830.431 842.030 +0,29 e2e4 e7e5 Ng1f3 Bf8d6 d2d4 e5xd4 Qd1xd4 Ng8f6 Bf1c4 10/10 01:31 34.288.860 561.720 +0,04 Nb1c3 d7d5 d2d4 Bc8f5 Ng1f3 Ng8f6 Bc1f4 Nb8c6 e2e3 Qd8d7 NegaScout со всеми сортировками + нулевой ход + продление на шахах 8/8 00:02 716.673 524.087 +0,12 e2e4 e7e5 Ng1f3 Ng8f6 d2d4 e5xd4 Qd1xd4 Bf8e7 9/10 00:04 551.952 541.953 +0,21 e2e4 d7d5 e4xd5 Qd8xd5 Ng1f3 Qd5e4+ Bf1e2 Bc8f5 d2d3 Qe4d5 10/11 00:32 13.001.137 518.485 +0,10 Nb1c3 d7d5 d2d4 Bc8f5 Nc3xd5 Qd8xd5 Qd1d2 Nb8d7 Ke1d1 Bf5xc2+ Kd1xc2 11/11 01:06 3.103.866 514.697 +0,22 e2e4 e7e5 Ng1f3 Nb8c6 Bf1b5 Nc6d4 Nf3xd4 e5xd4 Bb5c4 Bf8e7 f2f4 |