News for hackers. Stuff that matters.
Re:New Google AI Challenge: Planet Wars by _delirium on Monday September 06, 2010 @02:45PM (#1667164)
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.
Re:New Google AI Challenge: Planet Wars by endtime on Monday September 06, 2010 @03:03PM (#1667203)
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.

Re:New Google AI Challenge: Planet Wars by _delirium on Monday September 06, 2010 @03:26PM (#1667239)
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.

Re:New Google AI Challenge: Planet Wars by endtime on Monday September 06, 2010 @04:52PM (#1667403)
>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...

Re:New Google AI Challenge: Planet Wars by abecedarius on Monday September 06, 2010 @03:57PM (#1667299)
There's a recent one that's supposed to have done respectably on Pac-Man: http://www.vetta.org/2009/09/monte-carlo-aixi/