Fair shipyard placement in 4p


#1

A thought come to my mind: having 2 halite games with the same complexity it’s desirable to choose the flavour with smaller mu variance. This simply shortens the time to converge, makes it more fun for humans, nobody likes to wait.

4p has bigger variance than 2p. Not only 4 players, but also their “fair” placement on the map is harder. The definition of “fair” would be: every player has the same area (number of closest points to shipyard) and the same border size to all its enemies.

Especially when one of the players e.g. times out in the beginning. So currently the diagonal players share only 2 points of their area. However, with side neighbours they are sharing 2 sides, that’s much more. So if diagonal players times out, we are in big disadvantage - there is no way to go to that area without going through the area of our side neighbours. They don’t have this problem though. This increases the variance dramatically, since now in our set of games we would need to have similar games, but with our side neighbours being in unfortunate position. That usually doesn’t happen in couple of hundreds games.

Can’t we place 4 shipyards better?

Now the opposite players share 1 point and a side of length N. With a side neighbour we share a side of length N*sqrt(2)/2. So it’s not perfect, but way fairer (definition of “fair” as before) than current design it seems. So maybe for halite 4 : )

I didn’t find a 100% fair partition of a square. It doesn’t seem to exist, but maybe you can provide a proof for or against. Here was one idea (cheating a bit), dark player area is a triangle with equal sides. The white space is no-mans land, turtle gets teleported to corresponding border point when it tries to go on them: