Жабы и лягушки - Toads and Frogs - Wikipedia

Пример комбинаторной игры Toads And Frogs

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

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

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

Правила

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

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

Обозначение

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

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

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

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

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

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

${\displaystyle T\square \square F=0}$

${\displaystyle TF\square \square =1}$

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

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

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

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

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

Одиночная головоломка

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

Рекомендации

1. Берлекамп, Элвин Р.; Конвей, Джон Х.; Гай, Ричард К. (2001), «Жабы и лягушки», Выигрышные способы для ваших математических игр, 1 (2-е изд.), А. К. Петерс, стр. 12–13.
2. Эриксон, Джефф (1996), «Новые результаты жаб и лягушек», Новаковски, Ричард Дж. (Ред.), Игры без шанса, Публикации НИИ математических наук, 29, Cambridge University Press, стр. 299–310.
3. Как упоминалось как Эриксоном на своем веб-сайте, так и Танатипанондой в своей статье.
4. Танатипанонда, Тотсапорн (2011), «Дальнейшие прыжки с жабами и лягушками», Электронный журнал комбинаторики, 18 (1): P67: 1 – P67: 12, arXiv:0804.0640, Дои:10.37236/554, МИСТЕР  2788684, S2CID  35020735
5. Левитин, Ананий; Левитин, Анани (2011). «Жабы и лягушки». Алгоритмические головоломки. Издательство Оксфордского университета. п. 53.