Hello everyone !
Until now, I could success in AI Battles without managing timeouts. It means I adjust parameters so the programm answers before timeout. But now I feel I will need to optimize the few ms I do not use.
How do you manage timeout ? I use Python, but I guess tha way to do it is somehow the same for every language.
Usually, the only part of the bot where you should need any time management is your search algorithm. Most good CodinGame players manage time in their search algorithms like this:
while (still have time left) {search a bit more of the game tree}
In practice, this can be checking how much time you’ve spend after every MCTS rollout, or using iterative deepening with minimax, or looking one move deeper with beam search, or…
On CG, it’s important to know that sometimes the VMs can randomly pause your program for a couple of milliseconds, making you lose time (losing 5ms randomly is not uncommon, and I’ve seen 20+ms in some contests) and potentially making you time out, so it’s wise to leave a bit of a buffer. Also, your program will run on multiple different VMs, and in the last contest some of them were more than 2x slower than others for many bots.
If you want to know how much of an impact will using all the available time have: during the olymbits contest, I tried submitting my bot with a 5 times lower time limit, and it ranked approximately 2 rating points lower in high legend. It’s definitely significant, but don’t expect miracles.
Finally, using Python and then trying to optimize your code to use all of the available time is probably misguided. Python is so slow compared to the other options that by choosing it, you completely give up on performance.
2 Likes
Thank you very much for your answer. If I understand well, I get a t0 at the beginning of the turn (with clock() in C for instance). I perform some search. I do a new clock() : if there is time enough, I do some more search. The point is : the “some more search” must not be longer than the remaining time.
I realised Python is very slow and I started to learn C. Actually I wrote my first lines of code a few days ago and could succeed in resolving the problem. I did so because Python timed out. C is at least 10 times faster.
I’m currently trying to be better at Fall Challenge 2020 (witches preparing potions). My algorithm is a beam search with some bugs, and despite Python is slow, I would expect to progress in gold league. But I encounter to many timeouts.
I don’t feel comfortable enough to code a whole AI in C. But, of course, if I want to get better ranks in contests, I think I will.
This is not totally obvious (and you should experiment anyway) but starting your turn clock immediately after receiving the first bit of input from stdin that turn seems reliable. Earlier than that and you end up measuring the previous turn, even though your code has completed output for that turn. Sometimes you can appear to go over the advertised limit without problem but it’s risky even going close to it because of the random pauses @blasterpoard mentions. And ultimately in the middle of a busy competition you might still have to accept the odd timeout rather than compromise your compute too much. Getting the risk right arguably depends on the type of battle.
If your language has several methods of measuring time, again experiment with them all. Some can be a lot more costly than others.