Life In 19x19

Wow, there's a lot of us... should we get them to add L19 as an organization?

And somehow, I was able to create an account under the name "Marcus" ...

http://ai-contest.com/profile.php?user_id=12694

I haven't done anything yet. Let's see what this is actually all about ...

last weekend I spend an evening to make a new one. It's ranked at 622 (ELO 2325) I was hoping to get in the top 500. I guess I need to do a final update before the contest ends (this weekend)

Did somebody write a bot which uses a variant of MCTS? It should be possible to adapt it to this game pretty well.

@Li Kao
I don't think that works well because you need to calculate a lot of future states of the game for MCTS. You are only allowed 1 sec computation time per move. MCTS need time to perform well.

very short overview of my bot:
My program has a formula for finding the weakest planet and one for finding the strongest planet I own.
It also detects incoming enemy fleets and defends against them by sending available ships from other nearby planets.
Then it calculates the remaining ships and checks if that is enough to take over an enemy or neutral planet, if it is it sends ships from the strong to the weak planet.
besides that is directs new forces to the battlefront (shortening trip times when the ships are in demand for attack and defense)
finally it tries to "snipe" opponents planets if the opponent leaves it's planets too weak.

I also have the programming structure in place to change the strategy based on whether the program is ahead or behind in both nr of ships and growth rate.
at the moment the all section contain the same code though so even though it does detect if its ahead or behind it does not change it's strategy.

It is quite buggy though. it does not check enough things. for example it does not look to see if the enemy is sending forces to defend against an attack of my bot. It also does not use path finding to shorten trip times when tunneling ships to the front. one of the main flaws id that it does not check the result of the defense, so it starts to attack while the neighboring planet needs more help.

Li Kao wrote:Did somebody write a bot which uses a variant of MCTS? It should be possible to adapt it to this game pretty well.

I have tried, but not very successfully.

The first problem is the huge game tree complexity. What I did here was adapt the general idea of UCT to include dynamically expanding tree width. That is, when initially creating a node, I populate it with a few heuristically generated moves. Then I dynamically add random moves when the node is visited often. The obvious flaw is that the node is only visited often when the heuristic moves are good, so an extremely good followup that's completely different than the heuristics is extremely unlikely to be found. But on the other hand, visiting each possible move at least once just isn't practical when there are millions of possible moves at each point

The second problem is performance. My implementation just isn't able to search more than about 100k nodes a second, and that just doesn't seem enough to generate good moves.

The end result is that my MCTS/UCT bot is not really much better than my currently submitted "stupid" bot (which is currently ranked 485 after all ).

At least one person (forget who) in the top 50 was doing UCT/MCTS. I think it's pretty clear you can't use random playouts in this game, the move generator needs some intelligence. I did UCT to find the optimal order in which to achieve my goals.

My program was too complicated for the amount of time I had to write it, too many bugs and I didn't get even a small amount of what I wanted finished. Oh well, hopefully next time they'll pick something that doesn't interest me so I don't lose every second of my life for another three months...

Still, I guess #262 isn't a horrible finish.

Here is the winner: http://www.zdnet.com/blog/burnette/hung ... ntest/2131

Here is his blog: http://quotenil.com/Planet-Wars-Post-Mortem.html

The source code is available and very nicely commented.

At least I beat space.invaders!