Tic-Tac-Toe in einen Graphen darstellen: Wie kann man folgende Aufgaben bestimmen?

Question

Wir behandeln im Unterricht gerade das Thema Graphen und DFS und BFS. Als Aufgabe habe ich eine sehr theoretische Aufgabe bekommen. Nämlich die folgende:

Jeder Spielstand von Tic-Tac-Toe wird in einem Graphen dargestellt. (Z.B: http://www.aplu.ch/home/gifs/tictree.gif)

a) Wie viele Knoten auf Stufe 1 existieren (also alle Spielstände wenn Spieler X 1 Feld gesetzt)?

Hier hätte ich gesagt, dass es 9 Spielstände gibt. Das heisst in jedem Feld ein "X".

b) Wie viele Knoten auf Stufe 2?

Bei dieser Aufgabe, hätte ich gesagt, das wären hier nur 8 Spielstände pro oberen Spielstand. Das wäre ja dann: 9*8 = 72

c) Wie viele Spielstände die in einem Gewinn für X resultieren gibt es bei Stufe 8

Stimmt dann hier meine Rechnung: 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 = 362'880 Spielstände. Stimmt hier meine Rechnung?

d) Wie viele wirklich unterschiedliche Spielstände gibt es auf Level 2? Mit einemm DAG (Directed acyclic graph) können viele Knoten eliminiert werden, da einige Knoten denselben Spielstand repräsentieren (z.B. man rotiert oder spiegelt das Feld)

Wie geht man hier vor? Ich weiss auf Level 1 gibt es zum Beispiel nur 3 verschiedene Spielstände.

Answer 1

a) Wie viele Knoten auf Stufe 1 existieren (also alle Spielstände wenn Spieler X 1 Feld gesetzt)?

Das hast du richtig.

b) Wie viele Knoten auf Stufe 2?

Auch das hast du richtig.

c) Wie viele Spielstände die in einem Gewinn für X resultieren gibt es bei Stufe 8.

Du hast berechnet, wie viele theoretische Knoten es auf Stufe 8 gibt. Da gibt es aber sicher auch welche, die in einem Gewinn für O resultieren. Die sind hier nicht gefragt.

Man kommt nur bis stufe 8 ohne einen Gewinn für O wenn sowohl X als auch O keinen Dreier gebildet haben. Weiterhin muss aber X beim nächsten Zug den Gewinn für sich entscheiden.

Mir fehlt hier aber auch die Idee das zu berechnen, weil ich im Grunde genommen alle Knoten entfernen müsste für die es bei O zu einem Gewinn kam. Ich würde das also vermutlich durch ein kleines Computerprogramm lösen, anstatt auf mathematische Art.

d) Wie viele wirklich unterschiedliche Spielstände gibt es auf Level 2? Mit einemm DAG (Directed acyclic graph) können viele Knoten eliminiert werden, da einige Knoten denselben Spielstand repräsentieren (z.B. man rotiert oder spiegelt das Feld)

In der ersten Stufe gibt es drei, das ist völlig richtig. X links oben, X oben mittig oder X genau mittig.

Wie viele unterscheidbare Möglichkeiten gibt es für O bei den 3 Möglichkeiten und wie viele Knoten gibt es damit insgesamt? Ich komme hier auf 12 Knoten

Comments

Danke vielmals für die Hilfe. Bei der Aufgabe c) ist eben explizit gefordert, dass man dies nicht mit einem Programm löst. Für die Aufgabe d), gibt es keine andere Möglichkeit als sich dies versuchen aufzuzeichnen und dann die Schlüsse daraus ziehen?

---

c) Wie viele Spielstände die in einem Gewinn für X resultieren gibt es bei Stufe 8.

Vielleicht ist hier 0 Spielstände gefragt. In Spielstufe 8 hat O gerade seinen Zug gätätigt. Dies kann O nur tun wenn X noch nicht gewonnen hat. Also kann O nur in der 8. Stufe gewinnen.

Das Problem wird wenn halt auch die Zustände mit einbezogen werden sollen das der Gewinn für X erst in der 9. Stufe entsteht. D.h. X bekommt beim setzen seines 5. Steines 3 in eine Reihe. Natürlich wären diese Anzahl Spielstände schon in Stufe 8 bekannt. Aber die Anzahl ist meiner Meinung eben nicht so einfach berechenbar.

Ich wäre mal gespannt was die Musterlusung sagt. Ob es tatsächlich nur die 0 sind oder ob es eine einfache Möglichkeit gibt die Anzahl der Spielstände zu berechnen.