I'm working on a simple turn-based strategy game. The game has two types of units (soldiers and transportation units) and two types of buildings (to create new units and to gather resources). The game is played on a hexagonal grid with a maximum of about 100 tiles and can be played with 2, 3 or 4 players. The object of the game is the destroy the other players. Some of the players can be controlled by AI. Now my question is: What would be a good approach to implement an AI for this type of game? A common approach seems to be the use of rule-based systems. But I would prefer are more generic/computational approach. The number of possible moves per turn is quit large so min/max, alpha/beta etc is probably not the way to go. I read something about Monte-Carlo Tree Search (MCTS) but I'm not sure if this algoritm is a good match for my problem. What do other turn-based strategy games use besides rule-based systems?

I don't think it has been used before for strategy games, but I agree that MCTS seems like a good candidate for your situation.

However, MCTS has been very successful in go because playing randomly from a position and looking at the fraction of random games you win seems to be a decent evaluation function for go. It's unclear to me if this will be true of your game. Biasing the randomness so good moves are played more often than bad moves in the random games makes MCTS go programs much stronger, and you may need to work hard on that to get your program to do something sensible.

Another problem I can see is that it would be hard to deal with less than full information. I mean, if you can only see cells that are near one of your units/buildings or you don't know what resources your opponents have, you can't accurately simulate the game going forward. You would probably need some bayesian methods to deal with this, but it won't be easy.

In the game each player has complete information about the current world (including position and number of (enemy) units/buildings, and number of (enemy) resources). There is however a small random factor in the outcome of battles.

One quick vote for influence maps. It sounds like you are going to need them. It doesn't solve all your problems, but it will likely be a component.

Quote: Original post by crocomire
In the game each player has complete information about the current world (including position and number of (enemy) units/buildings, and number of (enemy) resources). There is however a small random factor in the outcome of battles.

Randomness is not a problem for MCTS. Since this is so easy to program, I would give it a try and see what happens. Write a simple Monte Carlo program first, without any tree search. If that looks promising, try to implement UCT. Then bias the move selection so you consider common moves more often than unusual ones.