УДК 004.021

Кузьменко Д.Е., Мизин Д.С.

Использование теории Шпрага-Гранди в прикладных задачах

Севастопольский национальный технический университет 

This work is about the application of the Sprague–Grundy theory. The analysis of the method of solving Nim-reduced problems has been performed.

Эта работа о применении теории Шпрага-Гранди. Проведен анализ метода решения задач, сводящихся к Ним.

Ключевые слова: теория игр, Ним.

Теория Шпрага-Гранди — это теория, описывающая так называемые равноправные (англ. "impartial") игры двух игроков, т.е. игры, в которых разрешённые ходы и выигрышность/проигрышность зависят только от состояния игры. От того, какой именно из двух игроков ходит, не зависит ничего: т.е. игроки полностью равноправны. [1]

Кроме того, предполагается, что игроки располагают всей информацией (о правилах игры, возможных ходах, положении соперника).

Предполагается, что игра конечна, т.е. при любой стратегии игроки рано или поздно придут в проигрышную позицию, из которой нет переходов в другие позиции. Эта позиция является проигрышной для игрока, который должен делать ход из этой позиции. Соответственно, она является выигрышной для игрока, пришедшего в эту позицию. Ничейных исходов в данной игре не бывает. В виде качестве такой игры может выступать игра Ним, Баше и прочие игры.

Игра Ним представляет из себя следующую игру. Есть несколько кучек, в каждой из которых по нескольку камней. За один ход игрок может взять из какой-нибудь одной кучки любое ненулевое число камней и выбросить их. Соответственно, проигрыш наступает, когда ходов больше не осталось, т.е. все кучки пусты. [2]

Решение данной игры было опубликовано в 1901 г. Чарлзом Бутоном. Оно опирается на следующую теорему: Текущий игрок имеет выигрышную стратегию тогда и только тогда, когда XOR-сумма размеров кучек отлична от нуля. В противном случае текущий игрок находится в проигрышном состоянии.

Существует лемма о Ниме с увеличениями и теорема Шпрага-Гранди, согласно которым любая равноправная игра двух игроков может соответствовать игре Ним.

Множество задач может быть сведено к игре Ним. Например, триомино, близнецы, игра Гранди, игра Кайля, игра Ласкера.

Таким образом, данный метод позволяет использовать более эффективное решение для задач, сводящихся к Ним.

Литература:

1. Куммер Б. Н. §2.2. Функция Гранди и суммы порядка p / Игры на графах, 1982. – 112 с.

2. Болл У., Коксетер Г. Математические эссе и развлечения — М.: Мир, 1986. — с. 47-51.