9 ms·

Relevant: http://cs227b.stanford.edu http://cs227b.stanford.edu (General Game Playing) GGPs can pretty much play any game with no continuous or unbounded vari

by endtime 16y ago

Relevant: http://cs227b.stanford.edu 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-base/games/rulesheets 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.

_delirium 16y ago
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.
- abecedarius 16y ago
  There's a recent one that's supposed to have done respectably on Pac-Man: http://www.vetta.org/2009/09/monte-carlo-aixi/ http://www.vetta.org/2009/09/monte-carlo-aixi/
- endtime 16y ago
  >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...

by endtime 16y ago

_delirium 16y ago

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.

abecedarius 16y ago
There's a recent one that's supposed to have done respectably on Pac-Man: http://www.vetta.org/2009/09/monte-carlo-aixi/ http://www.vetta.org/2009/09/monte-carlo-aixi/
endtime 16y ago
>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...