Подходы к решению задачи выбора хода в позиционных играх

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

При создании программ, играющих в такие позиционные игры, как шахматы или нарды, в основном используется так называемая эвристическая схема Шеннона (подробнее в "Г.М.Адельсон-Вельский, В.Л.Арлазаров, М.В.Донской. Программирование игр. - М.: Наука, 1978", "К.Э.Шеннон. Играющие машины. - В книге: К.Э.Шеннон. Работы по кибернетике и теории информации. М.: Физматгиз, 1956, с.216-223"). Дерево игры исследуется на фиксированную глубину. Далее применяется метод максимина для выбора наилучшего хода. Существуют и другие подходы к созданию играющих программ, например метод горизонтов (в книге "М.М.Ботвинник. Алгоритм игры в шахматы. М.: Наука. 1968") , но ни один из них не дал пока результатов, существенно лучше, чем у рассмотренного здесь метода Шеннона.

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

А.В.Мосеев, underwood.narod.ru, 1999 год