Archive for March, 2011

Artificial intelligence player for Carcassonne board game – ideas & thoughts

 

OK, I love playing board games. And among my favorites I’ve a warm place for Carcassonne. This simple tile-placing game is very tactical, offering different course of actions for the player to decide in each turn. I can’t help thinking, how good can I make an artificial intelligence player in the Carcassonne game. This post will cover some ideas and thoughts I’d like to share on this subject. I only refer to the basic Carcassonne game without any expansions for simplicity.

General setup and game play

The game rules for reference.

The basic question is what type of artificial intelligence to use? for example, some board games like chess are more suitable for the minmax mechanism, but this game has a dimension of uncertainly (drawing cards), so it won’t fit here. However, like in the minmax mechanism, I believe there should be a mechanism to read the board and calculate a score for each player, but it will not try to predict the other players moves, but it will stick to the maximum score possible in the current turn. Leaving the prediction of the future moves to be somehow integrated to the score of the current turn.

For this approach the AI should know to read the board and calculate a score for each player based on the situation on the board, considering the followers placed by each player and the number of remaining followers in the reserve. We will discuss further about guidelines for how to calculate this score. Once the AI can read the board then for each turn, we would have those following steps for the AI player:

  1. Once the new tile was drawn, calculate the different legal places for this tile. I think there shouldn’t be more than 20 legal place in each turn.
  2. For each legal place calculate the all the possibilities for placing a follower. It usually goes between 1-3 possibilities. Of course that not placing a follower is also a possibility.
  3. For each legal place and for each follower placing possibility, calculate the score for all the players, including of course the self AI player, according to the situation on the board.
  4. For each move (tile placing + follower placing) calculate  the delta(difference) from current board situation score for all the players. Compare all the scores delta – The important delta is the delta of the AI player but need to take into consideration also other players delta since sometime a decrease in other player’s score is more significant than the AI player gain.

The first 2 steps are merely technical and their aim is to calculate all the possible moves the AI player can perform. since there are not too many of those (averaging a few dozens I suppose) there should not be any performance problems to do it.

The heart of it all is calculate the score in step 3. In that score there should be all the logic that makes the AI an intelligent player. Ok, so how to calculate this score? The simple answer is that I’m not sure… There are many considerations that should be taken and it is quite complicated and require massive testing to reach exact formulas. I do want however, to share a few ideas for guidelines that would affect this score in different situations in the game.

Score basics

So what affects the score? Followers on the board will increase the score dependent on which feature they placed on. They will contribute to the score proportionally to how much their feature worth points in the game. Also, if you are the only one with a follower on the feature the feature is more valuable then if some other players has followers in the same feature.

completion bonus

Now, when completing a feature the follower returns to the supply, plus some features (cities) worth more when completed than in the end of the game so it is top priority to see the follower’s feature being completed. To ensure that, the more close to completion the feature is the higher the value it should get – completion bonus. Thus a city 3 tiles with a single open edge, worth more then a 3 tiles city with 3 open edges. Also, a farm will never get this completion bonus since it is being completed only in the end of the game.

Also, There are many situations in the game where a feature is being stuck. That means that very few types of tiles (or none at all) exist in the game that could be used in order to complete it. For those cases as well there should be a low or no completion bonus. Note, that since the system is calculating the score for all the players, placing a tile that will cause your opponent feature to be impossible to complete, will affect its completion bonus and thus make its score decrease.

Another point is to be sure to consider how many turns the player have until the end of the game. If you add your city a tile that makes it with 3 open edges instead of 1, you’d better not do it when there are only 2 turns left for the AI player to play. Therefore, the completion bonus should be reduced the more the game approached its end (less turns the AI player have got left).

Managing the number of followers

After playing your first few Carcassonne games, you clearly come to the conclusion that you must manage carefully the number of followers you place in the game since they tend to be run out of stock quite soon in the game. This knowledge should be reflected when calculating the score. The more followers the AI possess in its stock after the turn the more valuable it is. And it shouldn’t be linear, since the difference between 6 or 7 followers in hand in not like zero or 1 followers. The AI should play its last follower only when the gain is significant. Also there should be consideration to how many turns the AI has left to play. Of course that if you have n followers with only n turns to play you should place a follower in each turn.

Different tactics with different number of players in the game

When I played Carcassonne, I usually apply different tactics whether I’m played a 2-player game or 4-5 player game. In 2-player game if you complete a feature where both players have deployed the same number of followers – both players get points for it, so practically it is like no one got points at all. While in multi-player game the same situation where 2 players have the same number of followers will grant those players the same points, but since the rest of the players didn’t receive points, those point are valuable.

Moreover, since the tile amount is constant, the more players there are the less turns each player play. Thus, completing a feature alone in 5-player game is much harder than in 2-player, especially if it is a big one. Joining forces with another player may prove more valuable since there is more chance that the feature will be completed and in less time.

So clearly the score if affected. I think the more players there are in the game the less important is to have a feature where the AI player has the only follower. And vice-versa, if there are only 2 players, sharing a feature with the opponent should be least valuable and maybe give no score at all.

Tactics – joining a feature of another player

One of the great things about Carcassonne is the interaction between players. You may try to join an opponent who had built a big city and share the points when it is completed, or maybe a farm with many cities – even better! The rules of Carcassonne prohibit joining a feature that has already a follower placed on it. The way to do it is to create a similar new feature very close to the subject feature but not directly connected to it,  and place your follower on it. On the next turns in order to join the feature it is necessary to place the tiles in a way that both features will be connected and then would have more then one follower on it. This requires planning and is not always successful even for the intelligent human player since not always the appropriate tiles are drawn and there is always the opponent that is not always glad to share the feature.

 

Example for the steps taken to join a farm by 2 players

So how can our AI player implement it? It requires planning of at least 2 steps ahead and sometimes more.

The score! We would have to integrate this logic to the score.

It seems that for each open feature with a follower on it (let us call it the subject open feature), the system will scan the neighboring area for incomplete feature of the same type. Each neighboring incomplete feature will add value to the score of the subject open feature. The added score value will be proportional to the value of the incomplete feature and with inverse ratio to the tile distance from the subject open feature. Thus  with this bonus the AI could favor moves that are not contribute in the short run but could bring a lot of profit in the long run.

Remarks –

  • Sometimes a neighboring incomplete feature would have more opponent followers (of the same player) than the subject open feature. In that case if the features would be joined the player will lose points to the opponent. This also has to be reflected to the score by some sort of a penalty.
  • Farms are always incomplete features.
  • Joining farms will not necessarily add more points as when joining cities or roads, since some cities can be shared by more then one field and the joined farm will not have more cities as shown in the example above. In fact sometimes joining farms can even reduce the score. Therefore, when calculating the value of a neighboring farm it basically should be how many cities it adds to the subject farm that the subject farm doesn’t already have.

Summery

I enjoyed sharing my basic belief about how AI player should be implemented, and I would be happy to get feedback. Whether you have some more ideas or would like to share from your personal experience. Please feel welcome to comment.

Leave a comment