PART3 (Печатные лекции), страница 3

В описание состояния включается также – в качестве первого элемента списка – обозначение того оператора движения пустой клетки, который привел к данному состоянию. Этот элемент нужен, чтобы исключить тривиальные повторы состояний при раскрытии вершин. Операторы будут обозначаться соответственно именами-атомами right, left, up, down; а "пустышка" (пустая клетка) – как # .

Например, (S3 ('left 2 8 3 1 6 4 # 7 5) 1 6) - цель S3, полученная сдвигом "пустышки" влево, находящаяся в дереве перебора на глубине 1 и имеющая эвристическую оценку 6. Отметим, что эвристическая оценка используется только в алгоритме эвристического перебора, а глубина вершины – в алгоритмах эвристического перебора и ограниченного перебора вглубь.

Описанные ниже лисп-функции для игры в восемь могут быть пригодны и для игры в пятнадцать, так как размер стороны игрового квадрата, равный 3, используется в них как глобальная переменная переменная Size. Другая глобальная переменная Goalstate, хранит описание целевого состояния (без идентификатора, глубины и эвристической оценки). Значение оценочной функции EST – сумма числа фишек, стоящих не на «своих» местах, и длины пути (глубины) оцениваемого состояния в дереве поиска.

(defun IS_GOAL(State)

(equal (cdadr State) Goalstate ))

(defun EST (S)

(prog(Len G N E1 E2)

(setq Len (cadr S)) (setq N 0)

(setq S (cdar S)) (setq G Goalstate0

;одновременный просмотр списков-описаний

; заданного и целевого состояний:

ES (cond((null S) (return (+ N Len)) ))

(pop E1 S) (pop E2 G)

(cond( (eql E1 E2) (setq N (add1 N)) ))

(go ES) ))

(defun OPENING (State)

(prog(Op St Dlist K I J El)

; выделение составных элементов описания состояния:

(setq St (cadr State))

(setq Op (car St)) (setq St (cdr St))

(setq State St) (setq K 0)

; поиск порядкового номера К "пустышки" в списке:

OP (setq El (car St))

(setq K (add1 K))

(cond ((neq El '#) (setq St(cdr St)) (go OP) ))

; вычисление номера ряда и номера столбца "пустышки":

(setq I(add1(mod K Size))) (setq J (rem K Size))

; поочередно проверка возможности движения «пустышки»

; вправо/влево/вверх/вниз (за счет анализа оператора Op

; исключаем в дереве поиска тривиальные циклы(т.е. возврат

; после применения двух операторов в исходное состояние):

(cond((and (neq Op 'left) (< J Size))

(ADD_STATE 'right K (add1 K)) ))

(cond((and (neq Op 'right) (> J 1))

(ADD_STATE 'left K (sub1 K)) ))

(cond((and (neq Op 'down) (> I 1))

(ADD_STATE 'up K (- K Size)) ))

(cond((and (neq Op 'up) (< I Size))

(ADD_STATE 'down K (+ K Size)) ))

(return Dlist) ))

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

(defun ADD_STATE (Op K1 K2)

(push(list(gensym)

(cons Op

(cond((< K1 K2)

(EXCHANGE State 1 '# K1 (NTH K2 State)K2))

(t (EXCHANGE State 1(NTH K2 State)K2 '# K1))) ))

Dlist))

Рекурсивная функция EXCHANGE, использованная в ADD_STATE, формирует новое состояние игры путем перестановки заданных элементов исходного состояния-списка List (переменная K служит для просмотра этого списка, и при обращении к функции ее значение равно1).

(defun EXCHANGE (List K Elem1 K1 Elem2 K2)

(cond((eql K K1) (cons Elem2

(EXCHANGE(cdr List)(add1 K)Elem1 K1 Elem2 K2) ))

((eql K K2)(cons Elem1 (cdr List)) )) )

Функция CONNECT формирует список указателей от текущей вершины-состояния Curr к заданным (в списке Dlist) дочерним вершинам-состояниям. Каждый указатель есть трехэлементный список из идентификатора родительской вершины, идентификатора дочерней вершины и названия связывающего их оператора.

(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 G))

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) )

Поиск на игровых деревьях

Деревья игры. Поиск выигрышной стратегии

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

Таким образом, в рассматриваемый класс не попадают игры, исход которых зависит хотя бы частично от случая  большинство карточных игр, игральные кости, «морской бой» и проч. Тем не менее класс достаточно широк: в него входят такие игры, как шахматы, шашки, реверси, калах, крестики-нолики и др.

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

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

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

Пусть именами игроков будут ПЛЮС и МИНУС. Будем использовать следующие обозначения:

X^S (или Y^S)  некоторая конфигурация игры, причем индекс S принимает значения + или , указывая тем самым, кому принадлежит следующий ход (т.е. в конфигурации X⁺ следующий ход должен делать игрок ПЛЮС, а в X^ – игрок МИНУС);

W(X^S)  задача доказательства того, что игрок ПЛЮС может выиграть, исходя из конфигурации X^S;

V(X^S)  задача доказательства того, что игрок МИНУС может выиграть, отправляясь от конфигурации X^S.

Рассмотрим сначала игровую задачу W(X^S). Операторы сведения этой задачи к подзадачам определяются исходя из ходов, допустимых в проводимой игре:

• Если в некоторой конфигурации X⁺ очередь делать ход за игроком ПЛЮС, и имеется N допустимых ходов, приводящих соответственно к конфигурациям X₁^, X₂^, . . . X_N^ , то для решения задачи W(X⁺) необходимо решить по крайней мере одну из подзадач W(X_i^) (так как ход выбирает ПЛЮС, то он выиграет игру, если хотя бы один из ходов ведет к выигрышу)  см. рис. 16(а).

• Если же в некоторой конфигурации Y^ ход должен сделать МИНУС, и имеется K допустимых ходов, приводящих к конфигурациям Y₁⁺ , Y₂⁺ , . . . Y_K⁺, то для решения задачи W(Y^) требуется решить каждую из возникающих подзадач W(Y_i⁺) (так как ход выбирает МИНУС, то ПЛЮС выиграет игру, если выигрыш гарантирован ему после любого хода противника)  см. рис. 16(б).

Последовательное применение для исходной конфигурации игры данной схемы сведения игровых задач к совокупности подзадач порождает И/ИЛИ-дерево (И/ИЛИ-граф), которое называют деревом (графом) игры. Дуги игрового дерева соответствуют ходам игроков, вершины  конфигурациям игры, причем листья дерева  это позиции, в которых игра завершается выигрышем, проигрышем или ничьей. Часть листьев являются заключительными вершинами, соответствующими элементарным задачам  позициям, выигрышным для игрока ПЛЮС. Заметим, что для конфигураций, где ход принадлежит ПЛЮСу, в игровом дереве получается ИЛИ-вершина, а для позиций, в которых ходит МИНУС,  И-вершина.

Цель построения игрового дерева или графа  получение решающего поддерева (подграфа) для задачи W(X^S), показывающего, как игрок ПЛЮС может выиграть игру из позиции X^S независимо от ответов противника. Для этого могут быть применены разные алгоритмы поиска на И/ИЛИ-графах. Решающее дерево или граф заканчивается на позициях, выигрышных для ПЛЮСа, и содержит полную стратегию достижения им выигрыша: для каждого возможного продолжения игры, выбранного противником, в дереве или графе есть ответный ход, приводящий к победе.

Для задачи V(X^S) схема сведения игровых задач к подзадачам аналогична: ходам игрока ПЛЮС будут соответствовать И-вершины, а ходам МИНУСа  ИЛИ-вершины, заключительные же вершины будут соответствовать позициям, выигрышным для игрока МИНУС.

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

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

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

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

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

Минимаксная процедура

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

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

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