Ocean of Code - moving strategy

Please, feel free to correct me if this is a wrong place, a wrong question or a wrong post in general.

Looking forward to hearing your opinion on what strategy is possible and can be effective for moving submarine (U-boot) in this contest.

I guess I would you efficient, but not perfect one.
Looking for some snake game algorithms and other stuff there are:

  • BFS,
  • DFS,
  • Hamilton,
  • Longest path,
  • Flood fill
  • “go random” :wink:
  • keep to the left/right if possible

I tend to choose DFS or flood, as the other seems to OP.

I don’t think people would be too eager to discuss strategies while the contest is ongoing (me neither, of course), so I’d like to invite you to try it out. However, a few notes…

  • I’m confused why you would consider flood fill conceptually different from BFS or DFS in this case. In general, I’m rather against considering “flood fill” an algorithm, as much as I wouldn’t consider “max flow” an algorithm. I’d say that “flood-fill” is a problem that can be solved via several algorithms. However, I don’t want to get into that because it’s probably a lost fight and the whole Internet doesn’t agree with me.
  • You’d probably want to balance several factors: getting close to the most likely position for your enemy, not making your position too obvious, delaying as much as possible the need to surface… You’ll notice that these objectives go a little bit against each other, committing too much to one of them can sacrifice the others, and different algorithms are best suited for each of them.

So… who knows? :slight_smile:

These are my first steps with pathfinding.
Still, your reply was helpful.
I went with simplified BFS and the boat moves properly.
Although, moving alone is not enough to jump up out of Wood League :slight_smile:

I didn’t consider that the people would be so competitive and keep quiet with theirs ideas :smile:

@Neumann suggested to someone else on Discord that they look into Voronoi diagrams (https://www.codingame.com/playgrounds/243/voronoi-diagrams)

Yesterday evening in the chat, they told me to use Flood Fill (I’m only checking the 4 adjacents for now with some kind of evaluation of which would be the best, but it seems to be enough for Silver league with a few torpedoes and silence)

3 Likes

@_CG_Thibaud I was told the same things but I can’t figure it out how to use it proprely, do you fullfill all the map at the start of the game ?

every time I want to move, I check adjacent cells and evaluate them quickly taking into account if they have enough accessible adjacents themselves and how far they are from the closest possible enemy.

But I’ll do a flood fill because I’m running into dead-ends too often

Yeap, I started to rank the cell by the number of node they have, i’ll keep in touch if it work

Without sensible shooting you won’t advance out of wooden 1.
Optimized moving is not enough for that.

My understanding of Voronoi is that its goal is to determine the areas that are closest to some positions and I am not sure how it would help in this game.
A simple floodfill with a move depth of 1 should be enough for acceptable pathing (at least until silver league).

Here is an example:
ooo
ooo
oxx
poo
x: visited cells or islands
o: sea cells that are not visited
p: your current position

The algorithm is quite simple, for every every new cell you can reach, compute its accessible zone (cells that are linked to it by non visited sea cells), then choose the one with the biggest zone:
_N (0,2): 6
_E (1,3): 1
So here your best move is N.

In some edge cases you can make wrong decisions, but it’s marginal (and if you really want to you could compute the accessible zone after n moves instead of just 1):
ooooo
xxoxx
oopxx
oooxx
N: 6
W: 5
S: 5
So N seems to be the better option, but then your zone will be cut in 2. In the end you will only get 4 moves while W and S would have given you 5 moves. => this doesn’t arrive often.

My experience is that you won’t often surface more than once per game with by computing the accessible zones with a move depth of 1. Also most of the time the game will end before you even surface when at least one player has good opponent detection. (I think there is no silence in wood?)

1 Like

Managed to get into the silver league with flood filling and avoiding surface for as long as possible. Also I tried sticking to the walls as much as possible, but overall this revealed my position to opponent very much. Moving in the same direction many turns in a row also reveals your position to opponent pretty much.

1 Like

My current bot has yet to shoot a torpedo and is in the bottom half of the silver league…

Yep, good moving with silence can get you to silver.
Previously I tryied good moving with some random shooting and it was terrible.

Bad shooting tells opponent about your position =)