TicTacToe Strategie des Computers

Hallo Allerseits,

programmiere ein TicTacToe-Spiel gegen den Computer, als Konsolenanwendung (objektorinetiert). Nun komme ich auf keine Idee, wie ich die Strategie des Computers realisiere. Ich kann mit srand den Computer zufällig einen Zug machen lassen, bzw. mit Hilfe von <ctime> habe ich bei jedem Spiel einen anderen Zufall. Aber dies entspricht nicht dem Sinn des Spiels.

Nach der Aufgabenstellung (ist eine Praktikumsaufgabe an einer FH) soll eine private Methode den Sieger ermitteln. Ich dachte dies realisiere ich mit einer bool Funktion, die true zurückgibt, falls eine der 8 Gewinn-Kombinationen eintritt.

Nur wie bringe ich meinem Rechenknecht genügend verschiedene Strategien bei, dass er versucht 3 aneinanderliegende Kästchen (im Array) zu belegen und möglichst viele verschiedene Zugvariationen kennt?

Über Anregungen würde ich mich freuen!

Hallo,
du solltest dich mal mit dem Mini Max Algo auseinandersetzen, ich denke das is genau das was du suchst...

Zur Einführung vielleicht das hier:

http://de.wikipedia.org/wiki/Minimax-Algorithmus

Gruß

RedWing

Guter Hinweis mit dem Minimax-Algo!

thx 2 RedWing

sawamin

Gerade bei diesem Spiel wäre es simpel(und interessant), einfach mal sämtliche Spielsituationen auf Gewinnmöglichkeiten zu testen. Es gibt nur maximal 362880 (9!) unterschiedliche Situationen (inklusive Spiegelungen und ohne Berücksichtung bereits verlorener Partien), wenn ich mich nicht irre. Diese könnte man alle generieren und gemeinsam mit dem Zug, der zu ihrem Entstehen führt, speichern, und dann nacheinander bewerten. Alle Züge, die zu einer Verlustsituation führen, kann man dann nach und nach von hinten her eliminieren, so dass irgendwann nur noch Züge übrig bleiben, die immer zum Sieg führen.

Kachelator hat gesagt.:

Gerade bei diesem Spiel wäre es simpel(und interessant), einfach mal sämtliche Spielsituationen auf Gewinnmöglichkeiten zu testen. Es gibt nur maximal 362880 (9!) unterschiedliche Situationen (inklusive Spiegelungen und ohne Berücksichtung bereits verlorener Partien), wenn ich mich nicht irre. Diese könnte man alle generieren und gemeinsam mit dem Zug, der zu ihrem Entstehen führt, speichern, und dann nacheinander bewerten. Alle Züge, die zu einer Verlustsituation führen, kann man dann nach und nach von hinten her eliminieren, so dass irgendwann nur noch Züge übrig bleiben, die immer zum Sieg führen.

Zum Vergrößern anklicken....

Genau das macht der Algorithmus auch.
Man kann den Spielbaum ohne weiteres (bei Tic Tac Toe) bis zum Schluss
aufbauen

Gruß

RedWing

Genau das macht der Algorithmus auch.

Zum Vergrößern anklicken....

Schon klar. Ich dachte aber an eine ganz simple Brutalo-Version, die wirklich nur mit vollständiger Auswertung arbeitet.

TicTacToe ist auch ein, mehr oder weniger, interessantes Testobjekt für neuronale Netze.