Tic Tac Toe

Aufgrund seiner Einfachheit wird Tic-Tac-Toe häufig als pädagogisches Mittel eingesetzt, um die Konzepte des Sportsgeists und den Zweig der künstlichen Intelligenz zu vermitteln, der sich mit der Suche in Spielbäumen beschäftigt. Es ist einfach, ein Computerprogramm zu schreiben, um Tic-Tac-Toe perfekt zu spielen oder die 765 essentiell unterschiedlichen Positionen (die Zustandsraumkomplexität) oder die 26.830 möglichen Spiele bis hin zu Rotationen und Spiegelungen (die Spielbaumkomplexität) auf diesem Raum aufzuzählen.[1] Bei optimalem Spiel beider Spieler endet das Spiel immer unentschieden, was Tic-Tac-Toe zu einem sinnlosen Spiel macht.[2]

Das Spiel lässt sich zu einem m,n,k-Spiel verallgemeinern, bei dem zwei Spieler abwechselnd Steine ihrer eigenen Farbe auf ein m×n-Brett legen, mit dem Ziel, k Steine ihrer eigenen Farbe in einer Reihe zu erhalten. Tic-Tac-Toe ist das (3,3,3)-Spiel.[3] Hararys verallgemeinertes Tic-Tac-Toe ist eine noch breitere Verallgemeinerung von Tic-Tac-Toe. Es kann auch als nd-Spiel verallgemeinert werden. Tic-Tac-Toe ist das Spiel, bei dem n gleich 3 und d gleich 2 ist.[4] Es lässt sich noch weiter verallgemeinern, indem man auf einer beliebigen Inzidenzstruktur spielt, bei der Zeilen Linien und Zellen Punkte sind. Tic-Tac-Toe ist das Spiel, das durch die rechts gezeigte Inzidenzstruktur gegeben ist, die aus neun Punkten, drei horizontalen Linien, drei vertikalen Linien und zwei diagonalen Linien besteht, wobei jede Linie aus mindestens drei Punkten besteht.