Recall the post last month about my computer version of the board game Carcassonne? During the last couple of weeks I added several new features not available in the board game, including the AI opponent that was my original motivation for the project. Both the implementation of this opponent, as well as its resulting “personality,” have proved to be rather interesting; it plays much differently than I do, and at times seems to make critical errors… but I am already just 2-2 against it, so it must be doing something right.
You can download the game at the usual location. It is compiled for Windows, but it should work on any platform supported by FreeGLUT/OpenGL. Let me know if you have any problems (or success) getting it to work on another platform.
Note that for copyright reasons discussed in last month’s post, I called the game Aude, after the department in France where the city of Carcassonne is located. I also created my own tile artwork, which was pretty simple to do in Mathematica, although I admit I like the original tiles better. I cannot distribute the original tiles myself, but if you want to use them, they are available online from the American publisher, and it is a relatively simple matter to turn them into the 128×128 pixel 24-color uncompressed bitmaps required by the game. (You can even add expansion tiles pretty easily, too. Let me know if there is interest in doing this.)
This project was a lot of fun, and the result has been fun as well. Even without the AI opponent, there are several aspects of the 3D board interface that I think make the game more interesting. One is the “projected score” display, indicating not just the points for completed features as in the board game, but also the total points including farms and incomplete features. My wife and I have found that this information influences mid- to end-game strategy, reducing the perceived element of chance in the game.
Another feature that I added but generally do not use (it is turned off by default) is a display of the distribution of individual tile types remaining in the deck. This is interesting information, but it feels a little too much like “counting cards” to me.
Finally, you can undo a move at any time. This also must be used with some discretion, but after a few frustrating missteps with the laptop touchpad in the middle of a good game, being able to undo a mistakenly placed tile is pretty handy.
The move undoing was obviously critical to the tree search used by the AI opponent. Carcassonne is an interesting game from an artificial intelligence perspective, for a couple of reasons. First, it is complex; that is, its branching factor, or typical number of moves available to a player at any time, is pretty large, reaching well over 100 or even 200 as a game progresses, compared with 30-35 for chess. Also, it involves the chance element of drawing tiles from a shuffled deck. This doubly complicates matters, because not only does it effectively multiply the branching factor by about 24, but it also makes standard tree pruning techniques like alpha-beta cutoffs more challenging.
There is certainly much experimentation still to be done. The board evaluation function has a lot of room for improvement, even if just to tweak the weights applied to the components that are already computed. But first I plan to just enjoy playing the game a bit, to see how well or poorly it really plays.