Halite Home

Introducing (unofficial) Halite single-player mode

#1

Official SPM Record Holders:

-d "50 50" -s 123456789 -- @cdurbin -- 154 frames

-d "10 10" -n 2 -s 1886238180 -- @pepijno -- 54 frames

There is a really interesting algorithmic sub-problem inside the Halite game: setting aside the other players, what series of moves will allow you to mine the nearest squares most efficiently and most quickly? This question is not just academic; ramping up your controlled territory and production quickly may in fact be the key to the whole game (speculation). In any case, if your bot can mine more efficiently than the other guys, you're well on your way to a winner.

In another thread, ppl were asking about additional Halite challenges. So, here's my challenge for you: Halite single-player mode. Here's how to play: someone nominates a board size and seed, launch the (patched) Halite game environment on your local machine with the spec'd size and seed, along with a single bot. Whoever can mine all the productive (ie production > 0) squares in the fewest frames is the winner. The zero-production squares are optional; you don't have to mine them to finish, but you aren't penalized if you do (I feared that a requirement to mine the zero-production squares would break some existing bots, like, say ... mine). There can even be two categories of competition: timed and untimed.

Unfortunately, single-player mode is not available in the current Halite distribution :frowning:. However, I just submitted a pull request :slight_smile: , and I hope @truell20 and @syriax see value in this, and get it out to everyone. The commit to enable single-player mode is all of 8 inserts and 2 deletes. If there are delays in getting this committed to Official, you can download my fork of the Halite game environment from my github account, which has the patch needed to enable it.

Challenge #1:
./halite -d "50 50" -s 123456789 "python3 MyBot.py"

My current production bot completes that level in a sleepy 206 frames.
@nmalaguti's ProductionBot bests me at 201 frames.
@nmalaguti's DiscerningBot gets there in 195.
One of my older bots (~v8 I think?) does it in 172, so I guess that's the world's record for now. I have the .hlt replay file for proof! But I bet some bots can go a lot lower. I'm really interested to hear how low. For bonus points, what's God's Number for this map? :wink:

Also, would love to hear from anyone who can tell us: the Halite single-player mode game reduces to which well-known NP-hard / NP-complete / some-other-complexity-class problem?

Will there be a sequel?
Perimeter Optimization during Expansion
Early, Mid, and Late Game
#2

Just to note when trying to install your fork on OSX, I got the error below, suggesting the distribution is for linux.

fatal error: 'sys/prctl.h' file not found

I was able to install after replacing the edited files from the fork with the official distribution.

206 is impressive. The RandomBot starter gets it in over 300. My current bot times gets it at 237. Also noticed that single-player mode doesn't end the game once the bot has timed out or received an error though, which is probably an easy fix.

This is great for training as it removes the complexity of having rankings of various bots and scoring accordingly. Also it helps make sure that bots don't time out on large maps.

#3

One of my bots I'm currently working on did the challange in 168 frames :wink:
A hlt of the game can be found here.

EDIT: A visualization of this game can be found here.

#4

Wow, 168 is impressive. But if you look at the last frame, there are still unconquered squares remaining. To be fair, just from eyeballing it, it looks as though they would be conquered in the next 2 or 3 steps

#5

I think those squares were zero production squares.

#6

Will totally merge if stable. We were hoping someone would make a single player mode. Have you checked out @breeko's error, @erdman?

#7

Could you post the replays of your bot and @nmalagut's bots completing the challenge?

#8

@breeko's error appears to have come from the Install a parent death signal in child processes PR.

That header and API is only available on Linux. A PR to fix is here.

#9

One of my older bots (aka BetterBot) does it in 176.

However the my best bot of the BetterBot lineage (FrugalBot) did slightly worse at 178.

My current bot (aka DoubleBot) does it in 186. Looks like I have some work to do on my heuristic...

#10

Merged your PR, @nmalaguti.

#11

I managed to achieve 173.
I will try to break the record tomorrow. have you guys made any progress over the weekend?

#12

Just now, I beat my own record, my bot now takes only 163 frames.

#13

Thanks for adding this feature. My bot was at 173 when I first found this yesterday, now is at 161 after some simple fixes. My bot is still not very good at early game production a lot of times - it just happens to work ok on this map.

I was wondering if anyone has any suggestions for additional maps to try.

#14

now is at 161

Would you mind posting a replay?

#15

Here's a link to my 161 frames finish.

If there's somewhere official we can put these replay files I'll post it there.

#16

If there's somewhere official we can put these replay files I'll post it there.

  1. You can upload the replay file directly to the forums. Others will be able to download it.
  2. You can self-host and post a link to @nmalaguti visualizer. Ex: https://nmalaguti.github.io/halite-visualizer/?url=https%3A%2F%2Fhome.a-eskwadraat.nl%2F~pepijno%2F1481037923-123456789.hlt

(I think @nmalaguti might also provide hosting though I don't know details)

#17

142056-123456789.hlt (3.5 MB)

Thanks, I attached the 161 frames replay file here.

#18

Nice job, @pepijno and new SPM champ @cdurbin! Impressive results. I finally just broke 170, my current production bot can do it (not every time) in 169. But that's the best I've been able to do (so far!)

There are some new features that have been merged into the Official Halite github account that relate to SPM. To access them, clone the project and build the environment (not sure when they'll be available on website for regular download). The new features are:

  1. Single player mode enabled via specifying a single bot.
  2. Frame counts for each bot is reported at the end of match in both Verbose and Quiet mode (helpful for regular and SPM)
  3. SPM players have access to the same multiplayer maps you see in regular competition. See the --help file for the "-n" argument. Specify the dimensions (-d), the seed (-s), and the number of players (-n), then specify just a single bot, and you'll be playing a multi-player map in SPM.

There are two ways that I find SPM useful. The first is that, on some maps, 4 out of 5 players go a certain direction in the first 50 frames, while the one other player goes a completely different direction. Sometimes this works out for the trailblazer and leads to an amazing victory; other times, not so much. Replaying such a map in SPM makes it easier to investigate such behaviors. For example, I definitely did some investigation on this one: https://2016.halite.io/game.php?replay=ar1480621570-314927181.hlt . (40x40, 2player, seed 314927181, my best clear is 170).

The other is that I'm particularly intrigued by the first ~50 moves, even when both bots are pursuing same general plan. I think the speed and efficiency of those moves can sometimes make-or-break games, even before contact with enemies has occurred. My bot definitely lags in this area. So, to best replicate early game moves, I'm going to be looking at small maps, say 10x10. Here's one:

./halite -q -d "10 10" -n 2 -s 1886238180 "python3 MyBot.py"

My bot does it in 64 moves, but I get schooled by OverkillBot, who knocks it out in 56. Watching his replay (and knowing the botcode), it looks to me that there is a lot of room for improvement, so I'll bet several of you can go way lower. (If you mess around with smaller maps, you'll find it's a lot easier to run into the cap on number of moves, which is 100 for a 10x10 board.)

#19

148622-123456789.hlt (3.5 MB)

I tweaked some parameters for my bot and managed to get down to 159 frames. I think that's the best I can do without some changes to my heuristics.

#20

Thanks for the new map suggestion. I really like the idea of trying to better understand my moves in smaller maps.

I'm at 57 right now, and I clearly see some bad moves. It will be fun to try to see if I can improve.