Игра Сим: Стратегия, Рамсеева теория и выигрышные ходы.
Sim (game)
Сим – простая игра для двоих на бумаге. Соедините точки линиями и по очереди раскрашивайте их, избегая создания треугольников своего цвета! Простые правила, сложная стратегия.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Игра для двух игроков на бумаге и карандаше
Two player paper and pencil game
Sim — это игра для двух игроков, в которой используются бумага и карандаш.
Sim is a two player paper and pencil game.
Геймплей
На рисунке изображены шесть точек (вершин). Каждая точка соединена с каждой другой точкой линией (ребром). Два игрока по очереди раскрашивают любые нераскрашенные линии. Один игрок раскрашивает в один цвет, а другой – в другой цвет, при этом каждый игрок старается не допустить образования треугольника, состоящего только из линий своего цвета (учитываются только треугольники, вершины которых – это точки; пересечения линий не имеют значения). Игрок, который завершает такой треугольник, немедленно проигрывает.
Six dots (vertices) are drawn. Each dot is connected to every other dot by a line (edge). Two players take turns coloring any uncolored lines. One player colors in one color, and the other colors in another color, with each player trying to avoid the creation of a triangle made solely of their color (only triangles with the dots as all corners count; intersections of lines are not relevant); the player who completes such a triangle loses immediately.
Анализ
Теория Рамси также может быть использована для доказательства того, что ни одна игра в Сим не может закончиться вничью. В частности, поскольку число Рамси R(3, 3) равно 6, любое двухцветное раскрашивание полного графа на 6 вершинах (K6) должно содержать монохромный треугольник и, следовательно, не является ничейной позицией. Это также применимо к любому суперграфу K6. Дополнительное доказательство того, что в конечном итоге должен образоваться треугольник одного из цветов, можно найти в теореме о друзьях и незнакомцах. Компьютерный поиск подтвердил, что второй игрок может выиграть Сим при идеальной игре, однако поиск идеальной стратегии, которую люди могли бы легко запомнить, остаётся открытой проблемой. Игра Сим является одним из примеров игры Рамси. Возможны и другие игры Рамси. Например, игрокам можно разрешить раскрашивать более одной линии за ход. Другая игра Рамси, похожая на Сим и связанная с числом Рамси R(4, 4) = 18, играется на 18 вершинах и 153 ребрах между ними. Задача двух игроков состоит в том, чтобы избегать раскрашивания всех шести рёбер, соединяющих четыре вершины. Поскольку число Рамси R(3, 3, 3) равно 17, любое трёхцветное раскрашивание полного графа на 17 вершинах должно содержать монохромный треугольник. Соответствующая игра Рамси использует карандаши трёх цветов. Один из подходов предполагает участие трёх игроков, а другой позволяет двум игрокам поочередно выбирать любой из трёх цветов для раскрашивания ребра графа, пока один из игроков не проиграет, завершив монохромный треугольник. Поиск идеальных выигрышных стратегий для этих вариантов, скорее всего, невозможен. Технический отчёт Вольфганга Слани доступен в сети и содержит множество ссылок на литературу о Симе, начиная с момента представления игры Густавусом Симмонсом в 1969 году, включая доказательства и оценки сложности, а также вычислительной сложности Сима и других игр Рамси.
Ramsey theory can also be used to show that no game of Sim can end in a tie. Specifically, since the Ramsey number R(3, 3) is equal to 6, any two coloring of the complete graph on 6 vertices (K6) must contain a monochromatic triangle, and therefore is not a tied position. This will also apply to any super graph of K6. For another proof that there must eventually be a triangle of either color, see the Theorem on friends and strangers. Computer search has verified that the second player can win Sim with perfect play, but finding a perfect strategy that humans can easily memorize is an open problem. The game of Sim is one example of a Ramsey game. Other Ramsey games are possible. For instance, the players can be allowed to color more than one line during their turns. Another Ramsey game similar to Sim and related to the Ramsey number R(4, 4) = 18 is played on 18 vertices and the 153 edges between them. The two players must avoid to color all six edges connecting four vertices. Because the Ramsey number R(3, 3, 3) is equal to 17, any three coloring of the complete graph on 17 vertices must contain a monochromatic triangle. A corresponding Ramsey game uses pencils of three colors. One approach can have three players compete, while another would allow two players to alternately select any of the three colors to paint an edge of the graph, until a player loses by completing a monochromatic triangle. Finding perfect winning strategies for these variants is most likely out of reach. A technical report by Wolfgang Slany is available online, with many references to literature on Sim, going back to the game's introduction by Gustavus Simmons in 1969, including proofs and estimates of the difficulty as well as computational complexity of Sim and other Ramsey games.
Программное обеспечение
Приложение, включая его исходный код, написанное на визуальном кроссплатформенном языке программирования Catrobat, доступно для игры с использованием вашего смартфона.
An app including its source code in the visual multi platform Catrobat programming language is available for playing it against one's smartphone.