Representations of and strategies for static information, noncooperative games with imperfect information.

摘要

In this thesis, we will examine a card game called MYST, a variant of the Parker Brothers' classic board game Clue. In MYST, a set of cards is divided uniformly among a set of players, and the remaining cards form a hidden pile. The goal of each player is to be the first to determine the contents of the hidden pile. On their turn, a player asks a question about the holdings of the other players, and, through a process of elimination, a player can determine the contents of the hidden pile.; MYST is one of few static information games, wherein the position does not change during the course of the game. To do well, players need to reason about their opponents' holdings over the course of multiple turns, and therefore a sound representation of knowledge is required. MYST is an interesting game for AI because it ties elements of knowledge representation to game theory and game strategy.; After informally introducing the essential elements of the game, we will offer a formal specification of the game in terms of first-order logic and the situation calculus developed by Levesque et al. Strategies will be discussed including: existence of a winning strategy, randomized strategies, and bluffing. Implementation of some strategies will be discussed.