Жабы и лягушки - Википедия - Toads and Frogs

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

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

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

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

Правила

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

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

Обозначение

Положение Жаб-и-Лягушек может быть представлено строкой из трех символов: ${ displaystyle T}$ для жабы, ${ displaystyle F}$ для лягушки, и ${ displaystyle square}$ за пустое место. Например, строка ${ Displaystyle Т квадрат квадрат 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 Т квадрат квадрат F = { квадрат Т квадрат F | Т квадрат F квадрат }}$. Это означает, что Left может переместить жабу на один квадрат вправо, а Right может переместить лягушку на один квадрат влево.

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

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

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

${ Displaystyle Т квадрат квадрат F = 0}$

${ Displaystyle TF square square = 1}$

${ Displaystyle Т квадрат F квадрат = { гидроразрыва {1} {2}}}$

${ Displaystyle TFT квадрат F = {0 | 0 } = звезда}$

${ Displaystyle Т квадрат TFF = {0 | звезда } = вверх}$

В 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]

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