Что это за игра
В Chomp играют на плитке шоколада. Ход — выбрать квадратик и съесть его вместе со всеми квадратиками правее и выше: от плитки отламывается прямоугольный угол. Левый нижний квадратик отравлен, и проигрывает тот, кому приходится его съесть. Ничьих не бывает.
Под именем Chomp игра известна от Дэвида Гейла, описавшего её в 1974 году. Эквивалентная игра о делителях числа публиковалась и раньше — у Фредерика Шуха в 1950-е, — но форма с шоколадкой принадлежит Гейлу.
Какие бы ходы ни были сделаны, от плитки всегда остаётся «лестница»: ни один ряд не длиннее ряда под ним. Именно поэтому игра достаточно мала, чтобы пересчитать её по квадратику.
Кража стратегии
На любой прямоугольной плитке больше 1×1 у первого игрока есть выигрышная стратегия, и доказательство укладывается в три строки. Пусть при верной игре выигрывает второй. Тогда на первый ход «съесть правый верхний квадратик» у него есть выигрышный ответ. Но любой такой ответ первый игрок мог сделать сам, первым же ходом, — правый верхний квадратик всё равно исчез бы вместе с ним. Значит, у первого есть ход, после которого выигрывает он. Противоречие.
Доказательство неконструктивно: оно гарантирует, что выигрышный первый ход существует, и не называет ни одного. У нима есть формула Бутона — XOR, считающийся в уме. У Chomp формулы нет. Для конкретной плитки выигрышные ходы находит только перебор позиций — всех.
Плитка 8×5 просчитана целиком
Позиций-лестниц на плитке 8×5 около тысячи трёхсот. При загрузке страницы машина обходит их все и помечает каждую: выигрышная или проигрышная для того, чей ход. На это уходят миллисекунды.
Первый ход отдан вам — то есть вам отдана сторона, за которую победа доказана. На экспертном уровне машина играет по таблице точно: пока вы держите выигрышную линию, ей остаётся только тянуть, выбирая самые длинные продолжения, и ждать. Одна ошибка — и таблица доведёт партию до отравленного квадратика в ваших руках.
Уровни
- Обычный — компьютер сверяется с таблицей примерно на трети своих ходов, остальные берёт наугад.
- Сложный — таблица в трёх ходах из четырёх.
- Эксперт — таблица на каждом ходу. Из выигрышной позиции он всегда отвечает проигрышной для вас; из проигрышной — тянет партию так долго, как только можно.
Компьютер никогда не ест отравленный квадратик, пока у него есть любой другой выбор, — и вы не можете: квадратик открывается, только когда он остался последним.