Wondev Woman post-mortem


I ranked 3rd on the Wondev Woman contest, out of 2300 participants. I also managed to keep a comfortable lead in the top 2 for half the competition, then top 3 for the last half, so quite happy with that! Cheers to T1024 and Agade for such a heated battle at the top throughout the whole event. The game was really fun, simple to learn yet hard to master, which makes for the best competitions.

Following feedback from my last post-mortem on Coders of the Carribean, where I described my workflow, methods and the whole journey behind, this one will be more focused on my final game strategy. I hope you enjoy the read!

What worked well

I am not 100% certain on what made my bot dominant for most of the competition. I used similar strategies to what others described, so maybe the devil is in the details. This section will be about all the things that proved to work out great in practice, as removing/changing any of them made my bot play noticeably worse.


Big surprise here (not), a straightforward minimax search algorithm with alpha-beta pruning was the backbone of my bot’s decision making. A major obstacle to this kind of search is the ridiculous branching factor this game possesses, which can easily average to 128 on early-mid game. For this reason alone, I think the best algorithm to play this game would be Monte-Carlo tree search, which has proven to play Go at a professional level where minimax fails miserably. But given the tiny time limit (50 ms per move), I figured it would probably not be viable for this contest. Too bad, as I really wanted to try it.

Still, the branching factor remains an issue, as it will be almost impossible to see 4 moves in the future (2 per player) before the end-game when analyzing every move. But considering how easy it is to get trapped, it is essential to see this coming, to avoid it or make the opponent fall for it. I figured the only way to make this work would be by pruning very aggressively.

Taking inspiration from beam search, on every reached depth I am sorting the list of possible moves by my evaluation function, only keeping the best moves and discarding the others. With this, my bot was always able to reach depth 4, and often even depth 6. It could sometimes become blind to certain moves, but the extra depth made up for it, and the really good/bad moves were mostly sorted out by the evaluation function. I rarely saw an improvement when playing the same game with all moves allowed.

A transposition table also helped accelerating the search by eliminating redundancies in move sequences and giving a headstart to the higher depth search.

Enemy detection

As soon as I reached bronze and saw the fog of war, it became clear that, unlike CotC with the mines, knowing the enemy’s position would be essential, otherwise what are you going to run minimax against? Using a wrong position such as the last known one can have catastrophic results, as it turns the bot randomly blind to traps or proper territory control. Figuring it would be key to get this right before any other meaningful work could be done, I spent half of the first Sunday on getting it reliable enough.

After toying with a few ideas, I found one that worked reasonably well. My bot keeps the last known states it received as input, as well as the moves it played. Then, starting up to 20-25 turns ago, a depth-first search is used to try to reach the current state, using my played moves on my turn, and try every possible enemy position and move on his turn. I needed to write a bunch of rules to detect an impossible condition and fallback, which pruned out the vast majority of possibilities very quickly. For example, if an expected enemy position becomes visible, and the piece was not visible at that time, it quickly aborts and tries the next one.

Sometimes it would end with multiple possible positions. At first it just took the first one it found, but analyzing some losses that were directly caused by guessing badly, I then used my evaluation function on each possibility to keep the one with lowest score. That made the bot play better afterwards by anticipating the worst.

In the end there were still a few rare unhandled cases, like pushing a unit into an unseen one, which caused funny games where my bot would spend all its time ramming into an enemy that was defeated. Statistically speaking though, after parsing hundreds of replays, it did not seem to happen often enough to cause issues with my win rate.

Voronoi territory

Again, not a big surprise here, this game has similarities to Tron in which territory control is everything, so the most effective heuristic for this game is to compute a Voronoi territory (technically inaccurate, but for lack of a better term). This is done by using a breadth-first search using the initial unit positions to calculate the cells that can be reached before your opponent.

I have added one twist to it that turned out a big improvement. The problem with this technique is you need to give one side the advantage, which turns out to be an issue in practice. If two units are separated by an empty cell, one or the other will end up controlling it. But because of the game dynamics with pushing, it is uncertain if you really control those contested areas. For instance, I noticed on multiple games the bot thought the enemy was cornered, but where he ended up slipping away because it could not be pushed away.

I ended up fixing this with what I call a “double voronoi”. So basically, I run one version where I have the advantage, and another where the opponent has it, and sum the results together. This made sure to further limit the zones the enemy could get to, and maintain better board control.

Height analysis

Given the whole game is played around building on cells, it is straightforward to consider as a heuristic the height of the cell a unit stands on, as well as the neighboring cells. From that statement it would also be natural, like others did, to simply consider the average height of the surrounding cells. For some reason though, I did not even think of doing that until after the contest… so maybe it was one good factor I missed.

Instead, I went with classifying each neighboring cell in different categories:

Each of those categories had a score tied to it, and part of the evaluation is summing scores of all neighboring cells. Holes and walls had a big penalty, drops and stairs a smaller one, while floors and goals gave a positive score. The overall reasoning was to setup or avoid traps, favor flattening my own area and keep control of score tiles, while doing the opposite for the opponent.

I spent a lot of time tweaking those values, as they had a dramatic effect on the bot’s playstyle. It was also very hard to figure out what worked as a better strategy overall. Some styles were great against specific opponents but terrible against others, and so on.

The middle cell also added a linear score based on its height, the higher the better.

What didn’t work

I am not sure whether to be impressed or disappointed by how little made it to my final version… here’s some of what ended up on the cutting room floor, and other wastes of time.


Thanks for reading! If you have any questions or comments, feel free to poke me on the CG chat or leave me a private message on the forum. Feedback on the post-mortem content is also welcome.

– reCurse signing off with… a Kettlebell?! :p