Feel free to send your feedback or ask some help here!
Preview:
Related Post :
3 Likes
Anyone have any memory-conserving tips for this challenge? I seem to be hitting a ton of timeout problems due to garbage collection after generating a ton of solution states. Each one has to make a copy of the previous state’s list of bombs, items, players, and boxes on the field. I clone every item on each new state’s generation to ensure that I don’t modify a previous state’s data. Any tips would be appreciated.
1 Like
If garbage collection really is the issue, you could try using an object pool for the states.
1 Like
How do I recover the last revision of the code I used in the contest? I wouldn’t like to start from scratch. 
Go to the “Past Contests” and click on “View Report”: https://www.codingame.com/contests/finished
1 Like
Thanks a lot! 
can i anyone tell me a good strategy for hypersonic i am stuck on wood 3 for forever
Read the latest blog!! lots of good ideas and info in there.
Is it possible to get other submitted code? I had to roll back some good changes due to a bug at the 11th hour, so my final code isn’t really my best.
Really interesting question.
Had the same issue when playing with STC a few months ago. In each node of my tree, I was storing the gamestate which had been generated by applying the “game logic” to the previous gamestate and the chosen “action” (for reference I was trying MCTS).
Advantage was that to explore further from this node, you don’t have to simulate again all the steps of the path from the root up to the node, you just start from the stored gamestate, so it’s a lot of time gained.
Disadvantage is the time it needs to properly clone/copy a gamestate before starting to apply the game logic, AND the very same GC issues I had. At some point even with a good 30 ms margin (!) I was still having random timeouts.
Maybe GC issues could be solved with “pools” as proposed by reCurse.
I’m wondering if it’s always better to store the gamestate, or always better to NOT store it and recompute from the current gamestate, or if it depends on the game 
What are the top players doing ? Any advice ? 
1 Like
Depends on the game and whether you think going for a depth-first strategy is better over a breadth-first / best-first strategy. In the end it’s very similar to optimization, profile and tweak until it comes out better.
1 Like
OK thanks.
Just to be sure, in general you would NOT store in a DFS, and store in a BFS, right ?
About tweaking, should not take too much time to have both options ready for evaluation indeed.
Finally, just coming back to the “pool”, do you have any reference to share or general guidelines on how to implement it ?
I see the global idea, but never implemented it.
Generally yeah. Best-first is more situational depending if you want to do backtracking or not. You may also want to use a cache to store the first or two depth of the DFS.
I don’t really do Java so I can’t provide you with an implementation, and what I found on Google was unsurprisingly very enterprisey. But it’s rather straightforward actually.
You want to pre-allocate a large enough number of objects in an array, stack or queue at construction. Then you will call a method like Acquire() on the pool instead of newing the object, which will return the next free object in the collection. Then when you are done, you call Release() on the pool to put it back in the free collection.
You have to be careful to correctly initialize the data after Acquire() because it is very likely to be recycled and will not be in a clean state like a new one would. Depending on how you do it, this step alone can end up more costly than the added weight on GC so you have to design your structure in an efficient way that works with minimal initialization.
Make sure to do sufficient profiling and testing to conclude this really helped. Otherwise just get rid of it and keep your code simple. And maybe a better strategy would be to not need so many objects in the first place.
4 Likes
I don’t think it’s possible at the moment. Better keep your own history (git, svn…)
Yep, I did that with C# to overcome the high costs not only of the GC, but the object creation.
Visual Studio Community has a profiler, and you can see what takes most of the time.
For me it was the creation of new states.
I first tried to preallocate a lot of objects for future use, but that wasted a lot of time too. If the game doesn’t depend much on the first turn yeah you can do it then. In the Accountat that wasn’t possible.
What I did was a “create” and “destroy” functions,
The create function first checked on a queue if there was any available object, if not it will create a new one. Then it will clean up the object as needed. I don’t use constructor directly, the “create” function do it.
And the “destroy” one did the oposite, remove any links to other objects and put it in the queue. The object is just moved to the queued, not destroyed.
And in C# there are also some commands to control the GC a bit.
Anyways on managed code (Java, C# et al) this is a problem you can’t really solve, you must optimize the strategy to avoid that many objects.
And profilers help a lot on bottlenecks.
1 Like
I definitely need to pull my code down and try to run the Dart analyzer for it. I switched to a Beam Search that is only keeping around a specific number of states after each depth, and that seems to help with the memory management, so I am getting fewer timeouts. Now I need to improve my GC.
Thanks for the tips!
I’ve just posted an article about the contest, and now the multiplayer game, Hypersonic.
All the code is on my Github too, for those of you interested. There is a Javascript version, the one that reached gold during the contest, and also a work in progress with Java. I will post a second article about the java version soon.
The Javascript version is probably a bit different from what I can see on this topic. There is no decision tree, and I do not simulate turns ahead. So maybe it gives a few ideas now that the Gold league is open.
Here it is: http://salvatorelab.es/2016/11/hypersonic-game-programming-a-bot-for-fun-part-one/
6 Likes
Nice article, but I don’t think they like you put all the code available.
With basic 1 ply strategy you can’t beat a classic AI (with DFS,BFS, GA and such), because they are calculating N levels ahead.
I’m still at bronze because I don’t even have a bot yet, I just have a walking bot that just place bombs everywhere. Even with that I’m not the last! I think thats because others in bronze are even worse than me (=suicide themselves)
P.D: Shurmano!
Hi TheBronx,
Nice article. I don’t use a decision tree either, for the moment. I’m in the 100 position in the global currently. I will see if I can improve it before to use a “brute force” method.
Happy coding!
1 Like
It would be interesting to see code from other players. You can read/watch how DFS/BFS is done all day and still not be able to implement it for Hypersonic. How can somebody still learn in such a situation? For training puzzles you can see other implementations once you passed your tests. Something similar should be available for multiplayer games. If one is in the Bronze League why not look at code from Wood for example? I am sure many would benefit from this. Otherwise you might be stuck forever at you current level.