General game playing

From HandWiki
Short description: Learning to play multiple games successfully
Artificial intelligence
Major goals
Approaches
Philosophy
History
Technology
Glossary

General game playing (GGP) is the design of artificial intelligence programs to be able to play more than one game successfully.[1][2][3] 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 instance, a chess-playing computer program cannot play checkers. General game playing is considered as a necessary milestone on the way to artificial general intelligence.[4]

General video game playing (GVGP) is the concept of GGP adjusted to the purpose of playing video games. For video games, game rules have to be either learnt over multiple iterations by artificial players like TD-Gammon,[5] or are predefined manually in a domain-specific language and sent in advance to artificial players[6][7] like in traditional GGP. Starting in 2013, significant progress was made following the deep reinforcement learning approach, including the development of programs that can learn to play Atari 2600 games[8][5][9][10][11] as well as a program that can learn to play Nintendo Entertainment System games.[12][13][14]

The first commercial usage of general game playing technology was Zillions of Games in 1998. General game playing was also proposed for trading agents in supply chain management thereunder price negotiation in online auctions from 2003 on.[15][16][17][18]

History

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.[19] This system was able to play a number of chess-like games, given game rules definition in a special language called Game Description Language (GDL), without any human interaction once the games were generated.[20]

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.[21] 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.

In 1998, z-Tree was developed by Urs Fischbacher.[22] z-Tree is the first and the most cited software tool for experimental economics. z-Tree allows the definition of game rules in z-Tree-language for game-theoretic experiments with human subjects. It also allows definition of computer players, which participate in a play with human subjects.[23]

In 2005, the Stanford Project General Game Playing was established.[3]

In 2012, the development of PyVGDL started.[24]

GGP implementations

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[25][26] 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.[19] So far, the following programs were victorious:[27]

Year Name Developer Institution Ref
2005 Cluneplayer Jim Clune UCLA
2006 Fluxplayer Stephan Schiffel and Michael Thielscher Dresden University of Technology [28]
2007 Cadiaplayer Yngvi Björnsson and Hilmar Finnsson Reykjavik University [29]
2008 Cadiaplayer Yngvi Björnsson, Hilmar Finnsson and Gylfi Þór Guðmundsson Reykjavik University
2009 Ary Jean Méhat Paris 8 University
2010 Ary Jean Méhat Paris 8 University
2011 TurboTurtle Sam Schreiber
2012 Cadiaplayer Hilmar Finnsson and Yngvi Björnsson Reykjavik University
2013 TurboTurtle Sam Schreiber
2014 Sancho Steve Draper and Andrew Rose [30]
2015 Galvanise Richard Emslie
2016 WoodStock Eric Piette Artois University

Other approaches

There are other general game playing systems, which use their own languages for defining the game rules. Other general game playing software include:

System Year Description
FRAMASI 2009 Developed for general game playing and economic experiments during a PhD thesis.[31][32]
AiAi 2015-2017 Developed by Stephen Tavener (previous Zillions developer).[33][34][35]
PolyGamo Player 2017 Released by David M. Bennett in September 2017 based on the Unity game engine.[36]
Ludii 2020 Released by Cameron Browne and his team at Maastricht University as part of the ERC-funded Digital Ludeme Project.[37][38][39]

GVGP implementations

Reinforcement learning

GVGP could potentially be used to create real video game AI automatically, as well as "to test game environments, including those created automatically using procedural content generation and to find potential loopholes in the gameplay that a human player could exploit".[7] GVGP has also been used to generate game rules, and estimate a game's quality based on Relative Algorithm Performance Profiles (RAPP), which compare the skill differentiation that a game allows between good AI and bad AI.[40]

Video Game Description 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) 1980s-era arcade and console games are used instead of the board games used in the GGP competition. It has offered a way for researchers and practitioners to test and compare their best general video game playing algorithms. The competition has an associated software framework including a large number of games written in the Video Game Description Language (VGDL), which should not be confused with GDL and is a coding language using simple semantics and commands that can easily be parsed. One example for VGDL is PyVGDL developed in 2013.[6][24] The games used in GVGP are, for now, often 2-dimensional arcade games, as they are the simplest and easiest to quantify.[41] To simplify the process of creating an AI that can interpret video games, games for this purpose are written in VGDL manually. VGDL can be used to describe a game specifically for procedural generation of levels, using Answer Set Programming (ASP) and an Evolutionary Algorithm (EA). GVGP can then be used to test the validity of procedural levels, as well as the difficulty or quality of levels based on how an agent performed.[42]

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.[43]

A popular method for developing GGP AI is the Monte Carlo tree search (MCTS) algorithm.[44] 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.[45][46][47] Another variation of tree-search algorithms used is the Directed Breadth-first Search (DBS),[48] 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.[49] 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.[44][49]

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.[50] 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.[41]

See also

References

  1. ↑ Pell, Barney (1992). Metagame: a new challenge for games and learning.. Ellis-Horwood. https://svn.sable.mcgill.ca/sable/courses/COMP763/oldpapers/pell-92-metagame.pdf. Retrieved 2020-02-17. 
  2. ↑ Pell, Barney (1996). "A Strategic Metagame Player for General Chess-Like Games" (in en). Computational Intelligence 12 (1): 177–198. doi:10.1111/j.1467-8640.1996.tb00258.x. ISSN 1467-8640. 
  3. ↑ 3.0 3.1 Genesereth, Michael; Love, Nathaniel; Pell, Barney (15 June 2005). "General Game Playing: Overview of the AAAI Competition" (in en). AI Magazine 26 (2): 62. doi:10.1609/aimag.v26i2.1813. ISSN 2371-9621. 
  4. ↑ Canaan, Rodrigo; Salge, Christoph; Togelius, Julian; Nealen, Andy (2019) (in EN). Leveling the playing field. pp. 1–8. doi:10.1145/3337722. ISBN 9781450372176. 
  5. ↑ 5.0 5.1 Mnih, Volodymyr; Kavukcuoglu, Koray; Silver, David; Graves, Alex; Antonoglou, Ioannis; Wierstra, Daan; Riedmiller, Martin (2013). "Playing Atari with Deep Reinforcement Learning". Neural Information Processing Systems Workshop 2013. https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf. 
  6. ↑ 6.0 6.1 Schaul, Tom (August 2013). "A video game description language for model-based or interactive learning". 2013 IEEE Conference on Computational Intelligence in Games (CIG): 1–8. doi:10.1109/CIG.2013.6633610. ISBN 978-1-4673-5311-3. 
  7. ↑ 7.0 7.1 Levine, John; Congdon, Clare Bates; Ebner, Marc; Kendall, Graham; Lucas, Simon M.; Miikkulainen, Risto; Schaul, Tom; Thompson, Tommy (2013). "General Video Game Playing". Artificial and Computational Intelligence in Games (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik) 6: 77–83. http://drops.dagstuhl.de/opus/volltexte/2013/4337/. Retrieved 25 April 2015. 
  8. ↑ Bowling, M.; Veness, J.; Naddaf, Y.; Bellemare, M. G. (2013-06-14). "The Arcade Learning Environment: An Evaluation Platform for General Agents" (in en). Journal of Artificial Intelligence Research 47: 253–279. doi:10.1613/jair.3912. ISSN 1076-9757. 
  9. ↑ Mnih, Volodymyr; Kavukcuoglu, Koray; Silver, David; Rusu, Andrei A.; Veness, Joel; Hassabis, Demis; Bellemare, Marc G.; Graves, Alex et al. (26 February 2015). "Human-level control through deep reinforcement learning". Nature 518 (7540): 529–533. doi:10.1038/nature14236. PMID 25719670. Bibcode: 2015Natur.518..529M. 
  10. ↑ Korjus, Kristjan; Kuzovkin, Ilya; Tampuu, Ardi; Pungas, Taivo (2014). "Replicating the Paper "Playing Atari with Deep Reinforcement Learning"". University of Tartu. https://courses.cs.ut.ee/MTAT.03.291/2014_spring/uploads/Main/Replicating%20DeepMind.pdf. 
  11. ↑ Guo, Xiaoxiao; Singh, Satinder; Lee, Honglak; Lewis, Richard L.; Wang, Xiaoshi (2014). "Deep Learning for Real-Time Atari Game Play Using Offline Monte-Carlo Tree Search Planning". Conference on Neural Information Processing Systems. http://papers.nips.cc/paper/5421-deep-learning-for-real-time-atari-game-play-using-offline-monte-carlo-tree-search-planning.pdf. 
  12. ↑ Murphy, Tom (2013). "The First Level of Super Mario Bros. is Easy with Lexicographic Orderings and Time Travel ... after that it gets a little tricky.". SIGBOVIK. https://www.cs.cmu.edu/~tom7/mario/mario.pdf. 
  13. ↑ Murphy, Tom. "learnfun & playfun: A general technique for automating NES games". https://www.cs.cmu.edu/~tom7/mario/. 
  14. ↑ Teller, Swizec (October 28, 2013). "Week 2: Level 1 of Super Mario Bros. is easy with lexicographic orderings and". http://swizec.com/blog/week-2-level-1-of-super-mario-bros-is-easy-with-lexicographic-orderings-and/swizec/6392. 
  15. ↑ McMillen, Colin (2003). Toward the Development of an Intelligent Agent for the Supply Chain Management Game of the 2003 Trading Agent Competition. Master's Thesis. Minneapolis, MN: University of Minnesota. 
  16. ↑ Zhang, Dongmo (2009). From general game descriptions to a market specification language for general trading agents. Berlin, Heidelberg: Springer. pp. 259–274. Bibcode: 2010aecd.book..259T. 
  17. ↑ "AGAPE - An Auction LanGuage for GenerAl Auction PlayErs" (in fr-FR). https://www.irit.fr/agape/. 
  18. ↑ Michael, Friedrich; Ignatov, Dmitry (2019). "General Game Playing B-to-B Price Negotiations". CEUR Workshop Proceedings -2479: 89–99. http://ceur-ws.org/Vol-2479/project2.pdf. Retrieved 5 March 2020. 
  19. ↑ 19.0 19.1 Barney Pell's research on computer game playing .
  20. ↑ "Metagame and General Game Playing". http://satirist.org/learn-game/projects/metagame.html. 
  21. ↑ Available: Universal Game Engine email to comp.ai.games by Jeff Mallett, 10-Dec-1998.
  22. ↑ "UZH - z-Tree - Zurich Toolbox for Readymade Economic Experiments" (in en). https://www.ztree.uzh.ch/en.html. 
  23. ↑ Beckenkamp, Martin; Hennig‐Schmidt, Heike; Maier-Rigaud, Frank P. (1 March 2007) (in en). Cooperation in Symmetric and Asymmetric Prisoner's Dilemma Games. Social Science Research Network. 
  24. ↑ 24.0 24.1 Schaul, Tom (7 February 2020). "schaul/py-vgdl". https://github.com/schaul/py-vgdl. 
  25. ↑ GGP Server , platform for competition of general game playing systems.
  26. ↑ Dresden GGP Server , platform for competition of general game playing systems with automatic scheduling of matches.
  27. ↑ "General Game Playing". http://www.general-game-playing.de/. 
  28. ↑ Information about Fluxplayer , the winner of the 2nd International General Game Playing competition.
  29. ↑ Information about CADIAPlayer , more information about the winner of the 3rd, 4th, and 8th International General Game Playing competitions.
  30. ↑ Sancho is GGP Champion 2014! , winner of the 2014 International General Game Playing competition.
  31. ↑ Tagiew, Rustam (2009). Filipe, Joaquim; Fred, Ana; Sharp, Bernadette. eds. Towards a framework for management of strategic interaction. Porto, Portugal. pp. 587–590. ISBN 978-989-8111-66-1. https://www.scitepress.org/Papers/2009/15365/15365.pdf. Retrieved 2021-06-02. 
  32. ↑ Tagiew, Rustam (2011). Strategische Interaktion realer Agenten Ganzheitliche Konzeptualisierung und Softwarekomponenten einer interdisziplinären Forschungsinfrastruktur (neue Ausg ed.). Saarbrücken. ISBN 9783838125121. 
  33. ↑ "Zillions of Games - Who Are We?". http://www.zillions-of-games.com/whoarewe.html. 
  34. ↑ "AiAi Home Page – Stephen Tavener" (in en-US). http://mrraow.com/index.php/aiai-home/. 
  35. ↑ "Ai Ai announcement thread". BoardGameGeek. https://boardgamegeek.com/thread/1421771/ai-ai-announcement-thread/page/1. 
  36. ↑ "The PolyGamo Player Project | Programming Languages and General Players for Abstract Games and Puzzles" (in en-AU). http://www.polyomino.com/. 
  37. ↑ "Ludii Portal | Home of the Ludii General Game System" (in en-AU). http://ludii.games/. 
  38. ↑ "Digital Ludeme Project | Modelling the Evolution of Traditional Games" (in en-AU). http://ludeme.eu/. 
  39. ↑ Piette, E.; Soemers, D. J. N. J.; Stephenson, M.; Sironi, C.; Stephenson, M.; Winands M. H. M.; Browne, C. (2020). "Ludii – The Ludemic General Game System". European Conference on Artificial Intelligence (ECAI 2020), Santiago de Compestela. http://ludeme.eu/outputs/ecai-ludii-arxiv.pdf. Retrieved 2021-10-27. 
  40. ↑ Nielsen, Thorbjørn S.; Barros, Gabriella A. B.; Togelius, Julian; Nelson, Mark J.. "Towards generating arcade game rules with VGDL". http://julian.togelius.com/Nielsen2015Towards.pdf. 
  41. ↑ 41.0 41.1 Levine, John; Congdon, Clare Bates; Ebner, Marc; Kendall, Graham; Lucas, Simon M.; Miikkulainen Risto, Schaul; Tom, Thompson; Tommy. "General Video Game Playing". http://people.idsia.ch/~tom/publications/dagstuhl-gvgp.pdf. 
  42. ↑ Neufeld, Xenija; Mostaghim, Sanaz; Perez-Liebana, Diego. "Procedural Level Generation with Answer Set Programming for General Video Game Playing". http://www.diego-perez.net/papers/PLG_ASP_GVG.pdf. 
  43. ↑ Świechowski, Maciej; Park, Hyunsoo; Mańdziuk, Jacek; Kim, Kyung-Joong (2015). "Recent Advances in General Game Playing" (in en). The Scientific World Journal (Hindawi Publishing Corporation) 2015: 986262. doi:10.1155/2015/986262. PMID 26380375. 
  44. ↑ 44.0 44.1 "Monte-Carlo Tree Search for General Game Playing". https://www.researchgate.net/publication/228393769. 
  45. ↑ Finnsson, Hilmar (2012). "Generalized Monte-Carlo Tree Search Extensions for General Game Playing". Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/viewFile/4935/5300. Retrieved 2016-04-09. 
  46. ↑ Frydenberg, Frederik; Anderson, Kasper R.; Risi, Sebastian; Togelius, Julian. "Investigating MCTS Modifications in General Video Game Playing". http://julian.togelius.com/Frydenberg2015Investigating.pdf. 
  47. ↑ 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
  48. ↑ "Changing the root node from a previous game step.". https://www.researchgate.net/figure/Changing-the-root-node-from-a-previous-game-step_fig1_280087542. "DBS: A Directed Breadth First Search (DBS) algorithm" 
  49. ↑ 49.0 49.1 Perez, Diego; Dieskau, Jens; Hünermund, Martin. "Open Loop Search for General Video Game Playing". http://www.diego-perez.net/papers/OpenLoopGVG.pdf. 
  50. ↑ Jesper Juul. Half-Real: Video Games Between Real Rules and Fictional Worlds. MIT Press, 2005.

External links




Retrieved from "https://handwiki.org/wiki/index.php?title=General_game_playing&oldid=3375610"