Can we consider seeding the game with something truly random?


#1

The current game engine uses unsigned int time() as the seed which is unix time in seconds. This makes the generated maps predictable. There are only half a million seconds in a week so I could generate all the maps for the final week of competition and fine tune my bot for them.


#2

We also probably shouldn’t be sending the game seed to bots.


#3

Have they mentioned anywhere if this is intentional? It potentially adds a layer of strategic depth.


#4

If you have access to clusters of thousands of machines. Some of us don’t.


#5

@lidavidm any response from Two Sigma regarding trivial predictability of the maps?

Additionally the commit adding map seed to the constants sent to the bot is quite recent but short on details:


#6

Hello @AlanTuring,

Considering there are >0.6MM games/week, and you have a space of 20MB to store all your code and models, for you to accurately store that data you would need to be able to store all of each game’s data in 33 bytes. That’s 33 bytes to store ~500 turns and considering the random interactions between you and other players. Even if you could abstract that code such that each 1000 games could be stored in one meta representation, that’d give you 33KB per abstract game. Consider again that that is for 500 turns and hopefully >10 bot commands a turn, so even in that case you’d need to average 6 bytes to deal with randomness for each bot. That’s less than one long for each bot. Also note that this would not include your source code to deal with all that code. Even with encodings I don’t think that’s very feasible.

If you were somehow able to store all that, there’s still the problem of generating that and solving the maps and randomness in the first place. If you were able to do all that i would contently be the first to note that you have solved the game; and be happy to say so: here at Two Sigma, we love solving difficult, interesting problems. If you do solve that I would also posit there’s probably a good paper to be written about it (heck, this might be a whole dissertation-worth). So I definitely encourage that you try that solution :slight_smile:


#7

Here is an example of two different games seeded with the same seed, same board size and same players:


Results are roughly the same.


#8

It’s the end of 2018 and this issue has not been solved. There are 8 likes on this thread and a pull request trying to, at least partially, address the issue - https://github.com/HaliteChallenge/Halite-III/pull/121 and I am being asked to solve the game in order to prove using only 86400 consecutive and predictable values, out of 4 billions(0.002%), in the last day of the competition is a bad idea. I think Brandolini’s law would apply to the situation quite well.


#9

I was just thinking about how I’d gain a practical advantage here, and I reckon I could. What I’d do is:

  • Run two versions of my bot for every seed in the last day of the competition (my rough estimate is that this would cost hundreds but not thousands of dollars/pounds in cloud computing).
  • Store the winner for every seed, along with a hash of the map.
  • In competition, look up the winner and use that version.

My guess is that this would cause a very small but positive difference in my final rating. I think I’ll choose not to spend 10s of hours and 100s of pounds in this way, though :wink:

(IMO, it’s vanishingly unlikely that anyone actually exploits this, and even less likely that they gain any significant advantage. But I’d probably merge the PR switching to milliseconds, because why not?)


#10

Note the PR also mentions “This issue came up when I was testing using the Halite III gym and getting “runs” of wins that were much longer than statistically expected.” which may be responsible for slow convergence of the score and a suboptimal experience for the players.


#11

For the record as the creator of the PR, runs are probably not going to be that big of a problem on the servers. My problem with run lengths were due to games running less than a second because my bot would sometimes crash on startup. I do not know the rate of game creation on the server, but I doubt runs of the same seed are actually a problem on the server.


#12

These two statements seem to contradict each other.


#13

What would happen is that the my bots would sometimes crash on startup, either letting the other bot win or letting the winner be determined randomly. When the same seed was used multiple times, the exact same crash/win pattern would repeat itself, leading to the “runs” I described earlier. Nevertheless, I do not believe this would be a problem on the game servers.


#14

I put a PR - https://github.com/HaliteChallenge/Halite-III/pull/198/commits - to fix this using time in nanoseconds.


#15

@AlanTuring I don’t really think the seed thing is a big issue. It’s kind of like what j-clap said - I feel like its almost impossible to come up with a way to produce an advantage out of it. And it’s like if you did come up with something that was able to exploit the seeds, that’d actually be kind of cool.

Even if you did the thing teccles suggested with choosing a superior bot version per seed, all you know is that the version A beat version B on that map, but you don’t know if version A actually has a higher win rate against all other bots on that map.