New Google AI Challenge: Planet Wars | Hacker News Reader

New Google AI Challenge: Planet Wars

aerique.blogspot.com

84 pointsmnemonik40 comments

Open articleView on HN

To skip the 3 line interstital blog post: http://ai-contest.com/

Yeah, I don't understand why that link wasn't posted.

My blog post was just meant to get it on Planet Lisp and make the Lispers aware.

As someone who writes similar types of post (though usually a bit longer ;-)) I share your pain.

This one was indeed exceptionally short. My excuse: I was at work :-)

Heh, my bad everyone :)

This blog came in my Google Reader feed from Planet Lisp and I was mostly excited about the possibility of a CL package. I just submitted with my Reader + HN greasemonkey script (http://github.com/fitzgen/reader-submit-to-hn) without a second thought...

I like the "Advanced Strategy Guide". As of 16:22 UTC all it says is "I got nothin"

http://ai-contest.com/advanced_strategy_guide.php

Galcon itself used to be mod-able, with several people creating bots for it. Someone rolled them all together in a single mod allowing you to pit different AIs against each other, tournament style. The whole package was an excellent sandbox for teaching AI to budding programmers.

Sadly, that's all gone. Mods are gone, the modding forum is gone. Rather than an engrossing programming game, Galcon is now a mind-numbing clickfest. I am delighted to see Google picking up the concept.

Do you know who worked on it, and why it's gone? I might be interested in making a extensible HTML5 version of it...

Is the structure of this game isomorphic to some other real-world problem they're interested in?

Of course not Ender. It's just a game. Just a game.

It's being run by UW undergrads - I think it's just for fun.

>Use of multiple processes or threads is prohibited.

How about mimicking them? Can one perform in-process "context switches" to do the same thing?

If no: where do you draw the line? Must each second's decisions be deterministic from the board state?

If yes: what's the difference? Ease of programming seems a poor metric, and you could just nab something that's already written that does this for you, resulting in nothing but increased compilation times.

The reason for this restriction is because your process and your opponent's run simultaneously on the same machine, so you only get one CPU. Doing your own userspace threading or whatever is fine.

It's probably still too early on in these non-board-game-like game-AI competitions to do serious comparisons, but one thing that'd be cool to figure out in the future is how many components are resuable between these kinds of problems, versus requiring different strategy or hand tuning / hand feature extraction. For example, could similar bots do well at both Planet Wars and Starcraft (http://eis.ucsc.edu/StarCraftAICompetition)? If not, are there parts that can be shared (e.g. factor out high-level strategy versus low-level unit control)? Etc.

Relevant: http://cs227b.stanford.edu (General Game Playing)

GGPs can pretty much play any game with no continuous or unbounded variables, i.e. any game with a finite number of states. Popular examples include tic-tac-toe, checkers, and Connect 4; here's a larger list: http://code.google.com/p/ggp-base/source/browse/trunk/ggp-ba...

Planet Wars could be played by a GGP, assuming some bound on the number of ships that could be created, but standard approaches like UCT, which don't take into consideration similarity between states [1], would fail hard against a specialized player.

[1] For example, if UCT saw a good move in a given state, it wouldn't apply that knowledge to the adjacent state in which only one ship is in a different location.

Ah yeah, I'm quite familiar with GGP. I'm very skeptical of its "generality", though, once you get away from anything that's vaguely similar to chess. For example, try writing Starcraft in GDL (even a discretized version); it's not impossible, but I sure wouldn't want to do it, and the result wouldn't be tractably usable by any GGP engines either. I'm working on a project currently that needs a logical representation of videogames, but I'm not using GDL, because it's just a pain in the ass for videogames (and I want an internal time axis also, not a state-transition system).

But mostly I was thinking on the playing side: I don't think any of the current GGP approaches can even come close to playing strategy-type video games, because they don't typically have any real notion of, as you mention, similarity between situations, or a decomposition into hierarchical or interrelated concerns. A Starcraft bot that treated Dragoon microcontrol as an equivalent-level problem to build order probably isn't going to do well. I think the robotics community might actually have a better starting point: architectures with interrelated components like SLAM, planning, motor control, etc., as opposed to trying to turn the "robotics problem" into one giant state space to be navigated by one giant algorithm. Trying to build an agent that plays two quite different strategy games well (Starcraft and Planet Wars) might be one way of driving the development of those kinds of decompositions.

There's a recent one that's supposed to have done respectably on Pac-Man: http://www.vetta.org/2009/09/monte-carlo-aixi/

>But mostly I was thinking on the playing side: I don't think any of the current GGP approaches can even come close to playing strategy-type video games, because they don't typically have any real notion of, as you mention, similarity between situations, or a decomposition into hierarchical or interrelated concerns.

The problem is really all about game size, not generality or lack of "strategy". UCT is general (indeed, it converges to minimax in the limit), but with a large branching factor and a long game time it can be intractable to get a statistically significant number of samples. I guess you can think about strategy as a heuristic that drastically lowers the computational cost of planning...

Where's the html5/javascript package? :\

I don't think <video> is going to help you here.

I'm still holding out for the COBOL package.

Is there any place where the game's rules are exactly given? I'm particularly interested in how the growth rate and battles work. The Python package that I've downloaded contains no such info.

http://ai-contest.com/problem_description.php

That's the first place I've looked and it contains no clear information about the questions I'm asking.

A. "the number of ships on non-neutral planets increases according to the growth rate for that planet."

What does "according" mean - simple addition? And what happens to the neutral planets - no growth? In which case, how many fleets do the neutral planets start with?

b. "If the result is less than zero, then your bot gains control of the planet."

And how many losses have you incurred - exactly the number of defenders? If the defenders win, do they suffer losses equal to the number of attackers?

The reason I'm asking is that, if all the game does is simple addition and subtraction (no defense advantage, no Lanchester-type law for combat), then there probably exists a very simple optimal strategy, and it's more a problem of mathematics than AI.

I'm pretty sure everything is just simple addition/subtraction. Watching the video, neutral planets don't have any growth. When you get a planet to -1 you take control and are left with 0 ships there. (In the video green sent a fleet of 50 to a planet with 4, green took control of the planet and had 45 ships there)

I haven't seen specific info yet. Your best bet is to download a starter package and run the game locally.

I've only played with it a little and my impression is that growth rate is an integer that's added to the planet's population every turn, but only occupied planets not neutral ones. (So a planet of yours with a population of 138 and a growth rate of 5 will have a population of 143 next turn (assuming no increase or decrease from friendly or enemy ships).)

The best way to get a feel for it is to download the free demo of Galcon. It's a great game and it's available on Windows, Mac, Linux, iPhone, iPad, Android, and even WebOS; give it a try.

The answers to your questions are simple addition, no growth, random numbers, yes, and yes.

Little-stars-for-little-wars flash game looks very similar to description:

http://bestonlinerpggames.com/game/972/Little-stars-for-litt...

1) "then there probably exists a very simple optimal strategy, and it's more a problem of mathematics than AI."

I don't see how existence of the optimal strategy entails that this is not the problem of AI. After all, all finite state deterministic games can be essentially solved by traversing the game tree, searching for the best strategy. The thing is that in most games, this approach is not acceptable because of time and space issues. That's why we call for AI - to find a strategy which may not be optimal, but is "good enough" and does not take much resources to find.

Besides, I do not understand why do you think that simple optimal strategy exists. The game of Go has equally simple rules, finding good strategy in it is not easy though.

2) The rules are not clear for me either. Last night I wrote a simple engine for planet wars [1], and I had to make some important decisions about things which the game description did not cover - for instance, what is the order of events in game? Is the number of ships on players' planets increased before or after the fleets arrive to them?

[1] - http://bitbucket.org/dodek/gaclon/src

Is anyone aware of an AI game that has a homeostatic goal? I am thinking along the lines of a SimCity style game where random negative events happen and our AI would have to account and route around these types of issues. It would be interesting to see a simulation of that nature as compared to the normal competitive game (e.g. chess, go, reversi.)

I rather wish their forum was open. I'm only receiving a blank grey window when I run ShowGame over a game's text.

Alas.

Edit: I suppose the outage was momentary; the forum is rather hopping.

I downloaded the source from Google Code, and found the invocation in a .php file there. (Grep for "ShowGame"). After adjusting for the fact that I had the python starter kit, the invocation worked without problems.

I'm not familiar with the Google Code site. Could your provide a link?

I've downloaded my kit from: http://ai-contest.com/starter_packages.php

Also, for what it's worth: http://ai-contest.com/forum/viewtopic.php?f=18&t=405&...

I suspect I'm having a goofy Java issue, but that's likely a personal bias.

Check the source out from subversion, as described here:

http://code.google.com/p/ai-contest/source/checkout

Yet another fun challenge in the form of an AI challenge. I really enjoyed the tron ai contest and I am looking forward to this one.

Good luck Colonizing and coding.

Does this teach me how to think with artificial intelligence?

If you choose to solve it with artificial intelligence, then yes.

Is it just me or is having the navigation on the right hand side of the page really unusual?

It's not the "standard" but sidebars are common enough for it to work. Back in the 1998-2002 area, right hand navigation bars had a spurt of popularity because of usability findings in relation to the ease of moving between the scrollbar and the items. With the advent of scroll wheels, though, this hack became less significant and left handed navigation began to rule once again.

Seems like the standard 'blog' (or at least blogspot) format.

Reply on news.ycombinator.com