Traveling Salesman


#1

Obviously we need to (approximately) solve the traveling salesman problem. What is the best resource to learn and implement the algorithms needed to do this?


#2

That’s not at all obvious to me, why do you think this game reduces to TSP?


#3

I mean just a part of the game. And it won’t necessarily be the same algorithm, but one variant of the TSP corresponds to weighted vertices. That’s what I’m thinking this is like. Bare minimum, I think knowing how to solve TSP would help.


#4

I know how to solve TSP, I still don’t see how it’s applicable. Your goal is to maximize halite income rate, not visit each node. Depending on halite distribution income maximization might mean staying in the neighborhood or going directly after some far-away node.


#5

I agree. I know of this problem on hackerrank that seems similar to halite: https://www.hackerrank.com/challenges/tbsp/problem. Do you think it’s seems similar? In my mind TSP doesn’t just refer to visiting all the nodes, but could just be visiting the most valuable nodes, or visiting the most valuable nodes first. Halite then is solving one “loop” of TSP at a time with the constraint of 1000 max halite and an objective of highest halite per time. Either way TSP is an optimization problem and learning to solve it would make me more capable of solving other optimization problems.

Perhaps we just have different strategies, but regardless, I’d love to know of any resources you or anyone else might have on TSP.


#6

I think you may find Dijkstra’s algorithm more applicable. Which is in essence the opposite of TSP.


#7

TSP will actually give you a sub-optimal strategy here. This is like Travel Salesman where your car runs out of gas, but fills up faster when you’re next to other salesmen. Oh and you can assassinate the other salesmen and also give birth to more.

Simplifying this to TSP will leave the other significant dimensions of the game behind and leave you in the dust. This is a far more dynamic problem than TSP. Adapting an approximate algorithm or even a brute force one will not be worth the time.

I’d recommend trying out a few different simple strategies to give yourself a baseline, and then play those strategies against a more advanced one as you try to develop it. You’d be surprised how well your simple solutions beat the more complicated ones.


#8

Indeed simple solutions have being beating my more sophisticate/complex ideas. And every time I comeback to the drawing board.

One good suggestion that was given in the intro of the forum (I think) is to do small steps or small improvements. In that sense, my 2cents, would be to start with the TSP algo and keep adding a new dimension (amount of halite, competition, attack, new ships, drop off, etc.)
Good luck.


#9

I did some research and found this paper. Apparently, what I’m after is already well known as “Orienteering” or “Discounted Reward TSP”

I encourage the haters to have a look. :stuck_out_tongue: :wink: I’ll try to start with this and keep this thread posted.


#10

Looking forward to seeing how this goes!


#11

I also definitely considered at the start of Halite III things like the team orienteering problem, since there are multiple agents you’re organizing. I haven’t needed to find anything like an exact solution to the team orienteering problem though, as relatively greedy approaches have been working fine, and it feels like my bigger miss at the moment is that I’m not playing with dropoffs.

I also just discovered that I was accidentally using a heuristic that assigned no reward to squares on the same y-level as my shipyard. Even with that pretty critical bug, I was around rank 220 until I submitted a version of my bot that replaced my hlt folder with a folder of replays.