Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


Описание программы, играющей в калах (ч2)

Поиск:
  5. Дерево игры и оценка позиции


    

Для поиска лучшего хода воспользуемся идей, которую иллюстрирует процедура F2 из статьи Кнута и Мура. Вот ее слегка переделанный текст на придуманном Д.Кнутом алголо/паскале-подобном языке:

Код

integer procedure F2(ref(position) p,integer alpha,integer beta): 
begin integer m,t; ref(position) q; 
   generate(p); 
   q := first(p); 
   if q = NULL then F2 := f(p) else
    begin m := alpha; 
     while q <> NULL and m < beta do
      begin t := -F2(q, -beta, -m); if t > m then m := t; q := next(q); 
      end; 
     F2 := m; 
    end; 
end.
  


Процедура находит оценку позиции p, рекурсивно оценивая все подчиненные ей позиции; во время поиска она вызывает функции generate, first и next, осуществляющие "проход" по дереву игры.

Вызов функции generate формирует всех сыновей исходной позиции в некотором порядке. Входным параметром функции generate является адрес p узла, для которого нужно сгенерировать поддерево. Вызовом функции first процедура F2 получит первого из сыновей позиции p, если он имеется. Последовательные вызовы next доставляют следующих по порядку сыновей позиции p (обратите внимание - сыновья, получаемые в результате вызова next, находятся на том же уровне дерева игры, что и первый, полученный вызовом first). Когда при обходе дерева игры будет достигнута терминальная позиция, вызов first/next даст NULL.

Применение процедуры F2 представляется совершенно тривиальным. Нужно порождать узлы очередного уровня дерева игры при каждом вызове процедуры generate; освободить занимаемую деревом память можно по окончании оценки исходной позиции. На первый взгляд все это выглядит совершенно замечательно, однако, следует принять во внимание, что совершенно нет необходимости реально строить полное дерево игры, расточая память и время. Для прохода деревьев имеется стандартная техника - использование стека; см. первый том замечательного "Искусства программирования для ЭВМ" Д.Кнута. Каждому вызову generate/first соответствует операция проталкивания (push) в стек, а когда first/next возвращает NULL, мы убираем (pop) из стека текущий узел, переходя к анализу узла, лежащего в стеке "ниже".

Когда first возвращает NULL, позиция p оценивается напрямую - в программе это делает функция estimate, которая возвращает попросту разность камней, находящихся в калахах противников. Однако, за разумное время достичь терминальной позиции удается лишь в самом конце игры, поэтому в начале и середине игры мы вынуждены ограничивать глубину просмотра: объявлять терминальными узлы, находящиеся на уровне, большем заданного, и вводить оценочную функцию для них.

Стандартный способ ограничения глубины просмотра заключается в том, что функция generate(p) НЕ генерирует сыновей позиции p, если уровень p превосходит константу MAXLEVEL, ограничивающую глубину просмотра. Эту константу будем считать параметром, задаваемым извне программы. Когда глубина просмотра превосходит заданный уровень, функция first возвращают NULL.

Идею, иллюстрируемую процедурой F2, в программе реализует функция ABprune. Ниже содержатся комментарии к этой реализации. Сразу обращу внимание на отличие ABprune от приведенного выше "канонического" варианта F2: отсутствует вызов функции generate - вместо нее добавлены операторы, управляющие текущим уровнем дерева игры.

Текущий уровень рассматриваемых узлов дерева игры содержится в переменной cL. Перебирая позиции уровня cL, будем использовать cL-й элемент массива wStack типа NODE. Процедура first инициализирует cL-й элемент этого массива, а процедура next увеличивает на 1 поле move и возвращает NULL, если значение этого поля вышло за допустимые пределы.

Функция first проверяет значение cL: если оно сравнялось с максимально допустимым уровнем перебора, функция возвращает NULL, в противном случае устанавливаются поля cL-го элемента массива wStack, после чего вызывается процедура next, которая пытается сделать очередной допустимый ход. Устанавливаемое значение wStack[cL].move[0] - "предпервое", оно будет увеличено в функции next.

Несколько сложнее устроена функция next. Ее входным параметром является оцениваемый узел p. Используя информацию об исходной позиции, содержащуюся в p->desk, и текущую позицию, содержащуюся в cL-м элементе стека wStack[cL], функция next формирует следующую позицию, если она есть.

Прежде всего нам нужно "вернуть" позицию, которая была на поле до того, как был сделан последний ход. Все очень легко, если в эту позицию мы прибыли непосредственно из позиции p, заданной входным параметром, если между ними не было вынужденных позиций. В этом случае нам достаточно скопировать позицию из p в wStack[cL]. Если же были сделаны форсированные ходы, wStack[cL].forced > 0 и, значит, нам нужно получить позицию, получаемую из позиции p->desk форсированными ходами wStack[cL].move[0], wStack[cL].move[1],..., до хода с номером wStack[cL].forced-1. Соответствующие действия реализует функция retPos.

Очередной ход должен быть сделан с непустого поля, номер которого больше поля, ход с которого мы рассматривали ранее. При этом необходимо учесть, куда попадает последний камень; функция scatterStones возвращает 1, если он попадет в свой калах. Если сделанный ход приводит в вынужденную позицию, увеличивается на 1 значение поля forced структуры, соответствующий элемент массива move устанавливается в "предпервое" состояние и поиск хода повторяется. Если допустимого хода нет, функция пытается уменьшить содержимое поля forced - ведь текущая позиция могла быть получена из вынужденной. Когда значение forced равняется нулю, и допустимого хода нет, функция возвращает NULL. Если же forced > 0, процесс поиска хода повторяется.

Вспомним еще, что нам нужно управлять текущим уровнем дерева игры (глобальная переменная cL). Наиболее естественно было бы увеличивать ее в процедуре first и уменьшать в next. При этом, однако, возникают трудности согласования работы first/next с перебором: вовсе не обязательно процедура next доработает до конца - посмотрите на второе условие выхода из цикла в F2. Поэтому было принято решение изменять переменную cL внутри процедуры ABprune.

Поговорим еще немножко об оценке терминальных позиций. Из множества возможностей здесь выбрана простейшая: оценкой позиции является разность количества камней в калахах противников. Ясно, что если в позиции ход сделал игрок А, его выигрыш равен desk[6] - desk[13], если же ход сделал игрок B, он выигрывает desk[13] - desk[6]. Это вычитание и реализует приведенная в программе функция estimate.

В литературе, посвященной программам для игры в калах, приводят и более сложные функции.

Одна из них основана на понятии активности поля. Ее принимают равной количеству камней, попадающих при ходе с этого поля на свои поля (но не в калах), минус количество камней, попадающих при этом на поля противника, плюс семь. Добавление семерки делается для того, чтобы активность всякого непустого поля была положительной. Активность пустого поля по определению равняется нулю. Сумму активностей всех полей обозначим через Da и Db, количества камней, попадающих в калахи, - через Ka и Kb. В журнале "Electronische Rechenanlagen" (1970, No.1) немецкий математик П.Рехенберг описал программу, оценочная функция в которой равнялась W = Ka*Da - Kb*Db. Сведения взяты из журнала "Наука и жизнь", 1971, N 12, с. 106- 114.

В этом же номере журнала "Наука и жизнь" рассмотрена и другая оценочная функция, предложенная Г.С.Цейтиным:

W = (Ka + 17.3/(37-Ka) - 40/Da) - (Kb + 17.3/(37-Kb) - 40/Db).

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

В проведенном соревновании программ П.Рехенберга и Г.С.Цейтина победила последняя, хотя и не с подавляющим результатом.

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


  6. Заключение



    

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

При программировании игр мы сталкиваемся ровно с такой ситуацией. Поэтому, когда планируется достаточно длительная работа над достаточно объемным проектом (скажем, задумано запрограммировать шахматы), необходимо предусматривать адекватные средства исследования программы.

Рискну утверждать, что такие средства нужны всегда и, чтобы не ходить за примером далеко, скажу, что по моему мнению в приведенном коде есть какая-то тонкая ошибка, найти которую без инструментария мне не удалось. А индикатором наличия ошибки для меня служат некоторые партии, в которых программа играет "странно" - с моей точки зрения. Вот пример такой странной партии:

Игрок A : Программа
Игрок B : Программа
Первым ходил игрок A

1) A: 0 3 B: 11
2) A: 5 B: 7
3) A: 2 B: 11 9
4) A: 3 5 B: 11
5) A: 2 B: 12
6) A: 5 3 B: 8
7) A: 0 5 4 5 B: 11 10
8) A: 5 4 5 1 B: 11 9 8
9) A: 2 B: 10 11 12
10) A: 5 B: 7
11) A: 4 B: 9
12) A: 5 3 B: 9
13) A: 5 4 B: 10 12 11

Камней по окончании игры: в калахе А - 32, в калахе B - 40
Партия игралась с MAXLEVEL, равным 5.

Конечно, быть может, программа работает верно (но что значит "верно" в подобном контексте?), а странность вызвана малой глубиной МОЕГО перебора: я просто не вижу того, что видит программа.

Я был бы рад узнать от кого-нибудь правду об этой программе.
Автор: algolist






Просмотров: 2215

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную