Главная » Игры, Теория » Проще некуда (оценочная функция)

0

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

Рассмотрим основные идеи, используемые в этой программе. Первый вызое функции счета предполагает сразу большую глубину, например двадцать, не счет идет, пока не исчерпан лимит времени и функция TimeOverO не воз­вратит true. В самом начале, прежде чем нашли хоть одно перемещение осуществляется поиск лучшего хода на глубину N—2. Если такой ход най­ден, его пробуем первым, в надежде получить отсечку сразу. Вот приме{ кода:

static TMove glMove; //сюда вернется лучший ход

int Search(int alpha,int beta,int Depth,PMove retMove,int ply) {

//пока не нашли лучшего хода

NoFindMove(retMove);

if (Depth <= 0 I I TimeOverO) return Evaluate ();

TMove tmpMove; //стековая промежуточная переменная

//найдем лучший ход на меньшую глубину Search(alpha,beta,Depth-2,retMove,ply); //если лучший ход найден, попробуем его первым

if(findMove) {

MakeMove(retMove);

int tmp = -Search(-beta,-alpha,Depth-1,

StmpMove, //нам не потребуется ply+1); UnMakeMove(retMove); if(tmp > alpha) alpha = tmp; if(alpha >= beta) return alpha;

}

//основной счет {. . . }

///допустим, нашли ход {…}

MakeMove(move);

tmp = -Search(-beta,-alpha,Depth-1,StmpMove,ply+1); UnMakeMove(move);

if(tmp > alpha) {

alpha = tmp; if(!TimeOver()) memcpy(retMove,move,sizeof(TMove));

}

if(alpha >= beta) return alpha; {…)

return alpha;

}

Первый вызов данной функции будет выглядеть примерно так:

Search(-INFINITY,INFINITY,20,sglMove,0);

Мы вызываем функцию на большую глубину. Она сразу "ныряет" на глуби­ну N—2 для получения лучшего хода, и первый ход при piy=o будет найден при Depth=2. Этот ЛУЧШИЙ ХОД будет использован при Depth=4 и т. д. Функ­ция не будет исследовать узел, не попытавшись найти лучший ход для дан­ного узла на меньшей глубине. Сколько полуходов переберет данная функ­ция? Это неизвестно. Пока не исчерпан лимит времени. Лучший ход запи­сывается всегда, когда результат счета больше текущего значения alpha. Если исчерпан лимит — лучший ход не записывается. Таким образом, функция, помимо упорядочивания перемещений, осуществляет постепенное углубление перебора, пока не исчерпан лимит времени. Сортировка пере­мещений в узлах все равно нужна. Взятия можно рассматривать первыми и без сортировки. Остальные перемещения берутся позже. Взятия в большин­стве случаев дают отсечку. Остальные перемещения нужно сортировать. Лучшие можно обсчитывать сразу, средние и худшие (прирост отрицатель­ный) — оставлять на потом.

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

Итак, определим основные типы данных. Фигуры у нас остаются прежни­ми. Тип, описывающий перемещение:

typedef struct _TMove{ int xl,yl,x2,y2; //откуда и куда пошла фигура int f;   //сама фигура

int newF;     //значение фигуры на новом месте

//пешка после превращения меняет значение int eatFX, eatFY;//координаты съеденной фигуры

//при взятии пешкой через битое поле //эти координаты не совпадают с новым //местом фигуры int eatF;      //сама съеденная фигура

int score;    //приращение оценки при ходе

bool isExtMoveKing; //рокировка? int Depth;    //глубина счета

}TMove,* PMove; #define В BLACK #define W WHITE

static unsigned char _joos[8][8] =


{

{ROOKIB,KNIGHT IB,BISHOP|В     },

{…}

}

//делает перемещение

void MakeMove(PMove move) {

if(!move->isExtMoveKing) {

_pos[move->yl][move->xl] = 0; _pos[move->eatFY][move->eatFX] = 0; _pos[move->y2][move->x2] = move->newF; }else{

//рокировка {…}

}

}

//восстанавливает позицию

void UnMakeMove(PMove move) {

//все в обратном порядке {…}

}

//массивы со стратегической оценкой typedef int TStBoard[8][8]; //стратегическая оценка //для верхних

static TStBoard _upSt = {

{ 1, 2, 3, 4, 5, 6, 7, 8}, { 9,10,11,12,13,14,15,16}, {17,18,19,20,21,22,23,24}, {25,26,27,28,29,30,31,32}, {33,34,35,36,37,38,39,40}, {41,42,43,44,45,46,47,48}, {49,50,51,52,53,54,55,56}, {57, 58, 59, 60, 61, 62, 63, 64 } } ;

//для нижних

static TStBoard _botSt = {

{64,63,62,61,60,59,58,57}, {56,55,54,53,52,51,50,49}, {48,47,46,45,44,43,42,41},

{40,39,38,37,36,35,34,33}, {32,31,30,29,28,27,26,25}, {24,23,22,21,20,19,18,17}, {16,15,14,13,12,11,10, 9}, { 8, 7, 6, 5, 4, 3, 2, 1} } ;

//массив быстрой перекодировки кода фигуры в ее вес

static int _wf[7] = {0,W_KING,W_QUEEN,W_ROOK,W_BISHOP,W_KNIGHT, W_PAWN}; //возвращает приращение оценки хода int delRes( TStBoard *шуВ, //оценка наших фигур TStBoard *орВ, //противника PMove move //описатель перемещения

)

{

int score;

if(move->isExtMoveKing) {

//рокировка {…}

}else{

score = _wf[FIGURE(move->newF) – _wf[FIGURE(move->f)] + (*myB)[move->y2][move->x2] – (*myB)[move->yl][move->xl];

if(eatF) {

score += _wf[FIGURE(move->eatF);

score += (*opB)[move->eatFY][move->eatFX];

}

}

return score;

}

//цвет верхних фигур

static int _upFColor;

//сама функция счета (схематично)

int Search(PMove node, //описатель хода в эту позицию int Depth, //сколько полуходов осталось int ply, //абсолютная глубина от 0 int alpha, int beta,

PMove retMove, //найденный ход int score, //текущая оценка узла

bool isLazyEval, //идет сокращенный просчет int color    //цвет наших фигур

)

{

TStBoard *шуВ,*орВ;

int nextColor = color==BLACK?WHITE:BLACK; //инициализируем переменные if(color != _upFColor) (

//если наши фигуры нижние шуВ = &_botSt; орВ = &_upSt; }else(

iuyB = &_upSt; орВ = &_botSt;

}

retMove->f = 0;       //нет пока лучшего хода

if (Depth <= 0 | | TimeOverO) return score;

int res = -INFINITE; //возвращаемая оценка

//в эту стековую переменную будет возвращен лучший ход

TMove tmpMove;

//структура выборочного поиска static int ext[100] = (-64,-64,-64,-64,

-64,W_PAWN,W_BISHOP,W_ROOK,W_QUEEN,INFINITY,INFINITY,…}; //повышаем alpha текущей оценкой

if(ply >0 &&              //если не первый полуход

node->score < ext[ply] && //ход не продлевается !InCheck(node) //не шах

)

{

res = score;

if(res > alpha) alpha = res; if(alpha >= beta) return alpha;

}

//переберем на глубину Depth-2 для получения //лучшего хода

int tmp = Search(node,Depth-2,ply,alpha,beta, retMove, score,

ply==0?false:true, color ) ;

/// lazy eval 11 III

//если данный узел удовлетворяет некоторым требованиям, //мы можем отсечь его, основываясь на результате сокращенного счета if(retMove->f &&  //если нашли лучший ход

retMove->Depth >= Depth-2 //достаточная глубина

ply != О &&            //не первый вызов

!isLazyEval &&        //не делаем сокращенного поиска

score – 64 >= beta && //оценка и поле роста >= beta tmp-64 >= beta  && //проверка подтверждает

node->score < W_PAWN SS //не взятие !InCheck(node)  //не шах

)

{

return beta; //целая ветвь подрезана!!!

}

//прежде, чем нашли перемещения, //попробуем найденный лучший ход

if(retMove->f) //если такой ход найден {

MakeMove(retMove);

tmp = -Search( retMove, //описатель хода в эту позицию Depth-1, //сколько полуходов осталось ply+1, //абсолютная глубина от О -beta, -alpha,

StmpMove, //найденный ход(нам не нужен) -(score+retMove->score), //текущая оценка узла isLazyEval, nextColor

) ;

UnMakeMove(retMove); if(tmp > res) res = tmp;

if(res > alpha) {

//если не превышен лимит времени

if (!TimeOverO ) {

//лучший ход тот же, //только корректируем глубину retMove->Depth = Depth;

}

alpha = res;

}

if(alpha >= beta) return alpha; )//endif

III НИИ взятия /////////////////////////////

//нашли взятие – сразу в следующую позицию //// {. . . }

ППП допустим, нашли ход //////////////////// {…}

//приращение при ходе move->score = delRes(myB,opB,move); MakeMove(move);

tmp = -Search( move, //описатель хода в эту позицию

Depth-1, //сколько полуходов осталось ply+1, //абсолютная глубина от О -beta, -alpha,

stmpMove, //найденный ход(нам не нужен) -(score+move->score), //текущая оценка узла isLazyEval, nextColor

) ;

if(tmp > res) res = tmp;

if(res > alpha) {

alpha = res;

if(ITimeOver()) {

memcpy(retMove,move,sizeof(TMove)); retMove->Depth = Depth;

)

}

if(alpha >= beta) return alpha;

UnMakeMove(move); {. . . }

{. . . }

return res; }//end function

Пример первого вызова данной функции:

static TMove glMove; //сюда вернется лучший ход memset(SglMove, 0,sizeof(TMove));

static TMove tmpMove; //описатель первого перемещения memset(stmpMove,0,sizeof(TMove)); //нет этого перемещения Search(StmpMove, //описатель хода в эту позицию 20,     //сколько полуходов осталось

0,    //абсолютная глубина от 0

-INFINITY, //alpha INFINITY, //beta sglMove, //найденный ход

Evaluate О, //текущая оценка узла false,  //идет сокращенный просчет

WHITE //цвет фигур получаемого хода

) ;

Данный пример является схематичным. При создании реальной программы нужно быть очень внимательным. Особенно следует обратить внимание на то, что если мы считаем на N—2, то не должны уже в этом сокращенном поиске подрезать ветви поиска без предварительного исследования. Это возможно только в основном поиске, с учетом характеристики узла и ре­зультата сокращенного просмотра.

Вместо внутренних итеративных углублений можно использовать большую хеш-таблицу. Это гарантированно ускорит поиск. Конкретная реализация может быть различной. Слишком сильно данная программа упрощенного выборочного поиска играть не будет, но и обижать себя не даст. Как прави­ло, у среднего любителя она будет выигрывать.

В конце игры, когда на доске нет пешек, нужно использовать одну страте­гическую оценку с приоритетом центра.

Литература:

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

По теме:

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