Лекция: Программы игры в шахматы.

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

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

Многое зависит от функции оценки. Если бы у нас была идеальная функция оценки, то достаточно было бы рассмотреть только непосредственных преемников те­кущей позиции, фактически устранив при этом поиск. Но в таких играх, как шах­маты, любая функция оценки с практически приемлемой вычислительной сложностью обязательно должна быть просто эвристической функцией оценки. Эта оценка основана на «статических» свойствах позиции (в частности, числа фигур на доске) и поэтому в некоторых позициях является более надежной, чем в других. Например, рассмотрим подобную функцию оценки для шахмат, основанную на учете количества фигур (как принято называть их в шахматах — материала) и представим себе пози­цию, в которой белые имеют лишнего коня. Безусловно, что эта функция оценит по­зицию белых как более благоприятную. Разумеется, такая оценка является вполне приемлемой, если игра развивается спокойно и черные не имеют в своем распоряже­нии внезапных угроз. С другой стороны, если на следующем ходе черные могут взять ферзя белых, то такая оценка может привести к роковой ошибке, поскольку она не позволяет оценить позицию динамически. Безусловно, что статической оценке можно скорее доверять в спокойной игре, а не в резко изменяющихся позициях острой борьбы, когда каждая из сторон непосредственно угрожает взять фигуры противни­ка. Очевидно, что статическая оценка может использоваться только в спокойных по­зициях. Поэтому стандартный прием состоит в том, что поиск в опасных позициях должен продлеваться за пределы глубины до тех пор, пока не будет достигнута спо­койная позиция. В частности, для применения этого расширения необходимо запро­граммировать последовательности взятия фигур с обеих сторон (обмена фигурами) в шахматах.

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

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

9. Позволяет учитывать контроль времени; после достижения предела времени всегда имеется в запасе некоторый наилучший ход, найденный до сих пор.

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

При последовательном углублении возникают определенные дополнительные из­держки (связанные с повторным поиском в верхних частях дерева игры), но они явля­ется довольно незначительными по сравнению с общим положительным результатом.

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

Но программы, основанные на использовании принципа минимакса, имеют более фундаментальное ограничение, связанное с тем, что в них применяются лишь огра­ниченная форма знаний, характерных для данной проблемной области. Это стано­вится особенно заметным при сравнении лучших шахматных программ с опытными шахматистами. Мощные программы часто выполняют поиск среди миллионов (и да­же большего числа) позиций, прежде чем выбрать очередной ход. А психологические исследования показывают, что шахматисты обычно выполняют поиск лишь среди нескольких десятков позиций, самое большее среди нескольких сотен. Несмотря на такую «низкую производительность» поиска, шахматист все еще может выиграть у программы. Преимущество шахматных мастеров заключается в их знаниях, которые намного превосходят все, что содержатся в программах. Соревнования между ком­пьютерами и сильными шахматистами показывают, что невероятное превосходство вычислительной мощности не всегда может полностью компенсировать нехватку знаний.

Знания, которые могут быть введены в программы, основанные на принципе ми­нимакса, принимают следующие основные формы.

10. Функция оценки.

11. Эвристические методы отсечения поддеревьев дерева.

12. Эвристические методы поиска спокойных позиций.

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

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

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