First Impressions


#1

Hey all, I placed #44 last year, and I just submitted my first 2 bots (2 (not 1) because I saw an immediate issue and addressed it). Submission #2 is nothing to be proud of yet, but it’s one or two steps away from something I suspect could hit gold or silver tier. I’ll get to that, no worries.

Anyway, last year’s competition IMO was a nearly perfect example of “easy to learn, hard to master.” This year, I spent an inordinate amount of time getting butt stupid pathfinding to work just to submit my first bot. This year, the game itself is simpler, but the emergent complexity of its mechanics is more complex IMO and I wonder if this is off-putting to beginners here. In comparison to last year, I believe I hit silver tier in the first 24 hours (correct me if I’m wrong) and I flirted with platinum after I eventually hit gold.

Second, my original plan this year was to build an RL client, but the limitations on memory and the deprecated nature of GPU clients dissuaded me from doing so. I still intend to build a value function from a neural network that looks at games (I’ve downloaded many days of gameplay to do so), but a lot of my initial plans to brute force this have been scrapped. Why a value function? Well, all the post-mortems last year indicated the top players had value functions for the board. I suspect if my client had had one, it might have done quite a bit better (it didn’t).


#2

I’d really recommend not having anything that can be called “pathfinding” to start with (I still don’t have anything much more complex than picking one of the 1 or 2 directions that could take me closer to my target, without any thought to the future…)


#3

Thanks for the amazingly helpful visualizer! And I just hit silver tier so I guess I’m eating my words :-)…

I am thinking of just looking 2-4 steps ahead and picking a path that leads to the shortest distance in those 2-4 steps, but you’re right, the map is dynamic, so too much lookahead is for naught*. That said, if you watch my replays, I need to do better than back and forth until a path opens, no?

Then again, it was that crazy lookahead in AlphaGo that led to move 37, so who knows?


#4

Do you have link for the post-mortem articles last year? I’m a super n00b on this contest.


#5

@dbancajas, I believe this is the link you are looking for:


#6

I agree with @fohristiwhirl, I implemented A* and some dynamic programming approaches to find the best path, only to go back and for now just do a random.choice on the directions that get me closer. And it works surprisingly well and gives you a lot more time to think of where you want to move and how you want to resolve conflicts etc.


#7

I agree that A* is overkill for an open grid like this, something like not reversing (ala Pacman ghosts in chase mode) unless there’s no other choice ought to work in most cases. Alternatively, I’ve thought beam searching out to 2 or 3 step lookahead with the goal that every ship is closer or at its goal by then would resolve a lot of conflict as well. I can definitely do better than what I’m seeing my 1st client do though!

I also highly recommend reading those post-mortems from last year. The winning bots all had value functions and they all spent a lot of time fine tuning moves to optimize that value function.


#8

I spent the last two weeks (well, a few hours in total) trying to get some variant of dijkstras shortes path running. While it works in general, the results are all worse than my “lets just walk to the next tile that has a lot of halite” strategy which got me to gold so far. I dont even have switching places implemented yet.
It’s a bit frustrating to be honest that some random algorithm to get started got me the farthest so far.


#9

What do you mean by value function? What is a value function?


#10

An equation based on the state of the game that is in some way an indicator of your likelihood of winning or the desirability of one state over another. A simple function might be summing up the distances to the destinations of all your turtles and trying to find a set of legal moves that minimizes that function. A more sophisticated version would be to rate how likely a given board configuration will lead to victory.


#11

Oh so kind of like how minimax would score a state. Thanks for the explanation!


#12

Funny enough, when I added “future” planning I did worse :laughing:


#13

A lot has changed since I started this thread…

  1. 2P vs 4P are completely different games. 4P requires collision and inspired management. 2P not so much at platinum.
  2. Ship quotas are going up in 2P! I am seeing a significant number of losses to just not deploying enough ships in 2P. Reverse engineering has begun!
  3. Still can’t figure it why or when to build a new dropoff. That remains my biggest confusion