Monte Carlo Tree Search for simultaneous multiplayer game

Question

I am developing AI for bomberman and i want to implement monte carlo tree search. I read that MTCS can be applied for simultanous multiplayer game. Problem i have is that i dont know how to implement it. For instance, how to store all possible moves in one game state or how to apply UTC selection. Should i call utc selection for all players and final state to select will be combination of their moves? Has anybody any literature to read or article? Thanks

Answer 1

the Monte Carlo Tree Search (MCTS) is applicable but not very good in this case, as the opponents actors are not "random" but will choose the best move they can.

However, if you choose to use MCTS you have to

1. copy the current game state for simulation...

2. loop through all possible moves m in that state

   A. For N times do...

   • Setup simulation-copy to "saved state"
   • do the move in the simulation-copy.
   • Finish the game by simulating random moves (Monte Carlo Simulation)*
   • At the end of each simulation, evaluate the result in numbers (seen from the view of the current player, e.g. "lost" = -1, "draw" = 0, "won" = 1).
   • Add result to "sum"

   B. Store "Average Result" (= "sum" divided by "N") for move m

3. Select move with highest average result and execute it

As the moves in your simulation are "random" it will possibly take a very long time till one of the player actually looses (by not bombing itself). So you should limit how long a simulation runs at maximum.

You should also use a more complex result evaluation not only based on final results (win/loss, but in case of "draw" you should e.g. subtract the number of bombs that will soon explode nearby).

You'll of course need to copy/simulate the whole game state (for all players). Just choose random moves at each time step for each player and simulate them.

BUT, it's better if you use an algorithm like "minimax". MCTS can be combined with "minimax", if your game contains randomness (as for example random behaviour for items gathered). Have a look at http://en.wikipedia.org/wiki/Minimax for a good reference...

In that case your search algorithm must be implemented recursively (see http://en.wikipedia.org/wiki/Recursion). For bomberman you'll need to adapt minimax a bit, if there will be more than 2 players.

To quickly give the key idea of minimax, let us look at the following example search tree from the above wikipedia article.

Above we have the current game state as a node. It's connected to the possible following states (timesteps are "downwards"), left and right. At each following state you follow the new possible moves until you reach the maximum depth (here: 4) or until the game ends. Then you evaluate the state. In the minimax/negamax algorithm each player does its move in its own time step (knowing the other players move of the previous time steps). A player always chooses the path, that guarantees the -best- result for her/him. This result is recursively returned by the search function. In 2-person games an "evaluation function" is often like "Player A wins" = positive number, "Neither Player wins (draw)" = 0, "Player B wins" = negative number. So player A tries to maximize the result of the evaluation of the game and player B tries to minimize it. We always evaluate the game at the leave nodes (here: depth = 4). Between the depth levels (0 to 4) there are the moves of one player each:

• depth level 0 to 1: Player A
• depth level 1 to 2: Player B
• depth level 2 to 3: Player A
• depth level 3 to 4: Player B

Assume, we are at the leave node (the one in the bottom-left) and have evaluated the game state ("10" at depth level 4). We return the game state evaluation (10) for move variation "left"... then we recursively go into depth for "right", which returns "+Infinite". As this is player B's turn (depth level 3 to 4) he tries to minimize the evaluation. So he would choose "left", as "10" is better because the move "right" would be "+Infinite" (player A wins). So for this node "10" is the result, which is returned, when leaving the recursion. Now we are at depth level 2 and got "10" returned for move "left" - we would recursively call our function for "right", which returns "5". Depth level 2 is Player A's turn... he/she tries to maximize the value and would choose "left" (10). This way we continue until we have an evaluation of the start position. When having recursively evaluated all moves at depth level 0, we will decide for one (here: player A's turn... so he/she would take "right" (-7)) of them an store it as the search result.

This needs to be adapted to bomberman: Evaluation must be done/stored for each player separately. And you'll need to search all combinations of all players moves in one time step. The evaluation of a move "m" for player "p" is calculated by the calculating the minimum of the evaluations (evaluated for player "p") of all move combinations containing move "m" for Player "p". The new evaluation of the state for player "p" is then the maximum of the evaluations for those moves. In other words: When in game state "n" player "p" plays move "m" and the other players play their moves, player "p" will achieve at least a score x (= minimum calculation for own view). A player in state "n" always chooses the move "m" that maximizes its own evaluation. This way you will get "backwards" in time to the current game state and know for all players their best move.

Even thought simple minimax produces optimal results, it's also -very- slow if your search depth becomes high. You should therefore use alpha-beta pruning (http://en.wikipedia.org/wiki/Alpha-beta_pruning), which causes -roughly- that "bad" move combinations get less and "good" move combinations get more computation time. The speedup with alpha-beta-pruning is about factor 100. But you should more invest in a good evaluation function and not search too deep through all possible moves.

Hope that helps... Don't bother to ask, if you need more help!

Stefan