The Halite 3 AI competition has finally concluded and after too many if statements and for loops and a ton of hard work, I was able to rank #66 globally, and #5 out of highschool students.
Halite 3 was an amazing competition for me. It was my first time competing in Halite, and my 2nd time in an AI competition, my first being MIT Battlecode 2018, which really motivated me to pursue computer science further in my final years of highschool and hopefully university. I cannot thank Two Sigma and the team behind Halite 3 for hosting such a smooth and brilliant AI competition!
If you don't know what Halite 3 is or need a refresher, check out the game rules here. They are simple and quick to understand (and the rest of this post-mortem will make more sense).
By the way, I wrote my bot in JavaScript and ranked #1 out of all JavaScript bots, although this doesn't really mean much compared to my global and high school student rankings and the reason why will be explained below
I approached Halite 3 as more of a competition that tests your ability to model with the highest accuracy of the most optimal play with some special strategies sprinkled in. For me at least, this competition was less about knowing your AI algorithms such as Dijkstra's algorithm or even data structures such as linked lists or graphs (all of which I didn't use in my bot and as always KISS - Keep It Simple Stupid), and more about how well you can model the game and make the best decision for each entity at each turn. Additionally, one of the key reasons behind not using the popular Dijkstra's algorithm is because my bot is fairly narrow-sighted, meaning it doesn't look ahead that far and performs all its moves fairly locally. There are nice applications of it as seen in some of the other top bots post-mortems and would have definitely improved my bot a little, but I never came around to using any of those applications.
Saying that, I do not believe I did that good of a job of modeling and more of went by intuition and used really simple methods to help abstract the game a little and achieve results. If you take a look at the 3rd place competitor reCurse's post-mortem, he shares some very interesting models and how he uses it to gain that extra competitive edge and I HIGHLY recommend reading through that.
But following the approach of competing with good modeling and strategical thinking, is the key reason why I chose to use JavaScript (another reason being that it is my most proficient language, ahead of Java, Python and C, and I love web development). With JS, I don't need to worry about memory management, variable types, and all that low-level programming that probably could speed up my bot by a lot. Additionally, I do believe that the 2 second time limit for each turn in Halite is a little too generous because my JS bot consistently ran each turn in 100ms or less. Hence code efficiency was not an issue (although it made running local matches a bit of a pain). So with JS, I was able to quickly implement any of my ideas and models without frequently running into bugs. This saved me a lot of brain power and time for other things in life such as school and exams.
I also recognize that having a good workflow is key to pushing out new code efficiently with fewer bugs and speed up the entire programming process. Again, reCurse has an excellent workflow, you should really check out his post-mortem where he shares his "Battlestation." I, on the other hand, had a horrible workflow. Because I love web development, I practically use the Adobe Brackets for all my programming (its local server and live preview functions are just 👌). Hence? I continued to use Brackets for programming my Halite bot. I'm still a high school student and have yet to learn a lot of standard approaches to programming (such as using an IDE). The only good part of my workflow is some file organization and using Git for source control, keeping my sanity in check. Another nice part of my bot is that it uses 0 random variables to run. This makes it really easy to replay an entire game and get the same exact results and was fairly helpful for running local matches.
Competing in Halite 3 did force me to learn some Bash in order to easily run my own local matches between my bot and old bots and implement various features that I wanted. One of which is testing my new bot against an old bot twice with a team switch in the middle. If you read the game specs, you might ask "Why do you need to test it twice? The entire map is symmetrical, wouldn't the same exact game be played out?" My answer: I don't know why, but different results appear, despite my bot having 0 random variables. Generally, through my own local match runner, I was able to determine with higher accuracy whether my new bot is better than my old bot. This allowed me to make sure subsequently submitted bots are working the way I intend to and are actually better than the previous one (don't want to drop in rankings!)
My bot was "simple" in that it doesn't use really advanced modeling techniques to do fairly well against most competitors
Generally, in each turn, the following occurs
Before looping through each ship and deciding on where they should move, we first process the current game state.
The key things we process is the total halite left and optimal dropoff locations. These are stored into a variable for future decision making by our ships. There are some other things going on here that help organize the ships a little bit, but I won't bother with the details in this section, they will be referred to in a future section.
Yup, that's it. My bot is somewhat "simplistic."
if ((game.turnNumber < 0.65 * hlt.constants.MAX_TURNS && numShips ≤ 1.7*Math.sqrt(mapSize))
and
if (averageHalite >= 50, (60 for 4P games))
and
if (designatedDropoffBuildPositions.length >= 1
&& me.haliteAmount >= hlt.constants.DROPOFF_COST + 500)
Essentially, if it isn't too late into the game, number of ships we own is less than 1.7 * sqrt(mapSize), average halite per tile left on the maps is ≥ 50 (60 for 4 player games), and if we have decided to build a dropoff, we need enough halite to build the dropoff first before spawning more ships, else if we didn't decide to build a dropoff, build a ship. There are some other if statements involved and a bit of code that prevents our bot from spawning a ship when there are too many ships surrounding the shipyard, but that didn't have much impact on my bot's performance.
The values 0.65, 50, 1.7, 500, etc... are what I call "Magic Numbers." They are partly based on intuition, from what I saw on replays of top bots, and some optimization through running my bot against itself with different parameters. I did attempt to use a machine learning library at one point to try and optimize some parameters but quickly found out that 1. I don't have enough data from running matches against myself to make any reasonable conclusions and 2. I really need to learn more machine learning concepts to better understand how to effectively use the library. You will see many more magic numbers in my source code if you choose to look through it. My code is hopefully nicely commented.
I found this to be fairly important, especially when it comes to dealing with some edge cases in my collision management code. But this also helped improve the efficiency of the bot and allowed the more important ships to get first pick on what to do. Here's a quick ordered list of the priority in which ships get to make their decision
Halite III ultimately boils down to where do you move a ship. (Along with the occasional building actions and spawning actions). As thus, this is how I primarily structured my code. All my decision code for each ship will eventually return a sorted array of directions in order of priority (and no collisions), of which the first direction in the array is what will be executed.
Each ship is assigned a status/goal, implying what it's trying to do this turn, and is probably one of 'return', 'mine', 'leaveAnywhere', 'buildDropoff', 'final', 'goingToBuildDropoff', 'blockDropoff'
Switch(status){
'mine':This is where all the mining code happens. Mining is possibly the most important aspect of the game (it helps you win unless you are one of those guys who doesn't mine and tries to collide with the opponent). This is also possibly my bot's biggest flaw :( ... I have to say, the heuristic I used for deciding on which location a ship should try to go to and mine is too simple. Theoretically, the method of calculating the rate at which halite will be mined or assigning a specific score to each tile taking factors such as turn count, distance, cost to go there, etc. should be really optimal mining code. I did that. My bot didn't like it and performed worse against my simple heuristic. Ok enough talk and typing, this is my heuristic:
The ships search in Manhattan radius of 20 and looks for the tile with the highest ratio = R
Where
R = (Halite At That Tile - Halite Cost to Reach That Tile) / ((Distance To That Tile + 1.5) * Halite At The Tile The Ship is On)
If the tile is within a radius of 1 from the ship, and the ship has inspiration on that tile, R is multiplied by 3.
Intuitively, this method will work and makes sense. By dividing by distance, the ships are discouraged from going too far away to mine. By dividing by the halite at the tile the ship is on, we get a ratio. (Actually, as of writing this, I just realized there's no need for a ratio, just divide by distance and the same result occurs...)
'return':
If the ship has over 1000/1.02 = 980.3921568627 halite in cargo (another magic number), it will return to the nearest dropoff/shipyard to store it. This was somewhat optimized for my bot through running a bunch of matches against myself, but again its a magic number and its origins are partially unknown.
Additionally, these ships also attempt to attack the opponent by crashing into enemy ships with at least 1.5 times the amount of halite in their ship than our ship and if there are at least 2 friendly ships nearby to help pick up the remains.
'goingToBuildDropoff':This status is just for ships that are designated to go and build a dropoff at one of the previously decided (in game state procession) optimal dropoff locations. Nothing fancy happens, the ship just moves towards its target destination.
'buildDropoff':Ship is preparing to build a dropoff and will stay still
'final':This is a special status given to ships to do the same thing as returning but allow for collisions if within 3 units of the nearest dropoff/shipyard. This allows us to quickly store all our mined halite ASAP as friendly collisions don't matter anymore in the end game
'blockDropoff':All ships with this status will look for the nearest reachable dropoff (in the turns left) that has the most enemies nearby and attempt to block it. This is done at the end of the game and often helps me win some tight games by forcing the opponent to drop a lot of their halite through collision or not store any at all. Generally, blocking a dropoff follows the following rules
The previous section gave each ship a role and a destination to try and move to. In giving this destination, the bot finds the most viable directions to go closer to that destination. Generally, our ships will take a greedy approach, and always avoid locations where a collision with the enemy may occur. Movement is finalized in the order in which the ships are looped through, which was already sorted by priority.
The bot runs a function that returns an array of every possible direction the ship can move in, ordered in desirability, with the first direction the most desirable and last direction least desirable. Desirability mostly depends on which direction is safe from enemy collisions and which get the ship closer to its destination. After the array of directions are found, we compare the first direction with the finalized direction of all the ships looped over before this one. If there is a conflict that could lead to two ships colliding, we then compare the next direction in the array. We keep doing this until we find the most desirable direction that avoids collisions.
However, there are some edge cases where a ship will have no viable move that avoids collisions. At this point, the ship just moves in its most desired direction and tells the ship that conflicted with this ship to choose a separate direction that doesn't collide with anyone to move in. This is usually more than enough to ensure unwarranted friendly collisions do not occur.
Halite III was fun, interesting, and a joy to compete in. I can't wait to compete in future Halite AI competitions and cannot express how grateful I am for Two Sigma and the team behind Halite to help host this competition. I certainly learned a lot about programming through this and became more experienced in terms of using tools to help me organize my code and speed up the development process (such as Git, which I, unfortunately, did not use in Battlecode 2018). Halite III really helped me get even more hooked into the fields of AI and machine learning, and I would highly recommend this competition to any budding programmer, even if you only just started to program.
Thanks for reading this post-mortem to its very end, or if you just skimmed through this, please click the elevator button (kindly borrowed from Tim Holman) to go back and read the rest >:(
(jk)