>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/
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.