Phutball (сокращение от Philosopher's Football ) - это абстрактная настольная игра для двух игроков , описанная в книгах Элвина Берлекампа , Джона Хортона Конвея и Ричарда К. Гая « Победные пути для ваших математических игр» . [1]
Правила [ править ]
В футбол играют на пересечениях сетки 19 × 15, используя один белый камень и столько черных камней, сколько необходимо. [1] В этой статье двух игроков зовут Ош (O) и Экс (X). Доска обозначена буквами от A до P (без I) слева направо и от 1 до 19 снизу вверх с точки зрения Оса. Строки 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), является NP-полной . [2] Исходя из начальной позиции, неизвестно, имеет ли какой-либо игрок выигрышную стратегию или у обоих игроков есть стратегия вытягивания, но существуют другие конфигурации, из которых оба игрока имеют стратегии вытягивания. [3]
Учитывая произвольную позицию на доске, с первоначально белым камнем, помещенным в центр, определение того, имеет ли текущий игрок выигрышную стратегию, является трудным для PSPACE . [4]
Ссылки [ править ]
- ^ a b c d e Шмиттбергер, Р. Уэйн (1992). Новые правила классических игр . John Wiley & Sons Inc., стр. 112–14 . ISBN 978-0471536215.
- ^ Demaine, Эрик Д .; Демейн, Мартин Л .; Эпштейн, Дэвид (2002). «Футбол-эндшпиль тяжелый» (PDF) . Больше игр без шанса . Публикации ИИГС 42, Cambridge Univ. Нажмите. С. 351–360.
- ^ Саркар, Sucharit (2019). «Футбол ничьи» . Игры без шанса 5 . Публикации ИИГС 70, Cambridge Univ. Нажмите. С. 439–446.
- ^ Dereniowski, Дариуш (2010). «Футбол - это тяжело для PSPACE». Теоретическая информатика . 411 (44–46): 3971–3978. arXiv : 0804.1777 . DOI : 10.1016 / j.tcs.2010.08.019 . S2CID 14975402 .
Дальнейшее чтение [ править ]
- Гроссман, JP; Новаковски, Ричард Дж. (2002). «Одномерный Phutball» (PDF) . Больше игр без шанса . Публикации ИИГС 42, Cambridge Univ. Нажмите. С. 361–367.
