C Alpha-Beta-Suche an Dame umsetzten?

[SourceCoder]

Schönen guten Abend Zusammen,

also ich habe ein Dame Spiel programmiert das Spiel möchte ich durch eine KI erweitern und dabei die Alpha-Beta-Suche verwenden. Nur ich weiß nicht wie ich vorgehen muss wie genau die Alpha-Beta-Suche in meinem Spiel einbauen muss usw.

Vielleicht irgendwelche Tipps?

 

[omaliesschen]

Dame programmieren? Wird so ein anstößiger Sexbot?

 

[AP Nova]

Du könntest überprüfen, ob die KI nach ihrem Zug einen gegnerischen Stein geschlagen hat oder gefährdet ist, selbst einen zu verlieren. Dann wird natürlich versucht, wenn möglich einen gegnerischen zu schlagen (was wieder damit abgewägt werden muss, ob man danach einen verlieren kann, am besten nimmt man natürlich die Variante, in der man nur schlägt, aber nicht unmittelbar verliert), wenn nicht zumindest keinen zu verlieren.

Sprich einen Gegner zu schlagen hätte zum Beispiel den Wert 1, sich nur zu bewegen den Wert 0 und nach einem Zug einen Stein zu verlieren den Wert -1. Wenn man will, könnte man "schlagen und geschlagen werden" auch mit 1 versehen und das reine Schlagen dann mit 2 oder so, da müsstest du selbst überlegen, was sich am ehesten anbietet.

Stellt man sich damit geschickt an, hat man zwar noch keine meisterhafte KI, aber auch keine, die wirklich gar nichts auf die Reihe kriegt.

 

[AlexandeKappner]

@op:
Die A-B-Heuristik schneidet dir 'schlechte' Zuege im game tree weg. Folglich brauchst du zuerst einmal einen game tree (logisch) und einen Algorithmus, der beurteilt, wie gut oder schlecht eine Position ist.
Hast du schon einen Algorithmus, der dir den 'game tree' ausrechnet, also von einer bestimmten Position ausgehend die moeglichen Zuege aufzaehlt? Und hast du eine Metrik, die die einzelnen Positionen bewerten kann? Dann muesste deine KI ja schon grundsaetzlich funktionieren, wenn auch langsam. In dem Fall ist die A-B-Heuristik fast trivial einfach zu implementieren... einfach checken, ob der gerade analysierte Zug schlechter ist als ein bereits analysierter, und falls ja nicht mehr weiter in die Tiefe gehen. Wenn du das nicht hast, musst damit anfangen und nicht mit der Suche.

@oma
So gelacht hab ich auch schon selten nicht mehr, ein echter Brueller-Wortwitz... -.-

MfG

 

[Dese]

entweder ich hab dich nicht ganz richtig verstanden, oder da ist was falsch:

man sollte nicht erst den kompletten spielgraphen aufbauen und dann mit a-b bei traviersierung teile wegschneiden. während man aufbaut kann man dank a-b-heuristik entscheiden, ob man einen bestimmten unterbaum überhaupt noch durchsuchen muss und damit überhaupt noch generieren muss.

 

[omaliesschen]

@oma
So gelacht hab ich auch schon selten nicht mehr, ein echter Brueller-Wortwitz... -.-

ich weiß, etwas flach.. aber es gibt Leute die damit Geld verdienen.

 

[AP Nova]

@Dese: Natürlich ist der Sinn dieser Suche gerade, nicht immer alle Möglichkeiten, wie sich die KI und der Spieler verhalten könnte, durchzurechnen, da man so auch viel Unnötiges berechnen muss, das von Anfang an sinnlos ist. Aber trotzdem hat AlexandeKappner damit recht, dass man erst einmal die Möglichkeit braucht, den Spielbaum (schrittweise) zu erstellen und zu bewerten. Damit geht man dann die einzelnen Optionen durch und wählt letztendlich die, die am höchsten bewertet wird. Hier könnt man natürlich noch überlegen, mit einer Tiefe von nur einem, zwei, drei... Zügen zu rechnen, zwischendrin die zu der Zeit ganz unlukrativen Züge zu verwerfen oder Ähnliches, um das noch ein bisschen intelligenter zu gestalten.

 

[Dese]

na dann hab ich ihn offenbar falschverstanden.

 

[Scheppat]

Wenn Englisch für dich kein Problem ist, dann kann ich dir das Chess Programming WIKI empfehlen.

Dort geht es zwar hauptsächlich um Schach, aber gerade die Artikel über die Suche kann man sehr gut verallgemeinern. Ich selbst habe z. B. vor längerer Zeit ein 4-Gewinnt Programm geschrieben und arbeite gerade (wenn ich die Zeit dazu finde) an einem Pentago-Programm.

Insbesondere die folgenden Artikel dürften für dich interessant sein:

1. Minimax
2. Negamax (Ist ein bißchen Geschmackssache. Es geht auch ohne, aber die folgenden Beispiele bauen darauf auf.)
3. Alpha-Beta
4. Transposition Table
5. Iterative Deepening

Oft wird dort auch auf die Seite Programming Topics von Bruce Moreland verwiesen. Die hat mir sehr gut geholfen, auch weil dort viele Code-Beispiele gezeigt werden.