Sim (Spiel)

Spielbrett von Sim

Sim ist ein Spiel für zwei Personen. Das Spielbrett besteht aus sechs Punkten, von denen jeder mit jedem anderen durch eine Linie verbunden ist. Jedem Spieler ist eine Farbe zugeordnet und abwechselnd färbt jeder Spieler eine Linie mit seiner Farbe ein. Wer ein Dreieck in der eigenen Farbe produziert, verliert sofort.

Die Ramseytheorie zeigt, dass kein Sim-Spiel unentschieden ausgehen kann. Dies gilt insbesondere, weil die Ramsey-Zahl R(3,3)=6 ist. Jede 2-Färbung des vollständigen Graphen mit 6 Knoten ($K_{6}$) muss ein einfarbiges Dreieck enthalten. Dies gilt auch für jeden Obergraphen des $K_{6}$. Der Grund dafür ist sehr einfach nachzuvollziehen: Man wähle einen beliebigen Punkt aus. Nennen wir diesen P1. Dieser ist mit den fünf anderen Punkten verbunden. Von diesen fünf Linien müssen mindestens drei in einer Farbe sein, nennen wir diese Farbe F1. Wir schauen uns nun die drei Punkte an, die durch diese drei gleichfarbigen Linien erreicht werden. Entweder die Linien zwischen diesen drei Punkten sind alle in einer Farbe, dann bilden diese drei Punkte ein gleichfarbiges Dreieck oder mindestens zwei der drei Punkte sind mit einer Linie in Farbe F1 verbunden, dann bilden diese zwei Punkte mit P1 ein gleichfarbiges Dreieck.

Mittels vollständiger Enumeration mit dem Computer hat man herausgefunden, dass der zweite Spieler bei fehlerfreiem Spiel immer gewinnt. Eine perfekte Spielstrategie zu finden, die sich auch Menschen merken können, ist bisher nicht geglückt.

Sim ist ein Beispiel eines Ramsey-Spiels. Andere Ramsey-Spiele sind möglich. So muss beispielsweise nach der Ramseytheorie auch jede 3-Färbung eines vollständigen Graphen mit 17 Knoten ein einfarbiges Dreieck enthalten. Bei dem dazugehörigen Ramsey-Spiel benutzen die zwei Spieler beliebige von drei Farben. Es ist noch unbekannt, wer dabei gewinnt.

Weblinks

• Java-Applet an der Technischen Universität Wien für das Spiel gegen ein Computer-Programm
• Smartphone-App in der visuellen Programmiersprache Catrobat
• Graph Ramsey Games von Wolfgang Slany, technische Beschreibung mit weiterer Literatur, inklusive über die Einführung des Spieles durch Gustavus Simmons (1969)