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