0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS@SE. Most of SE is about answerable questions. Reading you have a working implementation you have concerns about, give the community you posted the question to a chance to answer (say, 49 hours) and have a look at CodeReview@SE (where opinions are allowed). $\endgroup$ – greybeard Nov 20 '19 at 6:35
1
$\begingroup$

Without more details, I think it is important to precise that Pandemic is 2-4 players cooperative game. Players are allowed to discuss about strategy and share any information (even if the rules are ambigous on the possibility to share card in hand information). Moreover to achieve victory efficiently, players have to trade cards which is hard without coordination.

Type of AI

So first of all, you have to be clear on what you expect for your AI:

  • Global AI: The AI play for all players and then have no need to predict another player turn. This is the simplest to implement.
  • Independant equivalent AI : this is nearly the same but with a different paradigm. Every player is managed by a different bot. But they can predict perfectly any other turn.
  • Independant AI : this is probably your objective as it let a human player participate. But there is a need to predict what it would do or to simulate communication.

Evaluation function

Now let's talk about the algorithm begining by the evaluation function. As you said, you have to compute the game state resulting of any action you may do. Then to evaluate it to give a score to every action sequence and chose the best.

Computing the full new state may be indeed very time/space consuming. You may probably work with "delta" to the initial state. you have to be able to run you evaluation function on this "delta" state to get a "delta" score.

A tip to treat the 4-action sequence is to first determine all accessible position and their cost in action/card. Then decide what is the best to do with the remaining actions.

Having a good evaluation function is the most important of any game AI. It needs experience and abstraction of the game to model which state changes are likely to lead to victory or defeat. Unfortunatly, Pandemic is a very hard and complex game and you might need experience on simpler games to design a proper evaluation function.

Prediction algorithm

As you said, if you limit the computation to your 4 next actions, there is no sense to use MCTS. But to have better prediction, you can compute the state resulting of the next players and the random issues.

Generally the depth of the analysis depends on the time you accept to spend to it. Then, optimizing your state computation (with "delta" for instance) let you go far deeper in analysis.

An important feature is to "prune" any unefficient branch as soon as possible. This is typically what you mean with "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". In fact you have to express this feature in term of state score.

Knowing well Pandemic game, I would expect that a decent AI has to predict at least the next turn of every other player. As you can expect, it is no worth to spend a full turn of 4 actions to do the thing that the next player will do in 1 action.

My advice

Start simple, build a 2 players global AI and assume random card draws are totally predictable. Improve your capacity to do "delta" on state, your MCTS and overall your evaluation function.

Sequence management

The idea is to first compute all positions in range (a BFS is perfect for this). The "range cost" is expressed in "card(C)/action(A)". A "1C2A" range is actually worse than a "0C2A" range but you may consider 2 ranges if you have for instance "1C1A" and "0C2A".

Thus you have to build a 4-actions sequence, so you have to consider all positions you can go to in 4 actions. On these positions, you will either: - end you turn (if you used the 4 actions for instance) - do an useful action (cure, trade, build)

In the first case, you won't move again as it would be equivalent to another direct move of your initial position list. But if you do an action, you may have a subsequent move(/action) needing a 2nd depth level in your exploration tree but with a lower range.

Let's take a simple example. You are at position "O" in this graph:

"B1" <= "A1" <= "O" => "A2" => "B2" => "C2" => "D2"

There are possible actions only on O (cure), A1 (2 cures), B2 (trade) and C2 (build).

So your first level tree is [(pos, remaining actions)]:

(O, 4), (A1, 3), (A2, 3), (B1, 2), (B2, 2), (C2, 1), (D2, 0)

if you stay at O, you will at least do an action which is cure before moving again. And you may build the subtree

(O, 3), (A1, 2), (A2, 2), (B1, 1), (B2, 1), (C2, 0)

if you go to A2, you won't move again because there is no action to do here and any accessible position is already considered in tree. So you may directly compute the delta score of this state with the delta position of your marker.

If you go to A1, you will do either 1 cure, with a remaining subtree (A1, 2), (B1, 1), (O, 1), (A2, 0), either 2 cures with a remaining subtree (A1, 1), (B1, 0), (O, 0)

and so on... Also note that there is no point to use charter (use the card of the origin point to anyway) to go on a position where you can perform no action. It will limit the tree size.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your awesome answer. I expect to implement a Global AI. I did implement such AI for games that are easier to solve (chess, tic-tact-toe), but never for a game with such a heavy State and high number of moves. Finding all the next possible moves in chess is easy and quick. In Pandemic, as a player "move" is actually a sequence of 4 actions, this is tricky. According to your suggestion, I will implement an action score and after computing all the 4-actions sequence, I can keep only the one with a positive score (that should be considered as potential next game state by the MCTS). $\endgroup$ – AllirionX Nov 21 '19 at 23:00
  • $\begingroup$ This does not solve the pruning problem though... I am trying to simply the problem from one rule: all sequence of 4 action should be: X Move Action - Y Static Action - Z Move Action... This allows to split the problem in two: finding all the possible sequences of move actions (this is easy to prune), finding all the possible sequences of static action (this is easy to prune). But i still can't deal with cases such as : moving to city A - Heal - Moving to City B- Heal and moving to city B - Heal - Moving to City A- Heal, which have the same outputs... $\endgroup$ – AllirionX Nov 21 '19 at 23:00
  • $\begingroup$ Yes that is what my tip was for, to prevent computing strictly equivalent sequence. In fact I applied this method successfully on several game bots, it is inspired from Held-Karp algorithm. I will update my answer with a new paragraph on it. $\endgroup$ – Optidad Nov 22 '19 at 9:25
  • $\begingroup$ Thank you very much for this detailed paragraph. It looks more efficient than what I had (mostly because the algorithm focus on going to places where actions can be performed). However, I don't see how this does prevent to consider two equivalent sequences of actions: I guess you could simply check for each tree node if an equivalent tree node was already explored, or is there something I am missing? You can consider the O<=>A, O<=>B, A<=>B graph, with only one cure action possible on A and on B. $\endgroup$ – AllirionX Nov 25 '19 at 3:15
  • $\begingroup$ Ok you may have a look to Held-Karp algorithm. This is a DP method to treat for instance TSP. The application on your AI is that 2 sequences are equivalent if the same actions (not move) have been conducted and if they have the same final position. Thus you keep only the cheapest of the 2 sequences. Note that in your example (move A, cure A, move B, cure B) and (move B, cure B, move A, cure A) are not equivalent as the final position is different. $\endgroup$ – Optidad Nov 25 '19 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.