General Game Playing (GGP) represents a pinnacle of artificial intelligence, where systems are designed to understand and play novel games based solely on their formal rules. While GGP has seen significant success in virtual domains, transitioning these capabilities to physical robotics introduces a host of real-world challenges. In the physical world, actions are not always deterministic: robots may drop pieces, sensors may fail, and human opponents may commit errors or even cheat.
The Challenge of Physical Execution
Traditionally, "execution monitoring"—the process of detecting and recovering from such real-world failures—is handled by separate, often hard-coded modules. This approach limits the "generality" that GGP aims to achieve. This paper, presented at IJCAI 2015, proposes a novel framework that treats execution monitoring itself as a "meta-game."
The Meta-Game Framework
The authors introduce a method for the automatic construction of meta-games. By embedding a source game's rules ($\Sigma_G$) into a broader Game Description Language (GDL) framework, they create a "meta-game" ($\Sigma_{meta}$) that accounts for physical realities.
The framework consists of three primary layers:
- Source Game ($\Sigma_G$): The original rules of the game (e.g., Chess or Tic-Tac-Toe).
- Environment Model ($\Sigma_{env}$): This layer describes the physical world, including potential "illegal" or accidental transitions, such as a piece toppling over or being placed incorrectly.
- Execution Monitoring Strategy ($\Sigma_{em}$): This defines the role of the Arbiter.
The Arbiter is a specialized player within the GDL description. Under normal play, the Arbiter remains passive (noop). However, if the game state becomes "abnormal" due to a physical failure, the Arbiter takes control. Using standard GGP search and planning, the Arbiter determines the necessary sequence of actions to restore the game to a valid state.
Implementation and Case Studies
The framework's effectiveness was demonstrated through physical implementations, most notably using the game Breakthrough. In this setup, a robot arm plays against a human using tin cans on a 4x4 grid.
In addition to Breakthrough, the authors used Connect Four to illustrate more complex recovery scenarios. For instance, if a disc is dropped into the wrong column, the Arbiter must plan a multi-step process to clear the column and recreate the intended state.
Key Insights
- Arbiter as a GGP Player: By framing monitoring as a game, any off-the-shelf GGP engine can serve as an execution monitor. The monitor "wins" by successfully restoring the board state.
- Axiomatic Embedding: The paper provides a formal method to rewrite any GDL game into a meta-game, ensuring the result remains a "well-formed" game compatible with standard GGP tools.
- Generality: This approach is game-independent. The same transformation logic can be applied to any game described in GDL, providing the robot with a built-in, game-specific execution monitor.
Limitations and Future Directions
While promising, the current model assumes perfect observability—the Arbiter sees every state change immediately. Future work suggests utilizing GDL-II to handle partial observability, where a robot might only detect an error several turns after it occurred. Additionally, the increased state space of the meta-game introduces computational overhead, which may require optimization for more complex games.
Summary updated