Minimax for Bomberman

Question

I am developing clone of Bomberman game and I am experimenting with different types of AI. First I used searching through state space with A* and now i want to try different approach with Minimax algorithm. My problem is that every minimax article i found assumed players alternates. But in Bomberman, every player make some action at the same time. I think i could generate all possible states for one game tick, but with four players and 5 basic actions (4 moves and bomb place) it gives 5^4 states at first level of the game tree. That value will raise exponentially with every next level. Am I missing something? Are there any ways to implement it or should i use totally different algorithm? Thanks for any suggestions

Answer 1

Real-Time Strategy games like bomber man have a difficult time with AI. You want it to be intelligent, but at the same time it cannot be perfect.

If the AI is perfect, your players will get frustrated. Either because they always lose or you get .3 frames per second.

If it is not intelligent enough, your players will get bored.

My recommendation is to have two AI functions, one that determines where the AI goes, the other that determines when is best to drop a bomb. You can use things like movement prediction to determine if an enemy is moving towards a spot that will be dangerous if a bomb is dropped in the current location.

Depending on difficulty you can modify these functions to improve or decrease difficulty.

Answer 2

As you have noticed, Bomberman is much too complex to be simulated as a turn-based game. Extrapolating any possible own decision plus every possible decision of every other player just doesn't work out.

Instead of that you should rather use a more strategical approach.

You should ask yourself: How does a human player make decisions while playing bomberman? Usually, a player should follows four basic priorities:

1. avoid explosion areas of bombs
2. place bombs so others can't avoid their explosion areas
3. collect powerups
4. place bombs to blow up rocks

The first priority can be fulfilled by creating a "danger map". When a bomb is placed, all tiles covered by it should be marked as "dangerous". The sooner the bomb explodes (keep chain reactions in mind!), the higher the danger level. Whenever the AI notices that it is on a field with a high danger, it should move away. When it plots a path (for whatever reason) fields with a high danger level should be avoided (can be implemented by artificially adding a higher path cost to them).

The danger map calculation can be further enhanced to protect the AI from stupid decisions (like entering areas which are hard to escape from when another player is near).

This should already create a reasonable defensive AI. So what about offense?

When the AI realizes that it is reasonably safe right now, it should plan offensive maneuvers: It should consider how it can increase the danger map around the other players by placing bombs itself. When choosing a location to plant a bomb, it should prefer close locations so it doesn't have to move so far. It should also disregard bomb locations when the resulting danger map doesn't allow for a reasonable escape route.

Answer 3

I think i could generate all possible states for one game tick, but with four players and 5 basic actions (4 moves and bomb place) it gives 5^4 states at first level of the game tree.

Correct! You need to search all 5^4 (or even 6^4, as you can walk in 4 directions, stop and "put a bomb"?) actions for each game tick. BUT, when a player already decided to move, it takes some time till the move is executed (e.g. 10 game ticks). During this period the number of possibilities reduces.

That value will raise exponentially with every next level. Am I missing something? Are there any ways to implement it or should i use totally different algorithm?

You can use a Hash-Table to only calculate the same game state "subtree" once. Imagine player A walks up and down, while all other players "wait", you end up in the same game state. It's the same as for "left-right" or "right-left". Also moving "up-then-left" and "left-then-up" results in the same state. Using a Hash-Table you can "reuse" the calculated score for a game state that has already been evaluated. This reduces the growth speed quite a lot. Mathematically, it reduces the base of your exponential growth function. To get an idea of how much it reduces the complexity let us look at the moves possible for only one player compared to reachable positions on the map (=different game states) if the player may just move up/down/left/right/stop.

depth 1: 5 moves, 5 different states, 5 additional states for this recursion

depth 2: 25 moves, 13 different states, 8 additional states for this recursion

depth 3: 6125 moves, 25 different states, 12 additional states for this recursion

To visualize that, answer yourself: which fields on the map can be reached with one move, two moves, three moves. The answer is: All fields with a maximum distance = 1, 2 or 3 from start position.

When using a HashTable you only have to evaluate each reachable game state (in our example 25 at depth 3) once. Whereas without a HashTable you need to evaluate them multiple times, which would mean 6125 evaluations instead of 25 at depth level 3. The best: Once you calculated a HashTable entry you can re-use it in later time steps...

You can also use incremental deepening and alpha-beta pruning "cut" subtrees that are not worth searching in more depth. For chess this reduces the number of searched nodes to about 1%. A short introduction to alpha-beta pruning can be found as a video here: http://www.teachingtree.co/cs/watch?concept_name=Alpha-beta+Pruning

A good start for further studies is http://chessprogramming.wikispaces.com/Search . The page is related to chess, but the search and optimization algorithms are quite the same.

Another (but complex) AI algorithm - that would be more suitable to the game - is "Temporal Difference Learning".

Regards

Stefan

PS: If you reduce the number of possible game states (e.g. very small size of the map, only one bomb per player, nothing else), there is a chance to pre-calculate an evaluation for all game states.

--edit--

You could also use offline-calculated results of the minimax calculations to train a neuronal network. Or you could use them to evaluate/compare hand-implemented strategies. For example you could implement some of the suggested "personalities" and some heuristics that detect, in which situations which strategy is good. Therefore you should "classify" situations (e.g. game states). This could also be handled by a neuronal network: Train a neuronal network to predict which of the hand-coded strategies is playing the best in the current situation and execute it. This should produce extremely good real-time decisions for a real game. Much better than a low-depth-limit search that can be achieved otherwise, since it doesn't matter that much how long the offline-calculations take (they are before the game).

-- edit #2 --

If you only recalculate your best moves every 1 second, you could also try to do more higher level planing. What do I mean by that? You know how many moves you can do in 1 second. So you can make a list of reachable positions (e.g. if this would be 3 moves in 1 second, you would have 25 reachable positions). Then you could plan like: go to "position x and place a bomb". As some others suggested you can create a "danger" map, which is used for the routing algorithm (how to go to position x? which path should be prefered [there are some variations possible in most cases]). This is less memory consuming in comparision to a huge HashTable, but produces less optimal results. But as it uses less memory it could be faster because of caching effects (better use of your L1/L2 memory caches).

ADDITIONALLY: You could do pre-searches which only contains moves for one player each to sort out variations that result loosing. Therefore take all other players out of the game... Store which combinations each player can choose without loosing. If there are only loosing moves, look for the move combinations where the player stays alive the longest time. To store/process this kind of tree structures you should use an array with index-pointers like this:

class Gamestate {
  int value;
  int bestmove;
  int moves[5];
};

#define MAX 1000000
Gamestate[MAX] tree;

int rootindex = 0;
int nextfree = 1;

Each state has a evaluation "value" and links to the next Gamestates when moving (0 = stop, 1 = up, 2 = right, 3 = down, 4 = left) by storing the array index within "tree" in moves[0] to moves[4]. To build your tree recursively this could look like this:

const int dx[5] = { 0,  0, 1, 0, -1 };
const int dy[5] = { 0, -1, 0, 1,  0 };

int search(int x, int y, int current_state, int depth_left) {
  // TODO: simulate bombs here...
  if (died) return RESULT_DEAD;

  if (depth_left == 0) {
    return estimate_result();
  }

  int bestresult = RESULT_DEAD;

  for(int m=0; m<5; ++m) {
    int nx = x + dx[m];
    int ny = y + dy[m];
    if (m == 0 || is_map_free(nx,ny)) {
      int newstateindex = nextfree;
      tree[current_state].move[m] = newstateindex ;
      ++nextfree;

      if (newstateindex >= MAX) { 
        // ERROR-MESSAGE!!!
      }

      do_move(m, &undodata);
      int result = search(nx, ny, newstateindex, depth_left-1);
      undo_move(undodata);

      if (result == RESULT_DEAD) {
        tree[current_state].move[m] = -1; // cut subtree...
      }

      if (result > bestresult) {
        bestresult = result;
        tree[current_state].bestmove = m;
      }
    }
  }

  return bestresult;
}

This kind of tree structure is much faster, since dynamically allocating memory is really really slow! But, storing the search tree is quite slow either... So this is more an inspiration.

Answer 4

Would it help to imagine that everybody does take turns?

Technically, in the underlying system, they actually do, but since things are interleaved and overlapped, they appear to be running simultaneously.

Also remember that you don't have to run AI after every frame of animation. Many successful casual games only run the AI algorithm once every second or so, providing the AI-controlled characters with information on where they're supposed to go or what they're supposed to do, then that information is used to control the AI characters on the other frames.