3-gewinnt mit KI

[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