Главная » Игры, Теория » Статические понятия

0

В каждой позиции существует две статические оценки: до хода (l score) и после хода (r_score). Оценка до хода является общей для всей позиции, оценка после хода изменяется после каждого перемещения. Рассмотрим эти величины подробнее, r score, как правило, больше l_score. Это относится к взятиям, как к перемещениям, дающим наибольший прирост оценки, и к другим ходам, оценка которых больше 0. Существуют еще отрицательные ходы.

Реальная оценка после счета должна быть, как минимум, l score. Это — основное статическое понятие. Игрок после хода противника, как правило, может найти ход, не ухудшающий текущую позицию. Прирост оценки огра­ничен диапазоном от l_score до r_score. Если мы взяли пешку, то, согласно статическим критериям, это наш максимум. Дальнейший поиск только вы­ясняет: действительно ли мы можем ее взять, или противник ее отыграет.

Итак, мы имеем:

?     l_score — статический минимум

?     r score — статический максимум

?     alpha — реальный минимум П beta — реальный максимум

if (L_SCORE >= beta) return beta;

Если в узле alpha меньше l score, то можно сразу повысить alpha до вели­чины l_score.

procedure StaticALphaBeta(alpha,beta:integer):integer; var

l_SCORE,R_SCORE:integer; begin

L_SCORE := Evaluate; {статическая оценка позиции) if L_SCORE > alpha then alpha := L_SCORE; Generate; {список перемещений} while moveList and

(alpha < beta) do

begin

MakeMove;

tmp := -StaticALphaBeta(-beta,-alpha); UnMakeMove;

if tmp > alpha then alpha := tmp;

end;

StaticAlphaBeta := alpha; end;

У нас получился простейший статический поиск. Переменную r score мы пока не используем. Если мы будем брать не все перемещения, а только взятия, то получим простейший форсированный вариант.

В приведенном примере мы всегда повышали alpha. Можно делать иначе. Поиск прекращается, когда l score больше beta. Это уже имитация полного перебора. Мы просматриваем все, пока наш статический минимум меньше нашего реального максимума:

procedure StaticALphaBeta(alpha,beta:integer):integer; var

L_SCORE,R_SCORE:integer; begin

L_SCORE := Evaluate; {статическая оценка позиции) if L_SCORE >= beta then begin StaticAlphaBeta := beta;

exit;

end;

Generate; {список перемещений} while moveList and

(alpha < beta) do

begin

MakeMove;

tmp := -StaticALphaBeta(-beta,-alpha); UnMakeMove;

if tmp > alpha then alpha := tmp;

end;

StaticAlphaBeta := alpha; end;

Если смотреть из преузла, то условие l_score >= beta означает, что r score <= alpha. Если статический максимум нашего перемещения не по­вышает alpha, то оценка хода равна alpha:

procedure StaticALphaBeta(alpha,beta:integer):integer; var

L_SCORE,R_SCORE:integer; begin

Generate; {список перемещений} while moveList and

(alpha < beta) do

begin

MakeMove;

R_SCORE = Evaluate; if R_SCORE <= alpha then

tmp := alpha else

tmp := -StaticALphaBeta(-beta,-alpha); UnMakeMove;

if tmp > alpha then alpha := tmp;

end;

StaticAlphaBeta := alpha; end;

Этот пример идентичен предыдущему, только отсечение выполняется в пре- узле.

Варианты подрезания:

?      l_score >= beta. Мы режем целый узел и не получаем перемещения.

?     r score <= alpha после хода, подрезаем только один ход.

?    alpha >= beta, натуральная отсечка по результату счета.

Рассмотрим ситуацию:

(l_score <= alpha) and (beta <= r_score)

Реальные минимум и максимум находятся внутри статического промежутка. Это говорит о том, что мы знаем реальный диапазон статического измене­ния оценки и только уточняем его. Если промежуток от l_score до r score устраивает нас как погрешность вычисления, то можно прекратить счет. Варианты возвращаемых значений:

?    alpha;

?    beta;

?    среднее арифметическое, т. к. alpha и beta стремятся друг к другу; П среднее значение статического приращения;

?    случайное число или вероятностную оценку. Может быть некоторая аномальная ситуация, когда:

(l_score >= beta) and (r_score <= alpha)

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

Вместо фиксированного поля роста можно ввести динамическое. Принима­ем alpha как оценку хода. В предыдущем узле для противника были свои l_score и r_score. Назовем их pre_l_score и pre_r_score. Для нашего узла это инвертированные величины. Мы должны повышать alpha, по меньшей мере, до pre_l_score. Это значит, если противник взял фигуру, мы не долж­ны подрезать, пока не компенсируем материал. Введем константу:

MAX_ST_VALUE = wPawn div 2; (максимальное стратегическое приращение}

Поскольку мы не хотим нарушать стратегию, условие подрезания будет сле­дующее:

if (PRE_L_SCORE-MAX_ST_VALUE <= alpha) and (R_SCORE <= alpha) then …

Итак, мы компенсировали потерю материала, и оценка после хода не улуч­шает alpha, тогда подрезаем. Это работает довольно прилично, только нуж­но уточнять главное изменение.

Вообще мы должны дотягивать alpha и до l score. По статическим поняти­ям, оценка не должна быть хуже статической оценки узла, и мы должны компенсировать потерю:

if(alpha > PRE_L_SCORE) and (alpha > L_SCORE) and

(alpha > R_SCORE) then …

Данное условие представляет собой гибкое поле роста от 0 до максимально­го приращения (ферзя). На практике работает очень неплохо. Величины l score и другие не нужно вычислять всякий раз, а можно добавлять изме­нение оценки при ходе:

function StaticSearch(alpha,beta,L_SCORE,PRE_L_SCORE:integer):integer; var

R_SCORE:integer; begin

Generate;

while moveList and

(alpha < beta) do

begin

R_SCORE := DelScore(L_SCORE,move);{пошаговое приращение) if (alpha > PRE_L_SCORE) and (alpha > L_SCORE) and (alpha > R_SCORE) and not Check {не шах) then

tmp : = alpha else begin

MakeMove;

tmp := -StaticSearch(-beta,-alpha,-R_SCORE,-L_SCORE); UnMakeMove; end;

if tmp > alpha then alpha := tmp; end;

StaticSearch := alpha; end;

При итеративных углублениях строка главного изменения помещается в таблицу PV. Первым делом мы рассматриваем ходы из PV-таблицы. Для хода из PV или ответа на него узел не подрезается. Таким образом, мы уточняем главное изменение. Поле роста можно ограничить материальной составляющей и не дотягивать alpha до l score. Зачем нужно уточнять PV? В реальной игре не так много жестких строк с ограниченным количеством легальных перемещений. Они автоматически попадают в PV. Их нужно просто уточнять. Таким образом, в жестких позициях программа может счи­тать невероятно глубоко. В отличие от нулевого хода, это просчет самых жестких строк игры с полным окном, а не подрезка, основанная на догадке (плюс-минус кирпич).

Нужно отметить, что данное поле роста позволяет считать очень точно. Я тестировал программу без полного перебора и уточнения PV (только строка главного изменения просматривалась первой) с полным переборщи­ком, считающим очень глубоко и имеющим очень хороший тактический уровень. Этот чистый форсированный вариант выдержал все атаки против­ника и даже под конец получил стратегическое преимущество. В реальной программе выборочный поиск должен вставляться после сокращенного по­иска полной ширины (4—5 полуходов), и строка главного изменения долж­на уточняться.

Если выполнено условие, мы сразу принимаем оценку хода как alpha. Мож­но не обрезать дерево, а сокращать глубину перебора. Это намного точнее, но медленнее. Выглядит это примерно так:

function Search(alpha,beta,L_SCORE,PRE_L_SCORE, depth,ply:integer):integer;

var

R_SCORE,nextDepth:integer; begin

if (Depth <= 0) or (ply >= MAX_PLY) then begin

Search := Quies(alpha,beta); {форсированный поиск} exit;

end;

Generate;

while moveList and

(alpha < beta) do

begin

R_SCORE := DelScore(L_SCORE,move);{пошаговое приращение}

if Check then       {если ход объявляет шах}

nextDepth := Depth; else if notPV and {ход не PV}

(alpha >= PRE_L_SCORE-MAX_ST_VALUE) and (alpha >= R_SCORE) then

nextDepth := Depth-2 else nextDepth := Depth-1;

MakeMove;

tmp := -Search(-beta,-alpha,-R_SCORE,-L_SCORE, nextDepth,ply+1);

UnMakeMove;

if tmp > alpha then alpha := tmp; end;

Search := alpha; end;

Строки PV должны уточняться, и сокращение глубины в них недопустимо. Так как мы первой просматриваем только одну строку PV, и alpha-beta пре­делы максимально отдалены от корня дерева, она автоматически будет рас­сматриваться с полной глубиной. Чтобы данный алгоритм считал точно, искусственные alpha-beta пределы не годятся.

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

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

Литература:

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

По теме:

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