spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Man kann sowas auch googlen.

State of the Art beim Skat scheint Monte Carlo zu sein. Das heißt, einen Solver für das offene Spiel zu schreiben (da kannst logischerweise MiniMax nehmen, es geht vor allem darum dass es schnell ist. So gesehen kein ganz triviales Vergnügen wenn man noch optimieren will) und dann in jedem Zug einige mögliche Decks zu generieren, diese mit dem Solver zu analysieren und dann den Zug zu nehmen, der im Mittel über alle Decks am Besten ist.

Das Problem ist dass die Wahrscheinlichkeiten in Wirklichkeit nicht unabhängig sind. D.h. nicht jedes Deck was, nachdem einige Züge gespielt sind, noch möglich ist, ist auch noch gleich wahrscheinlich. Das heißt man muss die gesamte Historie des Spiels mit berücksichtigen, es geht nicht nur darum den aktuellen Zustand des Spiels ("Position") zu bewerten, egal, wie es dazu gekommen ist. Und daran scheitern die mir bekannten Standardansätze für Spiel KIs. Nicht so sehr an der Unsicherheit. Backgammon z.B. hat relativ hohe Unsicherheit, ist aber praktisch "gelöst".

Nur damit du mal ein gefühl für "ungefähr" bekommst:

Es gibt 32! Sortierungen für das Skatblatt (Größenordnung 2^118)

Da beim Verteilen mehrere dieser Sortierungen zum gleichen Blatt führen (Reihenfolge ist egal) sind es wenn ich mich nicht ganz irre in Wirklichkeit

(32 choose 2)*(30 choose 10)*(20 choose 10) verschiedene Spiele. Erklärung: Skat, Vorhand, Mittelhand in der Reichenfolge gezogen, Hinterhand ist dann eindeutig. Da es nicht egal ist wer aufspielt sind die Spiele echt verschieden. (Größenordnung 2^51) Wie ich oben schon sagte kommt es sehr stark drauf an, wie lange dein Solver braucht um ein Spiel zu berechnen. Je nachdem ist es nicht ganz unmöglich die Spiele alle zu berechnen (DES hatte 56-bit Schlüssel, nur zur Orientierung). Der Ansatz ist aber nicht besonders pragmatisch weil er dir nur die perfeke Zugfolge für jedes Spiel liefert, aber...

... eine KI die gegen Menschen spielt muss ja "dynamisch" auf die Fehler des Spielers reagieren können. Mal nur als Beispiel KI als Alleinspieler gegen zwei Menschen, worst-case, jeder Zug der Menschen ist unerwartet und erfordert eine vollständige Neuberechnung:

Ich komme da, wenn ich mich nicht vertue auf:

(22 choose 2) * (20 choose 10) + [vor dem Spiel]
[danach Skat bekannt aber Neuberechnung in jedem Zug:]
sum k=0 to 9 ((20-2k) choose (10-k))

Insgesamt in der Größenordnung von 2^25 (etwa 42 Mio). Sagen wir mal du strebst eine Zeit von etwa 10 Minuten pro Spiel an. Dann kommst du in der Sekunde auf etwa 71500 Spiele die du durchrechnen musst. Und um auf die richtigen a posteriori Wahrscheinlichkeiten zu kommen, musst du mindestens jedes dieser Spiele von Anfang an berechnen, wenn nicht schlimmeres. Find ich sportlich.

Naja das sind jetzt Untergrenzen, wenn ich die Kombinatorik nicht irgendwo verhauen habe. Reizen ist z.B. noch gar nicht drin. Und wie nun schon mehrmal angeklungen, die intellektuelle Herausforderung ist die richtige Berechnung der a posteriori Wahrscheinlichkeiten. Aber das hast du ja geflissentlich ignoriert.

Zitat von »ProAmateur«

Hmm, ja ok also ich hab eben mal fünf Spielrunden Simuliert und mir aufgeschrieben, wie viele verschiedene Möglichkeiten die viel Spieler jeweils haben,
und bin dann letztenendes auf diese Werte für die gesamten Möglichkeiten gekommen:
1. 10^12
2. 10^10
3. 10^12
4. 10^11
5. 10^10

also ich glaube, dass sind wirklich zu viele Möglichkeiten, oder?

Darum geht es nicht. Das sind ja die Möglichkeiten in einem Spiel (wenn sie denn stimmen). Das Problem ist, du weißt nicht welches Spiel du spielst, da dir einige Karten nicht bekannt sind.

Der Trick bei MiniMax ist ja eigentlich dass man mit alpha-beta Pruning nicht den ganzen Spielbaum durchsuchen muss, sondern nur einen Teil.

Implementier doch mal einen Solver für offene Skatspiele. Das löst zwar nicht das eigentliche Spiel, aber könnte dir helfen das einzuschätzen. Oder geht es hier nur um Hirnwichserei?