Ideen zur Schach KI

[dizzy]

Zitat von Cicaro:

Ganz nebenbei glaub ich bei MiniMax ein gewisses Bepunktungssystem gesehen zu haben. Ich hab' nämlich mal eine Source in die Finger bekommen, die aber nich' kompilierbar ist, da dort Units wie 'Diag*.dcu' nicht vorhanden sind.

Weiß da noch jemand was dazu ('ne komplette Source vielleicht) ?

Einen Source nicht, aber die Theorie:

Minimax liegt ein sog. Spielbaum zu Grunde, der folgendermaßen aufgebaut ist:
Wurzel ist das Schachbrett im Ausgangszustand. Davon ab gehen n Unterknoten, in denen jeweils ein möglicher Zug des nächsten Spielers (weiss hier) abgebildet wird. Von dieses aus gehen jeweils Kinder ab die alle Zugmöglichkeiten vom Gegenspieler (schwarz hier) darstellen, usw...
Ganz am Ende in den Blättern gibt es dann 3 Möglichkeiten die es zu erkennen gilt: Matt(weiss), Matt(schwarz), Remis. Nun vergibt man an diese Blätter eine Wertung, z.B. 1 für Matt(weiss), 0 für Remis und -1 für Matt(schwarz). Diese Wertung muss nun rekursiv bis in die Wurzel hochgezogen werden, und bildet die Grundlage der KI. Ziel von schwarz ist es ein Matt(weiss) zu erreichen - folglich spielt er immer zum Teilbaum mit der höchsten Bewertung hin, da es dort wahrscheinlicher ist zu gewinnen. Er ist somit hier der Maximierer, und weiss der Minimierer (da er auf -1 = Matt(schwarz) spielt).
Möchte man seiner KI jetzt auch noch beibringen möglichst schnell einen Sieg zu verbuchen, so empfiehlt sich eine Portion A*: Man zählt also den Baum hinab in welchem Teilbaum man den kürzesten Weg bis zu einer positiven trivialen Situation hat (Sieg), und entscheidet sich für diesen. (Das wäre aber nur nen Bonbon )

Man braucht für obiges System aber alle möglichen Spielstände! Was fällt einem auf? Genau: Das werden allein schon nach nur 2-3 Spielerwechseln irre viele Knoten! Einen kompletten Schachbaum aufzubauen sollte heutzutage nicht in vernünftiger Zeit schaffbar sein.

Lösung 1) Teilbäume aus der aktuellen Stellung mit vorgegebener Tiefe berechnen. So wird es imho auch gemacht. Das Problem hierbei: In den Blättern sind eher selten echte Endsituationen zu finden. Also kommt man nun an die Stelle die den ganzen Thread lang schon diskutiert wurde (und nur einen Teilaspekt einer KI darstellt ) - man muss ein unfertiges Spiel bewerten und das also Grundlage für eine Zahl von -1 bis 1 hernehmen mit der entschieden wird. (Diese Stelle ist vital für die Intelligenz der KI.)
Da kann ich allerdings kein geeignetes Verfahren anbieten, und würde ähnlich vorgehen wie es hier ja schon passiert. (Ideen sammeln + Try&Error)

Lösung 2) Das sog. Alpha-Beta-Pruning. Dies ist eine Verbesserung des Minimax-Algos (hinsichtlich der Laufzeit), da man auf Grund günstiger Konstellationen von vorne herein ganze Teilbäume einfach weglassen kann; also erst garnicht aufstellen muss. Das Verfahren ist jedoch nicht ganz so einfach nachvollziehbar (für Details sei auf Onkel Googel / WiKiPedia / etc. verwiesen) und es wäre wohl auch nicht ausreichend um einen kompletten Spielbaum aufzubauen, da es trotzdem noch zu viele Knoten würden.
Somit böte sich das also eher an um Lösung 1 zu verschnellern bzw. zu verbessern, da man ggf. tiefere Bäume aufbauen kann als ohne A-B-Pruning.


Der goldene Weg wäre also ein partieller Spielbaum mit A-B-Pruning aufgebaut für eine KI die einfach nur gewinnen will, und ohne A-B-Pruning aber mit einer Priese A* für eine KI die schnell gewinnen soll (heisst nach mögl. wenigen Zügen, das Programm ist sicherlich langsamer ). Warum nicht A-B-Pruning und A* zusammen? Weil durch das Wegschneiden der Teilbäume ohnehin schon auch schnellere Wege gekillt würden, so dass auch A* nur mittelmäßige Wege finden könnte. A-B-Pruning ist NICHT auf schnellen Sieg ausgelegt, nur auf "überhaupt gewinnen" .


Versteift euch nicht zu sehr auf die reine Bewertungsfunktion unfertiger Bretter. Die ist zwar sehr wichtig, aber auch nur ein Teilaspekt. Und sie muss schließlich zum eigentlichen Wegfindungsalgo passen .



Schönen Gruß,
Fabian