Datenstruktur GameTree (z.B. Minimax)
-
Hallo zusammen,
ich bin gerade dabei ein Brettspiel zu programmieren.
Klappt alles super.Jetzt versuche ich eine KI einzubinden.
Habe mir, der Einfachheit halber, Minimax rausgesucht.
Allerdings habe ich bisher keinen Schimmer, wie ich die Daten des Gametrees verwalten soll. Welche Datenstruktur macht da Sinn? Könnt ihr mir helfen?Derzeit ist meine Map in einem array "map.gamemap[x][y]".
Wenn ich jetzt die Möglichen Züge durchgehe, muss ich die ja irgendwo speichern.
"evalmap.gamemap[x][y]". Wie bekomme ich jetzt aber die Verbindung der verschiedenen Tiefen hin, so dass ich einen Zweig habe? Also Nachvollziehbarkeit - welcher Zug gehört wohin.Köönnt ihr mir da bitte helfen?
Vielen Dank
Viele Grüße
Edwart
-
Du könntest das Evaluieren so dur hführen, dass die getesteten Spielzüge am ende der Evaluierung wieder rückgängig gemacht werden.
Beispielsweise per Command-Pattern mit undo
-
ok, aber irgendwie verstehe ich noch nicht, in welcher Struktur ich einen Gametree vorhalten kann.
Ich muss ja mehrere Zweige durchgehen und dann bewerten.
-
ich würd ne klase treeitem machen, die einfach einen vector<treeitem*> children beinhaltet