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?

[inherited]

12-15 tuns auch, auch wenn es dann nicht mehr ganz sooo flüssig wirkt.
das mit dem Canvas ist so ohne weiteres nicht möglich.
Ach ja: die KI ist gut, aber die knack ich auch noch :P

[fLaSh11]

Zitat:

Zitat von inherited

12-15 tuns auch, auch wenn es dann nicht mehr ganz sooo flüssig wirkt.
das mit dem Canvas ist so ohne weiteres nicht möglich.

Wie wärs denn mithilfe von Canvas realisierbar?

Zitat:

Zitat von inherited

Ach ja: die KI ist gut, aber die knack ich auch noch :P

thx, in der neuen Version, voraussichtlich morgen sind noch zwei Fehler beseitigt. Bis jetzt erkennt sie zwei Zwickmühlenstellungen noch nicht.

MfG
Steffen

P.S.: Gratulation zum 1.111 Beitrag :mrgreen:
:party: :party: :party: :party: :party:


edit:
Diese Stellungen erkennt er in der aktuellen Version (0.3.1) noch nicht:

Code:

- X -   - - -
- - X   X - -
- - -   - X -

[inherited]

Zitat:

Zitat von fLaSh11

P.S.: Gratulation zum 1.111 Beitrag :mrgreen:
:party: :party: :party: :party: :party:

Hab ich garnicht drauf geachtet :duck:

[fLaSh11]

neue Version: V0.4.0

Neuerungen u.a. wie einmal gefordert Setztipps ;). Genaueres siehe 1. Beitrag.

Die Animationen kommen noch. Falls jemand diesbezüglich noch einen Tipp hat, her damit! :zwinker:

[fLaSh11]

Achtung, mir ist grad ein Bug aufgefallen:

Nicht auf Tipp klicken, wenn das Spielfeld voll ist, sonst hängt sich das Spiel auf, weil das Programm vergebens nach einem freien Platz sucht...

[passsy]

ich hab noch keine möglichkeit gefunden den KI zu besiegen kannst du ma den trick verraten?

gibt es überhaup eine möglichkeit zu gewinnen?

ich sehe sie nicht

[fLaSh11]

Zitat:

Zitat von passsy

gibt es überhaup eine möglichkeit zu gewinnen?

nein, es dürfe nicht mehr möglich sein, die KI zu besiegen (mit Ausnahme vom diesem Post hier, ich weiß nicht, was der Fehler ist, oder ob ich das mit anderen Bugfixes schon behoben habe... das hier)

Zitat:

Zitat von passsy

ich hab noch keine möglichkeit gefunden den KI zu besiegen kannst du ma den trick verraten?

Du musst für jede Situatuion die passende Aktion bereithalten ;)

[hibbert]

Zitat:

Zitat von fLaSh11

Zitat:

Zitat von passsy

gibt es überhaup eine möglichkeit zu gewinnen?

nein, es dürfe nicht mehr möglich sein, die KI zu besiegen

Ich habe mir das Ding mal vor ein paar min runtergeladen und habe die KI schon besiegt...

[passsy]

ich bin glaub echt zu dummm sagst du wenigstens wie?

[fLaSh11]

hibbert, wie setzt du? Diesen Fehler habe ich in Version 0.2.3 gefixt, ist warscheinlich durch die Codeoptimierung wieder aufgetreten...

[hibbert]

Zitat:

Zitat von passsy

ich bin glaub echt zu dummm sagst du wenigstens wie?

Ich habe begonnen.
Zug1: Mitte
Zug2: Oben rechts
Zug3: Oben links
Zug4: dreimal dürft ihr raten ;)

[fLaSh11]

In der nächsten Version gefixt. In der Tat habe ich bei der Codeoptimierung die hälfte einer Bedingung vergessen :stupid:

[ArmyMan]

Zitat:

Zitat von fLaSh11

nein, es dürfe nicht mehr möglich sein, die KI zu besiegen...

Da gibt es noch viele Arten zu gewinnen. Also nicht nur eine.
Falls bedarf besteht, kann ich auch screens posten..

Greetz

[Blink]

Hi

Ich dachte schon man kann deine KI wirklich nicht besiegen, aber dann wie es der Zufall will hab ich sie doch besiegt :bounce2:

Hier meine Züge

Ich beginne und setzte
1. oben rechts
2. unten mitte
3. unten rechts
4. unten links

das klappt so oft man will ich hab es 4 mal versucht und immer gewonnen

Achso mir ist noch was aufgefallen du schreibst das Sounds da sei aber ich konnte nichts hören, außer das von den Dialog Boxen.

[Rociel]

Zitat:

Zitat von Blink

Ich beginne und setzte
1. oben rechts
2. unten mitte
3. unten rechts
4. unten links

funktioniert nicht immer, ist in die ki n random eingebaut?

[Larsi]

habs auch grad geschafft gegen den ki zu gewinnen 8) :D :) hab leider mein desktop neulich wieder aufgereumt und hab den screenshot jetzt nicht mehr :( :)

[Crazy Ivan]

ich weiß nicht ob das schon bekannt ist, aber wenn ich ein spiel abgeschlossen habe und dann nicht neu starte, bleibt ja das feld gefüllt. wenn man dann "tipp" klickt stürzt die anwendung ab

[Strahlex]

Der Schwierigkeitsgrad macht sich nicht bemerkbar...

Eine stufenlose Schwierigkeitsgradeinstellung wäre nicht schlecht

[Spiderpig_GER_15]

ich bin gerade dabei ebenfalls ein drei gewinnt spiel mti ki zu programmieren,
könntest du vielleicht den quelltext mal posten?
würde mich interessieren wie du das gelöst hast,
hast du jeden zug vorprogrammiert, oder regeln aufgestellt?

hab gerade meine ersten 19.000 zeichen quelltext geschrieben, und ein ende ist immernoch
nicht in sicht...
mach ich was falsch oder hast du auch einen zig meter langen quelltext?

:gruebel:

Spiderpig

[Macci]

Hey,

interessantes Spiel. Ich habe inzwischen auch schon so einige Spiele mit KI programmiert (z.B. 4-Gewinnt, Mühle) und auch schon mal so ein TicTacToe Spiel. Die KI spielt hier mit Perfect Play, d.h. es ist unmöglich zu gewinnen, und - sowie man dem Computer die Chance gibt - wird er gewinnen. Sowie feststeht, dass der Computer gewinnen wird, kündigt er das auch gleich "großspurig" an ;-)
Damit das Proggy so klein ist, habe ich übrigens KOL anstatt der VCL benutzt.
Viel Spaß damit :-D


http://img153.imageshack.us/img153/4...pboard1rb6.jpg

Viele Grüsse,
Macci

[Macci]

Zitat:

Zitat von Spiderpig_GER_15

...
hab gerade meine ersten 19.000 zeichen quelltext geschrieben, und ein ende ist immernoch
nicht in sicht...
mach ich was falsch oder hast du auch einen zig meter langen quelltext?

:gruebel:

Spiderpig

Hallo Spiderpig ,

Schau mal hier: http://de.wikipedia.org/wiki/Alpha-Beta-Suche
Außerdem brauchst dann noch eine Bewertungfunktion, der du eine Spielsituation mitteilst, und die dir dann den Wert dieser Situation als Zahl ausspuckt.

[Spiderpig_GER_15]

Ich habe mir das jetzt zwar durchglesen, aber ich verstehe leider bis auf den Sinn dahinter garnichts.

Vielleicht kann mir das ja jemand erklären :mrgreen:
und wie man das in die praxis umsetzten kann ist mir erst recht ein rätsel :gruebel:

Spiderpig

PS: Vielleicht kann jemadn seinen quelltext posten, würde (mir) wahrscheinlich helfen...

[Macci]

Hi,

also es ist doch sogar ein Codebeispiel dabei (die beiden Funktionen Min und Max). Die kannst du im Grunde 1:1 übernehmen. Wenn du deine KI dann noch optimieren willst, solltest du noch eine Zugsortierung miteinbauen, am besten mit einem schnellen Sortieralgo. wie z.B. Mergesort (einmal kurz googlen und du findest auch hier Quelltext), und außerdem einen Test auf symmetrische Spielsituationen.

Damit wäre der 1. Teil deiner KI bereits geschafft. Als zweites brauchst du dann eine Bewertungsfunktion. Während der Alpha-Beta Algoritmus (der dazu da ist, die Spielsitationen zu durchforsten) immer praktisch der gleiche ist, ist die Bewertungsfunktion für jedes Spiel völlig verschieden (für Mühle z.B. ganz anders als für Schach).

Weil TicTacToe ein so überschaubares Beispiel ist, kann die Bewerungsfunktion da ganz einfach aussehen: Es genügt zu gucken, ob man gewonnen oder verloren hat. Für kompliziertere Spiele wie Mühle reicht das natürlich nicht (außer du hast Zeit für jeden Zug ein paar Wochen zu warten ;-)).

Hier mal in Pseudo-Code eine Bewertungsfunktion für TicTacToe. Damit es mit dem Code bei Wikipedia konsistent ist, habe ich das jetzt ebenfalls im C-Stil geschrieben.

Code:

bool Gewonnen(int spieler, int[9] felder) {
    return (drei_Steine_senkrecht(spieler) || drei_Steine_waagrecht(spieler) || drei_Steine_diagonal(spieler));
}

int Bewerten(int spieler, int[9] felder) {
    if (gewonnen(spieler, felder))
        return 1;
    if (gewonnen(gegner(spieler), felder))
        return -1;
    return 0; //unentschieden oder unbeendet
}

wobei noch zu sagen wäre, dass spieler angibt, für wen bewertet werden soll (0= Menschl. Spieler, 1=Computer) und jedes der 9 Felder entweder den Wert -1 (unbelegt), 0 (durch Spieler belegt) oder 1 (durch Computer belegt) hat.
Solang du kein Funktion wie "Tipp geben" oder "Computerzug" realisieren willst, ist spieler immer gleich 1 (es sei denn du benutzt den NegaMax-Algo. oder Abwandlungen davon).

Wenn du dann im Computerzug

Code:

Max(9, -unendlich, +unendlich);

aufrufst, wird der gesammte Spielbaum bis zum Schluss ausgewertet.
Gemeint ist hier die Max-Funktion der von mir vorher verlinkten Wikipedia-Seite und statt unendlich kannst einfach sehr große Zahlen einsetzen (hier würden sogar schon die Zahlen -1 und 1 reichen).

Viele Grüsse,
Macci