PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : TicTacToe-KI


sexy Studentin
2006-06-01, 15:01:26
Hallooo!!!!!!!

Ihr Jungs könnt mir doch bestimmt helfen! Ich soll eine 4D-TicTacToe-KI in C++ schreiben, die nicht mit Fallunterscheidungen arbeitet (d.h. soll im Prinzip auf nxnxnxn-Feld arbeiten, brauche aber nur 3x3x3x3). Leider habe ich gar keine Idee, wie ich da ran gehen soll, weil ich mir so ein 4D-Feld nicht vorstellen kann :(

Neomi
2006-06-01, 15:36:10
Wer auch immer dir diese Aufgabe gegeben hat, hat das Spiel an sich wohl kaum mit mehr als 2 Dimensionen ausprobiert, zumindest nicht mit einer Ausdehnung von 3.

Stell dir mal eine 2x2-Feld vor. Egal, wo Spieler A setzt und wo Spieler B kontert, Spieler A kann immer im 2. Zug gewinnen. Er kann nicht nur, er wird sogar gewinnen wenn er nicht will. Deshalb ist 2x2 unspielbar, bei 2 Dimensionen ist schon 3x3 nötig. Bei 3x3x3 sieht es ähnlich aus, Spieler A kann immer im 4. Zug gewinnen (diesmal aber nur, wenn er "richtig" setzt).

3x3x3 ist quasi ebenfalls unspielbar, bei 3 Dimensionen muß es schon mindestens 4x4x4 sein. Bei 4 Dimensionen ist schon n=5 das Minimum, damit Spieler B überhaupt eine Chance hat, nicht zu verlieren. Eine Chance auf einen Sieg hat Spieler B sowieso nie, wenn Spieler A richtig gut ist, aber bei zu kleinem n kann er nichtmal ein Unentschieden erwirken.

Monger
2006-06-01, 16:01:45
Bei KI gibt es ja mehrere Ansätze. Ein Ansatz wäre, dass man Strategien aus der Realität imitiert, und der KI einen Bewertungsmaßstab gibt welche Strategie gerade sinnvoll ist. Die KI kann selbst nicht beurteilen was gut ist, aber mit einer guten Chance gewinnt sie gegen einen durchschnittlichen Menschen trotzdem.

Der zweite Ansatz wäre, die Spielsituation in Zahlen zu fassen, und den gerade optimalen Weg stur durchzurechnen. In jedem Schachcomputer ist afaik mindestens dieser Ansatz drin, dass der Computer für die nächsten X Züge alle Kombinationsmöglichkeiten durchrechnet, und sich dann die raussucht die ihm die meisten Punkte (z.B. durch schlagen wertvoller Figuren) ergibt.

Das sind - glaube ich - die beiden Extreme: relativ komplexe, aber wenige Wege vs brutales durchrechnen selbst der sinnlosesten Züge. Wenn man beides in einem Lerneffekt kombiniert, hat man eine ziemlich gute KI...


Aber zum Thema: ich denke, für Tic-Tac-Toe wären festgelegte Strategien ganz gut. Was sind denn die wichtigsten Regeln?

- sobald der Gegner zwei Steine aneinander legt, und das dritte Feld frei ist, blockier ihn.
- Sobald der Gegner in die Mitte oder in die Ecken legt, blockier einen der Wege.
- Ansonsten: leg einen Stein an eine beliebige Stelle, vorzugsweise an eigene Steine.

Das alles sollte man natürlich verfeinern. Für die KI wäre es hilfreich, wenn sie wüsste welchen Stein der Gegner zuletzt gelegt hat, denn nur im Wirkungsfeld dieses Steins kann sich die Spielsituation ändern.

Gast
2006-06-01, 16:24:08
Eine andere Möglichkeit wäre, sich während des Spiels alle Situationen zu merken, die nicht zum Erfolg geführt haben. Diese werden dann einfach nicht mehr benutzt.

Ich hab so was schon mal vor Jahren programmiert. Nach kurzer Zeit hast du keine Chance mehr gegen den Computer.

Gulu-Gulu
2006-06-08, 10:44:18
Für das Problem würd ich einen Baum bei dem die Knoten die Wahrscheinlichkeiten für Erfolg sind vorschlagen. Also bei einem 3x3 Spiel hat man Am Anfang 9 Zweige (da es 9 Möglichkeiten gibt zu setzen), an jedem dieser 9 Zweige wieder 8 Zweige, an jedem dieser 8 Zweige wieder 7 Zweige, usw.
Die Wahscheinlichkeiten für die Knoten, kann man dann entweder vorher vom Computer komplett durchrechnen lassen oder dynamisch "erlernen" lassen. Das sieht dann so aus: Nehmen wir an es sind noch 2 Felder frei. Dann gibt es noch 2 Zweige nach dem aktuellen Knoten. Jetzt setzt der Computer auf den 1. Zweig und verliert. Also bekommt der Knoten am Ende des Zweiges eine 0. Irgendwann kommt es wieder zu der gleichen Situation. Also nimmt er den anderen Knoten, weil er weiss, dass er sonst verliert. Diesmal gewinnt er. Also wird eine 100 am Ende des Zweiges notiert. Und jetzt wichtig!!! Nach jedem Spiel, bzw. Berechnung müssen alle relevanten Knoten aktualisiert werden. D.h. der Knoten mit den 2 Zweigen bekommt eine 50, weil ein Zweig zum Sieg der andere zur Niederlage führt.
Die Knotenwerte berechnen sich also aus der Summe aller Nachfolgeknoten geteilt durch Anzahl der Knoten.

edit: So kann der Computer bei jeder aktuellen Spielsituation anhand der Knotenwerte entscheiden welchen Weg er geht. Er nimmt einfach den Weg mit der höchsten Zahl.

Das ganze rekursiv programmiert und es sollte recht einfach funktionieren. Sogar für alle Varianten.

Ich hofffe das war verständlich xD.