Resolving partial ties


#1

I've been trying to optimize rushing strategies in 4 player games and I have noticed that with all 4 players running the same bot that positions 3 and 4 frequently rank lower than positions 1 and 2. The effect vanishes if I turn off rushing. I've also noticed that pairs of players frequently annihilate each other when they both rush.

Question: if one pair of players ties (say 1 and 3) by early mutual annihllation, but the other pair has a well-defined winner, how are the annihilated players ranked at the end of the game? It looks like by player number without shuffling. Am I wrong?


#2

I did some digging, and what you're describing seems to happen less than you think, given that the 2 rushing bots are 2 different bots doing their own thing.

Anyways, I searched for some empirical data and went through the replays of some rushers, and found no games, but I have seen it before, so I dug into the Halite GitHub code. Here's the link, just Ctrl + F and search for "ranking."


#3

Oh, and to answer your original question, it looks like the players are shuffled in the beginning of the game so any "dead ties" are resolved by the RNG of being first in the shuffle.


#4

The final tiebreak when all the other factors have been taken into account is randomly assigned1 at the time of the tiebreak. But note that like other random things in the game the game seed is used to initialize that rng. So if you replay the game using the same seed the same player will always win the tiebreak.

Having said that, there was one other report from a windows user that particular bots always won the tiebreak (e.g. bot 0 always beat bot 1). But it only seemed to be reproducible using a particular bot if his. Specially created bots to test it didn't seem to be affected and looking at the statistics from official game server games also shows the tiebreak being distributed evenly. So there might be something weird going on with windows and if you find a way to consistently reproduce it maybe someone can figure out what it is.

1 Specifically by shuffling the players that have ended on the same turn before stably sorting them by the other criteria, this is done starting at line 1086 of Halite.cpp


#5

@Janzer, @RyanDraves Thanks for looking into this, I think I have figured this out. What I seem to be encountering is that if players 1 and 3 and players 2 and 4 rush each other, according to my combat code, the initial conditions cause players 1 and 2 to win every time unless there's an obstacle between them. So I added a random displacement to the first move of every player (not much), and the ratios now ever so slightly favor the bottom players (3 and 4). This came up during backtesting and watching my bot get slaughtered rushing other bots where it destroys all of my previous bots.

And if you watch any of my games where my bot comes in 4th, it's usually because it rushes too aggressively. Also, I suspect that up against other bots who are not attacking their nearest neighbors, this wouldn't apply. I am working on a countermeasure for this right now. I have seen @arjunvis counter me very effectively and if that's from his underlying model, that's awesome (it's still cool if it's a hacked rule, but it's awesome if the model figured this out!).

PS I am happy to share source code (though it's ugly as I am experimenting with a lot of things) if you want a repro of this behavior, but I'm not sure it's a bug in the engine so much as it's a feature of its deterministic behavior and deterministic starting conditions. That said, it would be nice if it were more random given different random seeds (maybe give the ships random displacements within + or -1 of their otherwise constant starting position?).


#6

Fascinating @scottlegrand , I hadn't noticed that but yes , it's just emergent behaviour of the model , it has not been handcoded. Nifty.

My bot is very bimodal and does some clever things but also very suboptimal things. Sadly my cores are engaged on a different core-smoking problem this week so it will be a couple of days before I get back to halite. Till then my halite contributions will be merely chatter on the discord or posts here ... Have a great weekend all


#7

Yeah, there's a lot of ways that what looks on the surface to be a tie is actually won by one side or the other because of overkill damage or such. Unfortunately the visualizer doesn't do a great job of showing what caused one bot to win over another at times.

Sounds like you got it figured out anyway.