Комбинаторная теория игр изучает несколько игр с раскраской карт . Общая идея состоит в том, что нам дается карта с нарисованными областями, но не со всеми областями окрашенными. Два игрока, левый и правый , по очереди раскрашивают одну неокрашенную область за ход с учетом различных ограничений. Ограничения на ход и условия выигрыша являются особенностями конкретной игры.
Некоторым игрокам легче раскрасить вершины дуального графа , как в теореме о четырех цветах . В этом методе игры регионы представлены маленькими кружками, а окружности соседних регионов соединены отрезками линий или кривыми. Преимущества этого метода заключаются в том, что на повороте нужно отмечать только небольшую область и что изображение обычно занимает меньше места на бумаге или экране. Первое преимущество менее важно при игре с компьютерным интерфейсом вместо карандаша и бумаги. Также можно играть с Go камнями или шашками .
Ограничения перемещения [ править ]
Неотъемлемым ограничением каждой игры является набор цветов, доступных игрокам в раскрашиваемых регионах. Если левый и правый имеют одинаковые цвета, игра беспристрастна ; в остальном игра партизанская . Набор цветов также может зависеть от состояния игры; например, может потребоваться, чтобы используемый цвет отличался от цвета, использованного в предыдущем ходу.
Ограничения перемещения на основе карты обычно основаны на окрашиваемой области и ее соседях, тогда как в задаче раскраски карты регионы считаются соседями, когда они встречаются вдоль границы, которая длиннее одной точки. Классическая задача раскраски карты требует, чтобы никакие две соседние области не имели одинаковый цвет. Классическое движение ограничение обеспечивает это путем запрета раскраски области с таким же цветом , как один из его соседа. Anticlassical ограничение запрещает окрасочное область с цветом , который отличается от цвета одного из своих соседей.
Другой вид ограничения - это следствие , при котором каждый ход после первого должен раскрасить соседа области, окрашенной на предыдущем ходу. Еще одно возможное ограничение - это анти-следствие .
Возможны и другие виды ограничений, например, требование к регионам, которые являются соседями соседей, использовать разные или одинаковые цвета. Эту концепцию можно рассматривать как применимую к областям на расстоянии два графа и можно обобщить на большие расстояния.
Условия выигрыша [ править ]
Победителем обычно становится последний игрок, который сделает ход. Это называется обычным игровым соглашением. Согласно соглашению об игре « misère», проигрывает последний игрок, который сделает ход. Существуют и другие возможные условия выигрыша и проигрыша, такие как подсчет территории, как в Го .
Монохромный и варианты [ править ]
Все эти игры, появившиеся в (Silverman, 1971), используют классическое ограничение на ход. В беспристрастной монохромной игре доступен только один цвет, поэтому каждый ход удаляет цветной регион и его соседей из игры. В бихроме оба игрока могут выбрать один из двух цветов при соблюдении классических условий. Оба игрока выбирают один и тот же цвет, поэтому игра беспристрастна . Трихром расширяет это до трех цветов для игроков. Условие может быть расширено до любого фиксированного количества цветов, что дает возможность дальнейших игр. Как упоминает Сильверман, хотя теорема о четырех цветах показывает, что любую планарную карту можно раскрасить четырьмя цветами, это не относится к картам, на которых были залиты некоторые цвета, поэтому добавление более четырех цветов может повлиять на игры.
Col and Snort [ править ]
В Col есть два цвета в зависимости от классического ограничения, но левый разрешается только цветные участки B л уе, а справа разрешается только цвет их R - е изд. Таким образом, это партизанская игра , потому что в ходе игры левым и правым становятся доступны разные ходы .
Snort использует аналогичное партизанское присвоение двух цветов, но с антиклассическим ограничением: соседним регионам не разрешается давать разные цвета. Раскрашивание регионов объясняется присвоением полей быкам и коровам, где на соседних полях не может содержаться рогатый скот противоположного пола, чтобы они не отвлекались от выпаса.
Эти игры были представлены и проанализированы в (Conway, 1976) . Имена являются мнемоническими для разницы в ограничениях (классическая раскраска карты по сравнению с шумами животных), но Конвей также приписывает их своим коллегам Колину Вауту и Саймону Нортону.
Другие игры [ править ]
В беспристрастной игре « Контакт» (Сильверман, 1971) используется один цвет с ограничением следования: все ходы после первого цвета являются соседом области, окрашенной последним. Сильверман также приводит пример Misère Contact .
Концепция игры с раскраской карты может быть расширена на такие игры, как « Ангелы и дьяволы» , в которых правила раскраски несколько отличаются по своему вкусу.
Ссылки [ править ]
- Конвей, Джон Хортон (1976). О числах и играх . Академическая пресса . ISBN 0-12-186350-6. Переработано и переиздано как
- --- (2000). О числах и играх . А.К. Петерс . ISBN 1-56881-127-6.CS1 maint: числовые имена: список авторов ( ссылка )
- Сильверман, Дэвид Л. (1971). Ваш ход . Макгроу-Хилл . Переработано и переиздано как
- --- (1991). Your Move: логические, математические и словесные головоломки для энтузиастов . Dover Press . ISBN 0-486-26731-8.CS1 maint: числовые имена: список авторов ( ссылка )
