#How I used Python3 to rank 44th,
##…rank first in Python/Python3, and##
##…have my bot chosen to be the notorious Gold Boss##
A lot of people expressed amazement in the chat that my Python bot made it to the leaderboard (at a time when all the other bots were in C/C++). The truth is that I didn’t do anything special.
##My algorithm##
-
I predicted all possible enemy positions accurately, including the possibility that the opponent is deactivated either because of a bad move or a lack of moves. This wasn’t about fancy algorithms or fast search, it was about basic logical reasoning. It took me about a day to code and test. I found Python’s
setandfrozensettypes to be very helpful here, as well as list/set comprehension. - At the start of each turn, I just fixed an arbitrary pair of possible enemy positions, assuming the opponents are still active if possible.
- I went through all possible moves and scored the best ones according to an evaluation function. My evaluation function took into account the heights around my units, and the positions I can travel to (using the move rules but with no building) and reach before my opponent (basically a modification of the Voronoi heuristic). Finding the right version of the Voronoi heuristic is what bumped me into the legend range. Later evaluation functions also penalized being in a position which can be pushed to a lower level.
##What didn’t work##
- Minimax (or alpha-beta). I couldn’t get it to be fast enough.
- Brute-force search. I thought this would be good at the end when I am no longer connected to the opponent. Then it is just about optimizing the score. It was fast enough at the end, but for some reason it was doing slightly worse. Maybe I had a bug.
What was reassuring to me is that many C++/Java/C# players were also complaining that they couldn’t get minimax to work.
##My takeaways/advice##
- Take the time to deduce all the hidden information. Most players won’t and this gives you a huge advantage.
- A good evaluation trumps extra search depth. For example, my Voronoi heuristic really helped get a big picture view of the game positions.
- Even though Python is slow, it is ease of code up new ideas, and that is a fair tradoff in my view.
- There is a luck element, but the more you can experiment and test, the better chance you have of hitting the jack-pot.
##A few other things##
- I have a CG contest template that makes it easy to get started on each new constest.
- I keep track of the time and stop early if I am close to timing-out.
- I try to adopt good programming style, including having classes for things like the board state. This makes it easy to modify and extend my code. (This time I even wrote my program as a bunch of seperate files and wrote a tool [a hack of the module import system] which converts those many Python files into one file.)
- I wrote my own arena app for this contest (and every recent contest). (I wrote it in Python using a template that I have). As Agade and others have said, having a personal arena app makes it really easy to test your ideas. I can run 1000 games in about 30 minutes. If a new version does really well against the current version, I know it is worth submitting. Also it has that advantage that I can run code that would time out on CG, and I can see if it is worth trying to speed up. (I did this with the Voronoi heuristic for example.) I also use the CG Spunk tool, but that is 10x slower than my app.
View of the contest##
I like that the rules were simple. I also liked the hidden information aspect even though it seemed silly at first.
As for the artwork, I was frankly embarrassed to be playing this game in public. I don’t think the scantily clad motionless wonder women on the side of the board added anything to the game. (I did think the advertisement artwork was much better.) I really appreciate CodingGame focusing on women-themed puzzles, like Wondev Women, Coders of the Caribbean(?), Ghost in the Cell, and Codebusters(?). I’d encourage the trend to continue, but with better artwork. I also understand that it is a huge stretch to incorporate the theme into the puzzle, so I don’t want to be too harsh.
(I have seen a lot of sexism and racism in the chats here, and I am worried about this website being uninviting to women and others. I hope it is just a few outspoken trolls in the minority.)