Сим (игра)

Sim — игра для двух игроков с бумагой и карандашом .

Геймплей

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

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

Анализ

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

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

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

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

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

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

приложение с исходным кодом на визуальном многоплатформенном языке программирования Catrobat. Доступно ^[4] для игры на своем смартфоне.

Ссылки

^ Мид, Эрнест; Роза, Александр; Хуанг, Шарлотта (1 ноября 1974 г.). «Игра Sim: выигрышная стратегия для второго игрока» . Журнал «Математика» . 47 (5): 243. дои : 10.2307/2688046 . ISSN 0025-570X . JSTOR 2688046 .
^ Слани, Вольфганг (10 ноября 1999 г.). «Графовые игры Рэмзи». arXiv : cs/9911004 .
^ Симмонс, Густав Дж. «Игра в SIM», J. Recreational Mathematics , 2 (2), 1969, стр. 66.
^ «Сообщество Катробатов» . Share.catrob.at . Проверено 18 февраля 2023 г.

[1] Мид, Эрнест; Роза, Александр; Хуанг, Шарлотта (1 ноября 1974 г.). «Игра Sim: выигрышная стратегия для второго игрока» . Журнал «Математика» . 47 (5): 243. дои : 10.2307/2688046 . ISSN 0025-570X . JSTOR 2688046 .

[sim-technical-report-2] Слани, Вольфганг (10 ноября 1999 г.). «Графовые игры Рэмзи». arXiv : cs/9911004 .

[3] Симмонс, Густав Дж. «Игра в SIM», J. Recreational Mathematics , 2 (2), 1969, стр. 66.

[sim-smartphone-app-4] «Сообщество Катробатов» . Share.catrob.at . Проверено 18 февраля 2023 г.

[1]

[2]

[3]

[4]