Giving a Bomberman AI intelligent bomb placement

I'm trying to implement an AI algorithm for Bomberman. Currently I have a working but not very smart rudimentary implementation (the current AI is overzealous in placing bombs).

This is the first AI I've ever tried implementing and I'm a bit stuck. The more sophisticated algorithms I have in mind (the ones that I expect to make better decisions) are too convoluted to be good solutions.

What general tips do you have for implementing a Bomberman AI? Are there radically different approaches for making the bot either more defensive or offensive?

Edit: Current algorithm

My current algorithm goes something like this (pseudo-code):

1) Try to place a bomb and then find a cell that is safe from all the bombs, including the one that you just placed. To find that cell, iterate over the four directions; if you can find any safe divergent cell and reach it in time (eg. if the direction is up or down, look for a cell that is found to the left or right of this path), then it's safe to place a bomb and move in that direction.

2) If you can't find and safe divergent cells, try NOT placing a bomb and look again. This time you'll only need to look for a safe cell in only one direction (you don't have to diverge from it).

3) If you still can't find a safe cell, don't do anything.

for $(direction) in (up, down, left, right): place bomb at current location if (can find and reach divergent safe cell in current$(direction)):
bomb = true
move = $(direction) return for$(direction) in (up, down, left, right):
do not place bomb at current location
if (any safe cell in the current $(direction)): bomb = false move =$(direction)
return

else:
bomb = false
move = stay_put


This algorithm makes the bot very trigger-happy (it'll place bombs very frequently). It doesn't kill itself, but it does have a habit of making itself vulnerable by going into dead ends where it can be blocked and killed by the other players.

Do you have any suggestions on how I might improve this algorithm? Or maybe I should try something completely different?

One of the problems with this algorithm is that it tends to leave the bot with very few (frequently just one) safe cells on which it can stand. This is because the bot leaves a trail of bombs behind it, as long as it doesn't kill itself.

However, leaving a trail of bombs behind leaves few places where you can hide. If one of the other players or bots decide to place a bomb somewhere near you, it often happens that you have no place to hide and you die.

I need a better way to decide when to place bombs.

• It's hard to think of something that works 100% out of the blue. But maybe if you add the algorithm that you currently have we can all help in gradually improving it. You're also probably not the first hobbyist trying to implement a Bomberman AI, and I've found quite a few Bomberman AI competitions with a random Google search which could prove invaluable sources of information for you. Commented Mar 11, 2012 at 11:47
• I think you can generalize bomberman AI in two things : 1) trying to protect yourself from getting blasted by other players bombs 2) placing bombs on game board to try to make others die (while keeping rule 1 in mind) : to avoid getting blasted/trapped by your own bombs). Commented Mar 11, 2012 at 15:46
• It would probably be better if you posted at least a high level overview of your current implementation (assuming it's a lot of code) and we could perhaps help you solve your problem with them being overzealous in placing bombs. Commented Mar 11, 2012 at 17:32
• @Tetrad I'm in the process of implementing a new algorithm. I'll see how that one goes and post the algorithm here if necessary. Commented Mar 11, 2012 at 18:35
• although it's not a real tip but you can take a look at clanbomber code. it's a game in many ways similar to bomberman. Commented Mar 11, 2012 at 20:03

The problem you're facing is that your AI never stops to make an intelligent decision about where it should place its next bomb, which leaves it just dropping bombs whenever it can and then working out "shit, shit, what do I do now!?"

Pausing to think

Right now, your AI just wanders to nowhere in particular. Sometimes, however, it should actually be moving to a target. For instance, if it sees a powerup and thinks it can reach it before the player, perhaps it ought to find a safe path to that tile and move there, keeping an eye out for bombs and avoiding them along the way.

The same moving-to-target behaviour can be used when it thinks about where to place its next bomb.

When your AI can place a bomb, instead of just doing so immediately, it should briefly use a search algorithm to choose from the available bomb placement spots based on criteria such as:

• Is it nearby? (so that it doesn't walk to the diagonal opposite corner of the map each time it wants to place a bomb)
• Is there a place I can hide from the explosion - and can I reach there before the bomb explodes?
• Will the explosion blow up tiles and give me powerups?
• Will it potentially attack the player? (an easier AI might avoid this in the early game, an aggressive AI will pursue this - whilst not forgetting about powerups)

When this decision has been made, the AI has chosen a bomb placement spot, and a place to hide from its explosion. It can now walk to the spot, place its bomb, then walk to its hiding place. Once it reaches its hiding place, it might want to keep walking and finding bomb locations (if it has multiple bombs), provided it keeps in mind to keep out of the way of the bomb it walked here to avoid.

On walking, and finding a safe path

You can develop for your AI a single walk-to-point method and use this each time you want it to walk someplace. This method could use the A* search algorithm to find its path.

In order to keep the AI safe, you may want to make it recheck its path each time a new bomb is placed. To avoid explosions, it could check the time til the bomb explodes, and consider a potential explosion tile safe to walk over if the bomb won't explode whilst it's walking through that tile - and if it's not safe, treat it as an impassable tile.

To give your AI faults (so it can actually be blown up sometimes) it should make calculation errors: forgetting about a bomb absent-mindedly, underestimating the explosion size or the time til the bomb explodes, etc.

Side note: You can also make its random walking seem more purposeful by randomly picking spots to walk to, or always having a new bomb placement spot in mind to walk to, instead of just randomly picking an adjacent tile to wander to. That way it won't go wandering back and forth on the same spot as if it can't make up its mind.

• I forgot to give some relevant details about the game. It's a simplified version of Bomberman: no power-ups, players can always place unlimited bombs, and bombs always have maximum range (from one end of the map to the other). The points system is different too... [cont'd] Commented Mar 24, 2012 at 12:38
• [cont.] You get 1 point for placing a bomb, but 0 points for destroying a wall. You also get 30 points for a kill, 15 for an assist and -20 for a suicide. [cont'd] Commented Mar 24, 2012 at 12:40
• [cont.] With that in mind, the AI should try to place a bomb as frequently as possible (because placing bombs gives bombs), but it doesn't need to be particularly careful about where the bomb is placed. It does have to be careful about always having a safe place to go. [cont'd] Commented Mar 24, 2012 at 12:42
• [cont.] Do you think that when choosing a direction, it is enough for me to pick the one that leads to a safe area. Instead of looking for a safe cell, I would be looking for the largest safe area, so I can hide from bombs placed by other players as well, not just my own. Also, would it be a good idea to favor directions that get me closer to one of the other players? Commented Mar 24, 2012 at 12:47
• Well then we're not talking about Bomberman and its AI at all! We're just about Some Game With Bombs Which Superficially Resembles Bomberman But Under The Hood Is Completely Different And Encourages You To Be A Trigger Happy Lunatic, and I have much less experience dealing with that game. Commented Mar 24, 2012 at 13:01