Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
A Skat Player Based on Monte-Carlo Simulation
verfasst von : Sebastian Kupferschmid, Malte Helmert
Erschienen in: Computers and Games
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We apply Monte-Carlo simulation and alpha-beta search to the card game of
Skat
, which is similar to Bridge, but sufficiently different to require some new algorithmic ideas besides the techniques developed for Bridge. Our Skat-playing program, called DDS (Double Dummy Solver), integrates well-known techniques such as
move ordering
with two new search enhancements.
Quasi-symmetry reduction
generalizes symmetry reductions, disseminated by Ginsberg’s Partition Search algorithm, to search states which are “almost equivalent”.
Adversarial heuristics
generalize ideas from single-agent search algorithms like
$\textrm{A}^*$
to two-player games, leading to guaranteed lower and upper bounds for the score of a game position. Combining these techniques with state-of-the-art tree-search algorithms, our program determines the game-theoretical value of a typical Skat hand (with perfect information) in 10 milliseconds.