WikiDer > Сим (игра с карандашом)

Sim (pencil game)
Игровая площадка

Сим это игра в карандаш и бумагу, в которую играют два игрока.

Геймплей

Нарисовано шесть точек («вершин»). Каждая точка соединена с каждой другой точкой линией («краем»).

Два игрока по очереди раскрашивают неокрашенные линии. Один игрок окрашивает в один цвет, а другой - в другой, причем каждый игрок пытается избежать создания треугольника, состоящего исключительно из его цвета (учитываются только треугольники с точками в качестве углов; пересечения линий не имеют значения); игрок, завершивший такой треугольник, немедленно проигрывает.

Анализ

Теория Рамсея может также использоваться, чтобы показать, что ни одна игра Сима не может закончиться ничьей. В частности, поскольку Число Рамсея р(3,3) = 6, любая двукратная раскраска полный график на 6 вершинах (K6) должен содержать монохромный треугольник и, следовательно, не является связанной позицией. Это также применимо к любому суперграфу K6. Еще одно доказательство того, что в конечном итоге должен быть треугольник любого цвета, см. Теорема о друзьях и незнакомцах.

Компьютерный поиск подтвердил, что второй игрок может выиграть Сима безупречной игрой, но найти идеальную стратегию, которую люди могут легко запомнить, является открытой проблемой.[1]

Игра Сима - один из примеров игры Рэмси. Возможны и другие игры Рэмси. Например, игрокам может быть разрешено раскрашивать более одной линии во время своего хода. Еще одна игра Рэмси, похожая на Сима и связанная с числом Рэмси. р(4,4) = 18, что снова не может закончиться ничьей, разыгрывается на 18 вершинах и 153 ребрах между ними. Двое игроков должны избегать раскрашивания монохромного тетраэдр (трехмерная пирамида с четырьмя треугольными гранями).

Число Рамсея р(3,3,3) = 17 означает, что любая трехцветная раскраска полного графа на 17 вершинах должна содержать монохромный треугольник. В соответствующей игре Рамсея используются карандаши трех цветов. В одном подходе могут соревноваться три игрока, в то время как другой позволяет двум игрокам поочередно выбирать любой из трех цветов, чтобы закрасить край графа, пока игрок не проиграет, завершив монохроматический треугольник. Найти идеальные выигрышные стратегии для этих вариантов, скорее всего, невозможно.

Технический отчет[2] Вольфганга Слэни доступен в Интернете, со многими ссылками на литературу о Симе, начиная с введения в игру автора Густав Симмонс в 1969 г.,[3] включая доказательства и оценки сложности, а также вычислительная сложность Сима и других игр Рэмси.

Программного обеспечения

Самосовершенствование Java-апплет включая его исходный код доступен[4] для онлайн-игры против компьютерной программы.

Доступно приложение, включающее его исходный код на визуальном мультиплатформенном языке программирования Catrobat.[5] для игры против своего смартфона.

Электронная версия доступна по адресу: https://wideaperture.net/sim/

Рекомендации

  1. ^ Мид, Эрнест; Роза, Александр; Хуанг, Шарлотта (1974-11-01). «Игра Сима: выигрышная стратегия для второго игрока». Математический журнал. 47 (5): 243. Дои:10.2307/2688046. ISSN 0025-570X.
  2. ^ Игры Graph Ramsey Вольфганг Слани в arXiv
  3. ^ Симмонс, Густав Дж. «Игра в SIM», J. Развлекательная математика, 2 (2), 1969, с. 66.
  4. ^ Страница Java-апплета, включая исходный код
  5. ^ Приложение для смартфонов, включая исходный код