I hope I am asking this on the right community.
I am building an Artificial Intelligence to play the board game Pandemic. The AI uses a Monte Carlo algorithm. After implementing the game rules and the AI, it works as expected (very poorly, but it works).
I figured the main problem the current algorithm has is the action dispersion. In Pandemic, each player is allowed up to 4 actions. The number of possible actions is usually between 10 and 100. The current algorithm run 1000 Monte Carlo simulations to chose to the best next action, perform the action and start again. This results in a lot of useless simulation as, if the AI play the action A, it will consider playing the action !A.
I think it would be much more efficient to compute all the valuable series a 4 actions, as there are usually less than 50 efficient/valuable series of 4 actions to play. But my current implementation is way to slow and memory inefficient.
Here is a recap of the rules (simplified):
- there are 48 cities on the board, each city having between 3 to 5 neighbours. The graph is always the same.
- part of the disease spreading mechanism is between 0 and 3 cubes on each city
- a player has between 0 and 7 city card in his hand
- a player moves between cities
The possible actions are:
- MOVE: the player moves from the city he is in to a neighbour city
- HEAL: the player removes one cube from the city he is in
- CHARTER FLIGHT: if the player has the card of the city he is in, he can discard it to move to any other city
- DIRECT FLIGHT: the player can discard any card from its hand to move to the card's city
- SHARE KNOWLEDGE: the player can give or take the card of the city he is in to/from another player in the same city
- BUILD: the player can discard the card of the city he is in to build a Research Center
- MOVE BETWEEN RESEARCH CENTER: if there is a research center in the city the player is in, he can move to any other research center
Implementation The implementation need to run very fast and require low memory, in order for the Monte Carlo simulation to run smoothly. It should only keep the series of 4 actions that have different and valuable results:
- if two series of 4 actions have the same effect except that one requires to discard a card, then the second series must be ignored
- if a series of 4 actions has an effect strictly inferior to the effect of another series, then the first series must be ignored.
I am looking for help regarding the strategy to use to determine all the valuable series of 4 actions, and any algorithm/implementation idea that could improve on my current work.
What I tried so far
The direct approach Given an action perform all next possible actions on a duplicated game state, store the resulting game states and only keep the series of 4 actions that have different output. Unfortunately, this requires to clone the game state too many times. Plus, it is not optimised: if the first two actions have the same output, there is no need to explore both branches.
The direct approach optimised For each action, evaluate the state of the board. Only keep the action that have different outputs. Do it again for each output. This is slightly better, but the game state duplication is still a problem.
The loop between all possible actions approach Pre-build the list of all possible series of 4 actions, independently of the board state. Loop through the list and remove series of 4 actions that are not playable. It was too slow, as without game state constraint there are around 1 billion possible series of 4 actions.
The cancel approach Similar to the direct approach, but instead of duplicating the game state before performing an action, we perform the action explore the branch, and then cancel it to try another branch. It was a bit better than the other approach, but it's impossible to cut useless branches before reaching the end.
The delta approach Each action is associated with a Delta object. When performing two actions the Delta of the 2 actions are added. Only series of 4 actions with different Delta are kept. This solves the game state duplication issue, but is slower to run as in order to make sure that before exploring a branch we need to make sure that after applying the delta of the previous actions to the game state, the branch's action is playable.
The goal approach Not yet implemented. It would determine each positive action available on the board (HEAL, BUILD, SHARE KNOWLEDGE) and try to build a series of 4 actions doing those.