Diploma thesis

Valid XHTML 1.0 Strict CSS ist valide!

Crafted with jEdit


The UCT Algorithm Applied to Games with Imperfect Information


The UCT algorithm was already used to search the best strategy in games with perfect information. The algorithm is known to handle games with high branching factors in the search tree very well. For the game of Go a computer player was implemented that uses the UCT algorithm and was able to cope with the best computer Go players. For games with imperfect information, this algorithm is now used for the first time. For the card game of Skat an implementation of the UCT algorithm is available that uses the algorithm in all three phases of the Skat game. These phases are bidding, discarding and playing the tricks. To be able to use the algorithm all unknown information must be replaced by simulated information. After that, the UCT algorithm can be used as in a game with perfect information. All results of the simulations are saved in one search tree with information sets.

The playing strength of the UCT player is tested against other computer players and against human players. For this purpose a tournament simulation program for Skat was developed. With this simulation program it is possible to let AI players compete against other AI players in games with predefined card distributions. Every player is given then the same chances to make all games. In games against human players a normal Skat series is simulated.

The UCT player can keep up with other computer players. Although it might not have reached its highest playing strength. The best combination of parameters is still to be found. The number of simulations the player can compute in a reasonable time for each move decision is also too low. The presented implementation is not optimized for speed, yet. Higher numbers of simulations will result in a higher playing strength. The UCT player can also keep up with human players. It looses the Skat series only due to conservative bidding.


The UCT Algorithm Applied to Games with Imperfect Information (PDF, 714 KB)