Chomp - это стратегическая игра для двух игроков, в которой используется прямоугольная сетка, состоящая из квадратных ячеек меньшего размера , которые можно представить как блоки плитки шоколада. Игроки по очереди выбирают один блок и «съедают» (убирают с доски) вместе с теми, что находятся под ним и справа от него. Левый верхний блок «отравлен», и игрок, который его съест, проигрывает.
Формулировка шоколадной плитки Chomp принадлежит Дэвиду Гейлу , но эквивалентная игра, выраженная в терминах выбора делителей фиксированного целого числа, была опубликована ранее Фредериком Шу .
Chomp является частным случаем посета игры , где частично упорядоченное множество , на котором проходит игра представляет собой продукт из общего количества заказов с минимальным элементом (ядовитый блок) удален.
Пример игры [ править ]
Ниже показана последовательность ходов в типичной игре, начиная с такта 5 × 4:
Игрок А ест два блока из правого нижнего угла; Игрок B съедает троих из нижнего ряда; Игрок A выбирает блок справа от отравленного блока и съедает одиннадцать блоков; Игрок Б съедает три блока из оставшегося столбца, оставляя только отравленный блок. Игрок А должен съесть последний блок и проигрывает.
Обратите внимание: поскольку доказуемо, что игрок A может выиграть, начиная с бара 5 × 4, по крайней мере, один из ходов A является ошибкой.
Победа в игре [ править ]
Chomp относится к категории беспристрастных игр с идеальной информацией для двух игроков .
Для любой прямоугольной стартовой позиции, кроме 1 × 1, первый игрок может выиграть. Это можно показать с помощью аргумента о краже стратегии : предположим, что у второго игрока есть выигрышная стратегия против любого первоначального хода первого игрока. Предположим, что первый игрок берет только правый нижний квадрат. По нашему предположению, у второго игрока есть ответ, который приведет к победе. Но если такой выигрышный ответ существует, первый игрок мог бы сделать его своим первым ходом и таким образом добиться победы. Следовательно, у второго игрока не может быть выигрышной стратегии.
Компьютеры могут легко вычислить выигрышные ходы в этой игре на двумерных досках разумного размера.
Обобщения Chomp [ править ]
В трехмерном Chomp есть начальная плитка шоколада, состоящая из кубовидных блоков, обозначенных как (i, j, k). Ход состоит в том, чтобы взять блок вместе с любым блоком, все индексы которого больше или равны соответствующему индексу выбранного блока. Таким же образом Chomp можно обобщить на любое количество измерений.
Chomp иногда описывают численно. Дается начальное натуральное число , и игроки попеременно выбирают положительные делители начального числа, но не могут выбирать 1 или кратное ранее выбранному делителю. Эта игра моделирует n- мерный Chomp, где начальное натуральное число имеет n простых множителей, а размеры доски Chomp задаются показателями простых чисел в его простой факторизации . Ordinal Chomp играется на бесконечной доске с порядковыми числами некоторых размеров.: например, стержень 2 × (ω + 4). Ход состоит в том, чтобы выбрать любой блок и удалить все блоки, оба индекса которых больше или равны соответствующим индексам выбранного блока. Случай ω × ω × ω Chomp - заметная открытая проблема; была предложена награда в размере 100 долларов [1] за первый выигрышный ход.
В более общем смысле, в Chomp можно играть на любом частично упорядоченном наборе с минимальным количеством элементов . Ход состоит в том, чтобы удалить любой элемент вместе со всеми более крупными элементами. Игрок проигрывает, взяв наименьшее количество элементов.
Во все разновидности Chomp также можно играть, не прибегая к отравлению, используя условность игры misère : игрок, который съедает последний кусок шоколада, не отравлен, а просто проигрывает в силу того, что он последний игрок. Это идентично обычному правилу при самостоятельной игре в Chomp, но отличается при игре с дизъюнктивной суммой игр Chomp, где проигрывает только последний последний блок шоколада.
См. Также [ править ]
Ссылки [ править ]
- ^ стр. 482 в: Игры без шанса (Р. Дж. Новаковски, ред.), Cambridge University Press, 1998.
Внешние ссылки [ править ]
- Подробнее об игре
- Бесплатная версия для windows
- Играть в Chomp онлайн
- Все выигрышные закуски для размера до 14
