# TicTacToe Strategie des Computers



## sawamin (16. Februar 2005)

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!


----------



## RedWing (16. Februar 2005)

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


----------



## sawamin (16. Februar 2005)

Guter Hinweis mit dem Minimax-Algo!

  thx 2 RedWing

  sawamin


----------



## Kachelator (16. Februar 2005)

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.


----------



## RedWing (16. Februar 2005)

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.



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

Gruß

RedWing


----------



## Kachelator (16. Februar 2005)

> Genau das macht der Algorithmus auch.


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


----------



## ocb (16. Februar 2005)

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


----------

