ВУЗ:
Составители:
Рубрика:
28
Цель построения игрового дерева или графа − получение решаю-
щего поддерева для задачи W(X
S
), показывающего, как игрок ПЛЮС
может выиграть игру из позиции X
S
независимо от ответов противни-
ка. Для этого могут быть применены разные алгоритмы поиска на
И/ИЛИ-графах. Решающее дерево заканчивается на позициях, выиг-
рышных для ПЛЮСа, и содержит полную стратегию достижения им
выигрыша: для каждого возможного продолжения игры, выбранного
противником, в дереве есть ответный ход, приводящий к победе.
Для задачи V(X
S
) схема сведения игровых задач к подзадачам
аналогична: ходам игрока ПЛЮС будут соответствовать И-вершины, а
ходам МИНУСа − ИЛИ-вершины, заключительные же вершины будут
соответствовать позициям, выигрышным для игрока МИНУС.
Конечно, подобная редукция задач применима и в случае, когда
нужно доказать существование ничейной стратегии в игре. При этом
определение элементарной задачи должно быть соответствующим
образом изменено.
Рассмотрим в качестве иллюстрации простую игру, называемую
«последний проигрывает». Два игрока поочередно берут по одной или
две монеты из кучки, первоначально содержащей семь монет. Игрок,
забирающий последнюю монету, проигрывает.
На рисунке 5 показан полный граф игры для задачи V(7
+
), жирны-
ми дугами на нем выделен решающий И/ИЛИ-граф, который доказыва-
ет, что второй игрок (т.е. игрок МИНУС, начинающий вторым), всегда
может выиграть. Конфигурация игры описана как число оставшихся в
текущий момент монет, также указание, кому принадлежит следующий
ход. Заключительные вершины, соответствующие элементарной задаче
V(1
+
), т.е. выигрышу игрока МИНУС, в графе подчеркнуты.
V(7
+
)
V(3
+
)
V(6
−
)
V(5
−
)
V(4
+
)
V(5
+
)
V(4
−
)
V(3
−
)
V(2
−
)
V(1
−
)
V(3
+
)
V(2
+
)
V(1
+
)
V(2
−
)
V(1
−
)
V(1
+
)
Рис. 5
Страницы
- « первая
- ‹ предыдущая
- …
- 26
- 27
- 28
- 29
- 30
- …
- следующая ›
- последняя »
