Thanks everyone for playing 2279 players!
You can share your strategies and ideas in this thread, but please don’t share runnable code as the game will be published as a multiplayer soon!
Thanks everyone for playing 2279 players!
You can share your strategies and ideas in this thread, but please don’t share runnable code as the game will be published as a multiplayer soon!
Name an algorithm or approach you used here.
Anything from BFS to Minimax.
What was useful and what happened to be of no practical benefit?
I’m only bronze. I’m not saying the contest was bad, but the lockdown has a very negative effect on my motivation
Thanks @Illedan, @eulerscheZahl and @G-Rom for the wonderful contest. Awesome rules and brilliantly designed. I was late to the contest and only managed to rough out a code to get me into mid wood 1 but will look forward to reading the top player`s post mortems and playing it as a multi.
Thanks again !!
C# ending (hopefully) top 20 after the rerun
Mostly hack around spagetti, trying stuff while also keeping an eye on the contest code, fixing bugs and rewriting the whole contest code for my own sanity. (code done in 2 days without tests )
Get that tracker working… Made as most top players a tracker following the game state from every possible starting location, expanding on silence and removing invalid states. Did about 3 full rewrites of the tracking…
Add a big block of InstaKill code which does combinations of torpedo, move, silence and surface. This was enough to get back in the game and into Legend.
Feel the lack of motivation rising and trying to rewrite everything as I add more ifs and stuff to the spagetti.
Every game state contains all the visited cells up to that point, health of the player, current position and locations of when mines was dropped.
I pruned opponent location based on them being on top of my own potential mines or not. And reduced the pruning if there was no possible locations left.
Also used the same tracking to track myself.
Run a depth 4 DFS with a score based on:
Find the target hitting the most enemy locations. Only fire if I can hit all targets or if I don’t reveal myself more. Try this before and after the move logic.
Trigger if there a mine can trigger more than
enemyLocations/coeff, where coeff is 1.55 at the start and increasing every 50 turns to trigger more later.
Only place mines if they can target 4 or more new cells given my other mine blast radiuses.
Except for InstaKill, I only silence with a length of 0, but only if there is more than 4 possible cells in both N+S and E+W. To give the most options. Silence is only done after the move logic.
Only when there is less than 4 moves left in my FloodFill territory.
I also started a big rewrite into some MinMax bot, but my motivation stopped me in the end.
Will see if I manage to finish it later
The idea is to play my bot with about 60 possible sequences of actions (all move directions, silence at 0 or max depth in every dir, torpedo the best position, trigger the best position, surface)
And the enemy with a branching of either:
Golang ~165 ish
basic “out of bronze to get every rules” bot : spam silence, basic detection, torpedo if in range
Rewrite everything, computing my possible positions as well (to be as silent as possible)
Movement decisions using beam search depth 5 size 20, with an evaluation taking into account both accessible positions with floodfill, my possible positions as seen by the opponent, and distance from enemy possible positions (average).
Never use sonar
Use silence if my possible positions < 3
Use torpedo if torpedo can hit at least all enemy possible positions
Mine otherwise, and trigger if enemy might be in range
Order of power : Torpedo > Silence > Mine
Didn’t change anything, force submit to reset derank from pushers
30 days is too long for me to get focused for the whole contest ahah
Very good contest:
I finished 28th.
Not much to say about my bot: tracking the opponent actions and using heuristics to determine the next move. Tracking myself as well to hide my location when choosing the next move.
But here is an animation for this game
Numbers represent the danger to get damaged by a mine, small red dots are my own locations as seen for the opponent while gray circles are the opponent locations.
I also generated some statistics about the gameplay of different users: https://eulerschezahl.github.io/OceanOfCode/ooc_stats.html
So as an author of a gold boss I have a few things to share.
I think most of features that are considered to be basic among legend players aroused in the duration of contest and gave a push for people who implemented them first, even if not in the most optimized way. Here goes a credit to @mchl12 for quite convenient implementation of self-tracking for estimation of all the actions in terms of giving up information about yourself, and, more importantly for implementing the killing blow or, as I call it, FATALITY. These features gave him a solid lead in bronze time, and even without improvements for the second half of the contest he still made it to gold, I believe basically with the same bot.
For me such a feature was mine avoidance. Silver was the time for most people to realize that some kind of mine avoidance is necessary. My first implementation of it was based on estimation of directions by flood-filling sum of the damage with discount. That was only a bit more effective than simple checking adjacent points, although it gave the possibility to estimate if you need to SURFACE not to go to the mine field. Being limited with python speed, I looked for a more precise and in the same time not very consuming algorithm. So the second implementation of mine avoidance aroused in the discussion with BorisZ and stayed this way for gold boss and almost the same in my final bot. The basic idea of it was to generate a bunch of valid random paths, and check the damage on them with discount, choosing an optimal path. I was able to generate only around 50-100 paths of length 15-20 in 5ms, which although was quite enough. Not to underestimate the damage, I greedily choose the maximum length path, and then minimized the damage. This path I did not just follow, but rather used as estimation of a direction and of necessity of SURFACE. Quite important thing here was not to prioritize mine escaping when there are too many candidates, not only because it is require some heavy computations, but also because it could lead to some suboptimal moves. So in the mean time I would rather just minimize the information given. This simple estimation together with other basic features gave me a solid lead in silver which I kept almost to the time gold was open. Around that time other players also come up with own effective mine escaping. With some minor improvements this bot became a gold boss and for a time being did guard legend pretty ok.
I also tried to resubmit the gold boss after 4 days in legend and in the last day of the contest. First time it landed around 12-15/35 and last time 40-50/60 which kind of made sense since late comers could optimize against boss and top players improving their bots quite significantly.
Couple more simple things I’d like to cover. One is handling spam silence in python. Tracking of all the paths possibilities when the opponent uses silence too often is almost impossible without pruning at some point even for more fast languages, so I made merging of the paths that come to the same point by keeping only common parts of them with summing all the mine planting positions for these two paths. The tricky thing is that if the damage was taken in the same turn SILENCE was used you can not tell for sure if the candidate is have to be pruned or not. This imperfect silence handling lead to losing some information, but occasionally it is quite enough, and the results are almost the same as for perfect tracking when it does actually matter (<~15 candidates).
The other thing was targeting SILENCE 0. Zero length is quite easy to use, do not require any estimations and you basically cannot harm yourself jumping to the mine field or in the dead end, so it was used widely by many people including top players. More importantly for me it was used by @kovi and I had 0/32 wins against him, so I decided to do something about it. Basically after opponent used silence once I tracked if the SILENCE 0 candidates will survive and based on that increased the weight of these candidates heavily, if, occasionally, opponent would use another length, the zero length candidates would be pruned and weights normed back to normal. This worked quite well even when opponent did not start to use SILENCE 0 right away, using different length at the start of the battle. The only thing I regret turning it off for gold boss submission, I guess it would be quite fun forcing people to use non-zero silences. In the end I weighted all the length with different weights based on @eulerscheZahl 's stats collection (thx :P), which actually helped a bit.
For my legend bot I basically did not add much, mostly working on mine placement and trying to control territory while in the same time "flattering" the opponent damage map, in a sense of reducing gradient of a damage map to get a better covering without much overlapping of a mine ranges, which also gave a clear strategy when to hold mines without spamming and some space for using sonar due to not overcharging mines. Also I think that important addition was to hold mines to place them after silence. That hits heavily on damage estimation of an opponent and looks quite dirty.
Overall I am quite happy making it to top20 on my first contest and winning a t-shirt. Thanks to all the community of the #world and #ru chat who was quite supportive and made it much more interesting to participate with all the interesting discussions and ideas, and also to @Illedan, @G-rom and @eulerscheZahl for making the contest. I think it is safe to congratulate @pb4 with a win, even though top4 is really close.
Thanks for the contest, guys!
It was fun. There are a lot of possible strategies and no need to write simulation - that my favourite kind of game. I was improving my bot till the last day and still there are thing to work on.
Pretty unhappy about not hiting top-50, but that’s life.
Looking forward for your next contests
Grats on your result wlesavo. Funny thing: Last night at 2 am or so, I coded a silence with more than 0 distance and I think that helped me a bit. Good find!
Thanks for the amazing stats and gg on this featured win
Most of my bot was basic stuff and a lot of if-statements but the best thing I did was modification for floodfill movement where it favoured squares with more previously visited neighbours. Made for a more compact movement and harder tracking by the opponent.
Also I believe trying to take ‘control’ of the middle was important in the start but I didn’t quite manage to use it as well as I wanted.
Nice challenge, cheers!
Thanks for the contest!
I feel so happy to reach the top 20 for the first time!
I personally used a kind of MCTS to find the best actions.
In UCT, the exploitation term mean (score/visit) is balanced by the exploration term.
I replaced the mean by the best score of the children.
And in each evaluation, I have a (poor) simulation of opponent play.
I loose time to evaluate every single step, but using an UCT, I don’t loose time to evaluate not promising nodes… Not sure it was the best approach, but it worked not so bad…
I also used some map of probable damages: one for opponent mines and another one for opponent fire damage.
Hello everyone, I came back on CG for this interesting contest. I really enjoyed it even if I would have loved reaching legend. Thanks @Illedan, @eulerscheZahl and @G-Rom for this contest inspired from the game, updated rules were pretty well balanced. GG
One month was perfect for me because I can’t connect a lot, this let the time to come and improve my code from day to day.
It was interesting to find a good strategy to follow and try to implement it. The bad thing on this contest, it is hard for someone who try a contest for the first time to code some ‘basic features’. I spent most of my time in the code to find the opponent according to its/my actions (and debug it BTW ^^).
I was working on a correct way to avoid opponents mines. It started working but didn’t had the time to finish it. Can’t wait to have this game in multi to finish my last features.
Thanks to this contest, I discovered the game “Captain Sonar” and really want to try it!
See you soon!
I ended 25th. Very happy with the result. Thanks to the creators for coming up with a great contest to spend the lockdown.
For some reason this contest failed to motivate me for 75% of the month. Not because there was anything wrong with it, but because I had other things that drew me away. I liked the information aspect of it, the tracking, eliminating paths etc. I had less fun (and less skill) with the strategic logic. Here’s the general flow of my bot:
Bitboards: I thought it was essential. For tracking I kept a 64 bit (* 15) minemap, a 16 bit map with visited cells and a single position for each possible opponent state. A quarter of my code is just a lot of helper functions for these bitboards. Copying, combining, adding, removing etc.
StartCell: My start is fully random, except that I don’t start in closed off sections of the map (you can check this with floodfill). I assume the opponent can start on any cell, meaning I start with 225
(minus islands) possible states for tracking.
OpponentOrders: The most important stage for tracking. For each state, I process all opponent orders and if one of them doesn’t match up to reality, the state is removed. There are two ways in which extra states can be created.
I also tracked all damage forms on a damagemap and any cell that got an amount of damage that does not correspond to opponent health lost, has its states removed. It’s also important to make sure you floodfill the cell torpedoed by the opponent to see where he could be.
A major issue in this game is chain-silence. It can time you out easily. I have a limit as to how many states are allowed to exist. If there are too many, i combine the ones with the same position and mines and combine their “visited” histories to only have cells that all cells share in their history. I also do this for self-tracking. I silence more than most players and if I didn’t prune, I would time myself out as well .
Mine avoidance:: Since I have a bunch of states with mines laid from various cells, I can combine this information into a mine probability map (where are mines likely to be?) and a mine probability damage map (which cells are those mines likely to damage?). I use a beamsearch to navigate the map, avoiding cells with high probability of mine damage. I also combine this with a floodfill-score (to keep room for myself to move and not have to surface) and a self-tracking score (so as not to give my position away).
Self-Tracking: Similar to opponent tracking but with a key difference: I don’t track mine-triggers. This was mostly to keep the complexity of my code smaller, but also to conserve calculation time.
Fatality!: I love this part of my bot. It simply brute forces all possible actions and checks if there is a guaranteed kill. It will also surface if necessary, silence-dash to the opponent, combine mine + torpedo damage and even damage different parts of the map if the opponent position is not yet determined. It could theoretically damage 18 cells just to do 1 guaranteed damage to the opponent and kill them if it is possible.
Ability Charging: This is the first area of the game where I didn’t really know what to do. In the end I preferred torpedo, then mine, then silence if the amount of cells where my opponent thinks I can be, drops below a certain value. Otherwise sonar.
Overall Action Logic: This is the second area where I tried stuff and did not know what was best. I think I got a reasonable set of heuristics in the end, but it could be much improved.
Make an opponent-probability-map. That is for each cell, calculate the likelyhood the opponent is there. This is necessary for other logic.
Check if moves are even possible (in case you need to surface). If not and you have more than 1 life remaining, then Surface.
If you have moves available (also after surface), do the earlier explained beamsearch to get a movement direction.
Check the best targets for a torpedo before and after the move and determine which is the best “shot”. If the score is above a certain threshold, launch the torpedo before or after the move (preferring before the move, on equal score). Score is determined by the target cell with the highest expected opponent damage (using the opponent probability map). Don’t shoot yourself…
Check the best targets for a mine-trigger and see if the score is above the mine trigger threshold. I also check if I need to move out of the way (trigger before or after move). Score is determined the same way as torpedo score, but the threshold is a bit lower. This is because torpedo’s reveal your position more strongly. I noticed a high torpedo threshold is very important.
If silence is available, check if it is worth using, meaning, does the opponent get more cells where it thinks I am (at least 4 more) and am I even below a certain value on this (below 30 self-tracked cells). So basically: Is it necessary to silence and does it even help me at all?
One of the last things I coded was a non zero distance silence. This to possibly avoid a bad position with mines. I don’t think it happens often, but it does happen.
Lay mines when if I can, but not when there is too much overlap with other mines. Try to lay mines that cover more available ocean.
If sonar is available (almost never). Use it only if the opponent could be in more than 1 sector and pick the sector with the most states.
If there are no orders recorded yet (because I can’t move and I can’t surface or I would die), I start blowing up mines.
That’s most of it I think. Works quite well, but I think in the end I wrote a heuristic bot and the trick to being in the top 10 is probably a more flexible search-based bot. People talked about battle simulations on the chat. That is probably a necessary component. Other than that I could have watched more games and added more heuristics. One example of this that dawned on me while writing this, is that I did not consider laying a mine before moving. Maybe that would sometimes be good.
Thanks to @Illedan, @eulerscheZahl and @G-rom for saving our lockdown month and one of the best MULTI CG game (simple but full of possibilities)
I finished #8 and 1st in java. Really happy about this result.
One of the hardest thing in java CG MULTI is dealing with garbage collector timeouts.
This time i used mainly primitives and byte arrays rather than objects.
For example :
I learned this by making UTTT legend which is the best MULTI to improve in coding java CG MULTI.
The heavy work was done during the first two weeks :
I spent the last two weeks on the “evaluation” (it became a bit boring but i tried my best to keep my ranking)
I struggled a lot with the size of my code.
I tried to code cleanly, but after two weeks i had to remove all spaces, “useless code” (like public, final…), even reduce the class and variable names when bundling my classes in one file.
At the end it was a bit blocking, i would think twice before starting a big improvement.
Just few questions.
Previously we were waiting around a month between the end of a contest and the opening of the game as multi. Is it still around a month?
Second, does anyone already tried to use the referee java code to perform local tests (Me against myself)? I really would like to finish and validate my last features now because in a month it will be hard to go back into it.
And if someone still have the link to the referee I am interested ^^.
The game should be available as a multiplayer later today
If you can’t wait, you can play some on this contribution:
Just select the 3rd league top right and there is some other players (3 weeks old) that submitted
Many thanks to @Illedan, @eulerscheZahl @G-Rom and Coding Game. You helped us go through these complicated weeks, with a game was really interesting and well balanced.
I ended 50th with a randomized MCTS, which proved to be rather weak.
It was nice to try a longer duration. 4 weeks were cool, maybe a bit too long : we had enough time to code all that we wanted,
but the last week I felt quite exhausted. Maybe a 2 weeks duration would be ideal for next contests.