Введение

Математическая игра, игра на бумаге и ручке.

Доминирование (также известная как Stop Gate или Crosscram) — это математическая игра, в которую можно играть на любом наборе квадратов на листе в клетку. Например, в неё можно играть на квадрате 6×6, прямоугольнике, полностью неправильной полиомино-фигуре или комбинации любого количества таких элементов. Два игрока располагают по очереди на сетке домино, покрывая квадраты. Один игрок ставит костяшки домино вертикально, а другой — горизонтально. (Традиционно этих игроков называют "Левый" и "Правый" соответственно, или "V" и "H". В этой статье используются оба обозначения.) Как и в большинстве игр в комбинаторной теории игр, проигрывает первый игрок, который не может сделать ход. Доминирование — это партийная игра, в которой игроки используют разные фигуры; беспристрастной версией игры является Крам.

Однокомнатная коробка

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

Горизонтальные ряды

Эта игра представляет собой сетку 2x1. Существует соглашение присваивать игре положительное число, когда выигрывает Левый, и отрицательное – когда выигрывает Правый. В данном случае у Левого нет ходов, в то время как Правый может поставить домино, чтобы покрыть всю доску, ничего не оставив, что явно является нулевой игрой. Таким образом, в сюрреалистической нотации чисел, эта игра {|0|} = −1. Это логично, поскольку эта сетка дает преимущество в 1 ход Правому. Эта игра также {|0|} = −1, потому что одиночная клетка не может быть использована. Эта сетка – первый случай выбора. Правый может занять две левые клетки, оставив −1. Две правые клетки также оставят −1. Он также может занять две средние клетки, оставив две одиночные клетки. Этот вариант оставляет 0+0 = 0. Таким образом, эту игру можно выразить как {|0,−1|}. Это −2. Если эта игра играется совместно с другими играми, это дает Правому два свободных хода.

Вертикальные ряды

Вертикальные столбцы оцениваются аналогичным образом. Если есть ряд из 2n или 2n+1 ячеек, он засчитывается как −n. Столбец такого размера засчитывается как +n.

Игра на высоком уровне

Институт исследований математических наук провёл турнир по игре Доминирование, с призом в 500 долларов для победителя. Игра проходила на доске 8x8. Победителем стал математик Дэн Калистрайт, обыгравший Дэвида Вулфа в финале. Подробности турнира описаны в книге Ричарда Дж. Новаковского «Игры без случая» (стр. 85).

Выигрышная стратегия

Проблема, связанная с игрой Доминирование, заключается в вычислении выигрышной стратегии для больших досок, и в особенности для квадратных досок. В 2000 году Денис Брёйкер, Йош Уйте́рвик и Яап ван ден Херик вычислили и опубликовали решение для доски 8x8. Доска 9x9 была решена вскоре после внесения некоторых улучшений в их программу. Затем, в 2002 году, Нейтан Буллок решил доску 10x10 в рамках своей диссертации, посвященной игре Доминирование. Доска 11x11 была решена Йосом Уйте́рвиком в 2016 году. В Доминировании побеждает первый игрок на квадратных досках 2x2, 3x3, 4x4, 6x6, 7x7, 8x8, 9x9, 10x10 и 11x11, а второй игрок – на досках 1x1 и 5x5. Другие известные результаты для прямоугольных досок можно найти на сайте Нейтана Буллока.

Задерживай .

Крам — это беспристрастная версия игры Доминирование. Единственное отличие в правилах состоит в том, что каждый игрок может выкладывать свои домино в любом направлении. Кажется, это незначительное изменение правил, но оно приводит к совершенно иной игре, которую можно анализировать с помощью теоремы Спрага — Гранди.