HyperSonic - Feedback & Strategy

Contests
30

Contest feedback

  • As with most CG contests, the strategy proved to be deeper than I expected on first glance. Kudos for making a challenging, but easily understandable challenge.

  • The difficulty of making a serviceable AI was about right.

  • It was more challenging to do something useful than in Coders Strike Back. This is a good thing.

  • It was less difficult to get up and going than in Code Busters. This is also a good thing.

  • The endgame was a bit disappointing. With a fuse time of only 8 moves, it’s not very useful to place more than 3 bombs at a time. With the limited board layouts available, this means that, once all the boxes were removed, it was practically impossible to kill a well-written AI. This could have been alleviated by:

  • Making more complex wall layouts, as has been mentioned before.

  • Add the ability to kick and / or throw bombs, as in many classic versions of Bomberman.

  • Add the ability to place bombs with longer than normal (12 turns) or shorter than normal (4 turns) fuses.

  • While I understand how these things happen, I found the mid-contest change to the Wood 1 boss to be a bit disruptive. Yes, he was hard. I agree. My personal opinion was that it should have been left as-is, though.

  • Does anyone else find the two top-placing contestants a bit suspicious? :smirk:

Game logic

  • My logic was designed with reproducibility in mind. I wanted to be able to provide a set of inputs for a given turn, and always get a predictable output. Two main guidelines fed into this:

  • Stateless - Moves were calculated each turn, with no information saved from previous turns. The one exception to this was score information, which was not provided in the game inputs, and needed to be tracked over time.

  • Deterministic - No random elements. A couple of times I accidentally broke this guideline, and had to correct my mistake.

  • The first action of each turn was to build a 3D representation of the game board, with the 3rd dimension being “time”. Then, when planning out moves, I could lookup the proper board state in the array to determine what the board would look like after N moves. To do this, I:

  1. Make an array of bombs where the remaining fuse is equal to board index and calculate a collection of squares exploded by these bombs.
  2. Make an array of bombs located on any exploded squares and loop to step #1 until no more bombs can be added.
  3. Replace any boxes (0, 1, or 2) with a ‘#’ character to indicate that it has been destroyed, but is still impassible for this turn.
  4. Remove any items on an exploded square.
  5. Add a new board to the array. Remove all exploded bombs and destroyed boxes, and add new items (from destroyed boxes) where appropriate.
  6. Repeat this procedure until no more bombs are left. After this point, board state is assumed to be static for subsequent turns.

  • Also at the start of each turn, I created up to seven additional hypothetical board state arrays, following the same procedure as above:

  • One in which I have placed a bomb in my current location.

  • One each for a bomb placed on the next turn in each reachable square adjacent to me.

  • One in which all my opponents have placed a bomb in their current location.

  • One in which all players (opponents and I) have placed a bomb in their current location.

  • I created a method called IsTrapped() which takes an X, Y location and a 3D board state as input and returns a boolean indicating whether or not a player on the provided location is able to survive.

  • I created a list of every single reachable square on the board (and a history of moves to get there) using a BFS.

  • Squares were eliminated if I would be trapped by moving to the square (according to the hypothetical board state in which opponents had placed bombs)

  • If a square had been previously “visited” by an alternate route, I would compare the scores of the two routes to determine which method was better, and drop the one with the lower score.

  • All reachable squares were scored by:

  • Number of boxes that could be destroyed from that location

  • Number of items collected along the way

  • Distance to the location (above and beyond the number of turns required to replenish my bomb supply)

  • If the square was less than 2 turns away, then bonus points if an opponent would be trapped by placing a bomb there (according to the appropriate hypothetical board state array).

  • Given this list of candidate destinations, I would either simply MOVE to the first square in the move history of the destination with the highest score, or I would BOMB if a logical combination of the following held true:

  • Placing a bomb would not leave me trapped (according to the hypothetical board state array where all players place a bomb)

  • My current location was the selected destination

  • The score for the current location was > 0 and I had more than one bomb available

  • If the list of candidate destinations was empty, this meant that I was potentially trapped. I would create a new list of candidate destinations, this time without discarding any previously visited squares, and using a DFS. This would allow me to “zigzag” to possibly avoid staggered explosions. This extra “Oh sh**!” logic got me out of a lot of tough situations, while keeping my default pathfinding much faster.

Tests

As I mentioned before, I ran MANY games in the IDE using CG Spunk. I formatted the STDERR in such a way that it printed both the information read from STDIN, and the move selected by my algorithm, as code that could be easily copy / pasted into my unit test framework. Whenever I came up with a situation where my AI made a bad move, I could paste this information into a test of the format:

Given contents of STDIN
Should not select stupid move

Over time, my arsenal of stupid moves to avoid grew, and I was able to hone my logic without repeating past mistakes.

  • danBhentschel
8 Likes