[alle] Spielzüge eines TicTacToe Spieles?

jo wir haben ne aufgabe bekommen die da lautet wir sollen ALLE möglichen Spielzüge eines TicTacToe Spieles auflisten. Da das natürlich ein bißchen viele sind (...) soll/kann man diejenigen halt nur einmal benutzen die sich durch Drehung/Spiegelung sozusagen gleich sind:

[X - -] [X - O]
[- X -] == [- X -]
[O - X] [- - X]
etc.

So wie ich da bis jetzt rangegangen bin sinds aber immer noch mehrere hundert, was mir etwas suspekt ist...
Meine Frage wäre jetzt ob es da irgendn Trick gibt mit dem sich das ganze vereinfachen lässt, muss es mir nämlich nicht antun 500 Solche Dinger aufzumalen und dann zu merken das sich das auf 50 reduzieren lässt.
Hab mal versucht dafür ein Programm zu schreiben welches die Sachen für mich überprüft, bin aber leider gescheitert und wollt jetzt hier mal anfragen bevor ichs nochmal neu versuch.

Abgeben sollen wir das ganze dann außerdem in der Form [X---X-O-X] usw., d.h. es müsste doch irgendeinen Methode geben mit der man das ganze recht leicht überprüfen könnte oder? Glaube kaum das unser Lehrer 20x500 Zahlenreihen von Hand überprüfen will...
Also wäre nett wenn mir da jemand mal einen Tipp geben könnte!

Thomas_h

hallo, hab mal eine KI zu TTT geschrieben ( ist zwar nicht sonderlich intelligent, aber was solls).

wie bist du bis jetzt rangegangen ?

Stichwort: Backtracking

Was das mit der Symmetrie soll, kann ich nur erraten.

danke für die antworten schonmal.

Also es geht nicht direkt darum dass ich ne KI für TTT brauche, sondern ich soll halt (soweit ich das bis jetzt erkennen kann) "alle möglichen Spielsituationen" auflisten (dumme arbeit meiner meinung).

Dabei kann ich diejenigen auslassen, die sich halt durch Spiegelung/Drehung gleich sein sollten, ich versuch nochmal das zu verdeutlichen ist oben irgendwie verrutscht.

- X -
O - -
- - -

An der schrägen \-Achse gespiegelt wäre das:

- O -
X - -
- - -

Solche "doppelten" kann ich wiegesagt auslassen (Spiegelung: -,|,/,\ ; Drehung: 90°, 180°, 270°) trotzdem gibt es für meinen Geschmack allerdings noch deutlich zuviele Möglichkeiten (grob geschätzt 200-300 wiegesagt).

Ich kann mir nicht vorstellen das die Aufgabe so gedacht war, denn es wäre ja auch eine Riesenarbeit das zu kontrollieren, deswegen ist meine Frage eher ob ich da nicht irgendwas verplant habe und sich da evtl. doch nicht so viele Möglichkeiten ergeben, bzw. ob es da unter Umständen einen 'einfachen' Trick gibt.

Weil ich im Grunde nach der Backtracking Methode vorgegangen bin (also alles einmal durchprobieren) , das aber wohl der "hard way" wäre, ich aber auf der suche nach dem "smart way" bin

kann auch sein das es den nicht gibt, aber dann ist die aufgabe wohl arsch, naja vielleciht weiß ja doch einer etwas?

Darkfalcon

www.falconhunter.de

Dort findest du den kompletten Source zur KI

PS: es gibt nicht mehrere 10 Möglichkeiten

Thomas_h

naja du hast noch immer nicht gesagt was du dir bis dato überlegt hast
kannst oder musst du alle doppelten auslassen ?
ich denke es ist einfacher alle aufzunehmen.

musst du alle fertigen spiele aufnehmen oder alle die es generell gibt ?
was hast du dir bis jetzt überlegt ?

TheTester

Schreib dir halt ein Programm dafür. D.h. kompletten Spielbaum aufbauen durchiterieren und in eine Datei ausgeben und auch die Möglichkeit implementieren den wieder einzulesen. Hat auch den Vorteil das man mit Bäumen umgehen lernt und sogar mit solchen wo die "Ebenen" andere Anzahlen von Kindern bekommen.

bye

tt

Also es geht nicht direkt darum dass ich ne KI für TTT brauche, sondern ich soll halt (soweit ich das bis jetzt erkennen kann) "alle möglichen Spielsituationen" auflisten.

Ausgezeichnet. Dafür ist Backtracking ideal.

hardy

also ich stimme mit den anderen überein, dass man sich als erstes den kompletten spielbaum aufbauen sollte. das sollte mit dem speicherausbau dabei seit ca. 15 jahren kein problem sein.
um nun doppelte auszulassen würde ich vorschlagen alle ergebnisse des spielbaumes zu normalisieren. damit meine ich das man ein ordnungskriterium anwendet.
vorstellen könnte ich mir da, dass man zu jeder matrix einen wert berechnet indem man die zeilen der matrix hintereinander schreibt.
also so :
X--OX-O-X
dann den 3 möglichen zuständen die werte von 0 bis 2 zuweist.
also so:
100210201
wenn man als basis des zahlensystems 3 nimmt kommt man da auch leicht mit einem 16-bit integer aus.
um nun deine spiegelwerte auszusortieren, musst du nun die matrix drehen, spiegeln etc. und jeweils dazu obiges verfahren anwenden. den niedrigsten wert merke dir zu jeder matrix.

ich hoffe nun nicht zuviel verwirrung oder unsinn erzählt zu haben und überlasse den rest der aufgabe dem geneigten leser