Ich würde gern verstehen, wie Skatfox oder ähnliche Analysesoftware den besten Zug in einer gegebenen Spielsituation findet.
Solche Software behandelt Skat spieltheoretisch als Spiel mit vollständiger Information, d.h. alle Spieler spielen während der Analyse mit offenen Karten; psychologische Spielchen sind ausgeschlossen.
In der Fachsprache sagt man statt "den besten Zug finden" auch "das Spiel lösen".
Also wie löst man nun ein gegebenes Spiel?
Mein naiver Ansatz lautet: alles ausprobieren (vgl. Minimax-Algorithmus).
Schnell sieht man, dass das zu einer kombinatorischen Explosion führt, d.h. die Anzahl der möglichen Spielverläufe kann in die Milliarden gehen und ist praktisch nicht durch Ausprobieren zu lösen.
Nächste Idee: Alpha-Beta-Suche. Das heißt salopp gesagt, man probiert nur soweit aus, bis man feststellt, dass die aktuell untersuchte Variante die bisher beste Lösung sicher nicht übertreffen kann.
Weitere Optimierung: gewisse Züge kann man schon ausschließen, z.B. wenn der Spieler alle 3 Luschen einer Farbe hat , muss ich nicht alle durchprobieren, sondern das Ergebnis ist für alle gleich.
Hypothese: Hat der Spieler am Zug eine fortlaufende Sequenz von Karten einer Farbe (z.B. ), so muss man nur die höchst- und niedrigstwertige Karte untersuchen.
(Bei Nullspielen reicht es sogar eine beliebige Karte zu wählen, das sollte klar sein.)
Außerdem kann man programmatisch leicht erkennen, ob der Alleinspieler alle restlichen Stiche macht bzw. keinen Stich mehr machen kann.
Nun meine Fragen:
- Gibt es vielleicht einen noch besseren Algorithmus?
- Wie kann man die obige Hypothese beweisen? Ich habe es im Gefühl, dass sie richtig sein muss, aber ich kann das nicht zweifelsfrei begründen.
- Welche Optimierungsmöglichkeiten habe ich vergessen? (Mal von Caching und Parallelisierung abgesehen)
- Wie kann man anhand einer gegebenen Kartenverteilung die Anzahl der möglichen Spielverläufe berechnen?
Als kleines Hobbyprojekt möchte ich eine kostenloses freies (Open Source) webbasiertes Skat-Analysetool schreiben, und hoffe, dass ihr mir hier weiterhelfen könnt, weil mein erster Prototyp viel zu langsam ist. Besten Dank