PDF-лекции, страница 17

Каждый указатель есть трехэлементныйсписок из идентификатора родительской вершины, идентификатора дочерней вершины и названиясвязывающего их оператора.(defun CONNECT (Dlist Curr)(prog (D Di Ci Rlist)C (setq D (car Dlist)) (setq Dlist (cdr Dlist))(setq Di (car D)) (setq Ci (car Curr))(setq Rlist(cons (list Ci Di (caadr D))Rlist))(cond ((null Dlist) (return Rlist) ))(go C) ))Функция SOLUTION, выделяя решающий путь, строит последовательность (названий)операторов, преобразующих начальное состояние в целевое (ее аргумент Reflist – список всехуказателей-связей между состояниями).

Для поиска указателя к очередной вершине решающего путифункция использует вспомогательную функцию LOOK_FOR .(defun SOLUTION (Goal Reflist)(prog (Sollist ;список, в котором строится решениеGi Edge)(setq Gi (car Goal))S (cond((eq Gi 'S0) (return Sollist) ))(setq Edge (LOOK_FOR Gi Reflist))(setq Sollist (cons(caddr Edge) Sollist))(setq Gi (car Edge))(go S) ))(defun LOOK_FOR (Id List)(cond((null List) (quote error))((eq ID (cadar List)) (car List))(t(LOOK_FOR Id (cdr List)) )) )В заключение приведем блок, инициализирующий эвристический поиск решения игры в восемь.В самом его начале устанавливаются значения параметров встроенной функции gensym.(prog(Goalstate Initstate Size)(setq *gensym-prefix* 'S)(setq *gensym-count* 1)(setq Size 3)(setq Goalstate '(1 2 3 8 # 4 7 6 5))(setq Initstate '(? 2 8 3 1 6 4 7 # 5))(HEURISTIC_SEARCH Initstate))День 11.

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

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

Например, в шашках игровая позиция включает задание положенийна доске всех шашек, в том числе дамок. Обычно описание конфигурации содержит также указание,кому принадлежит следующий ход.Пусть именами игроков будут ПЛЮС и МИНУС. Будем использовать следующие обозначения:XS или YS  некоторая конфигурация игры, причем индекс S принимает значения + или , указывая темсамым, кому принадлежит следующий ход (т.е. в конфигурации X+ следующий ход должен делать игрокПЛЮС, а в X – игрок МИНУС);W(XS)  задача доказательства того, что игрок ПЛЮС может выиграть, исходя из позиции XS;V(XS)  задача доказательства того, что игрок МИНУС может выиграть, отправляясь от позиции XS.Рассмотрим сначала игровую задачу W(XS). Операторы сведения (редукции) этой задачи кподзадачам определяются исходя из ходов, допустимых в проводимой игре:*Если в некоторой конфигурации X+ очередной ход делает игрок ПЛЮС, и имеется Nдопустимых ходов, приводящих соответственно к конфигурациям X1, X2, .

. . XN , то для решениязадачи W(X+) необходимо решить по крайней мере одну из подзадач W(Xi). Действительно, так как ходвыбирает игрок ПЛЮС, то он выиграет игру, если хотя бы один из ходов ведет к выигрышу  см. рис.1(а).*Если же в некоторой конфигурации Y ход должен сделать игрок МИНУС, и имеется Kдопустимых ходов, приводящих к конфигурациям Y1+ , Y2+ , . . . YK+, то для решения задачи W(Y)требуется решить каждую из возникающих подзадач W(Yi+). Действительно, поскольку ход выбираетМИНУС, то ПЛЮС выиграет игру, если выигрыш гарантирован ему после любого хода противника см.

рис. 1(б).Рис.1а)W(X1–) W(X2–)W(X+). . .б)W(XN–) W(Y1+) W(Y2+)W(Y–). . .W(YK+)Последовательное применение данной схемы редукции к исходной конфигурации игрыпорождает И/ИЛИ-дерево (И/ИЛИ-граф), которое называют деревом (графом) игры. Дуги игровогодерева соответствуют ходам игроков, вершины  конфигурациям игры, причем листья дерева  этопозиции, в которых игра завершается выигрышем, проигрышем или ничьей. Часть листьев являютсязаключительными вершинами, соответствующими элементарным задачам  позициям, выигрышным дляигрока ПЛЮС. Заметим, что для конфигураций, где ход принадлежит ПЛЮСу, в игровом деревеполучается ИЛИ-вершина, а для позиций, в которых ходит МИНУС, получается И-вершина.Цель построения игрового дерева или графа  получение решающего поддерева для задачиW(XS), показывающего, как игрок ПЛЮС может выиграть игру из позиции XS независимо от ответовпротивника.

Для этого могут быть применены разные алгоритмы поиска на И/ИЛИ-графах. Решающеедерево заканчивается на позициях, выигрышных для ПЛЮСа, и содержит полную стратегиюдостижения им выигрыша: для каждого возможного продолжения игры, выбранного противником, вдереве есть ответный ход, приводящий к победе.Для задачи V(XS) схема сведения игровых задач к подзадачам аналогична: ходам игрока ПЛЮСбудут соответствовать И-вершины, а ходам МИНУСа  ИЛИ-вершины, заключительные же вершиныбудут соответствовать позициям, выигрышным для игрока МИНУС.Конечно, подобная редукция задач применима и в случае, когда нужно доказать существованиеничейной стратегии в игре. При этом определение элементарной задачи должно быть соответствующимобразом изменено.56Рассмотрим в качестве иллюстрации простую игру, называемую «последний проигрывает». Дваигрока поочередно берут по одной или две монеты из кучки, первоначально содержащей семь монет.Игрок, забирающий последнюю монету, проигрывает.На рис.2 показан полный граф игры для задачи V(7+), жирными дугами на нем выделенрешающий И/ИЛИ-граф, который доказывает, что второй игрок (т.е.

игрок МИНУС, начинающийвторым), всегда может выиграть. Конфигурация игры описана как число оставшихся в текущий моментмонет, также указание, кому принадлежит следующий ход. Заключительные вершины, соответствующиеэлементарной задаче V(1+), т.е. выигрышу игрока МИНУС, в графе подчеркнуты.Представленная в решающем графе выигрышная стратегия может быть сформулированасловесно так: если в очередном ходе игрок ПЛЮС берет одну монету, то в следующем ходе МИНУСдолжен взять две, а если ПЛЮС берет две монеты, то МИНУС должен забрать одну. Отметим, что дляаналогичной задачи W(7+) решающий граф построить не удастся (начальная вершина неразрешима);таким образом, у игрока ПЛЮС нет выигрышной стратегии в этой игре.V(7+)Рис.2V(6)V(5+)V(4)V(3+)V(2)V(5)V(4+)V(3)V(2+)V(3+)V(2)V(1)V(1+)V(1)V(1+)В большинстве игр, представляющих интерес, таких как шашки и шахматы, построить полныерешающие деревья и найти полные игровые стратегии не представляется возможным.

Например, дляшашек число вершин в полном игровом дереве оценивается величиной порядка 1040, и просмотретьтакое дерево практически нереально. Алгоритмы же упорядоченного перебора с применением эвристикне настолько уменьшают просматриваемую часть дерева игры, чтобы дать существенное, на несколькопорядков, сокращение времени поиска.Тем не менее для неполных игр в шашки и шахматы (например, для эндшпилей), так же как идля всех несложных игр, таких как «крестики-нолики» на фиксированном квадрате небольшогоразмера, можно успешно применять алгоритмы поиска на И/ИЛИ-графах, позволяющие обнаруживатьвыигрышные и ничейные игровые стратегии.Рассмотрим, к примеру, игру «крестики-нолики» на квадрате 33.

Игрок ПЛЮС ходит первым иставит крестики, а МИНУС  нолики. Игра заканчивается, когда составлена либо строка, либо столбец,либо диагональ из крестиков (в этом случае выигрывает ПЛЮС) или ноликов (выигрывает МИНУС).Оценим размер полного дерева игры: начальная вершина имеет 9 дочерних вершин, каждая из которых всвою очередь  8 дочерних; каждая вершина глубины 2 имеет 7 дочерних и т.д. Таким образом, числоконцевых вершин в дереве игры равно 9!=362880, но многие пути в этом дереве обрываются раньше назаключительных вершинах.

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