Searching for resources


#1

Right now I have been using just a simple random search (check immediate 4 corners )and gotten to ~200 on breadboards. I have tried to implement a better heuristic for resource search and collection but everything I have tried so far has only producer worse results (A*, changing the heuristic to weight halite more over distance[bad idea fyi]), ect…). In top 20 games I notice that players bots tend towards high density areas and sometimes ignore 200+ halite squares right next to them.

Are these actual bots created through AI / ML to do this or is there a way to do this such as a density based search. Or is this more of a hard code to make the bots branch out in cross shape paths? I have been trying to figure out a math formula / statistical formula for this for a few days now but am blanking and my research has proven unsuccessful. Wonder if anyone could share or direct me to any resources / materials to give me ideas.


#2

I use weighted halite strategy for a few weeks and stayed in top50 until the last few days. But I have like 150 lines of different penalties/bonuses for halite weightes (including distance). A* is useful in some situations but not very much. Unfortunately this stategy sucks in large/low halite maps because my ships waste turns on clearing almost empty cells around shipyard.

At the moment I am trying to figure out new halite search strategy but lack of knowledge of algorithms…

So, I would also like to know what can be used to solve this problem besides ML.


#3

Now I’m using this kind of strategy:

  1. find rich cell, wich no no bot heading up to
  2. go there
  3. if there rich deposite under foot collect it first(for no to spend enegry)
    Seems like it works, but I now have some problems with navigation(there were many trafic jams so I’m working on logistic now, see some of my bot’s games and you understand)

#4

I’m really curious what the top players are doing so differently. Is it just a lot of hard-coded knowledge, or are their algorithms in a different league entirely?

I’m basically using A* to look for a path from ship to dropoff, but the implicit graph is weighted so that the path ‘detours’ towards higher amounts of halite, so the ship will move away from the dropoff instead of towards it if there is enough halite to be mined. It works reasonably well, but I wonder if I’m overlooking an even better algorithm – something like max-flow maybe…


#5

If you are mining squares with 10 halite, a ship would never even fill by the end of the game.

Just adjusting how much halite you ignore and leave in a square can make a mind boggling difference. I tuned this on my bot and went from 300th place to 100th (a week ago). A friend did the same and went from the third page to the first page.


#6

I was thinking about this. I think distance needs to be the primary decider and halite loss the second. Have to ask the question. If you dodge one square you might need an extra 2 moves in the worst case (going around an obstacle halite square in a straight line). Also in worst case you’ll loose 100 max on this square. How worth it is to loose 100 halite for 2 moves for your bot when there are 4-500 moves? Multiply this by 30 robots and multiple deposits you’re loosing 60 moves / deposit cycle. Honestly you can mine more with those moves and also deny more from your opponent with those 60 moves.


#7

I think A* algorithm (or similar ones) are useful only when you move towards shipyard. Otherwise you should clean up the path to rich halite chunks so you don’t burn a lot of resources when returning home. In my case I
accidentally did it using complex distance penalty formula (my ships start to move toward halite chunk but on half-full cells they stops to collect some and then move futher).


#8

How worth it is to loose 100 halite for 2 moves

I arbitrarily set a cost of 10 halite per square. So if the bot can shorten a ship’s path by one square, it will be willing to pay 10 halite for that. I guess one could try to analyze replays to find a more accurate value, but I haven’t gotten around to that yet.

Another thing you can do once you set a movement cost is a simple “skip mining” check: if it is more profitable to move to an adjacent square, mine there, and then move back to the current square (subtracting the 10 move cost twice) then don’t bother mining the current square.


#9

There are some algorithms based on potential matrix. I haven’t read/understood it myself yet. For example, this document describes algebraic approach to solve path-finding problem. Also, if you know Russian language you can read this series of articles. And finally, we can imagine 2D map as 3D space like in this video course. I’m not sure that the last link is related to path-finding problem, but as we say here in Russia - “attempt is not a torture”.

.


#10

"Just Do It."™ seems to be as appealing.