No description available.

No description available.

For zero-sum games, we have efficient solution techniques. Unfortunately, there are interesting games that are too large to solve. Here, a popular approach is to solve an abstract game that models the original game. We assume that more accurate the abstract games result in stronger strategies. There is substantial evidence to support this assumption. We begin by formalizing abstraction and refinement, a notion of expressive power for abstractions. We then show the assumption fails to hold under two criteria. The first is exploitability, which measures performance in the worst-case. The second is called the domination value, which measures how many mistakes a strategy makes. Despite these pathologies, we notice that larger strategies tend to make fewer mistakes and perform better in tournaments. Finally, we introduce strategy grafting, a technique that uses sub-game decomposition, which allow us to create good strategies in much larger spaces than previously possible.

This thesis formalizes a model of bounded rationality in extensive-form games called game-playing schemata. In this model, the strategies are repre- sented by a structure consisting of a deterministic finite automaton and two computational functions. The automaton represents a structured memory of the player, while the functions represent the ability of the player to identify efficient abstractions of the game. Together, the schema is a realization of a pure strategy which can be implemented by a player in order to play a given game. The thesis shows how to construct correctly playing schema for every pure strategy in any multi-player extensive-form game with perfect recall and how to evaluate its complexity. It proves that equilibria in schemata strategies always exist and computing them is PPAD-hard. Moreover, for a class of efficiently representable strategies, computing MAXPAY-EFCE can be done in polynomial time. 1

Efficient algorithms exist for finding optimal strategies in extensive-form games. However human scale problems, such as poker, are typically so large that computation of these strategies remain infeasible with current technology. State space abstraction techniques allow us to derive a smaller abstract game, in which an optimal strategy can be computed and then used in the real game. This thesis introduces state of the art abstraction techniques. Most of these techniques do not deal with public information. We present a new automatic public state space abstraction technique. We examine the quality of this technique in the domain of poker. Our experimental results show that the new technique brings significant performance improvement. Powered by TCPDF (www.tcpdf.org)