tictactoe KI

  • Hi!
    Ich hab folgendes Problem:
    Für meinen TicTacToe-gametree verwende ich die klasse TTTTreeNode mit folgenden Funktionen:



    Die Maximale Anzahl aller möglichen Knoten in TTT sind imho 9! (= 362.880)
    Da ja einige Knoten schon früher keine Nachfolger mehr haben, wel sie gewonnene Spielzüge enthalten, sollte die Anzahl der tatsächlichen Knoten noch etwas darunter liegen.
    Auf Symetrie und andere Optimierung verzichte ich einstweilen.
    Wenn ich init() jetzt von meinem wurzelknoten mit einem leeren board aus aufrufe, wir ein Baum aufgebaut der aus 549946 Knoten besteht.
    Also entweder meine count()-Methode ist falsch, oder in der init() klappt was nicht.
    Kann mir wer sagen wo der Fehler liegt?

  • Hoi, also wir haben neulich einen Spieltheorie Algorithmus zu TicTacToe besprochen und daraufhin das berühmte 8-Schiebe-Puzzle implementiert, das ungefähr die selben Ideen verwendet.. Die Zahl 362880 stimmt zwar, aber es ist glaub ich nicht sehr zu empfehlen, den Spielbaum komplett am Beginn aufzubauen, auch wenn du auf Optimierung verzichtest, wenn du von Anfang an den Baum komplett aufbaust wird das Optimieren danach um so schwerer.. Beim 8 Puzzle habe ich einen Algorithmus verwendet, der bisherige Züge beim Baumaufbau ausschliesst, vielleicht solltest du dir ein paar Methoden zurecht legen, die dir während dem Spiel auf n < 5 Ebenen den möglichen Spielbaum aufbaut. Eine genaue Lösung zu deinem Problem weiss ich jetzt nicht, aber die count methode an sich sieht nicht wirklich falsch aus würd ich sagen,.. durchsteppen mit debug wird halt recht schwer bei 362880 zyklen,.. aber du könntest mal ein paar läufe durchmachen und schauen ob er am anfang schon was unterschlägt, dafür solltest du aber eine eingerückte formatierung deines codes verwenden damit du optimal die ergebnisse nach zeilen analysieren kannst,.. bei dem if in ::count() mein ich,... sorry, ausser den paar tips kann ich dir nicht wirklich helfen,...

  • eigentlich gehts um den minmax algorithmus.
    die aufgabenstellung lautet zuerst den kompletten spielebaum aufzubauen.
    bei tictactoe ist der speicherverbrauch noch (halbwegs) vertretbar.

    362880 zyklen sind sicher zu viel, aber 15 hab ich mit zettel und bleistift gemacht, und dabei keinen fehler entdecken können.