Сим (игра)

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

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

Правила игры

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

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

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

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

Пример

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

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

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

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

История игры

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

Ничья

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

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

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

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

Примечания
  1. Java Game HEXI (англ.)
  2. Simmons, Gustavus J. "The game of SIM," J. Recreational Mathematics, 2(2), 1969, pp. 66.
  3. Гарднер, 1974, с. 406.
  4. Мельников С. Крэм и сим под «электронным микроскопом» // Наука и жизнь : журнал. — 1996. — № 3. — С. 145.

Литература

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.