At a glance, board games may seem to have no connection to artificial intelligence (AI). However, board games are quite useful when studying AI. When an AI is advanced enough to beat the best player in the world at a game like Chess or Go, it’s a huge scientific achievement.
One strategy for writing an AI is called the Monte-Carlo Tree Search (or MCTS). It is based on the Monte-Carlo math technique, named after a famous casino. Monte Carlo involves running many simulations of an event to predict a range of possible results. Using MCTS, the AI chooses a random move to begin. From there, it plays against itself thousands of times before making a move, tallying which move led to more winning games. This helps it pick better moves more often. Although the computer is not aware of what it is doing, this is an example of machine learning.
MCTS is an algorithm that works well for games with two players. It has normally been used in games where both players have “perfect information.” Chess is a perfect information game since both players can see the entire board. Poker is not a perfect information game since all players have secret cards.
Most modern board games don’t have perfect information, and many have random elements. This paper looks at the modern board game Settlers of Catan. This is a turn-based game where players gain and trade resource cards to build settlements, cities, and roads. The winner is the first player to reach 10 points, which are mostly gained through building settlements and cities.
To play Catan, you must have more than two players. Players can keep track of the cards other players have, but there are also hidden development cards, so it is not a perfect information game. On top of that, there are elements of randomness, so your actions will not always result in the same outcome. This limited information makes it challenging to create an AI for Catan.
Even so, the authors were able to use the MCTS algorithm in their AI, named SmartSettlers. They did this on a modified version of Catan, with simpler rules than the official game. All cards were made public, instead of some players having hidden development cards. Also, SmartSettlers was not allowed to trade with the other players. These changes made it easier to create an AI player while keeping the game mostly the same.
Although Catan has many rules, some parts are simple. One possible move in Catan is to build a settlement, which gives the player 1 point and increases their resource production, making it almost always a good move. Due to this, the authors programmed the AI to be 10,000 times more likely to build a settlement than other moves, when that move was possible. The authors made similar changes for other moves. The AI adjusted the chance for each type of move as it “learned,” but having a baseline chance to work from made the computer player much better.
The paper tested the skill of the AI by having it play against other Catan computer players. SmartSettlers won 49% out of all 3-player games, meaning that it was much better than the other computer players.
SmartSettlers was also tested against humans, notably Istvan Sita — one of the authors of the paper, and a skilled Catan player. During these games, SmartSettlers’ moves were usually the same moves a human would play. However, skilled human players could consistently beat the AI.
In comparison to humans, it is weak, but the authors plan to implement a better version later. MCTS is a strategy that is not widely used on games like Catan, and this paper was able to use it to create a decent AI player.
