Null move pruning

на главную страницу


Идея нулевого хода заключается в том, что если мы пропускаем ход, а противник все равно не смог улучшить оценку, значит, эту
ветку можно подрезать. Есть исключения это позиции цугцванга, в которых пропуск хода упускает победу или вообще ведет к
поражению. Выигрыш в скорости получается, потому что мы перебираем на меньшую глубину. Это так называемый коэффициент
редукции, который колеблется от 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