I ended 33th in legend. Thanks for another great contest.
I liked coding for the game at first, but got frustrated later on in the week when nothing I coded gave me a visible improvement. No feedback is a serious handicap when trying new ideas. The creators can’t be blamed for this though. This unpredictable behavior of the leaderboard is not easy to foresee and the game being fun and interesting to code a bot for is more important.
Normally I wouldn’t bother to write a large PM when I didn’t reach top 10 or at least top 20, but I think some parts of my bot are worth noting for future reference. I’ll go step by step to explain how the bot works and pay specific attention as to how the monte carlo search works:
The first turn
I do the following things:
-
Read the map and identify walls and setting all non-walls as having a possible pellet (except those at pac start-locations.
-
For each cell that is not a wall, I store all neighbors in an array.
-
I identify all dead ends of the map and put them in a list.
-
I set up the two pac teams as “Pac” objects.
-
On the first update I mirror all opponent pacs I don’t see.
-
I assign each pac a super-pellet as destination if it is closest to it (this part of my bot was weak and could have been much improved).
The update
-
I do the regular update from the input given. Also storing a copy of each pac from last turn, so I can compare changes.
-
For each possible pellet on the map I keep a pellet-history (for all 200 turns). For each visible pellet I see in the current turn, I set all pellets as being uncollected for all turns before that. So even if I did not see the pellet in earlier turns, I know it must have been there.
-
I list all visible cells and mark cells as visible if I can see them that turn. I mark all cells that have no pellets and remember that.
-
For all opponent pacs I keep a visibility history. I know for each cell if I saw that an opponent pac was not there that turn. So this is not about where the pac was, but where it wasn’t.
-
For dead ends I floodfill outward until I hit a pellet, so that my monte carlo search knows not to enter into this area without pellets. This helps reduce branching.
Elimination of invisible pellets by opponent pac routes
In a game it happens very often that you will see a pac in a certain turn, then it disappears and you see it again 10 turns later. You then have two locations and there must be a path between them. If the new location is far from the old location, there are often many cells, that the pac must have travelled through to get there. All those cells will no longer have pellets. It is useful to mark these as collected, so your search won’t try to go there. I do this as follows:
-
I start at the last seen location and make a “future” speed-analysis, moving the maximum number of cells. You have a lot of information about the speed history of each pac, even if you dont see it for a long time, because you have the speedturnsLeft and cooldown.
-
I flood outwards using the speed it has in each turn from when it was last seen. Any pellets it crosses are checked for whether they existed that turn (using the pellet history). If the pellet existed, then the pac cannot have passed it. This is why it is important to do this procedure only when you see the pac again, so you can use the full pellet-history information you have at that point. I also check whether the locations the pac passed were observed by other pacs. If they were observed and the pac was not there, then the pac can’t have passed through there either.
-
I will end up with a flooded area which I use as a limited set of cells to create a BFS-searched path from the last seen location to the new location.
-
If there are any cells that the pac must have passed through to get to the new location, they must be part of this shortest path, but this shortest path might contain non-mandatory cells as well and thus not be the only route. So I take the shortest path and for each cell on the path, I remove the cell from the flooded area and then I check if a BFS route is still possible within the distance travelled by the pac. Any cell which causes a BFS route to become impossible when it is removed, must have been passed by the pac and the pellet is marked as collected.
This feature worked quite well and I was often able to eliminate 5-10 pellet locations at once upon viewing an opponent pac. However, this is one of the features for when I added it, changed nothing on the leaderboard… which was unfortunate. You can imagine the amount of code that goes into this feature.
Blocking the entrance to dead ends
One of the latest additions to my bot was the blocking of dead ends when an opponent pac is near that can kill my pac. I didn’t get around to testing this well enough, so I don’t know it works. Basically I just did another speed analysis and a lot of BFS-distance testing to see if it was safe to be in cells inside a dead ended-area.
Tracking the opponent current possible positions
Assuming the opponent travels at maximum speed (speed chaining). I calculate for each opponent pac all possible positions it could have travelled too also taking into account cells viewed and pellet history just like when I am eliminating pellets as explained earlier. If there are not too many positions like this, I can use this information to avoid being killed around corners. I think it sometimes worked, but I am not sure. It wasn’t well tested.
Opponent pellet prediction
For my monte carlo search I mostly viewed opponents as being walls when they are dangerous and ignored them otherwise, but I did do a floodfill which recorded for each future turn for each cell whether the opponent could have reached there. If, during the monte carlo, my pac would collect a pellet too late from this cell, it would receive less points.
The Monte Carlo search
This is easily the best feature of my bot. When I finished it, 4 days into the contest, my bot jumped to rank 2 immediately. I can’t honestly say if my bot ever really improved after that. If it did, it happened so gradually I didn’t notice. It works as follows:
My monte carlo simulates 8 turns deep (there is no limit really, it could have gone 12 deep also). I could test over a million plans (combinations of routes over 8 turns) in turn 1 and 100k in other turns, which was overkill.
When i say 8, I mean to say both normal and speed move, so it could be 13 cells travelled. Basically, I choose random moves for each pac keeping some restrictions namely:
-
Pacs can’t move backwards in a corridor during the sim (except in first turn of sim). This is a slight reduction of freedom, because sometimes it might be worth grabbing a quick pellet and turning around. The exception is, of course, a dead end. I store the previous location each time a pac moves, to prevent it from turning around.
-
For each pac I have a series of blocked cells, because an opponent pac can travel there in the current turn, killing my pac. Opponent pacs are walls in the sim if they are dangerous this way. So not all pacs will have the same walls, because of different types.
-
Pacs wont go into dead-ended areas with no pellets.
-
Pacs wont cause friendly collisions. When two pacs want to go to the same place, one will wait (randomly). I do this in the “Resolve collision” functions below
The simulated turn is built up like this:
- Apply speed ability if necessary
- Generate random moves.
- Resolve collisions.
- Generate random speed moves (if a pac can speed).
- Resolve speed collisions.
- Apply all moves and calculate score per pac and total score.
- Reduce cooldown timers
Repeat this 8 times
After 8 times, check if the current plan gives more score than the previous best plan. Replace if so.
After calculation time is up (which is often after between 50k and 150k plans) apply the best plan to all pac moves.
Lost pac assignment
I keep a score per pac in the monte carlo. If the chosen plan gave 0 score for a specific pac, I default to a BFS route to the nearest uncollected pellet. This way I don’t get pacs just randomly moving around.
Hardcoded destinations and hardcoded moves
My monte carlo also had a system for hardcoded destinations, where instead of generating moves randomly it would just let pacs move closer to the destination, collecting pellets on the way. This way the hardcoded superpellet collection for some pacs does not conflict with the monte carlo plan for other pacs. I also had a system for “first sim turn” moves to avoid nearby opponent pacs, do switches and such, but I never ended up using it.
To do list
My to do included “kill code” (to kill pacs that you are in range of killing), improved superpellet assignment and many tests i didn’t get around to doing. My code was a 2.5k line mess at this point and I just couldn’t summon up the motivation to add these last things. Almost all of the above stuff I explained gave no visible improvement (except the MC search) and this is why I lost motivation.
During this contest I learned the power of a monte carlo search. I never took it seriously before because it seemed worse than mcts or minimax or even beamsearch, but I will look at it differently from now.
See you next contest!
Also I tried to use some pragma I found on CG forum but it made my code slower for some reason…
