Halite Home

Do you use A* in your algorithm?


#1

Continuing the discussion from @erdman has unseated @djma:

I have used A* to produce paths for some cells in Java (should have similar runtime to C#) and had reasonable performance. I basically worked from the example code on Wikipedia without any real optimizations.

Personally I found that calculating an entire path wasn't worth it because the map was so dynamic. By the time my cell had made a few moves towards its target, the path was no longer very valuable. Calculating a new path on each turn didn't prove to be much more effective than naïvely moving in the general direction of my target with some heuristics regarding my immediate surroundings.


#2

I actually dont use A*, I rather prefer Dijkstras.

Evey turn i run Dijkstras form all my cells on the map. Even though I am using C++ and a really efficient implementation of it, I was sure my bot would timeout on Large Maps. But surprisingly enough my bot has never timed out so far (although it takes 1.5 sec per turn on my local machine)

Even though the map is very dynamic every turn if you move closer towards your destination, your heuristics should increase and compel you even more to go to the same destination. Atleast thats the case for my heuristics.


#3

I use Dijkstras as well. I was thinking about how A* would be implemented but according to stack overflow Dijkstra is a special case for A* (when the heuristics is zero), which makes sense. For my strategy, I find the cheapest path to get an adjacent unit. It uses Djikstra it chooses the cheapest path as determined by the lowest production, sums up their weights and keeps a running track of the cheapest locations. I cut off the search after 5 moves. I analyze as many adjacent squares and calculate their net cost (production lost vs production gained from acquiring the adjacent piece) and choose my moves from there. When I have the moves required, I put them in a move queue based on the ordering and exclude those pieces from my search.

It works okay, but I lack a broader strategy. So I'll attain the highest production pieces relative to the lost production, but it doesn't take into consideration other factors, such as the new conquered pieces adjacent pieces. So, a piece may be less optimal to attain in terms of production, but it may be adjacent to very high production, low strength pieces. Unfortunately I have no been able to develop a meaningful scoring system to determine which pieces to attack and just rely on the single production and cost factors.