Cathleen Heyden hace su tesis sobre Carcassonne de Klaus-Jürgen Wrede.
En la Universidad de Maastricht: IMPLEMENTING A COMPUTER PLAYER FOR CARCASSONNE.
Thesis submitted in partial fulfillment of the requirements for the degree of Master of Science of Artificial Intelligence at the Department of Knowledge Engineering of the Maastricht University.
Cathleen Heyden
Maastricht University
Faculty of Humanities and Sciences
Department of Knowledge Engineering
Master Artificial Intelligence
Abstract:
Classic board games are an important subject in the field of Artificial Intelligence (AI) and a lot of research is done there. Nowadays modern board games get more and more interest from researchers. Most of the games support to play with more than two players. In addition they are often non deterministic, which means that they contain an element of chance, and/or have imperfect information.
This thesis describes the analysis of the game of Carcassonne and the implementation of the game engine and an AI player using different algorithms. Carcassonne is a modern board game for 2 to 5 players with perfect information, which means, that the entire state of the game is fully observable to each of the players. It is a non-deterministic game because during the game the players draw tiles randomly. These chance events are not uniformly distributed because several tiles have different frequencies. This thesis regards only the 2-player variant of Carcassonne.
This work includes a calculation of the state-space complexity and the game-tree complexity. After that two search algorithms are investigated. The first algorithm is Monte-Carlo search and an improved version of it – MonteCarlo Tree Search with Upper Confidence bounds applied to Trees. The second algorithm is Expectimax search, which is based on Minimax search. Additionally the improved algorithms Star1, Star2 and Star2.5 will be investigated.
The results show that Star2.5 search with a probing factor of 5 performs best. This player is able to win against advanced human players.
¡Nos jugamos!