Кол (игра)
Col — это игра с карандашом и бумагой , в частности игра по раскрашиванию карт , включающая заштриховку областей на рисовании линий в соответствии с правилами раскраски графов . При каждом ходе график должен оставаться правильным (никакие две области одного цвета не могут соприкасаться), и игрок, который не может сделать правильный ход, проигрывает. Игра была описана и проанализирована Джоном Конвеем , который приписал ее Колину Воуту , в книге «О числах и играх» . [1]
Пример игры
[ редактировать ]В следующей игре первый из двух игроков использует красный цвет , а второй — синий . Последний ход на каждом изображении показан ярче остальных областей.
Стартовый график: 
Для начала первый игрок может раскрасить любую область. Однако область за пределами графика не включена в эту игру.
После первого хода: 
Теперь второй игрок закрашивает белую клетку. Поскольку в настоящее время ни одна область не выделена синим цветом, допускается любая белая клетка.
Два хода: 
В этот момент вступает в силу требование корректности графика, так как необходимо создать красную область, не касающуюся существующей:
Как только третья область раскрашена: 
Обратите внимание, что области считаются соприкасающимися, только если они имеют общие края, а не только общие вершины, поэтому этот ход разрешен.
Игра продолжается, игроки ходят поочередно, пока один из игроков не сможет сделать ход. Этот игрок проигрывает. Возможное продолжение игры следующее (для наглядности каждый ход пронумерован):
Игра закончена: 
В этом исходе синий игрок проиграл.
Фыркать
[ редактировать ]Snort, изобретенный Саймоном П. Нортоном , использует аналогичное партийное присвоение двух цветов, но с антиклассическим ограничением: соседним регионам не разрешается присваивать разные цвета. Раскраска регионов объясняется закреплением полей за быками и коровами, при этом на соседних полях нельзя содержать скот противоположного пола, чтобы он не отвлекался от выпаса.
Решение результата в Snort является PSPACE-полным на общих графах. [2] Это доказывается сведением узла partizan Kayles , который является PSPACE-полным, к игре Snort.
Анализ
[ редактировать ]Значение позиции столбца всегда представляет собой число или число плюс звездочка. [3] Это делает игру относительно простой по сравнению со Snort, который имеет гораздо большее разнообразие значений.
Ссылки
[ редактировать ]- Берлекамп, Элвин Р .; Джон Х. Конвей; Ричард К. Гай (1982). Пути выигрыша в математических играх . Академическая пресса. ISBN 978-0-12-091101-1 . Переработано и переиздано как
- Берлекамп, Элвин Р. (2004) [2001]. Пути победы в математических играх (2-е изд.). АК Питерс Лтд. ISBN 978-1-56881-130-7 .
- Конвей, Джон Хортон (1976). О числах и играх . Академическая пресса. ISBN 978-0-12-186350-0 . Переработано и переиздано как
- Конвей, Джон Хортон (2000). О числах и играх . АК Питерс Лтд. ISBN 978-1-56881-127-7 .
- ^ О числах и играх : 1
- ^ Демейн, Эрик; Хирн, Роберт (2001). «Игры с алгоритмами: алгоритмико-комбинаторная теория игр». arXiv : cs/0106019v2 .
- ^ Пути победы : 2
Внешние ссылки
[ редактировать ]- [1] Игры Col и Snort в Google Play