Col (игра) - Col (game)

Col это игра с карандашом и бумагой, в частности карта-раскраска, предусматривающий затенение участков на линейном чертеже по правилам Раскраска графика. С каждым ходом график должен оставаться правильный (никакие две области одного цвета не могут касаться друг друга), и игрок, который не может сделать разрешенный ход, проигрывает. Игра была описана и проанализирована Джон Конвей, который приписал это Колин Воут, в О числах и играх.^[1]

Пример игры

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

Стартовый график:

Первый игрок может раскрасить любую из областей, чтобы начать. Тем не менее, область за пределами графика не включена в эту игру.

После первого хода:

Теперь второй игрок раскрашивает белую клетку. Поскольку в настоящее время нет участков с синим цветом, разрешены любые белые клетки.

Два хода:

На этом этапе вступает в силу требование, чтобы график был правильным, так как должна быть сделана красная область, которая не касается существующей:

Как только третья область окрашена:

Обратите внимание, что области считаются касающимися, только если они имеют общие ребра, а не только общие вершины, так что это перемещение является допустимым.

Игра продолжается, игроки перемещаются по очереди, пока один из игроков не сможет сделать ход. Этот игрок проигрывает. Возможное продолжение игры следующее (каждый ход пронумерован для наглядности):

Игра завершена:

В этом исходе синий игрок проиграл.

Фырканье

Snort, изобретенный Саймон П. Нортон, использует аналогичное партизанское присвоение двух цветов, но с антиклассическим ограничением: соседним регионам не разрешается давать разные цвета. Окрашивание регионов объясняется присвоением полей быкам и коровам, где на соседних полях не может содержаться рогатый скот противоположного пола, чтобы они не отвлекались от пастбищ.

Решение результата в Snort PSPACE-полный на общих графиках.^[2] Это подтверждается сокращением партизанский узел Кейлс, который является PSPACE-полным, к игре Snort.

Анализ

Значение позиции Col всегда либо число, либо число плюс звезда^[3] Это делает игру относительно простой по сравнению с Snort, который имеет гораздо большее разнообразие значений.

использованная литература

• Берлекамп, Элвин Р.; Джон Х. Конвей; Ричард К. Гай (1982). Выигрышные способы для ваших математических игр. Академическая пресса. ISBN  978-0-12-091101-1. Переработано и перепечатано как
•  ———  (2004) [2001]. Выигрышные способы для ваших математических игр (2-е изд.). A K Peters Ltd. ISBN  978-1-56881-130-7.
• Конвей, Джон Хортон (1976). О числах и играх. Академическая пресса. ISBN  978-0-12-186350-0. Переработано и перепечатано как
•  ———  (2000). О числах и играх. A K Peters Ltd. ISBN  978-1-56881-127-7.

1. О числах и играх: 1
2. Демейн, Эрик; Хирн, Роберт (2001). «Игры с алгоритмами: алгоритмическая комбинаторная теория игр». arXiv:cs / 0106019v2.
3. Пути победы: 2

внешние ссылки

• [1] Игры Col and Snort в Google Play