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.

I’ve been thinking a lot recently about an algorithm to compute the maximum score possible for a given game variant considering the number of players. For instance, I would love to be able to give the computer algorithm an input of 4 players on a basic game plus Inns & Cathedrals and Traders & Builders, and it respond back with a maximum score by a player in this game (e.g. say, 350 points). Since you seemed to have specifically done some work in this area, I was wondering if you could help me.

This is an interesting question. If I understand you correctly, you want to compute the maximum score that a single player could achieve, assuming that “everything goes his way,” so to speak, with an advantageous ordering of drawn tiles, no other players playing any meeples, etc.? (This is sort of like asking what is the maximum possible one-day winnings in Jeopardy!, by answering every clue correctly, with optimally placed “true” Daily Doubles, etc.; in that case, it’s not difficult to show that a player could win $566,400.)

Even with these not-so-realistic assumptions, I think the problem for Carcassonne might be difficult. Just using the basic game without the river, we can add up all of the possible feature points, assuming that our player is able to score and complete all cloisters, cities, and roads– I get 234 points for these. This is already questionable, since it assumes, for example, that none of the completed roads “loop back” on themselves, and I’m not sure if this is possible.

The even more difficult problem is the maximum score for farms, which I have given less thought. If we assume that we can finish the game by placing meeples on farms (wrapping up our completion of cloisters/cities/roads in the process), then the question is how to position the tiles so that we can place as many meeples as possible on *separate* farms, thus duplicating scores for as many completed cities as possible. (I am assuming the latest 3rd generation rules here.)

As I continued researching this, I came across this link, which I found to be enormously helpful:

http://boardgames.stackexchange.com/questions/7375/maximum-attainable-points-for-a-single-player-in-a-two-player-game-of-carcassonn