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

0

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

Мы в alpha-beta поиске извлекли строку главного изменения. Как можно ею воспользоваться? Можно использовать ее для следующей итерации в упоря­дочивании перемещений. Тут следует вспомнить алгоритм Principal Variation. Он ход из строки главного изменения просматривает с полным alpha-beta окном, а остальные (они, вероятно, хуже) пытается отсечь снача­ла нулевым окном. Если оценка больше alpha, то ход пересчитывается с полным окном. Таких пересчетов немного, и ускорение достигает двух и более раз (зависит от конкретной реализации).

CONST

max ply = 20;

TYPE

TMove = record

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

TLine = record

1ine:array[0..MAX_PLY] 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;

{строка главного изменения} var mainLine:TLine;

function PrincipalVariation(alpha,beta,depth:integer;

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

opponent:integer; {противника} ply:integer     {глубина от 0}

):integer;

label

done ; var

move:TMove;

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

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

if (depth <= 0) or (ply >= MAX_PLY) then begin {приблизительная оценка горизонта} PrincipalVariation := Quies(…); exit;

{попытаемся получить ход PV из глобальной строки} if FindPV(move) then begin MakeMove(move);

tmp := -PrincipalVariation(-beta,-alpha,depth-1, tmpLine,opponent,player,ply+1);

UnMakeMove(move); if tmp > alpha then begin

alpha := tmp; if alpha < beta then

SaveLine(tmpLine,bestLine,move); else

goto done;

end;

end;

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

ResetLine(tmpLine); MakeMove(move);

tmp := -PrincipalVariation(-(alpha+1),-alpha,depth-1,

tmpLine,opponent,player,ply+1); if (tmp > alpha) and (tmp < beta) then

tmp := -PrincipalVariation(-beta,-alpha,depth-1, tmpLine,opponent,player,ply+1);

UnMakeMove(move);

if tmp > alpha then begin

alpha := tmp; if alpha < beta then

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

end;

end;

done:

PrincipalVariation := alpha;

end;

{старт }

function IterativeDeepening(var bestMove:TMove):integer; const

MAX DEPTH = 6;

var

tmpLine:TLine; depth:integer- score: integer; begin

ResetLine(tmpLine) ; ResetLine(mainLine) ; depth := 1;

while (depth <= MAX_DEPTH) and not TimeUp do begin

IterativeDeepening := score; mainLine := tmpLine;

bestMove := mainLine.line[0]; {лучший на это время ход} score := PrincipalVariation(-INFINITY,INFINITY,

depth, tmpLine, player, opponent, 0 ) ;

depth : = depth+1 ; end;

end;

Переменная ply показывает абсолютную глубину от 0. Depth может не со­кращаться во время просчета, например при шахе, a ply всегда строго уве­личивается на 1. Нашли ход из главной строки изменения — переберем его сразу с полным окном, остальные попытаемся отсечь, т. к. они, вероятно, не улучшают alpha. Для полной корректности нужно не перебирать во вто­рой раз ход PV, если он встретится в основной массе перемещений, но в данном случае это не важно. При каждой итерации извлекается главная строка изменения, а при последующей она просматривается первой. Так как у нас полный перебор, то это просто улучшает порядок ходов и увеличивает скорость вычисления. Не очень много для начала, тем более что хорошая хеш-таблица разгонит программу значительно лучше. Но пойдем дальше. У нас функция была стандартная AlphaBeta, не отсекающая ничего и просмат­ривающая все ветви. Давайте перепишем эту функцию как форсированный вариант, или точнее, некий вариант статического поиска. Полного перебора пока вообще нет. Если оценка позиции после хода не улучшает alpha, и ход не шах, не взятие и не ход пешки на предпоследнюю горизонталь, то функ­ция просто подрезает дерево, и оценка хода принимается равной alpha.

function Search(alpha,beta,depth:integer;

var bestLine:TLine; {возвращаемая строка}

player,                      {цвет наших фигур}

opponent:integer; {противника} ply:integer     {глубина от 0}

):integer;

label

done ; var

move:TMove;

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

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

if (depth <= 0) or (ply >= MAX_PLY) then begin {приблизительная оценка горизонта} Search := Quies(…); exit ;

end;

{попытаемся получить ход PV из глобальной строки} if FindPV(move) then begin MakeMove(move);

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

tmpLine,opponent,player,ply+1);

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

SaveLine(tmpLine,bestLine,move); else

goto done;

end;

end;

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

ResetLine(tmpLine); MakeMove(move);

if (Evaluate(player) <= alpha) and {оценка после хода не лучше alpha} moveNotCapture(move) and    {ход не взятие}

moveNotCheck(move) and      {ход не шах}

moveNotPawnRank_6_or_7(move) then {не аванс пешки}

begin

{подрезаем дерево} trap := alpha; else begin

tmp := -Search(-(alpha+1),-alpha,depth-1,

tmpLine,opponent,player,ply+1); if (tmp > alpha) and (tmp < beta) then tmp := -Search(-beta,-alpha,depth-1,

tmpLine,opponent,player,ply+1);

end;

UnMakeMove(move);

if tmp > alpha then begin

alpha := tmp; if alpha < beta then

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

end;

end;

done:

Search := alpha;

end;

Данный вариант не является образцом статического поиска. Обратите вни­мание, что мы грубо подрезаем дерево, основываясь на характеристике хода и пределе alpha. Если бы мы не извлекали главную строку, то такой вариант не видел бы практически ничего. С главной строкой он несколько умнее. Почему? Это трудно объяснить. Видимо, дело в том, что мы уточняем alpha- beta пределы, и отсечка становится выборочной. Данный статический поиск обладает удивительной особенностью. Если он первыми просчитывает луч­шие ходы, он играет сильнее. Намного сильнее. Он может не увидеть про­стейшей комбинации, но иногда поражает своей игрой. Для упорядочива­ния ходов мы просто извлекали главную строку изменения. Этого, конечно, не достаточно. В идеале все дерево перебора должно храниться в памяти, и лучшие ходы при каждой итерации передвигаются вверх. В нашем случае в конце перебора вызывается функция Quies, которая возвращает приблизи­тельную оценку позиции горизонта. Она должна, как минимум, рассматри­вать взятия до конца, а желательно, и сглаживать эффект горизонта от шахов.

Теперь внесем небольшое изменение. Так как все дерево игры мы в памяти хранить не можем, то будем хранить все главные строки, которая программа собиралась использовать в игре. Так мы приходим к мысли о необходимо­сти создать таблицу PV или дерево. Это ограниченное дерево игры, которое программа проанализировала. Оно уже не такое большое, несколько десят­ков элементов. В нашем случае мы будем просто после каждой итерации извлеченную главную строку изменения вставлять в это дерево PV:

type

PPVNode = ~PVNode; (узел дерева PV} PVNode = record

move:TMove; {ход}

next:PPVNode; {следующий ход в этой позиции} list:PPVNode; {начало списка ходов оппонента} end;

PVTree = …. {конкретную реализацию опускаем} var PVRoot:PPVNode; {корень дерева PV} {вставляет строку в дерево}

procedure InsertLinelnPVTree(var line:TLine); {возвращает true если ход в дереве PV)

function MoveInPV(var move:TMove; node:PPVNode):boolean;

Наша функция будет содержать указатель на элемент ограниченного дерева игры.

function Search( node:PPVNode; {узел PV-дерева}

alpha,beta,depth:integer;

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

opponent:integer; {противника} ply:integer     {глубина от 0}

):integer;

label

done ; var

move:TMove;

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

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

if (depth <= 0) or (ply >= MAX_PLY) then begin {приблизительная оценка горизонта} Search := Quies(…); exit;

end;

{

перебираем ходы дерева PV и просматриваем их с полным окном

while node о NIL do begin

move := node.move; MakeMove(move);

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

tmpLine,opponent,player,ply+1, node~. list) ;

UnMakeMove(move); if tmp > alpha then begin

alpha := tmp; if alpha < beta then

SaveLine(tmpLine,bestLine,move); else

goto done;

end;

node := nodeл.next;

end;

Generate(player,bufMoves);

while NextMove(move) do

begin

{если ход уже был рассмотрен как часть дерева PV, пропустим} if movelnPV(move,node) then continue; ResetLine(tmpLine); MakeMove(move);

if (Evaluate(player) <= alpha) and {оценка после хода не лучше alpha} moveNotCapture(move) and    {ход не взятие}

moveNotCheck(move) and     {ход не шах}

moveNotPawnRank_6_or_7(move) then {не аванс пешки} begin

{подрезаем дерево} tmp := alpha; else begin

tmp := -Search(-(alpha+1),-alpha,depth-1,

tmpLine,opponent,player,ply+1,NIL); if (tmp > alpha) and (tmp < beta) then tmp := -Search(-beta,-alpha,depth-1,

tmpLine,opponent,player,ply+1,NIL);

end;

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

if alpha < beta then

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

end;

end;

done:

Search := alpha;

end;

{старт }

function IterativeDeepening(var bestMove:TMove):integer; const

MAX_DEPTH = 6; var

depth:integer; score:integer; begin

ResetEine(mainLine); PVRoot := NIL; depth := 1;

while (depth <= MAX_DEPTH) and not TimeUp do begin

IterativeDeepening := score;

bestMove := mainLine.line[0]; {лучший на это время ход} InsertLinelnPVTree(mainLine); score := Search(PVRoot,

-INFINITY,INFINITY, depth, mainLine, player, opponent, 0 ) ;

depth := depth+1; end;

end;

После каждой итерации мы главное изменение заносим в дерево PV. Это делается, чтобы программа помнила продуманные варианты и избегала ста­рых ошибок. Если этого не делать, то программа может постоянно возвра­щаться к ошибочным вариантам. В функции счета мы сначала перебираем все ходы PV в узле, если они есть. Обратите внимание, что ходы из PV- дерева просматриваются с полным окном. Затем смотрим основную массу перемещений. Они подрезаются статической оценкой. Так как alpha-beta пределы постоянно корректируются лучшими ходами, то этот выборочный поиск не так глуп, как кажется. Просто мы создаем дерево обдуманных хо­дов с полным (!) окном и постоянно его уточняем.

Мы ходы из PV считаем лучшими и рассматриваем их с полным окном, не подрезая статической оценкой. Основной принцип статического поиска гласит, что если мы ход считали хорошим и не подрезали статической оценкой, то и ответ на него нужно рассматривать, не подрезая его, т. е. иметь точный ответ на некоторую угрозу. В нашем случае, можно для про­стоты ввести некоторую переменную, которая устанавливается в false, если ответ в следующем узле нужно рассмотреть с полным окном. Выглядит это примерно так:

function Search( node:PPVNode; {узел PV-дерева}

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

opponent:integer; {противника} ply:integer;    {глубина от 0}

isCut:boolean                 {подрезать ли ход}

):integer;

label

done ; var

move:TMove ;

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

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

if (depth <= 0) or (ply >= MAX_PLY) then begin {приблизительная оценка горизонта} Search := Quies(…); exit ;

end;

{

перебираем ходы дерева PV и просматриваем их с полным окном

}

while node о NIL do

begin

move := node.move;

MakeMove(move);

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

tmpLine,opponent,player,ply+1, node’4.list, false);

UnMakeMove(move); if tmp > alpha then begin

alpha := tmp; if alpha < beta then

SaveLine(tmpLine,bestLine,move); else

goto done;

end;

node := nodeл.next;

end;

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

{если ход уже был рассмотрен как часть дерева PV – пропустим} if movelnPV(move,node) then continue;

ResetLine(tmpLine); MakeMove(move); if isCut and    {если не ответ на PV}

(Evaluate(player) <= alpha) and {оценка после хода не лучше alpha} moveNotCapture(move) and  {ход не взятие}

moveNotCheck(move) and     {ход не шах}

moveNotPawnRank_6_or_7(move) then {не аванс пешки} begin

{подрезаем дерево} tmp := alpha; else begin

tmp := -Search(-(alpha+1),-alpha,depth-1,

tmpLine,opponent,player,ply+1,NIL,true); if (tmp > alpha) and (tmp < beta) then tmp := -Search(-beta,-alpha,depth-1,

tmpLine,opponent,player,ply+1, NIL,true);

end;

UnMakeMove(move);

if tmp > alpha then begin

alpha := tmp; if alpha < beta then

SaveLine(tmpLine,bestLine,move);

else

break;

end;

end;

done:

Search := alpha;

end;

При первом вызове переменная iscut равна false, т. к. первый вызов всегда от корня дерева PV. Данная программа будет уже довольно неплохо играть даже без полного перебора. Ходы из таблицы PV можно использовать для гибкой системы выборочных продлений, не основанной на формальных признаках. Здесь надо учесть один фактор. Когда позиция определилась, существует не так много строк игры, которые нужно уточнять (две или три).

Извлеченную строку PV можно добавлять в дерево не обязательно в корне, айв каждом узле, если он доступен (это практически не улучшает игру). Элементов для построения дерева тогда понадобится не несколько десятков, а несколько сотен. После выдачи хода можно сбрасывать дерево и думать над ответом. Если противник выбрал другой ход, ну и шут с ним, все равно не наше время было. Если угадали — возможен практически мгновенный ответ. Это производит впечатление, тогда как у полного переборщика нико­гда не будет физической возможности считать с полным окном на такую громадную глубину.

Относительно генерации перемещений. Совершенно не обязательно скани­ровать все перемещения, а потом листать их. Если мы используем списки фигур, можно очень просто получить взятия последней ходившей фигуры противника, причем в отсортированном порядке. Для этого список наших фигур перебираем, начиная с пешек и заканчивая королем. Для каждой фи­гуры выясняется принципиальная возможность взять последнюю ходившую фигуру противника. Эту функцию можно назвать Attack. Существует мас­сив, где в каждой ячейке записано, может ли фигура отсюда бить конкрет­ную клетку. Если может, надо построить линию. Для пешек, королей и ко­ней линия не нужна. После взятия последней ходившей фигуры можно по­пробовать эвристику убийцы, чтобы отсечь узел, даже не генерируя перемещений для него. Тихие ходы можно делать по принципу: нашел хо­рошее перемещение — сразу в следующую позицию. В технике BitBoard можно иметь маски перемещений для всех фигур. Тогда выяснить потенци­альную возможность взять конкретную фигуру проще простого.

Литература:

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

По теме:

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