Catálogo de publicaciones - libros

Temporal difference (TD) learning has been used to learn strong evaluation functions in a variety of two-player games. TD-gammon illustrated how the combination of game tree search and learning methods can achieve grand-master level play in backgammon. In this work, we develop a player for the game of hearts, a 4-player game, based on stochastic linear regression and TD learning. Using a small set of basic game features we exhaustively combined features into a more expressive representation of the game state. We report initial results on learning with various combinations of features and training under self-play and against search-based players. Our simple learner was able to beat one of the best search-based hearts programs.

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.

A one-player, finite, probabilistic game with perfect information can be presented as a bipartite graph. For one-player Can’t Stop, the graph is cyclic and the challenge is to determine the game-theoretical values of the positions in the cycles. In this contribution we prove the existence and uniqueness of the solution to one-player Can’t Stop, and give an efficient approximation algorithm to solve it by incorporating Newton’s method with retrograde analysis. We give results of applying this method to small versions of one-player Can’t Stop.

Various efficient game problem solvers are based on PN-Search. Especially depth-first versions of PN-Search like DF-PN or PDS – contrary to other known techniques – are able to solve really hard problems. However, the performance of DF-PN and PDS decreases drastically when the search space significantly exceeds the available memory. A straightforward enhancement trick to overcome this problem is presented. Experiments on Atari Go and Lines of Action show great practical value of the proposed enhancement.

The questions focusing on diminishing returns for additional search effort have been a burning issue in computer chess. Despite a lot of research in this field, there are still some open questions, e.g., what happens at search depths beyond 12 plies, and what is the effect of the program’s knowledge on diminishing returns? The paper presents an experiment that attempts to answer these questions. The results (a) confirm that diminishing returns in chess exist, and more importantly (b) show that the amount of knowledge a program has influences when diminishing returns will start to manifest themselves.

We give upper and lower bounds on S _3[ n ] equal to the number of three-player partizan cold games born by day n . In particular, we give an upper bound of $O(S_2[n]^3)$ and a lower bound of Ω ( S _2[ n ]) where S _2[ n ] is the number of surreal numbers born by day n .

We analyze a new popular video-game called Lumines , which was developed by Sony for the PSP platform. It involves a sequence of bichromatic 2×2 blocks that fall in a grid and must be shifted or rotated by the player before they land. Patterns of monochromatic 2×2 blocks in the terrain are regularly deleted. The primary goal is to contain the terrain within a fixed height and, if possible, clear the grid. We deal with questions such as: (1) Can the game be played indefinitely? and (2) Can all terrains be eliminated? We examine how answers to these questions depend on the size of the grid and the rate at which blocks are deleted.

We show that a proper equilibrium of a matrix game can be found in polynomial time by solving a linear (in the number of pure strategies of the two players) number of linear programs of roughly the same dimensions as the standard linear programs describing the Nash equilibria of the game.

Combinatorial games of the form {{A|B}|{C|D}} can be classified as either left excitable, right excitable, or equitable [2]. Several approximate strategies for playing sums of games of this form have been proposed in the literature [2,3,4]. In this work we propose a new approach for evaluating the different strategies based on the types of the subgames participating in a sum game. While previous comparisons [3,4] were only able to rank the strategies according to their average performance in a large number of randomly generated games, our evaluation is able to pinpoint the strengths and weaknesses of each strategy. We show that none of the strategies can be considered the best in an absolute sense. Therefore we recommend the development of type-based approximate strategies with enhanced performance.

Rush Hour is a sliding blocks game where blocks represent cars stuck in a traffic jam on a 6 ×6 board. The goal of the game is to allow one of the cars (the target car) to exit this traffic jam by moving the other cars out of its way. In this paper, we study the problem of finding difficult initial configurations for this game. An initial configuration is difficult if the number of car moves necessary to exit the target car is high. To solve the problem, we model the game in propositional logic and we apply symbolic model-checking techniques to study the huge graph of configurations that underlies the game. On the positive side, we show that this huge graph (containing 3.6 ·10^10 vertices) can be completely analyzed using symbolic model-checking techniques with reasonable computing resources. We have classified every possible initial configuration of the game according to the length of its shortest solution. On the negative side, we prove a general theorem that shows some limits of symbolic model-checking methods for board games. The result explains why some natural modeling of board games leads to the explosion of the size of symbolic data-structures.