General game playing

General game playing (GGP) is the design of artificial intelligence programs to be able to play more than one game successfully.[1] For many games like chess, computers are programmed to play these games using a specially designed algorithm, which cannot be transferred to another context. For example, a chess-playing computer program cannot play checkers. A general game playing system, if well designed, would be able to help in other areas, such as in providing intelligence for search and rescue missions.

Stanford project

General Game Playing is a project of the Stanford Logic Group of Stanford University, California, which aims to create a platform for general game playing. It is the most well-known effort at standardizing GGP AI, and generally seen as the standard for GGP systems. The games are defined by sets of rules represented in the Game Description Language. In order to play the games, players interact with a game hosting server[2][3] that monitors moves for legality and keeps players informed of state changes.

Since 2005, there have been annual General Game Playing competitions at the AAAI Conference. The competition judges competitor AI's abilities to play a variety of different games, by recording their performance on each individual game. In the first stage of the competition, entrants are judged on their ability to perform legal moves, gain the upper hand, and complete games faster. In the following runoff round, the AIs face off against each other in increasingly complex games. The AI that wins the most games at this stage wins the competition, and until 2013 its creator used to win a $10,000 prize.[1] So far, the following programs were victorious:[4]

Other approaches

There are other general game playing systems, which use their own languages for defining the game rules. In 1992, Barney Pell defined the concept of Meta-Game Playing, and developed the "MetaGame" system. This was the first program to automatically generate game rules of chess-like games, and one of the earliest programs to use automated game generation. Pell then developed the system Metagamer.[8] This system was able to play a number of chess-like games, given game rules definition in a special language called Game Description Language, without any human interaction once the games were generated.[9]

In 1998, the commercial system Zillions of Games was developed by Jeff Mallett and Mark Lefler. The system used a LISP-like language to define the game rules. Zillions of Games derived the evaluation function automatically from the game rules based on piece mobility, board structure and game goals. It also employed usual algorithms as found in computer chess systems: alpha-beta pruning with move ordering, transposition tables, etc.[10] The package was extended in 2007 by the addition of the Axiom plug-in, an alternate metagame engine that incorporates a complete Forth-based programming language.

The General Video Game AI Competition (GVGAI) has been running since 2014. In this competition, two-dimensional video games similar to (and sometimes based on) 80s-era arcade and console games are used instead of the board games used in the GGP competition.

Algorithms

Since GGP AI must be designed to play multiple games, its design cannot rely on algorithms created specifically for certain games. Instead, the AI must be designed using algorithms whose methods can be applied to a wide range of games. The AI must also be an ongoing process, that can adapt to its current state rather than the output of previous states. For this reason, open loop techniques are often most effective.

A popular method for developing GGP AI is the Monte Carlo tree search (MCTS) algorithm.[11] Often used together with the UCT method (Upper Confidence Bound applied to Trees), variations of MCTS have been proposed to better play certain games, as well as to make it compatible with video game playing.[12][13][14] Another variation of tree search algorithms used is the Directed Breadth First Search (DBS), in which a child node to the current state is created for each available action, and visits each child ordered by highest average reward, until either the game ends or runs out of time.[15] In each tree search method, the AI simulates potential actions and ranks each based on the average highest reward of each path, in terms of points earned.[11][15]

Assumptions

In order to interact with games, algorithms must operate under the assumption that games all share common characteristics. In the book Half-Real: Video Games Between Real Worlds and Fictional Worlds, Jesper Juul gives the following definition of games: Games are based on rules, they have variable outcomes, different outcomes give different values, player effort influences outcomes, the player is attached to the outcomes, and the game has negotiable consequences.[16] Using these assumptions, game playing AI can be created by quantifying the player input, the game outcomes, and how the various rules apply, and using algorithms to compute the most favorable path.[17]

See also

References

  1. 1 2 General Game Playing: Overview of the AAAI Competition by Michael Genesereth, Nathaniel Love and Barney Pell.
  2. ↑ GGP Server, platform for competition of general game playing systems.
  3. ↑ Dresden GGP Server, platform for competition of general game playing systems with automatic scheduling of matches.
  4. ↑ General Game Playing World Championships
  5. ↑ Information about Fluxplayer, the winner of the 2nd International General Game Playing competition.
  6. ↑ Information about CADIAPlayer, more information about the winner of the 3rd, 4th, and 8th International General Game Playing competitions.
  7. ↑ Sancho is GGP Champion 2014!, winner of the 2014 International General Game Playing competition.
  8. ↑ Barney Pell's research on computer game playing.
  9. ↑ "Metagame and General Game Playing". Metagame and General Game Playing. Retrieved 27 March 2016.
  10. ↑ Available: Universal Game Engine email to comp.ai.games by Jeff Mallett, 10-Dec-1998.
  11. 1 2 "Monte-Carlo Tree Search for General Game Playing". ResearchGate. Retrieved 2016-04-01.
  12. ↑ Finnsson, Hilmar (2012). "Generalized Monte-Carlo Tree Search Extensions for General Game Playing". Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence.
  13. ↑ Frydenberg, Frederik; Anderson, Kasper R.; Risi, Sebastian; Togelius, Julian. "Investigating MCTS Modifications in General Video Game Playing" (PDF).
  14. ↑ M. Swiechowski; J. Mandziuk; Y. S. Ong, "Specialization of a UCT-based General Game Playing Program to Single-Player Games," in IEEE Transactions on Computational Intelligence and AI in Games , vol.PP, no.99, pp.1-1 doi: 10.1109/TCIAIG.2015.2391232
  15. 1 2 Perez, Diego; Dieskau, Jens; Hünermund, Martin. "Open Loop Search for General Video Game Playing" (PDF).
  16. ↑ Jesper Juul. Half-Real: Video Games Between Real Rules and Fictional Worlds. MIT Press, 2005.
  17. ↑ Levine, John; Congdon, Clare Bates; Ebner, Marc; Kendall, Graham; Lucas, Simon M.; Miikkulainen Risto, Schaul; Tom, Thompson; Tommy. "General Video Game Playing" (PDF).

External links

This article is issued from Wikipedia - version of the 8/28/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.