Игра Гранди

Игра Гранди

Игра Гранди — это математическая игра на стратегию для двух игроков. Сначала существует одна куча предметов. Два игрока по очереди разделяют одну кучу на две кучи разных размеров. Игра заканчивается, когда остаются только кучи из двух и менее предметов и ни одна не может быть разделена на кучки разных размеров. В игру обычно играют как и в поддавки. Это означает, что последний игрок, который сможет сделать разрешенный ход, выигрывает.

Содержание

Пример

Игра в поддавки, которая начинается с одной кучки из 8 предметов, выигрышна для первого игрока, если он разделит исходную кучу на две из 7 и 1 предметов:

 игрок 1: 8 → 7+1

Игрок 2 сейчас может сделать один из трех ходов: разбить 7 на 6 + 1, 5 + 2 или 4 + 3. В каждом из этих случаев игрок 1 может обеспечить возврат противнику куч из 4 предметов и кучи размером 2 и меньше:

игрок 2: 7+1   → 6+1+1        игрок 2: 7+1   → 5+2+1        игрок 2: 7+1   → 4+3+1
игрок 1: 6+1+1 → 4+2+1+1      игрок 1: 5+2+1 → 4+1+2+1      игрок 1: 4+3+1 → 4+2+1+1

Сейчас игрок 2 должен разделить кучу из четырех предметов на 3 + 1, игрок 1, в дальнейшем, разделит 3 на 2 + 1:

игрок 2: 4+2+1+1   → 3+1+2+1+1
игрок 1: 3+1+2+1+1 → 2+1+1+2+1+1
игрок 2 не может сделать ход и проигрывает.

Математическая теория

Игра может быть проанализирована с помощью теории Шпрага-Гранди. Для этого нужно размерам куч в игре Гранди поставить в соответствие эквивалентные размеры куч в игре Ним. Это соответствие описывается последовательностью:

Размеры куч                   : 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 ...
Эквивалентные размеры Ним куч : 0  0  0  1  0  2  1  0  2  1  0  2  1  3  2  1  3  2  4  3  0 ... (последовательность A002188 в OEIS)

Используя это соответствие, стратегия для игры Ним может быть также использована и для игры Гранди. Вопрос, становится ли последовательность Ним-значений для игры Гранди периодичной, это нерешенная проблема. Elwyn Berlekamp, John Horton Conway и Richard Guy предположили[1], что она периодична, несмотря на то, что первые 235 значений, найденые Achim Flammenkamp, этого не подтверждают.

См. также

Литература

  1. ↑ E. Berlekamp, J. H. Conway, R. Guy. Winning Ways for your Mathematical Plays. Academic Press, 1982.


Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Игра Гранди" в других словарях:

  • Игра с нулевой суммой — Запрос «Zero sum» перенаправляется сюда. Cм. также другие значения. Антагонистическая игра (игра с нулевой суммой, англ. zero sum) термин теории игр. Антагонистической игрой называется некооперативная игра, в которой участвуют два игрока,… …   Википедия

  • Игра Ним — Ним  математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет. В… …   Википедия

  • Игра (задача) — Для улучшения этой статьи желательно?: Викифицировать статью. Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. У этого термина существуют и другие значения, см. Игра (значения). Игра  тип олимпиад …   Википедия

  • ИГРА НА ГРАФЕ — обобщение позиционной игры на случай, когда граф позиций не древовидный, а произвольный. Частным случаем И. на г. является игра Ним антагонистическая игра с полной информацией, в к рой для каждой окончательной позиции указано, выигрывает или… …   Математическая энциклопедия

  • Функция Шпрага-Гранди — широко используется в теории игр для нахождения выигрышной стратегии в комбинаторных играх, таких как игра Ним. Функция Шпрага Гранди определяется для игр с двумя игроками, в которых проигрывает игрок, не имеющий возможности сделать… …   Википедия

  • Функция Гранди — функция, определённая для игр для 2 игроков, где проигрывает игрок, не имеющий возможности сделать очередной ход. Широко используется в теории игр. В случае дискретных игр иногда называется нимбером. Функция определена на множестве всех позиций… …   Википедия

  • Антагонистическая игра — Запрос «Zero sum» перенаправляется сюда; см. также другие значения. Антагонистическая игра (игра с нулевой суммой, англ. zero sum)  термин теории игр. Антагонистической игрой называется некооперативная игра, в которой участвуют два… …   Википедия

  • Ним (игра) — У этого термина существуют и другие значения, см. Ним (значения). Ним  математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее… …   Википедия

  • Гарринча — Гарринча …   Википедия

  • Капоэйра Ангола — «Capoeira or the Dance of War» («Капоэйра или танец войны»). Картина художника Johann Moritz Rugendas (1793 1838). Создание 1825, опубликована в 1835 году. Капоэйра А …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»