Finding the optimal ship count


#1

Hi,

I hope I am not bothering you to much with this question but I struggle with the optimal ship count.

My thoughts so far:
Spawning a ship is always a good idea if given ship will earn atleast 1001 halite .
To predict the amount of halite a ship will farm in its lifetime you need to know the amount of Halite on the map, the number of turns left and the ratio between the amount of halite a ship will earn (25% of current cell) and the halite it will spend traveling to the next cell(10% of halite on cell). To make everything a little simpler I would use the average halite for my calculations(not sure wether this is a good idea). Using all the information I would end up with something like:
(turns left) * (x*(avg_halite0.25)-y(avg_halite*0.10))

->this is just a rough approximation because it doesn’t take inspiration and crashes into account

However the average halite will change during the game and to predict it I would need to know how much ships I will have in a given turn, but to know the ships i will have in that turn I need to know the average halite.
Am I overlooking something obvious here? Is my method generally not possible? I would understand if you don’t have the time to give me proper feedback. However I would really appreciate if you could give me a hint or a mathematical approach I could google or something.


#2

I cant tell you exactly what I do but this is a nice hint of what worked really well for me…

what I did is take the total halite on the map at the start of the game and then take that same value again every turn, and if the percentage collected is greater than a certain percentage stop spawning ships


#3

Thank you very much.
I will definitely experiment with your idea:)


#4

What if in addition to analyzing the map, you also analyze the average rate of halite collected by all ships in the past X turns? Then use the rate of halite depletion + current state of halite on the map to make a decision.

I think your current model could be improved if you are able to somehow factor in what other ships are doing into your calculation.


#5

Interesting, I got into the 70s with just a fixed maximum number of ships calculated based on the map size and total Halite at the beginning combined with a fixed stopping time to switch over to halite accumulation.

I just got rid of this in favor of current Halite as a fraction of total Halite. Offline, it’s a win. But this year, offline testing has been a surprisingly unreliable predictor of online performance.

I consistently get the feeling a lot of these failed experiments aren’t so much failures as failures to address a root cause limiting further improvement, but that’s just a gut feeling ATM.


#6

Another angle to look at the problem is that it is a game, not an exact science. What we need to do is be competitive with the opponent rather than focusing on to have the ideal and absolutely correct number of ships. For example, let’s say the number of ships required for a certain map is 25. If we overstep and create 26 ships, we risk loosing out by wasting resources. However, the opponent is having only 15 ships, In this case, with about 18-20 ships, we can easily beat him, without risk of losing by attempting to create the mathematically optimum number of ships for that map.

On the other hand, there could be opponents who create a larger than necessary force and planning to wipe us off the board. (As in that example game shared in the Halite 3 competition Update post, I was in the receiving end there).

In short, the opponent behavior too may be needed to take into account.


#7

Indeed! In 2p games it’s possible to opt out of spawning decisions nearly completely by mirroring your opponent. That’s actually the strategy I employ. Unfortunately, there’s no good way to do this in 4p, as far as I can see.


#8

How does mirroring your opponent work if your opponent would employ the same strategy? Specifically, what happens when you run your mirroring bot against itself? It seems to me that mirroring can’t be the only thing it does, can it?


#9

I don’t mirror locally, for the reasons you say. There, I use a “normal” spawning strategy (which I also use online when very close to the opponent in ships).

If someone else implemented the same spawning strategy, we’d both end up spawning for most of the game. There are some safeguards against really obviously bad spawning decisions, so we’d stop a bit before the end.


#10

Heres an Idea I haven’t implemented but thought about. Creating a new ship has a positive marginal cost if it is able to collect at least 1,000 halite before the end of the game. Granted, ships might have subtle additional benefits/costs not strictly related to halite collection such as ‘blocking’ in strategy, inspiring opponent ships, increasing the rate of halite collection (and therefore frequency of new ships) etc. which you can account for. If you can then forecast the expected time for each ship to collect 1,000 halite and return each turn to a drop-off, you could stop producing ships right before they become marginally unproductive. Any thought about this or has anyone implemented something similar?


#11

@harryshi: Yes, I use an estimate of the figure you describe (with some extra checks and balances) to decide when to build ships.

It works okay, but in 2p games it does suffer from the problem of not being responsive enough to the opponent’s ship numbers. It does include the count of opponent ships in its estimate, but this can actually mean it produces fewer ships when the opponent gets an early lead (particularly on poor maps). Even in 4p games I think I could do better by responding more to opponent ship numbers, but how to do so is much less clear than in 2p games.

I’ve tried a few methods to improve the accuracy of the estimate, but these have all resulted in a drop in performance, and I’ve (so far) always reverted to something very similar to the first idea I wrote down.


#12

There has to be more than 1,000 halite available per ship, out there, so I take the: if (total halite / num opponents / my number of ship > 1500) then spawn a ship, until 100 turns until the end.

This will spawn new ships automatically if the opponent is colliding with mine.

Also don’t forget the inspiration bonus could triple the available halite, the pro’s seem to be totally cleaning up boards and scoring about 200% of the initial halite so they are probably spawning more ships than my calculation.