Representing and Reducing Uncertainty for Enumerating the Belief Space to Improve Endgame Play in Skat

摘要

In most fully observable board games, current AIs outperform expert play. For partially observable trick-taking card games, however, human experts still play consistently better. This paper proposes efficient knowledge representation and reasoning algorithms for the internationally played three-player card game Skat by representing, progressing, enumerating, evaluating and voting for the possible worlds, each player refers to as his/her knowledge about the other players' and the Skat cards. By using expert rules, elicited from statistical information in millions of games, this knowledge is accumulated in the first few tricks in order to reduce the uncertainty in the players' belief. In the so-called endgame, after five to six rounds of trick play, refined exploration algorithms suggest cards that lead to improved play. The proposed AIs have been tested both in reconsidering recorded human games, and in interactive play.