Сим (игра) (Vnb (nijg))

Возможное положение при игре в Сим, при котором игрок, делающий последний ход, проигрывает

Сим — топологическая игра, заключающаяся в том, что два игрока по определённым правилам проводят линии на плоскости.

Правила игры

Перед началом игры на окружности (нарисованной или воображаемой) ставят несколько (обычно 6) точек.

Затем игроки по очереди ходят.

Каждый ход игрока состоит в том, что он проводит отрезок, соединяющий две из поставленных на окружности точек. Отрезки, проводимые разными игроками, различаются между собой: например, один игрок проводит красные, а другой — синие. Повторно соединять уже соединённые одним из игроков точки нельзя.

Проигрывает тот игрок, после хода которого образуется треугольник со сторонами, проведёнными этим игроком (треугольники, образовавшиеся в результате пересечения отрезков не в точках, поставленных перед игрой на окружности, не учитываются).

Пример

Пусть на поле с 6 точками оба игрока сделали по 7 ходов (не важно, в каком порядке): красные — AB, AE, AF, BD, CD, CE, CF; синие — AC, AD, BC, BE, BF, DE, DF (см. рис.). Остался единственный возможный ход — EF, который вынужден сделать игрок, ходивший первым, и которым он проигрывает, так как если ход красных, то будут построены треугольники AEF и CEF, а если синих — BEF и DEF.

Топологичность игры

Собственно, располагать соединяемые игроками точки по окружности не обязательно, так как ни взаимное расположение точек, ни прямолинейность соединяющих их отрезков не имеют значения, поэтому можно рассматривать игру на полном графе: проводимые игроками отрезки — его рёбра, а соединяемые точки — его вершины. Игроки по очереди выбирают (окрашивают в свой цвет) рёбра, ещё не выбранные ни одним из игроков с начала игры. Проигрывает игрок, после хода которого образуется цикл длины 3, состоящий из рёбер, выбранных этим игроком.

Например, в Hexi — компьютерной реализации игры Сим с 6 вершинами — после каждого хода вершины полного графа, на котором происходит игра, перемешиваются (такое поведение можно отключить в настройках), что показывает несущественность способа вложения графа в плоскость или пространство.

История игры

Игра изобретена и описана в 1969 году Густавом Симмонсом, от его фамилии и произошло название игры.

Ничья

При раскраске рёбер полного графа с n вершинами в k цветов треугольник (цикл длины 3, полный подграф с тремя вершинами) с рёбрами одного цвета может отсутствовать, только если число Рамсея $R(\underbrace {3,\ldots ,3} _{k})>n$.

Поэтому при игре двух участников с 6 и более точками ничейный исход невозможен, так как $R(3,3)=6$.

Шансы игроков

Сим является детерминированной игрой с полной информацией. Исследование игры с 6 точками, проведённое с помощью ЭВМ её изобретателем, показало, что у второго игрока имеется выигрывающая стратегия. В статье Сергея Мельникова в журнале «Наука и жизнь» сообщается, что проведённое автором подобное исследование игры с 7 точками показало, что и в этом случае у второго игрока есть выигрывающая стратегия.

Литература

• Гарднер М. Новые игры «Гонки», «Сим» и «Щёлк!» = Sim, Chomp and Race track // Математические новеллы : сборник / пер. с англ. Ю. А. Данилова; под ред. Я. А. Смородинского. — М.: Мир, 1974. — С. 404—407, 412.
• Арсак Ж. Программирование игр и головоломок = Jeux et casse-tête à programmer / под. ред. А. Г. Кушниренко. — М.: Мир, 1990. — С. 63—65, 136—137. — 224 с. — ISBN 5-02-013959-9.

Ссылки

• Game of SIM (англ.) — игра Сим на сайте BoardGameGeek
• Описание (англ.) и история (англ.) игры Сим на сайте «Pencil and Paper Games» (с англ. — «Игры с карандашом и бумагой»)