Жабы и лягушки

Пример комбинаторной игры «Жабы и лягушки».

Комбинаторная игра «Жабы и лягушки» — партизанская игра, придуманная Ричардом Гаем . Эта математическая игра использовалась в качестве вводной игры в книге « Пути к победе в математических играх» . ^[1]

Игра «Жабы и лягушки», известная своей простотой и элегантностью правил, полезна для иллюстрации основных концепций комбинаторной теории игр. В частности, нетрудно оценить простые игры с участием всего одной жабы и одной лягушки, построив дерево игры исходной позиции. ^[1] Однако общий случай оценки произвольной позиции, как известно, NP-труден. Есть некоторые открытые предположения о ценности некоторых замечательных позиций.

Также рассматривалась версия игры-головоломки для одного игрока.

Правила

В игре «Жабы и лягушки» используется 1 × n полоса квадратов размером . В любой момент каждый квадрат либо пуст, либо занят одной жабой или лягушкой. Хотя игра может начинаться в любой конфигурации, обычно она начинается с того, что жабы занимают последовательные клетки в крайнем левом конце, а лягушки занимают последовательные клетки в крайнем правом конце полосы.

Когда наступает очередь хода левого игрока, он может либо переместить жабу на одну клетку вправо, в пустую клетку, либо «перепрыгнуть» жабу на две клетки вправо через лягушку, в пустую клетку. Прыжки через пустую клетку, жабу или более чем через одну клетку не допускаются. Аналогичные правила применяются для правого: на ходу правый игрок может переместить лягушку влево в соседнее пустое пространство или перепрыгнуть лягушку через одну жабу в пустой квадрат непосредственно слева от жабы. По правилам обычной игры, общепринятым в комбинаторной теории игр, проигрывает тот игрок, который первым не сможет сделать ход в свой ход.

Обозначения

Позиция жаб и лягушек может быть представлена строкой из трех символов: $T$ для жабы, $F$ для лягушки и $\square$ за пустое место. Например, строка $T\square \square F$ представляет собой полоску из четырех квадратов, на первом из которых изображена жаба, а на последнем — лягушка.

В комбинаторной теории игр позиция может быть описана рекурсивно с точки зрения ее вариантов, то есть позиций, на которые могут перейти левый игрок и правый игрок. Если Левый может двигаться с позиции $P$ на позиции $L_{1}$ , $L_{2}$ , ... и Право на должности $R_{1}$ , $R_{2}$ , ..., тогда позиция $P$ написано традиционно $P=\{L_{1},L_{2},\dots |R_{1},R_{2},\dots \}.$

В этих обозначениях, например, $T\square \square F=\{\square T\square F|T\square F\square \}$ . Это означает, что Левая может переместить жабу на одну клетку вправо, а Правая может переместить лягушку на одну клетку влево.

Теоретико-игровые ценности

Большая часть исследований, посвященных игре «Жабы и лягушки», была направлена на определение теоретико-игровой ценности некоторых конкретных позиций игры «Жабы и лягушки» или определение того, могут ли в игре возникнуть некоторые конкретные ценности.

Пути выигрыша для ваших математических игр сначала показали множество возможных значений. Например, :

T\square \square F=0

TF\square \square =1

T\square F\square ={\frac {1}{2}}

TFT\square F=\{0|0\}=\star

T\square TFF=\{0|\star \}=\uparrow

В 1996 году Джефф Эриксон доказал, что для любого двоично-рационального числа q (единственного числа, которое может возникнуть в конечных играх) существует позиция жаб и лягушек со значением q. Он также нашел явную формулу для некоторых замечательных позиций, таких как $T^{a}\square ^{b}F$ и сформулировал шесть гипотез о ценности других позиций и сложности игры. ^[2]

Эти предположения стимулировали дальнейшие исследования. Джесси Халл доказал гипотезу 6 в 2000 году. ^[3] в котором говорится, что определение значения произвольной позиции жаб и лягушек является NP-трудным. Дорон Зейлбергер и Тоцапорн Аек Танатипанонда доказали гипотезы 1, 2 и 3 и нашли контрпример к гипотезе 4 в 2008 году. ^[4] Гипотеза 5, последняя из оставшихся открытыми, утверждает, что $T^{a}\square ^{b}F^{a}$ является бесконечно малой величиной для всех (a, b), кроме (3, 2).

Однопользовательская головоломка

Игра «Жабы и лягушки» может закончиться досрочно. Версия головоломки для одного игрока «Жабы и лягушки», опубликованная в 1883 году Эдуардом Лукасом , требует последовательности ходов, начиная со стандартной исходной позиции, которая длится как можно дольше, заканчивая всеми жабами справа и всеми лягушек слева. Ходы не обязательно чередуются между жабами и лягушками. ^[5]

Ссылки

^ Jump up to: ^а ^б Берлекамп, Элвин Р .; Конвей, Джон Х .; Гай, Ричард К. (2001), «Жабы и лягушки», Пути победы в математических играх , том. 1 (2-е изд.), А. К. Петерс, стр. 12–13.
^ Эриксон, Джефф (1996), «Новые результаты жаб и лягушек», в Новаковски, Ричард Дж. (редактор), « Игры без шансов » , Публикации Научно-исследовательского института математических наук, том. 29, Издательство Кембриджского университета, стр. 299–310.
^ Как упоминалось Эриксоном на его веб-сайте и Танатипанондой в его статье.
^ Thanatipanonda, Thotsaporn (2011), «Дальнейшее прыжок с жабами и лягушками», Электронный журнал комбинаторики , 18 (1): P67: 1–P67: 12, Arxiv : 0804.0640 , doi : 10.37236/554 , MR 2788684 , S2CID 35020735, MR 2788684, S2CID 35020735/554, MR 2788684, S2CID 35020735/554, MR 2788684 , S2CID 35020735/554 .
^ Левитин, Анани (2011). «Жабы и лягушки». Алгоритмические головоломки . Издательство Оксфордского университета. п. 53.

[ww-1] Jump up to: ^а ^б Берлекамп, Элвин Р .; Конвей, Джон Х .; Гай, Ричард К. (2001), «Жабы и лягушки», Пути победы в математических играх , том. 1 (2-е изд.), А. К. Петерс, стр. 12–13.

[2] Эриксон, Джефф (1996), «Новые результаты жаб и лягушек», в Новаковски, Ричард Дж. (редактор), « Игры без шансов » , Публикации Научно-исследовательского института математических наук, том. 29, Издательство Кембриджского университета, стр. 299–310.

[3] Как упоминалось Эриксоном на его веб-сайте и Танатипанондой в его статье.

[4] Thanatipanonda, Thotsaporn (2011), «Дальнейшее прыжок с жабами и лягушками», Электронный журнал комбинаторики , 18 (1): P67: 1–P67: 12, Arxiv : 0804.0640 , doi : 10.37236/554 , MR 2788684 , S2CID 35020735, MR 2788684, S2CID 35020735/554, MR 2788684, S2CID 35020735/554, MR 2788684 , S2CID 35020735/554 .

[5] Левитин, Анани (2011). «Жабы и лягушки». Алгоритмические головоломки . Издательство Оксфордского университета. п. 53.

[1]

[2]

[3]

[4]

[5]