Главная » Алгоритмы, Игры » Извлечение строки главного изменения

0

Главная строка изменения — это строка перемещений, которую программа посчитала лучшей. Оценка, возвращаемая функцией AlphaBeta, является результатом этой строки. Данная строка как бы является продолжением хо­да, который программа делает. Насколько информативна эта строка? Это трудно сказать однозначно. Для напряженных строк игры бывает, что вся строка предсказана правильно. Для спокойных позиций бывает, что пра­вильно предсказан только первый ход, т. к. программа его непосредственно сделала. Извлечение главной строки представляет интерес еще и с точки зрения скорости выполнения программы. Если мы после каждой итерации имеем главную строку изменения, нам легче просчитать следующую. До по­явления хеш-таблиц это был основной (вместе с эвристикой убийцы) спо­соб перебрать более глубоко.

Как же извлекать главную строку изменения? Если в узле была отсечка за beta, то это уже узел не главной строки. Главная строка — это строка, кото­рая начинается в корне дерева перебора, и все узлы имеют точную оценку больше alpha, но меньше бета. Если бы мы перебирали алгоритмом alpha- beta без искусственных отсечений, то получили бы ту же главную строку, что и при полном переборе.

Главная строка называется Principal Variation, или PV. Извлекается PV сле­дующим программным кодом:

CONST

MAX_DEPTH = 20;

TYPE

TMove = record

N1,N2:byte; {откуда куда} end;

TLine = record

line:array[0..MAX_DEPTH] of TMove; {сама строка} count:integer; {количество элементов} end;

procedure SaveLine(var sourceLine,destLine:TLine; var bestMove:TMove); var n:integer;

begin

for n := 0 to sourceLine.count-1 do

destLine.line[n+1] := sourceLine[n]; destLine.line[0] := bestMove; destLine.count := sourceLine.count+1; end;

procedure ResetLine(var line:TLine); begin

line.count := 0;

end;

function ALphaBeta(alpha,beta,depth:integer;

var bestLine:TLine; (возвращаемая строка} player,   {цвет наших фигур}

opponent:integer; {противника} ):integer;

var

move:TMove;

bufMoves:array[0..MAX_MOVES] of TMove; tmp:integer;

tmpLine:TLine; {временная строка} begin

if depth <= 0 then begin

{приблизительная оценка горизонта}

ALphaBeta := Quies(…);

exit;

end;

{получим все перемещения} Generate(player,bufMoves); {покажите весь список while NextMove(move) do begin

ResetLine(tmpLine); MakeMove(move);

tmp := -ALphaBeta(-beta,-alpha,depth-1,

tmpLine,opponent,player);

UnMakeMove(move); if tmp > alpha then begin alpha := tmp; if alpha < beta then

SaveLine(tmpLine,bestLine,move); else break;

end;

ALphaBeta := alpha;

end;

Мы записываем лучший ход и всю строку за ним только в случае, если ре­зультат больше alpha, но меньше beta. Записываемый ход ставится на первое место, его строка далее. Функция, записывающая PV, выполняется сравни­тельно редко, она не принципиальна по времени исполнения, так что цикл ничего не значит.

Если у нас есть хорошая хеш-таблица, то не обязательно принудительно извлекать PV. Узлы PV запишутся в таблицу с флагом hash exact. Можно в стеке функции счета передавать некоторую логическую переменную pv. При первом вызове она всегда true. Далее, если в этом узле pv = true, и дан­ный узел есть в хеше с флагом hash_exact, то pv для следующего вызова true. Во всех остальных случаях — false. Таким образом, мы отслеживаем все строки PV (предположительно), начинающиеся в корне дерева перебора. Это своего рода дерево PV. Там есть и главная строка изменения от преды­дущей итерации. Такое дерево не будет отслеживаться абсолютно точно, т. к. узлы в хеше могут перезаписываться другими узлами, но абсолютная точность здесь и не требуется. Можно предпринять некоторые меры для сохранения узлов в хеше или завести для них отдельную таблицу. Таких уз­лов будет очень немного.

Литература:

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

По теме:

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