Граф игры
Граф игры — это ориентированный граф, в котором вершины изображают позиции игры, а дуги показывают допустимые ходы из одной позиции в другую. Такое представление позволяет определить, какие стратегии ведут к победе, поражению или ничьей.
Как строится граф
Сначала фиксируют правила игры и начальную позицию. Затем для каждой позиции перечисляют все разрешённые ходы и добавляют дуги к получающимся позициям. Если один и тот же результат можно получить разными способами, это всё равно одна вершина: граф объединяет одинаковые позиции. Поэтому граф игры может быть существенно компактнее дерева всех партий.
По графу удобно выполнять анализ от конечных позиций к начальной. Позиция является выигрышной, если существует ход в проигрышную позицию соперника. Она является проигрышной, если любой разрешённый ход ведёт в выигрышную позицию соперника.
Пусть за ход разрешено прибавить к числу 1 или 2, а тот, кто получает 5, выигрывает. Вершины графа: 1, 2, 3, 4, 5. Из вершины 2 идут дуги в 3 и 4, а из 4 — в 5. Вершина 5 — конечная выигрышная позиция для игрока, который сделал последний ход; поэтому позицию 4 оценивают с учётом правил о том, кто должен ходить дальше.
Дерево игры хранит каждую последовательность ходов отдельно, поэтому одинаковые позиции могут встречаться много раз. В графе одинаковые позиции объединяются в одну вершину, а между вершинами могут быть разные пути.
Что означает дуга \(u\to v\) в графе игры?
Главное
- Вершины графа игры — позиции, ориентированные дуги — разрешённые ходы.
- Граф описывает все возможные переходы и помогает находить выигрышные и проигрышные позиции.
- В отличие от дерева игры, граф объединяет одинаковые позиции.