Phutball - Phutball - Wikipedia

Для наброска Монти Пайтона см. Футбольный матч философов.
Игра в пхутбол после того, как пять человек были размещены (мяч еще не двигался)

Phutball (Короче для Философский футбол) - это двое игроков абстрактная стратегия настольная игра описано в Элвин Берлекамп, Джон Хортон Конвей, и Ричард К. Гай с Выигрышные способы для ваших математических игр.[1]

Правила

В футбол играют на пересечениях сетки 19 × 15, используя один белый камень и столько черных камней, сколько необходимо.[1]В этой статье двух игроков зовут Ohs (O) и Eks (X). Доска обозначена буквами от A до P (без I) слева направо и от 1 до 19 снизу вверх с точки зрения Ohs. Строки 0 и 20 представляют собой «вне доски» после строк 1 и 19 соответственно.

Поскольку найти специализированные доски для футбола сложно, в игру обычно играют на доске 19 × 19. Идти доска, с белым камнем, представляющим футбольный мяч, и черными камнями, представляющими мужчин.

Цель состоит в том, чтобы забивать голы, используя людей (черные камни), чтобы переместить футбольный мяч (белый камень) на линию ворот соперника или над ней (ряды 1 или 19). Ohs пытается переместить футбольный мяч в ряды 19 или 20, а Eks - в ряды 1 или 0. В начале игры футбольный мяч помещается в центральную точку,[1] если только один игрок не дает другому фору, и в этом случае мяч начинается ближе к воротам одного игрока.

Игроки по очереди делают ходы. Ход состоит либо в добавлении человека в любую свободную точку на доске, либо в перемещении мяча. Нет никакой разницы между мужчинами, которых играет Ох, и мужчинами, которых играет Экс.[1]

Прыжок

Мяч перемещается серией прыжков через соседних мужчин. Каждый прыжок совершается на первую свободную точку по прямой по горизонтали, вертикали или диагонали над одним или несколькими людьми. Затем прыгнувшие люди удаляются с доски (до того, как произойдет любой последующий прыжок). Этот процесс повторяется до тех пор, пока остаются люди, которых можно перепрыгнуть, и игрок желает. Прыжки не обязательны: прыгать не нужно. В отличие от шашки, несколько человек подряд прыгают и удаляются как группа.[1]

На диаграмме справа показан прыжок.

  • Ohs перемещает футбольный мяч из K6 – G9 – G11 – J11.
  • Люди на J7, H8, G10 и H11 удалены.
  • Прыжок с K6 – G9 – J9 – G7 не будет законным, так как при этом человек на H8 прыгнет дважды.

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

Стратегия

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

Вычислительная сложность

Игра достаточно сложна, поэтому проверить, есть ли выигрыш в ней (на доске размером m × n), не составит труда. НП-полный.[2] Из начальной позиции неизвестно, имеет ли какой-либо игрок выигрышную стратегию или у обоих игроков есть стратегия вытягивания, но существуют другие конфигурации, из которых оба игрока имеют стратегии вытягивания.[3]

Учитывая произвольную позицию на доске, с первоначально белым камнем, помещенным в центр, определение того, имеет ли текущий игрок выигрышную стратегию, является PSPACE -жесткий.[4]

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

  1. ^ а б c d е Шмиттбергер, Р. Уэйн (1992). Новые правила классических игр. John Wiley & Sons Inc., стр.112–14. ISBN  978-0471536215.
  2. ^ Демейн, Эрик Д.; Демейн, Мартин Л.; Эппштейн, Дэвид (2002). «Футбол-эндшпиль тяжелый» (PDF). Больше игр без шанса. Публикации ИИГС 42, Cambridge Univ. Нажмите. С. 351–360.
  3. ^ Саркар, Сухарит (2019). «Футбол ничьи». Игры без шанса 5. Публикации ИИГС 70, Cambridge Univ. Нажмите. С. 439–446.
  4. ^ Дерениовский, Дариуш (2010). «Phutball - это тяжело для PSPACE». Теоретическая информатика. 411 (44–46): 3971–3978. arXiv:0804.1777. Дои:10.1016 / j.tcs.2010.08.019. S2CID  14975402.

дальнейшее чтение

  • Grossman, J.P .; Новаковски, Ричард Дж. (2002). "Одномерный Phutball" (PDF). Больше игр без шанса. Публикации ИИГС 42, Cambridge Univ. Нажмите. С. 361–367.