Piotr Beling

Ph.D. thesis, prepared under the supervision of Prof. Goldstein at the University of Łódź and defended at the Łódź University of Technology in 2006.

The main goal of the thesis is to analyse and improve on a certain group of decision making algorithms for games with imperfect information. In such games, some information has been hidden away from one or more players, like the cards of their opponents during a game of bridge. This makes choosing the best move nontrivial, even in theory.

The decision making algorithms which we take under scrutiny, are based on the idea of the Perfect Information Monte Carlo, which is one of the best-known and widely used methods for dealing with imperfect information games, especially card games. In order to choose the best move possible to make in a given position, the method “imagines” a number of hypothetical, full pictures of this position. Each of these pictures are constructed by setting unseen information (like placement of hidden cards) at random, but with taking player’s previous observations under consideration, as some facts about the current situation can be deduced from past decisions of other competitors. In each of these imagined scenarios, the result of taking each action (playing each card) is computed under the assumption that all participants have perfect information, that is, as if everybody put their cards on the table face up. In the end, the move that was the best on average is chosen.

The strength of the algorithm tends to increase with the numbers of scenarios which are considered, but there is a trade-off between speed and predictive power. The more situations we consider, the more perfect information games we have to solve. Since time for decision is typically limited, we often need to compromise. However, if we speed up calculating the solution to perfect information games, we can consider more of them before the time for a decision runs out. That is why solving perfect information games as efficiently as possible is so crucial in our work. The Perfect Information Monte Carlo has been successfully applied to many card-games, like bridge, skat or hearts, and also to board game of scrabble. It was first proposed in 1989 by David Levy in the article “The million pound bridge program” and successfully implemented by Matthew Ginsberg in his bridge program GIB. His implementation used partition search, the innovative method which enabled him to solve double-dummy bridge problem (perfect-information game which is related to bridge) fast enough.

For both types of games (with and without perfect information), we have developed several new algorithms. In order to confirm high effectiveness of these methods in practice, we have created a computer program which uses them to solve problems in the popular card game of bridge. Our program, which we have called Bridge Calculator, is freely available on the Internet and is a practical (and quite popular) tool for fans of the game.

In the thesis, we give a formal proof of the correctness of the partition search algorithm and a formal definition of a partition system for the double dummy bridge. Our thorough analysis led to the improvement of the algorithm, which we call local partition search. We confirmed the high effectiveness of the presented methods in practice. The tests showed that using the local partition search leads to significant reduction of the search tree size. In the case of bridge, this allows us to cut the calculation time almost in half. We also put forward other techniques which improve the effectiveness of a double-dummy bridge solver. One of them is novel, fast and accurate algorithm for counting sure tricks.

We also put forward two new decision-making algorithms for games without perfect information: the highest number of winning pairs and the largest set of winning pairs. In addition, we formalised the concept of a guaranteed payoff in a set of positions (both new algorithms use it) and the concept of finding the largest collection of winnings position (it is used only by the latter algorithm). We also outlined how to take advantage of the latter concept when possible outcomes are not limited to win and loss. Moreover, we formalised the method of analysis of the potential past course of the game. This analysis assigns probabilities to possible sequences of moves that can lead to the current situation, by taking the players decisions into consideration. It was proposed to utilise ancillary perfect information games to help with the evaluation of these probabilities. The effectiveness of the proposed techniques was confirmed experimentally.

Szybkie algorytmy decyzyjne w grach z doskonałą informacją i ich wykorzystanie w grach jej pozbawionych [Effective decision making algorithms for games with perfect information and their applications in games without it]