3-gewinnt mit KI

[fLaSh11]

Hallo DPler,

ich weiß, dass 3-gewinnt ein sehr simples Spiel ist ; aber mir gings um die KI! Ich habe mich an einer versucht und eine recht akzeptable hinbekommen, wie ich denke.

Features:
- Spieler gg. Spieler
- Spieler gg. KI
- Im "Zeichendesign"

Version 0.2.1-KI - 28.3.07
Version 0.2.2-KI - 28.3.07
Version 0.2.3-KI - 28.3.07
Version 0.2.4-KI - 29.3.07
Version 0.2.5-KI - 29.3.07
Version 0.3.0 - 30.3.07
Version 0.3.1 - 30.3.07
Version 0.4.0 - 1.4.07

Verbesserungen:
V0.2.2:
- Fehler bei neuem Spielbeginn behoben (von Martin K: Hier)
- teilweise: Fehler des Falschsetzens bei Gewinn (von alleinherrscher Hier und noch von anderen...)
V0.2.3:
- Weiterer Spielbeginnfehler gefixt
- Nichtgewinnbug endlich vollständig gefixt
V0.2.4
- Beginnfehler gefixt (von Florian Bernd: Hier)
- Es dürfte nicht mehr möglich sein, gegen die KI zu gewinnen. (Außer meine Funktionen kommen sich gegenseitig in die Quere^^...)
V0.2.5
- Jetzt sollte man definitiv nicht mehr gewinnen können!
V0.3.0
- Einstellungsdialog
- KI-Stärke auswählbar
- neues Design
V0.3.1
- Matzes Fehler von hier korrigiert
V0.4.0
- Codeoptimierung (einmal komplett drüber gegangen , darum können neue/alte Fehler auftreten...)
- lautere Sounds
- kleine Fehler behoben
- KI verbessert (zwickmühlenbedingt)
- AboutBox
- Man kann sich Tipps geben lassen

Bekannte Bugs:
- diese eine letzte ominöse^^ Möglichkeit die KI auszutricksen (von Florian hier)
- Aufhängen bei Klick auf Tipp nach Spielende (in V0.4.1 gefixt)

Todo:
- Animationen beim Setzen
- siehe "Bekannte Bugs"

Ich hoffe es gefällt euch ...

Feedback/Fehler bitte posten!

MfG
Steffen

P.S.: Ist meine erste KI.

[Macci]

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?



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
und wie man das in die praxis umsetzten kann ist mir erst recht ein rätsel

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