Halite Home

Tips for climbing the ladder - spoiler free


#1

I figured I would write a post with some tips for what has worked (and not worked) for me in climbing the rankings ladder. I will avoid any specific discussion of implementation details or game strategies (other than a note on overkill). The main reason for not going into specifics is that I am a fan of figuring out the implementation details and strategies myself, and I want people with the same mentality to still be able to read and benefit from this post without feeling like I took some of the fun out of the game.

I realize most people don't share this same mentality, and so I would first point you to a fantastic post So you’ve Improved the Random Bot. Now what? that goes into implementation details and strategy. I wouldn't be surprised if the code provided for the OverkillBot will put you close to the Gold Tier right away.

A lot of these tips will come across as common sense, but I still find myself spending a lot of time doing things that aren't actually helping my bot, so this list is as much for new players as it is for myself.

1. Your bot should never error out.

Stop on any new feature you are implementing, fix that bug, resubmit your bot, and carry on.

2. Your bot should not time out.

Yes, there can be rare server issues that will cause your bot to time out, but in general if your bot is timing out it is a problem with your code. If you see you are timing out on more than 5% of your games, you should stop whatever new feature you are implementing and figure out how to fix it.

3. Use source control.

Ok, yes this is pretty much a no brainer for any developer, feel free to skip this section.

I implement any major changes to my strategy or new ideas on a new git branch. If I am struggling to make that strategy work correctly, it is no big deal, I just check it into the branch and then move back to master.
On two different occasions I've figured out why things weren't working well with a strategy several days after I'd given up on that idea. Luckily since I still had the code lying around on the branch I was able to make the changes and watch it work as I had hoped and merge it onto master.

4. Practice against bots locally.

Local matches are essential to testing fixes to your bot. You will want to be able to test specific maps multiple times as you are debugging and modifying your bot. In order to effectively test you will need other bots to test against. One suggestion early on is to take some of the bots from the previously mentioned post. In addition I save a jar file of every version of my bot so that I can test any changes I make against previous versions of my bot.

I also use the local match manager to test for regressions in my bot. It would probably have been better for me to come up with some kind of test suite for regressions, but I never made it around to that.

5. Keep iterating on fixing all clearly bad moves your bot makes, until you are confident that any bugs in your implementation are fixed.

I should probably have made this #1 since this is the most important point to remember early on. Avoiding bad moves and mistakes is the most effective way to quickly climb the ladder.

6. Understand root cause of losses

You should watch a bunch of replays to understand the root cause of most of your bot losses. I know it is much more fun to watch the replays where you win, but it isn't as easy to learn that way. Be careful you are actually getting to the root cause and not just an observed effect. Keep asking "why" until you can't go any deeper, and then work on a solution. The tricky balance here is that you don't want to change something so that you win in this scenario, but suddenly your bot loses a lot of matches it won before. Again my current solution for this is to use the match manager to catch regressions.

7. Make sure you understand overkill.

I thought I understood overkill early on, but it wasn't until V52 of my bot that I actually understood how it worked. I see the documentation is much better now than when I first started so it may not be a problem for new users. I figured I would mention it though since I struggled with it, and I see so few bots that attempt to take overkill into account.

My mistake was that I thought overkill to surrounding sites occurred after reducing the strength of all enemies attacking the same site. It's amazing how many replays I watched without realizing I was wrong. I guess when you think you know how something works you glaze over evidence to the contrary. I finally figured it out by watching an attack in slow motion, which I think is the best advice for making sure you completely understand the overkill rules.

8. Bot ranking != number of lines of code

I believe @erdman posted that he had somewhere in the neighborhood of 100 lines of code with his #1 ranked bot at the time. I'm guilty of writing lots of code, but anecdotally two of my best bot improvements have been when I figured out more general solutions to produce the effect I was going for (and resulted in removing a lot of code).

9. Performance improvements have a snowball effect.

Initially I looked into improving the performance of my bot because I was timing out too much. As I improved the performance I started to realize some side benefits.

a) Obviously not timing out helped my bot ranking quite a bit
b) I could now run local matches faster, resulting in faster feedback while testing changes to my bot.
c) Match manager can run more matches to find regressions quicker.
d) I had leeway to add more calculations where it could further improve my bot.

How did I improve performance? First you have to be able to understand where the time is being spent. Sometimes it may seem obvious where the time is being spent, but it is always good to use a profiler to confirm.

Anyone using a JVM based language should be able to use jvisualvm. I use jvisualvm sampling and a Clojure specific library Criterium to execute the code I want to benchmark. I never managed to get the jvisualvm profiler to work with my code (probably some environment properties I need to set), but sampling was sufficient to understand where I needed to improve performance.

Once you know where the performance problem is you can fix it by improving the performance of the culprit function or finding a way to reduce the number of calls to that function.

It looks like if you are using Python you should definitely use Erdman's starter package to be at a good starting point performance wise.

10. Make use of tools

The community has put together some great tools. You have the match manager from @smiley1983 I mentioned before, the enhanced visualizer from @nmalaguti, and so on. Take advantage of those. Figure out things that you want to measure and build a tool yourself to give you better insight into your bot.

I should probably say that building your own tool is a double-edged sword. A lot of us would end up sinking a lot of time into a tool, which in the end might be great. If your goal is to move up in the rankings though you might be better off not spending time on a tool. There aren't a lot of people like @nmalaguti that are so focused and productive they can build a tool, rewrite the documentation, write a bunch of example bots and tutorials, and become the #1 ranked bot. If you are a mere mortal like me it may be best to sticking to just logging the metrics you want to capture and building something really simple to analyze those logs.

What did not work out well for me

1. Constant tweaking of parameters

I spent way too much time running matches with slightly different parameter settings, changing one in isolation, changing a few together, or revisiting the parameters after implementing a new feature. There is probably a scientific way to go about picking optimal values, but for me it was just a big time sink without any benefit realized. My limited time could have been much better spent.

2. Too many changes at one time

I've learned this too many times as a developer. Focus on one thing at a time. If you watch a match and suddenly have an idea for a new thing you should try, put it on a list of things to implement or explore later. Completely finish your current task first otherwise you are going to be doing too much context switching, be prone to not catching bugs as you are implementing, and having no idea which one of the things you are implementing made your bot better or worse.

Make each change as small as possible and then submit that to see where you rank.

There are several other things that did not work out well for me (I love to experiment with different strategies), but most of them are too closely related to strategy for this post.

Final thought:

I'm sure a lot of people think that watching the top players bots compete is the best way to improve. I would argue against that for a couple of reasons. The first being completely psychological. It can be a little disheartening and overwhelming when you look at the movement of the top players and think there's no way I can implement that behavior. Or you look at certain aspects of those players and try to emulate them only to find that your bot is actually worse. It can make some people just want to give up. The second reason is that none of the top players have the optimal strategy. First @djma looked unbeatable, then @erdman, @timfoden, and now @nmalaguti. Each player that takes over first place has implemented something quite different. It is possible to try and copy the observed behavior of the other top players, but remember it is a moving target. New top players will emerge because they came up with creative new strategies.

Hopefully this helps out some of the players just getting started. If you want to provide more tips in this thread, please try to keep them spoiler free (no tips on specific strategies or example implementations).

Thanks,
Chris


#2

One thing I'd add: it's great if you can make your bot deterministic in some sense, i.e. it plays the same game given the very same map and starting position (though obviously it will depend on opponents' actions) and/or makes the same move in a specific position, regardless of history. For one thing it means you can do code refactors and then easily check you didn't change behaviour. For another, if you find some odd unexplained behaviour in a game, you can probably reproduce it.

(To that end, I'd like to remind people of the Halite Reloader I wrote, which enables you to play on from a specific turn of a replay. You may need to supply some RandomBots on the command-line to fill the other slots.)

The enemies of deterministic behaviour are things like arbitrary order of iterating over a map/dictionary, and so on. You can still use pseudo-randomness, as long as the seed is always the same...


#3

Something else, I'm not well ranked but I have been able to observe some little things. I may be wrong, but I'm not competing for a job and I'm interested in discussing around halite strategy.

Remember that you don't have to aim for the control of all the map.

You just have to be the last player to survive. I've seen a lot of bots (I'm guilty too) which spend a lot of time on the borders, waiting to be strong enough to capture uninteresting squares while battle zones were lacking forces.
Furthermore, assuming enemies bots are not too stupid, it's usually more prolific to capture enemy territories than neutral ones. Indeed, you're more likely to find interesting spots into already conquered zones, particularly during mid-end game, and it's always better to annoy your opponents than letting them grow.
So, if you're strong enough to attack, be aggressive.

Chose the right battle formation depending on your forces and your production

(No sure of this part, don't take it as an absolute truth)

I've seen two main kinds of battle strategies. Flank against flank, where there is a large contact zone between opponents, and "piping" where a player deploys pipes to attack the ennemy on little spots.

I think flank against flank is better when you have more strength than the enemy because a large contact zone means you will be able to deploy a huge amount of armies per turn into the enemy territory. Nevertheless, if the battle turns bad, you risk to be countered and destroyed pretty quick, moreover creating a large flank requires taking a lot of neutral territory, which can be expensive and time/strength wasting.

Piping is more difficult to set up but can turn desperate situations into your advantage. When you pipe another player, you actually cap the amount of forces he will be able to deploy against you because each pipe has a capacity of 255. So, when you pipe someone you can win the battle even with less strength at the beginning, assuming you're productive enough.
The best way to counter piping is probably to take control of the enemy's pipes because trying to overflow the spaces around the pipes with your armies will be really damaging due to overkill.

A good bot is a sleeping bot

Each time a square moves, it does not produce anything. You should try to make your forces be as still as you can. We are tempted to move more often our most productive squares to support our other forces, but it's actually wasting production.

We can show that thanks to really basic mathematics: Let S be a square with a production of 10.
On 10 turns, if S has moved 8 times, the sum of S productions is 20.
On 10 turns, if S has moved 5 times, the sum of S productions is 50.
On 10 turns, if S has moved 3 times, the sum of S productions is 70.

I think finding a first good way to move as rarely as possible is to avoid long paths. Of course, it should be coupled with an algorithm to avoid losses when merging cells.


#4

Great post!

So incredibly true. I fall into this hole every time. Tweaking parameters without a rationale behind it tends to end nowhere - although I usually end up with a better understanding of how parameters influence gameplay which comes in handy.

Outside of very poor parameter choices (you'll know it was bad because the minute you change it the bot becomes way better) the only thing I've found that materially improves my bot is new behaviors.

Most of my new behavior ideas come from watching other bots and imitating them. Pick a part of the game you're weaker in and watch how others do it better.

  • Why is it better?
  • What does it accomplish?
  • How do they do it?
  • Can I do it better?

Just because another bot does something better doesn't mean they do it the best. Experiment yourself and see what aspects are important and which aren't.


#5

It's interesting to try out different formulae though. Having minimum strength for a movement depend on the tile's production or average map production, instead of a flat number that I'm sure most people use, for example.