3-gewinnt mit KI

[alzaimar]

Hier mal eine Tic-Tac-Toe-Version, die alle Spielzüge durchprobiert und dann den dann den Besten nimmt (Minimax-Algorithmus). Der algorithmus kommt auch bei Schachprogrammen zum Einsatz (auch wenn er da optimiert wird).

Der Algorithmus führt jeden Zug 'im Geiste aus'. Dann wird jeder Zug des Gegners nacheinander ausgeführt, dann wieder der darauf mögliche eigene usw. bis es zu einer Endstellung kommt, die bewertet wird. Der letzt Zug wird zurückgenommen, dann der nächste probiert usw.

Bei Tic-Tac-Toe kann man noch bis zum Ende durchrechnen, bei Schach geht das nicht mehr: Hier kommt dann eine Stellungsbewertung zum Einsatz, die am Ende des Suchbaumes für jede Stellung einen Wert ermittelt, der angibt, wie gut / wie schlecht die Stellung aus Sicht eines bestimmten Spielers ist.

[QuickAndDirty]

Gebe meinem Vorredner recht.
Für solche kleinen Probleme ist nur ein Minmax geiegnet.
Bau einen Rekursiven Minmax-Brute-Force ein.
Am leichtesten kannst du denn Minmax durch das Programmieren eines "Nimm Spiels" verstehen.
(man darf 1,2,3, Streichölzer nehmen, jeder Spieler nimmt abwechselnd, wer den Letzen nimmt hat verloren)

Die aufgebauten Suchbäume sind mit Werten belegt. Die kommen dadurch zustande das ein Blatt in dem man verloren hat den wert -1 nachoben reicht und ein blatt in dem man gewonnen hat +1 nach oben reicht. So hat man in der Liste der Möglichen züge dich ja allesamt wurzeln sind für jeden ZUG eine Bewertung. Je höher der Wert desto besser der Zug.

[alzaimar]

Da muß ich Dir widersprechen: Bei so einem kleinen Spiel muss man eigentlich keinen Suchbaum aufbauen, da tut es auch eine Heuristik (keine KI), die hier implementiert wurde. Diese Heuristik wird aber versagen, wenn das Spielfeld vergrößert wird. Dann greift die hinter der Heuristik stehende Annahme nicht mehr: Erst den Gegner am Gewinnen hindern, und wenn das nicht nötig ist, selbst einen 2er aufbauen.

Es fehlt nämlich die Möglichkeit, eine "Zwickmühle" zu verhindern: Das geht bei TTT eigentlich gar nicht, aber wenn das Spielfeld größer wird, schon...

Bei Dame/Mühle/Schach etc sieht die Sache schon anders aus. Hier sind Suchbäume bzw. deren Traversierung (Minimax, NegaMax, etc) schon eher geeignet. Wobei hier das Abbruchkriterium, also das Ermitteln der maximalen Baumtiefe, das größte Problem ist ('Horizonteffekt').

Neuronale Netze sind auch interessant, z.B. spielt das weltbeste Backammonprogramm mit einem NN.

[edit] Eins nicht zu vergessen: Flash11 hat eine saubere Heuristik hinbekommen, die offenbar keine Fehler mehr macht. :thumb: Alle Achtung! [/edit]

[QuickAndDirty]

Ob es ihm auch für zukünftige Probleme was nützt wenn er sich jedes mal ne andere Heuristik überlegen muss?
IMHO Lernt er mehr über KI wenn er ein NN oder einen MinMax implemtiert als wenn er eine nur einmal nutzbare
Heuristik implementiert...
Kann ja jeder seine Meinung dazu haben.

[fLaSh11]

neue Version (V0.3.0) - BETA! :party:

Ich hab dem ganzen ein neues Design verpasst. Feedback dazu bitte :). (Achtung: Jewils in die Mitte der Kästchen drücken!)
Außerdem kann amn jetzt die KI auch auf leicht* stellen.





*Dann erkennt sie keine Zwickmühlen... :)

[Matze]

Ich find's bissl einfach. Man erkennt am Screenshot zwar nicht, dass es sich um ein KI-Spiel handelt, aber es ist eines und das auf Stufe "schwer". Ich (X) bin an der Reihe. Aber von Design schon ganz nett. :)

[Glocke89]

Das Spiel ist gut!! Die KI haste schön gemacht

Nach ca. 5min Spielzeit: :coder:
Ich habe die KI noch nicht besiegen können - wurde aber auch noch nicht von ihr besiegt

Also gratz für die geile KI :spin2:

[fLaSh11]

Zitat:

Zitat von Matze

Ich find's bissl einfach. Man erkennt am Screenshot zwar nicht, dass es sich um ein KI-Spiel handelt, aber es ist eines und das auf Stufe "schwer". Ich (X) bin an der Reihe.

Der Fehler müsste behoben sein. (V0.3.1) :D

edit: Hat schon jemand gemerkt, dass es auch Sounds gibt :), werden in der nächsten Version lauter^^...

[Martin K]

Sound nicht schlecht, jetzt fehlt nur noch die passende Animation dazu.
Also dass auch passend zum Sound gezeichnet wird :wink:

Sollte doch eigentlich über die Canvas möglich sein, einfach Pixel für Pixel zeichnen...
Oder du bastelst dir eine Gif-Animation, eine die ein X zeichnet und eine die ein O zeichnet.

[fLaSh11]

Kann ich einem Canvas ein Bild angeben und das dann Pixel für Pikel zeichnen lassen ;)? Oder ist das schon etwas schwerer? Weil eine Gif-Animation zu basteln möcht nicht unbedingt. Denn damit das dass flüssig wirkt, braüchte ich für eine Sekunde Animation 24 Bilder, oder?