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

0

Когда в 70-е годы прошлого века состоялся второй матч между русской "Каиссой" и американской Chess, то создатели американской программы сделали эпохальное заявление: "Мы собираемся заниматься выборочным

поиском, потому что полный перебор — это тупик". Такое или подобное заявление делали многие шахматные программисты на определенном этапе своей деятельности. И только очень немногие сделали приличную програм­му выборочного поиска. Среди них Ричард Лэнг с его программой Genius. В чем же трудность? Почему так мало удачных программ выборочного по­иска? На этот вопрос можно ответить, но меня смущают некоторые вещи. Я недавно читал книгу по ЗЭ-движкам и понял содержание только первых нескольких глав, да и то потому, что сам в свое время построил простей­ший ЗЭ-движок. Остальная часть книги совершенно непонятна. Темы не раскрыты, а только затронуты, тон менторский, автор — явный зазнайка. В примерах программ к книге у него вращался (очень медленно) трехмер­ный зеленый бублик, и это приводилось в качестве достижения трехмерного моделирования. Если бы все читали только эту книгу, то не было бы ни Doom, ни Ducke, ни других хороших игрушек. Для кого была написана та книга? Видимо, для тех, кто и так все знает, а только хочет нечто освежить в памяти. Я все боюсь уподобиться этому автору. Для меня в alpha-beta ал­горитме и его свойствах нет ничего сложного, потому что я долго занимался этим вопросом. Как дела обстоят у читателя? Да простят меня профессио­налы, я буду много времени уделять тривиальным вещам и много раз по­вторяться. Я надеюсь, что при каждом повторе высветится та или иная грань алгоритма.

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

albl а8Ь8 Ыа1 Ь8а8

Здесь белая ладья пошла с al на bl, а черная — с а8 на Ь8. Это 2 полухода. В следующих двух полуходах видно, что белая и черная ладья вернулись на свои места. Получился повтор позиции через 4 полухода. Если такая ситуа­ция повторится 3 раза, то через 12 полуходов может быть предъявлена оценка draw. Оценка draw при просчете в большинстве случаев принимается равной нулю (ничья). Некоторые программисты делают оценку draw равной небольшой отрицательной величине, чтобы программа при просчете не за­цикливалась из-за небольшого минуса в стратегической оценке. Что такое стратегическая оценка?

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

Вот примерные величины материальной оценки:

Название фигуры

Материальная оценка

пешка

1

слон

3

конь

3

ладья

5

ферзь

9

король

1000

Король "весит" больше, чем все остальные фигуры, вместе взятые, потому что когда съели короля — игра прекращается, и программа должна это по­нимать. Можно принять вес короля равным 0, а когда его съели, то просчет прекращается, и возвращается некоторая максимальная величина (обычно называемая infinity) минус глубина просчета. Почему вычитается глубина просчета? Дело в том, что программа считает только на некоторую глубину. Если белого короля съели на 10 полуходе, и это неизбежно (белые не могут ничего предпринять против), то оценка будет infinity-iо. Если при этом же просчете есть другой способ поставить мат белым на 12 полуходе или глуб­же, то оценка будет infinity-12. Если мы во всех случаях будем возвращать просто infinity, то программа может зациклиться. В одном случае она бу­дет выбирать вариант, ведущий к выигрышу на 12 полуходе, в другом — на 10.

Кроме материальной, есть еще и позиционная оценка. Относительно спосо­бов формирования позиционной оценки нет однозначного мнения (как и по большинству аспектов шахматного программирования), и мы пока не будем на ней останавливаться подробно. Нужно лишь помнить, что макси­мальное позиционное преимущество не переходит в материальное.

Если мы ведем перебор или поиск, и съеден король, то, как было сказано, просчет досрочно прекращается, и возвращается точная оценка.

Если мы в строке поиска встретили повтор позиции 3 раза, то просчет тоже прекращается, и, для простоты, можно возвратить 0.

Это явные два случая, когда программа сосчитала до конца. Как быть с ос­тальными? Простейший вариант: превышена глубина перебора — вернем статическую оценку.

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

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

Вот пример:

int AlphaBeta(int alpha,int beta,TPos pos, int ply) {

//если исчерпан лимит глубины — вернем статическую оценку позиции if(ply >= MAX_PLY) return Evaluate();

//получим все позиции-перемещения Generate ();

//перебираем список (:

while(moveList) {

tmp = -AlphaBeta(-beta,-alpha,nextPos,ply+l); if(tmp > alpha) alpha = tmp; if(alpha >= beta) return beta; //отсечение }//while

//если дошли до этой точки, то не было отсечения return alpha; }//function

Первый вызов:

AlphaBeta(-INFINITY,INFINITY,pos,0);

Это несколько сложно для понимания, но нужно не пожалеть времени и разобраться. Разберем подробно данную функцию и принятые в ней обо­значения:

П Generate — определяет набор позиций, полученный в результате возмож­ных ходов из данной позиции; наборы позиций в реальных программах не используются, это сделано только для простоты;

П alpha — наш максимум;

?     beta — максимум противника. При рекурсивном вызове эти переменные меняются местами и заносятся со знаком минус. Таким образом, в каж­дом узле у нас корректные alpha и beta;

П pos — позиция со сделанным в ней последним ходом противника. Если начало игры, то хода противника в эту позицию нет;

?     ply — глубина просчета от 0. Если глубина просчета превысила некото­рое значение (max ply может быть равно, например, 6, чтобы программа не "умерла"), то просчет досрочно прекращается;

?     Evaluate — функция, возвращающая статическую оценку позиции. В са­мом простейшем случае она считает только материал.

Вот пример простейшей функции Evaluate: //цвета

#define BLACK 128 #define WHITE 64 //коды фигур ¦define KING 1 tdefine QUEEN 2

#define ROOK    3

#define BISHOP  4

#define KNIGHT  5

#define PAWN    6

#define wPAWN 1 #define wKNIGHT 3 #define wBISHOP 3 ttdefine wROOK 5 #define wQUEEN 9 #define wKING 100

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

int _wf[7] = {0,wKING,wQUEEN,wROOK,wBISHOP,wKNIGHT,wPAWN};

//позиция

typedef unsigned choir TPos[64];

int Evaluate(TPos pos, int player) {

int score = 0, n, square;

for(n =0; n < 64; n++) {

square = pos[n];

if(square == 0) continue;

if((square & (BLACK | WHITE)) == player)

score += _wf[square & 7];

else

score -= _wf[square & 7]; }//for

return score; }//function

Клетка доски у нас представлена типом unsigned char. Это переменная раз­мером один байт без знака. Байт содержит 8 бит, каждый из которых может принимать значение 1 или 0. Если значение некоторого бита 1 (все осталь­ные 0), то это соответствует следующему десятичному числу:

Номер установленного бита 76543210 Десятичное значение     128 64 32 16 8 4 2 1

Маска выделения кода 00000111

Маска выделения цвета     11000000

Коды фигур занимают первые 3 бита, и поэтому когда мы делаем square & 7, то выделяем фигуру. Это можно записать как макрос с параметрами:

#define PIECE(square) ((square) & 7)

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

int Piece(int square) {

return square & 7; }

Из-за такой тривиальной функции нет смысла загружать процессор, а мы должны помнить, что скорость выполнения программы — это критичное условие в данном случае. Современные процессоры очень хорошо считают, но миллионы лишних вызовов функций — это как раз тот случай, что мо­жет отобрать "излишки" скорости.

Для выделения цвета из клетки доски (суммарного кода фигуры) мы тоже можем написать макрос:

#define COLOR(square) ((square) & (BLACK | WHITE))

Операция | — это поразрядное ИЛИ, операция & — это поразрядное И, операция | оставляет в результате те биты, которые хоть в одном из операн­дов были установлены в 1. Например, двоичная запись:

01010 первый операнд ИЛИ

10100 второй операнд

11110 результат

////////////////////// 01010 И

00011 00010

Операция поразрядного И (&) используется как маска, чтобы выделить пер­вые 3 бита, обозначающие код фигуры. Десятичное 7 — это двоичное oooooiil. Если у нас в клетке доски черный король, это будет black + king = 129, ИЛИ black | king = 129, ИЛИ В ДВОИЧНОЙ ЗЭПИСИ 10000001. Применив

маску для выделения кода фигуры ооооот, получим oooooooi.

Получили только код короля. Кто знает хитрости двоичной арифметики, да простит мне это отступление. Позиция у нас представлена массивом 0..63. Можно использовать и двумерный массив, это не принципиально. Это только в дальнейшем раздует некоторые структуры данных.

8*8 = 64;

Наш массив 0..63 — это одномерный массив, имитирующий двумерный. Если использовать хитрости двоичной арифметики, то, имея один индекс N для массива 0..63, можно легко получить координаты X и Y для массива [8] [8].

х = п & 7; у = п » 3;

Операция >> — это битовый сдвиг вправо, в данном случае на 3. Сдвиг вправо на 1 эквивалентен делению на 2, соответственно, влево на 1 — ум­ножению на 2. Сдвиг вправо на 3 эквивалентен п / 8. Если записать приве­денное выше иначе, то, чтобы получить координату X и Y по N, надо:

х = п % 8; //остаток от деления (х := n mod 8) у = п / 8; //деление (у := n div 8)

Функция Evaluate у нас сканирует весь массив игры в поисках фигур. Это расточительно по времени, но пока мы не будем на этом заострять внима­ние. Если позиция представлена одномерным массивом, то в реальных про­граммах организация его несколько сложнее для определения выхода за пределы доски. Для двумерного массива 8×8 общий случай определения выхода может быть записан так:

if((unsigned)х <8 && (unsigned)у < 8))

{

//клетка X,Y в пределах доски 8*8 \

Если функция Evaluate считает материал с точки зрения белых, она сумми­рует вес всех белых фигур, а потом из них вычитает вес всех черных фигур. Если оценка берется для черных, то наоборот. Оценка, таким образом, по­лучается инвертированная. Если у белых лишняя пешка, то это +1 для бе­лых и —1 для черных.

Этот алгоритм называется NegaMax. В функции AlphaBeta, если переменная ply превысила максимальную глубину просчета, то перебор прекращается, и возвращается статическая оценка позиции Evaluate для конкретного цвета фигур.

Это типичный пример грубого усилия по Клоду Шеннону — перебор всех вариантов в некотором фиксированном горизонте. Сейчас никто такого грубого усилия не использует, а б конце перебора вместо функции Evaluate вызывается некоторый упрощенный вариант поиска, считающий только форсированные ходы. Что такое форсированные ходы?

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

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

Что лучше? Трудно сказать. В настоящее время появился нулевой ход, как усредненный метод выборочного поиска, но некоторые шахматные про­граммисты не признают его или признают частично, в качестве некоторого дополнительного условия. Итак: и грубое усилие, и избирательность в на­стоящее время не сильно отличаются друг от друга. Речь идет о конкретных настройках для конкретной программы. Основная идея выборочного поис­ка — это отсечение некоторых ветвей дерева перебора без их просчета на полную глубину. Человеку понятно, что просчитывать некоторые ветви про­сто абсурдно, но как научить этому машину? Машина признает только точ­ные оценки. Она может всегда "подрезать" интересную ветвь, и наоборот, считать всякий абсурд. Сторонники грубого усилия, исходя из того, что на каждое правило отсечения ветви дерева перебора может найтись исключе­ние, считают, что любые Forward pruning — неприемлемо. Такие взгляды легко иметь, когда не пишешь реальную программу. Даже мощности DeepBlue мало для грубого усилия. Можно подождать еще лет 30, и такие процессоры, применительно к шахматам, наверняка появятся. Это напоми­нает ситуацию с ЗО-играми. Сейчас существуют мощные процессоры и графические ускорители, позволяющие делать игры с высокой степенью детализации, но если взять частный случай — Doom-образные миры, то та­кие программы работали и на 386, а самые простые — и на 286 процессоре с 16 МГц тактовой частоты. Если бы создатели игры Doom ждали, пока не решится задача построения ЗО-миров в целом, и не появятся суперпроцес­соры, мы не имели бы этой и многих других игр, поразивших воображение в свое время. Применительно для программирования шахмат, можно ска­зать, что совершенно не обязательно ждать появления процессоров, с по­мощью которых задача (конкретная) для доски 8 на 8 и данного набора фи­гур и правил будет решена силовым методом. Ведь мы имеем дело не с аб­страктной переборной задачей, а с конкретной. Если учесть определенную шахматную специфику, то можно построить хорошую программу на не очень мощном процессоре, и она не будет просить 100 Мбайт под хеш- таблицу. Все это требует, однако, большого усилия, и нужно много думать. Нет, к сожалению, готовых рецептов. Есть некоторые приемы, до последне­го времени (а частично, и сейчас), не разглашаемые шахматными програм­мистами-профессионалами. Кроме приемов, многое зависит и от конкрет­ной реализации. В любом случае, если современная программа и не исполь­зует некоего хитроумного способа выборочного поиска, она применяет нулевой ход для подрезки ветвей дерева, а это тоже, в сущности, выбороч­ный поиск.

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

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

Русская программа "Каисса" в первом матче с Chess нашла форсированный мат на много ходов вперед. Американцы недоумевали, как может программа считать так глубоко? Им показали, что все ходы, ведущие к мату, были форсированными — взятия и шахи. Ко второму матчу американцы были подготовлены значительно лучше. Они использовали достижения противни­ка и сделали одну из лучших программ для своего времени. Подобная си­туация, в принципе, сохраняется и теперь. Кто нашел новое интересное решение, тот и написал сильнейшую программу.

Литература:

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

По теме:

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