CodinGame Spring Challenge 2020 - Day 3

08 May 2020

Today is day 3 of the CodinGame Spring Challenge 2020 and today I am going to set about defeating the Bronze boss. Defeating the Wood League bosses yesterday was a good start but in reality I didn’t even scratch the surface of of the problem space. For instance, there is bunch of grid data that I did absolutely nothing with yesterday. I did the bare minimum to advance, and I actually intend to do the same for this league as well.

Since the Silver League does not open for two more days we won’t know today if we can defeat the Boss or not, however I enter today ranked 1,786th out of 3,117 participants. I’m not even half way up the ladder, which is not surprising. This bot is far from being competitive at the moment, hopefully we can make significant movement up the ladder today.

Bronze League Rule Changes

The added rules that we have to deal with are significant changes. In addition to the grid data that I ignored yesterday the following rules also need to be handled:

• You can now give a speed boost to your Pacs
• You can now switch their type to attack your opponent’s pacs! Collisions are handled in Rock-Paper-Scissors fashion.
• You can only see pacs and pellets that are in the line of sight of your pacs

Problems with WoodBot

Watching some of the replays there are some glaring problems with WoodBot that need to be quickly resolved in BronzeBot.

1. Target cell selection is broken. Since we only know of the pellets we can see this code only runs as long as there are pellets in view of at least one PacMan. As soon as there are no pellets in view the bot dies, and we immediately lose.

The exception is:

Unhandled exception. System.InvalidOperationException: Sequence contains no elements
   at System.Linq.ThrowHelper.ThrowNoElementsException()
   at System.Linq.Enumerable.First[TSource](IEnumerable`1 source)
   at CodinGameWood.BotBrain.Next() in /tmp/Answer.cs:line 130
   at CodinGameWood.Program.Main(String[] args) in /tmp/Answer.cs:line 21

1. There is no collision detection/handling. This led to some interesting cases in Wood League where opposing PacMen spent 100 turns butting against each other. In this league my PacMen simply walk into the waiting mouths of opponents that are ready for them. This needs to stop.

Today’s Goals

There is a lot that my bot is not doing right now, but there are few things that I think will give me biggest return on time invested.

Today I’m going to:

• Improve target cell selection – Manhattan Distance is more of an estimate, we can get an exact distance to cells with a little more work. We would like to get all the super pellets we can, but also scout the entire grid. But first and foremost we need to not error out for an immediate loss.

• Path finding – we need to determine where each PacMan is headed, and we need to be able to adjust his path if necessary.

• Use PacMan abilities – not using speed and type switch leaves my guys at a huge disadvantage.

Some Thoughts on Strategy

• At the beginning of the game we know that every square except those occupied by a PacMan contain pellets, and we also know where each super pellet is located, so on the first turn we have a pretty good idea of the initial board layout. Known pellet data can be used to calculate estimate path reward for a given PacMan. Path reward can be used to prioritize a PacMan in collision resolution.

• We should be able to keep track of all the cells we have visited.

• Each PacMan should have a unique target cell.

Today’s Result

I had more problems replacing the wood strategy than I anticipated but I have a working BronzeBot that does not error out anymore. The improvements however did not move me up the rankings as I had hoped. I only move up 411 spots on the ladder to 1375. This biggest problem at the moment is not handling collisions with either my own Pacs or the opponents packs. This becomes a problem in almost every game where the opponent doesn’t timeout early in the game. In other words, we defeat none of the properly coded bots, and not even the dumb ones.

This is an example of the problems my bot has.