Главная » Игры, Теория » Просмотр шахов в форсированном поиске

0

Тема эта чрезвычайно важна. Для того чтобы alpha-beta процедура находила лучший ход, мы должны считать до конца или создавать некоторую иллю­зию с помощью форсированных вариантов. Относительно того, какие ходы нужно рассматривать в форсированном поиске, не существует единого мне­ния. Чем больше ходов мы просматриваем, тем точнее результат, но тем медленнее поиск, в ущерб полному перебору.

Почему так важно просматривать шахи в статическом (форсированном) по­иске? Дело в том, что цель игры — поставить мат, а прежде, чем поставить мат, нужно объявить шах. Кроме того, при шахе игра как бы продолжается на один полуход, и от противника требуется немедленная реакция. По мо­ему мнению, без просмотра шахов в статическом поиске невозможно сде­лать хорошую программу. Выборочных продлений явно недостаточно. Ре­зультат статического поиска приближенный, но для большой глубины и комбинаций, основанных на шахах, он очень точен. Для примера можно привести программу Genius. Она просматривала тактические выпады, осно­ванные на шахах, на десятки полуходов с минимальным количеством иссле­дованных позиций. Совместить выполнение требований к просмотру шахов в форсированных вариантах позволяет старый алгоритм, который использо­вался еще Ричардом Лэнгом:

1.    Начальная глубина просмотра шахов равна двум.

2.     Если нам объявлен шах, и существует только одно легальное перемеще­ние, то глубина просмотра увеличивается на два.

3.    Если два легальных перемещения, то глубина просмотра увеличивается на единицу.

4.     Если больше двух легальных перемещений, то глубина просмотра остает­ся неизменной, в результате смягчается эффект горизонта от шахов.

Алгоритм прост, но как его реализовать на практике? При некотором мас­терстве можно оптимизировать просмотр шахов. Можно иметь некоторый код, который считает количество легальных перемещений под шахом. Пер­вым делом мы рассматриваем взятия последней ходившей фигуры против­ника. Остальные взятия (кроме взятия короля противника) пропущены, т. к. наш король под шахом. В каждом узле есть описатель хода противника в эту позицию.

Можно использовать счетчик легальных ходов. Вначале считаем, что у нас всего один легальный ход, глубина просмотра шахов при первом ходе всегда увеличивается на два. Если мы в результате счета получили ход, при кото­ром короля не съели на следующем, счетчик увеличивается, и глубина про­смотра шахов будет увеличиваться не на два, а на единицу для всех после­дующих ходов. При величине счетчика два (и далее) глубина просмотра не увеличивается, т. к. легальных ходов много. В пределах глубины просмотра мы обрабатываем шахи, ответы на них и взятия. Что делать с остальными перемещениями? Их можно вычеркнуть. Оценка хода принимается равной alpha. Если вычеркнуть простые перемещения, то скорость почти не будет отличаться от простого форсированного варианта (кроме позиций с множе­ством шахов).

Данная схема не является догмой, а всего лишь одним из возможных ре­шений:

Const

MAX_CHECK_PLY = 30; function ChecklnQS(alpha,beta,MaxCheckPly,ply,score: integer- check: boolean; player,opponent:integer; ):integer;

var

legalMoves,NextCheckPly:integer; begin

if (ply >= MaxCheckPly) or

(ply >= MAX_CHECK_PLY) then begin

ChecklnQS := Quies(alpha,beta); exit;

end;

if not check then begin

if score > alpha then alpha := score; if alpha >= beta then begin

ChecklnQS := beta; exit;

end; end;

Generate(player) ; legalMoves := 0;

while moveList and (alpha < beta) do begin

if moveCaptureKing then begin

ChecklnQS := INFINITY-ply; exit; end;

nextCheck := CheckDetect(move,opponent); if not check and not nextCheck and moveNotCapture then begin

tmp := alpha; end else begin

MakeMove(move); NextCheckPly := MaxCheckPly; if check then begin

if legalMoves = 0 then

NextCheckPly := MaxCheckPly+2 else if legalMoves = 1 then

NextCheckPly := MaxCheckPly+1;

end;

tmp := – ChecklnQS (-beta,-alpha,NextCheckPly, ply+1,-MakeNextScore(score,move), nextCheck, opponent,player

) ;

UnMakeMove(move); end;

if tmp <> -(INFINITY-(ply+1)) then

legalMoves :- legalMoves + 1; if tmp > alpha then alpha := tmp;

end;

ChecklnQS := alpha; end;

Генератор перемещений должен первым возвращать взятия короля. Глубину просмотра шахов в реальной программе нужно все равно ограничивать. Вот примерный вызов функции просмотра шахов из основной функции поиска:

function AlphaBeta(alpha,beta,ply,depth ):integer;

begin

if depth <= 0 then begin

AlphaBeta := ChecklnQS(alpha,beta, ply + 2, {!!!!) ply,score, check,

player,opponent,

) ;

exit;

end; {…}

end;

Приведенный пример только демонстрирует принцип. При вызове функции ChecklnQS из основного поиска MaxCheckpiy = piy+2, где ply — абсолютная глубина поиска от 0, Depth — изменяемая глубина поиска. При первом вы­зове функции AlphaBeta она равна стартовой глубине и уменьшается на единицу в каждом узле (если нет выборочных продлений). Таким образом, мы динамически увеличиваем глубину только в позициях с малым количе­ством легальных ходов. Если шахов мало, то основной поиск почти не тор­мозит. Максимальный прирост простого перемещения ограничен прираще­нием при ходе.

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

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии