Killer heuristic

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


Мы запоминаем ход, который улучшает альфу за белых или бету за черных. И в соседней позиции этот ход пробуем одним из первых в надежде, что раз он был лучшим для соседней позиции, то пройдет и здесь. Как правило, эта надежда оправдывается. Использование двух киллеров заметно улучшает эффективность. Киллер-ход используется только на одной глубине, т.е. для соседей по горизонтали и не идет ни вверх, ни вниз. И еще одно - киллер не может быть взятием. Дело в том, что выгоднее все-таки местное лучшее взятие смотреть раньше киллера. Ирония заключается в том, что киллер не берет фигуру, т.е. содержит вполне миролюбивые ходы :)

Приведу алгоритм за белых. Понятно, что в случае черных все делается так же.

int AlphaBetaWhite(int alpha, int beta, int depth)// поиск за белых
{
  int tmp;
  int max = -INFINITY;// устанавливаем локальный максимум в минус бесконечность
  if(depth <= 0) return Evaluate();// на предельной глубине считаем оценку позиции
  GenerateWhite ();// генерируем список ходов за белых
  if(в списке нет взятий) // если нет взятий, то киллер пишем на первую позицию иначе на вторую
  {
     Insert_killer(0);
  }else{
     Insert_killer(1);
  }
  while(moveList) списки ходов локальные, т.е. действуют только в узле
  {
     MakeMoveWhite;// делаем ход
     tmp = AlphaBetaBlack (alpha, beta, depth-1);
     UnMakeMoveWhite;// откатываем ход
     if(tmp > max) max = tmp; //
     if(tmp > alpha) // ищем усиления alpha
    {
       alpha = tmp; //
       if(не взятие) Save_killer;// если ход не взятие, то записываем киллер
    }
    if(max >= beta) return max; //
  }
  return max;
}

Два киллера я записываю следующим образом:
void Save_killer(int i,T_list_surplus_moves * list_surplus_moves,int depth){
  killer_moves_2[depth].move = killer_moves_1[depth].move;
  killer_moves_1[depth].move = list_surplus_moves->move[i];
}//void Save_killer(int i,T_list_surplus_moves * list_surplus_moves,int depth){

Таким образом, первый киллер всегда содержит ход, который признан лучшим последним, а второй тот, что был лучшим до этого.

Это очень мощная эвристика. И это первая сортировка, которую следует добавить в программу. Потому что она очень эффективная т.е. дает заметный эффект но при этом очень просто реализуется. Приведу пример (Ifrit_b_2_5):

Просто alpha-beta без сортировок, правда, генератор ходов сделан, так что взятия всегда идут первыми
7/10   00:04    2.736.235 899.083      +0,27   e2e4 Nb8c6 Nb1c3 Ng8f6 d2d4 d7d5 Nc3xd5 Nf6xd5 e4xd5 Qd8xd5
8/8     00:44    27.470.423 760.636    +0,12   e2e4 e7e5 Ng1f3 Nb8c6 Bf1b5 Ng8f6 Bb5xc6 b7xc6

Alpha-beta без сортировок, но киллеры включены.
7/10   00:01   585.459 824.436         +0,27   e2e4 Nb8c6 Nb1c3 Ng8f6 d2d4 d7d5 Nc3xd5 Nf6xd5 e4xd5 Qd8xd5
8/8     00:07   3.150.324 632.292      +0,12   e2e4 e7e5 Ng1f3 Ng8f6 d2d4 e5xd4 Qd1xd4 Bf8e7
9/9     00:44   25.307.131 798.009    +0,29   e2e4 e7e5 Ng1f3 Bf8d6 Bf1c4 Ng8f6 d2d4 e5xd4 Qd1xd4

Видим, что эта эвристика дает нам целый полуход!

У меня в программе в начале смотрится лучшее в позиции взятие, а уже потом киллер-ход. При такой сортировке результат еще лучше:
7/10   00:01   520.250 843.556         +0,27   e2e4 Nb8c6 Nb1c3 Ng8f6 d2d4 d7d5 Nc3xd5 Nf6xd5 e4xd5 Qd8xd5
8/8     00:05   2.263.364 640.027      +0,12   e2e4 e7e5 Ng1f3 Ng8f6 d2d4 e5xd4 Qd1xd4 Bf8e7
9/9     00:29   16.707.264 808.338    +0,29   e2e4 e7e5 Ng1f3 Bf8d6 Bf1c4 Ng8f6 d2d4 e5xd4 Qd1xd4