일반적인 게임 플레이

General game playing
시리즈의 일부
인공지능
Anatomy-1751201 1280.png
주요 목표
접근
철학
역사
테크놀로지
용어집

GGP(General Game Playing)는 두 개 이상의 게임을 성공적으로 [1][2][3]할 수 있도록 인공지능 프로그램을 설계한 것이다.체스와 같은 많은 게임의 경우, 컴퓨터는 특별히 설계된 알고리즘을 사용하여 이러한 게임을 하도록 프로그램 되어 있는데, 이 알고리즘은 다른 맥락으로 옮겨질 수 없다.예를 들어, 체스를 두는 컴퓨터 프로그램은 체커를 할 수 없다.일반적인 게임 플레이는 인공지능으로 [4]가는 길에 필요한 이정표로 여겨진다.

General Video Game Playing(GVGP; 일반 비디오 게임 플레이)은 비디오 게임을 하는 목적에 맞게 조정된 GGP의 개념입니다.비디오 게임은 게임 규칙 다중 반복하거나 정복되는 이상 TD-Gammon,[5] 같은 인공적인 선수들에 또는 수동으로 도메인 고유 언어에 미리 전통적인 소변이 마려워요에서 같은 인공적인 players[6][7]에 보낸 있다 2013년부터 중요한 진보가 깊은 강화 학습 접근법에 따라 나 만들었어요ncluding아타리 2600 게임을[8][5][9][10][11] 할 수 있는 프로그램 개발뿐만 아니라 닌텐도 엔터테인먼트 시스템 [12][13][14]게임을 할 수 있는 프로그램 개발.

일반 게임 플레이 기술의 첫 번째 상업적 사용은 1998년 질리언즈 오브 게임즈였다.2003년부터 [15][16][17][18]온라인 경매에서 공급망 관리를 담당하는 거래업자를 대상으로 가격협상을 통해 일반 게임플레이를 통해 일반 게임 플레이가 제안됐다.

역사

1992년 바니 펠은 메타 게임 플레이의 개념을 정의하고 "메타 게임" 시스템을 개발했습니다.이것은 체스 같은 게임의 게임 규칙을 자동으로 생성하는 첫 번째 프로그램이었고, 자동화된 게임 생성을 사용하는 가장 초기의 프로그램 중 하나였다.그 후 Pell은 Metagamer [19]시스템을 개발했습니다.이 시스템은 게임 설명 언어(GDL)라고 불리는 특별한 언어로 정의된 게임 규칙과 같은 많은 체스 게임을 게임 [20]생성 후 어떠한 사람의 개입 없이 실행할 수 있었다.

1998년에 Jeff Mallett와 Mark Lefler에 의해 상업용 시스템인 Zillions of Games가 개발되었습니다.이 시스템은 게임 규칙을 정의하기 위해 LISP와 같은 언어를 사용했습니다.질리언스오브게임즈는 피스 이동성, 보드 구조, 게임 목표에 따라 자동으로 게임 규칙에서 평가 기능을 도출했다.또한 컴퓨터 체스 시스템에서 볼 수 있는 일반적인 알고리즘(이동 순서를 사용한 알파 베타 가지치기, 전위 테이블 등)[21]을 사용하였습니다.이 패키지는 2007년에 완전한 Fourth 기반 프로그래밍 언어를 통합한 대체 메타게임 엔진인 Axiom 플러그인을 추가함으로써 확장되었습니다.

1998년에 Urs Fischbacher에 [22]의해 z-Tree가 개발되었습니다.z-Tree는 실험 경제학을 위한 최초의 소프트웨어 도구이자 가장 많이 인용된 도구입니다.z-Tree는 인간 피험자를 대상으로 한 게임 이론 실험을 위해 z-Tree 언어로 게임 규칙을 정의할 수 있습니다.그것은 또한 [23]피실험자를 가지고 놀이에 참여하는 컴퓨터 플레이어의 정의를 가능하게 한다.

2005년에 스탠포드 프로젝트 일반 게임 플레이가 [3]설립되었습니다.

2012년에는 PyVGDL 개발이 시작되었습니다.[24]

GGP의 실장

스탠포드 프로젝트

General Game Playing은 일반 게임 플레이를 위한 플랫폼을 만드는 것을 목표로 하는 캘리포니아 스탠포드 대학의 Stanford Logic Group의 프로젝트이다.이는 GGP AI 표준화에 있어 가장 잘 알려진 작업이며 일반적으로 GGP 시스템의 표준으로 간주됩니다.게임은 게임 설명 언어로 표시되는 규칙 집합에 의해 정의됩니다.게임을 플레이하기 위해 플레이어는 적법성을 감시하고 플레이어의 상태 변화를 계속 알려주는 게임 호스팅[25][26] 서버와 상호작용합니다.

2005년부터 매년 AAAI 총회에서 일반 게임 플레이 대회가 개최되고 있다.대회에서는 각 개인전에서의 성적을 기록함으로써 경쟁사 AI의 다양한 게임 플레이 능력을 판단한다.대회 첫 단계에서는 참가자들의 법적 움직임과 우위를 점하고 게임을 더 빨리 완료할 수 있는 능력으로 평가된다.다음 결선투표에서 AI들은 점점 더 복잡해지는 게임에서 서로 맞붙는다.이 단계에서 가장 많은 게임을 획득한 AI가 대회에서 우승하며 2013년까지는 1만 달러의 [19]상금을 받곤 했다.지금까지,[27] 다음의 프로그램이 승리했습니다.

연도 이름. 개발자 기관. 참조
2005 클룬플레이어 짐 클룬 UCLA
2006 플럭스 플레이어 스테판 쉬펠과 마이클 틸셔 드레스덴 공과대학교 [28]
2007 캐디아플레이어 잉비 비욘손과 힐마르 핀손 레이캬비크 대학교 [29]
2008 캐디아플레이어 잉비 비욘손, 힐마르 핀손, 길피 토르 구드문트손 레이캬비크 대학교
2009 아리 장 메하 파리 8 대학교
2010 아리 장 메하 파리 8 대학교
2011 터보터틀 샘 슈라이버
2012 캐디아플레이어 힐마르 핀슨과 잉비 비욘손 레이캬비크 대학교
2013 터보터틀 샘 슈라이버
2014 산초 스티브 드레이퍼와 앤드류 로즈 [30]
2015 아연도금 리처드 엠슬리
2016 우드 스톡 에릭 피에트 아르토이스 대학교

기타 접근법

게임 규칙을 정의하기 위해 그들만의 언어를 사용하는 다른 일반적인 게임 플레이 시스템이 있습니다.기타 일반적인 게임 플레이 소프트웨어는 다음과 같습니다.

시스템. 연도 묘사
프라마시 2009 박사학위[31][32] 논문 중 일반적인 게임 플레이 및 경제 실험용으로 개발됨
아이아이 2015-2017 Stephen Tavener(이전 Zillions 개발자)[33][34][35]가 개발
PolyGamo 플레이어 2017 David M에 의해 출시되었습니다.2017년 9월 [36]베넷은 유니티 게임 엔진을 기반으로 합니다.
루디 2020 마스트리히트 대학의 Cameron Browne과 그의 팀이 ERC가 출자하는 디지털 루데메 [37][38][39]프로젝트의 일환으로 발표했습니다.

GVGP의 실장

강화 학습

GVGP는 실제 비디오 게임 AI를 자동으로 생성하기 위해 사용될 수 있을 뿐만 아니라 "절차적인 콘텐츠 생성을 사용하여 자동으로 생성된 환경을 포함한 게임 환경을 테스트하고 인간 플레이어가 이용할 수 있는 게임 플레이의 잠재적인 허점을 발견하기 위해 사용될 수 있다."[7]GVGP는 또한 게임 규칙을 생성하고 RAPP(Relative Algorithm Performance Profiles)를 기반으로 게임의 품질을 추정하는 데 사용되었습니다. RAPP는 게임이 허용하는 기술 차이를 좋은 AI와 나쁜 [40]AI 사이에서 비교합니다.

비디오 게임 설명 언어

GVGAI(General Video Game AI Competition)는 2014년부터 운영되고 있다.이 대회에서는 GGP 대회에서 사용되는 보드 게임 대신 1980년대 아케이드 및 콘솔 게임과 유사한 2차원 비디오 게임이 사용됩니다.연구자와 실무자가 최고의 일반 비디오 게임 플레이 알고리즘을 테스트하고 비교할 수 있는 방법을 제공했습니다.경쟁사는 비디오 게임 기술 언어(VGDL)로 작성된 다수의 게임을 포함한 관련 소프트웨어 프레임워크를 가지고 있으며, GDL과 혼동해서는 안 되며 간단한 의미론과 쉽게 구문 분석할 수 있는 명령을 사용하는 코딩 언어입니다.VGDL의 한 예는 [6][24]2013년에 개발된 PyVGDL입니다.GVGP에서 사용되는 게임들은 현재 가장 단순하고 [41]정량화하기 쉬운 2차원 아케이드 게임인 경우가 많다.비디오 게임을 해석할 수 있는 AI를 만드는 과정을 간소화하기 위해 이를 위한 게임을 수동으로 VGDL로 작성한다.VGDL은 ASP(Answer Set Programming) 및 EA(Evolutionary Algorithm)를 사용하여 프로시저 레벨 생성에 특화된 게임을 기술하기 위해 사용할 수 있습니다.그런 다음 GVGP를 사용하여 절차 수준의 유효성 및 에이전트의 수행 [42]방법에 따른 수준의 난이도 또는 품질을 테스트할 수 있습니다.

알고리즘

GGP AI는 여러 게임을 할 수 있도록 설계해야 하기 때문에 특정 게임 전용 알고리즘에 의존할 수 없다.대신 AI는 다양한 게임에 적용할 수 있는 알고리즘을 사용해 설계해야 한다.AI는 또한 이전 상태의 출력이 아닌 현재 상태에 적응할 수 있는 진행 중인 과정이어야 한다.이 때문에 오픈루프 기법이 가장 [43]효과적인 경우가 많습니다.

GGP AI를 개발하는 일반적인 방법은 Monte Carlo Tree Search([44]MCTS) 알고리즘입니다.UCT 방식(Upper Confidence Bound to Trees)과 함께 자주 사용되는 MCTS의 변형은 비디오 게임 [45][46][47]플레이와 호환성을 높이기 위해 제안되어 왔다.사용되는 트리 검색 알고리즘의 또 다른 변형으로는 Directed Width-first Search(DBS;[48] 다이렉트 폭 우선 검색)가 있습니다.Directed Width-first Search는 사용 가능한 각 액션에 대해 자노드가 생성되어 게임이 종료되거나 시간이 [49]다 될 때까지 가장 높은 평균 보상으로 주문된 각 어린이를 방문합니다.각 트리 서치 방법에서 AI는 잠재적인 행동을 시뮬레이션하고 [44][49]각 패스의 평균 최고 보상에 기초하여 획득된 포인트로 순위를 매긴다.

전제 조건

게임과 상호작용하기 위해서는 모든 게임이 공통의 특성을 공유한다는 가정 하에 알고리즘이 작동해야 합니다."Half-Real: Video Games Between Real Worlds and Fictional Worlds"라는 책에서 Jesper Juul은 게임의 정의를 다음과 같이 제시합니다.게임은 규칙을 기반으로 하고, 다양한 결과를 제공하며, 다른 결과를 제공하며, 플레이어의 노력은 결과에 영향을 미치고, 플레이어는 결과에 애착을 가지며,[50] 게임은 협상 가능한 결과를 가져옵니다.이러한 전제조건을 이용하여 플레이어의 입력, 게임 결과 및 다양한 규칙이 어떻게 적용되는지를 수치화하고 알고리즘을 사용하여 가장 유리한 [41]경로를 계산함으로써 게임 플레이 AI를 만들 수 있다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Pell, Barney (1992). H. van den Herik; L. Allis (eds.). "Metagame: a new challenge for games and learning" [Heuristic programming in artificial intelligence 3–the third computerolympiad] (PDF). Ellis-Horwood. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  2. ^ Pell, Barney (1996). "A Strategic Metagame Player for General Chess-Like Games". Computational Intelligence. 12 (1): 177–198. doi:10.1111/j.1467-8640.1996.tb00258.x. ISSN 1467-8640. S2CID 996006.
  3. ^ a b Genesereth, Michael; Love, Nathaniel; Pell, Barney (15 June 2005). "General Game Playing: Overview of the AAAI Competition". AI Magazine. 26 (2): 62. doi:10.1609/aimag.v26i2.1813. ISSN 2371-9621.
  4. ^ Canaan, Rodrigo; Salge, Christoph; Togelius, Julian; Nealen, Andy (2019). Leveling the playing field [Proceedings of the 14th International Conference on the Leveling the playing field: fairness in AI versus human game benchmarks]. dl.acm.org. pp. 1–8. doi:10.1145/3337722. ISBN 9781450372176. S2CID 58599284.
  5. ^ a b Mnih, Volodymyr; Kavukcuoglu, Koray; Silver, David; Graves, Alex; Antonoglou, Ioannis; Wierstra, Daan; Riedmiller, Martin (2013). "Playing Atari with Deep Reinforcement Learning" (PDF). Neural Information Processing Systems Workshop 2013. Retrieved 25 April 2015.
  6. ^ a b 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. CiteSeerX 10.1.1.360.2263. doi:10.1109/CIG.2013.6633610. ISBN 978-1-4673-5311-3. S2CID 812565.
  7. ^ a b 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. 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". Journal of Artificial Intelligence Research. 47: 253–279. arXiv:1207.4708. doi:10.1613/jair.3912. ISSN 1076-9757. S2CID 1552061.
  9. ^ Mnih, Volodymyr; Kavukcuoglu, Koray; Silver, David; Rusu, Andrei A.; Veness, Joel; Hassabis, Demis; Bellemare, Marc G.; Graves, Alex; Riedmiller, Martin; Fidjeland, Andreas K.; Stig Petersen, Georg Ostrovski; Beattie, Charles; Sadik, Amir; Antonoglou, Ioannis; King, Helen; Kumaran, Dharshan; Wierstra, Daan; Legg, Shane (26 February 2015). "Human-level control through deep reinforcement learning". Nature. 518 (7540): 529–533. Bibcode:2015Natur.518..529M. doi:10.1038/nature14236. PMID 25719670. S2CID 205242740.
  10. ^ Korjus, Kristjan; Kuzovkin, Ilya; Tampuu, Ardi; Pungas, Taivo (2014). "Replicating the Paper "Playing Atari with Deep Reinforcement Learning"" (PDF). University of Tartu. Retrieved 25 April 2015.
  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" (PDF). NIPS Proceedingsβ. Conference on Neural Information Processing Systems. Retrieved 25 April 2015.
  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." (PDF). SIGBOVIK. Retrieved 25 April 2015.
  13. ^ Murphy, Tom. "learnfun & playfun: A general technique for automating NES games". Retrieved 25 April 2015.
  14. ^ Teller, Swizec (October 28, 2013). "Week 2: Level 1 of Super Mario Bros. is easy with lexicographic orderings and". A geek with a hat. Retrieved 25 April 2015.
  15. ^ McMillen, Colin (2003). "Toward the Development of an Intelligent Agent for the Supply Chain Management Game of the 2003 Trading Agent Competition" [2003 Trading Agent Competition]. Master's Thesis. Minneapolis, MN: University of Minnesota. S2CID 167336006. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  16. ^ Zhang, Dongmo (2009). From general game descriptions to a market specification language for general trading agents [Agent-mediated electronic commerce. Designing trading strategies and mechanisms for electronic markets.]. Berlin, Heidelberg: Springer. pp. 259–274. Bibcode:2010aecd.book..259T. CiteSeerX 10.1.1.467.4629.
  17. ^ "AGAPE - An Auction LanGuage for GenerAl Auction PlayErs". AGAPE (in French). Retrieved 5 March 2020.
  18. ^ Michael, Friedrich; Ignatov, Dmitry (2019). "General Game Playing B-to-B Price Negotiations" (PDF). CEUR Workshop Proceedings. -2479: 89–99. Retrieved 5 March 2020.
  19. ^ a b Wayback Machine에서 Archived 2007-08-12를 플레이하는 컴퓨터 게임에 대한 Barney Pell의 연구.
  20. ^ "Metagame and General Game Playing". Metagame and General Game Playing. Retrieved 27 March 2016.
  21. ^ 이용 가능: Jeff Mallett의 Universal Game Engine 이메일 comp.ai.1998년 12월 10일
  22. ^ "UZH - z-Tree - Zurich Toolbox for Readymade Economic Experiments". www.ztree.uzh.ch. Retrieved 17 February 2020.
  23. ^ Beckenkamp, Martin; Hennig‐Schmidt, Heike; Maier-Rigaud, Frank P. (1 March 2007). "Cooperation in Symmetric and Asymmetric Prisoner's Dilemma Games". Social Science Research Network. SSRN 968942. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  24. ^ a b Schaul, Tom (7 February 2020). "schaul/py-vgdl". GitHub.
  25. ^ GGP 서버, 일반 게임 플레이 시스템 경쟁 플랫폼.
  26. ^ Dresden GGP Server는 경기 자동 스케줄링을 갖춘 일반 게임 플레이 시스템 경쟁 플랫폼입니다.
  27. ^ "General Game Playing". www.general-game-playing.de.
  28. ^ 제2회 국제 종합 게임 플레이 대회 우승자 플럭스 플레이어에 대한 정보입니다.
  29. ^ CADIAPlayer에 대한 정보, 제3회, 제4회 및 제8회 국제 일반 게임 플레이 대회 우승자에 대한 자세한 정보.
  30. ^ 산초는 GGP 챔피언 2014!로 2014 국제 종합 게임 플레이 대회 우승자입니다.
  31. ^ Tagiew, Rustam (2009). Filipe, Joaquim; Fred, Ana; Sharp, Bernadette (eds.). Towards a framework for management of strategic interaction [Proceedings of the International Conference on Agents and Artificial Intelligence] (PDF). Porto, Portugal. pp. 587–590. ISBN 978-989-8111-66-1.
  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?". www.zillions-of-games.com. Retrieved 2017-11-16.
  34. ^ "AiAi Home Page – Stephen Tavener". mrraow.com. Retrieved 2017-11-16.
  35. ^ "Ai Ai announcement thread". BoardGameGeek. Retrieved 2017-11-16.
  36. ^ "The PolyGamo Player Project Programming Languages and General Players for Abstract Games and Puzzles". www.polyomino.com. Retrieved 2017-11-16.
  37. ^ "Ludii Portal Home of the Ludii General Game System". www.ludii.games. Retrieved 2021-10-27.
  38. ^ "Digital Ludeme Project Modelling the Evolution of Traditional Games". www.ludeme.eu. Retrieved 2021-10-27.
  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" (PDF). European Conference on Artificial Intelligence (ECAI 2020), Santiago de Compestela.
  40. ^ Nielsen, Thorbjørn S.; Barros, Gabriella A. B.; Togelius, Julian; Nelson, Mark J. "Towards generating arcade game rules with VGDL" (PDF).
  41. ^ a b Levine, John; Congdon, Clare Bates; Ebner, Marc; Kendall, Graham; Lucas, Simon M.; Miikkulainen Risto, Schaul; Tom, Thompson; Tommy. "General Video Game Playing" (PDF).
  42. ^ Neufeld, Xenija; Mostaghim, Sanaz; Perez-Liebana, Diego. "Procedural Level Generation with Answer Set Programming for General Video Game Playing" (PDF).
  43. ^ Świechowski, Maciej; Park, Hyunsoo; Mańdziuk, Jacek; Kim, Kyung-Joong (2015). "Recent Advances in General Game Playing". The Scientific World Journal. Hindawi Publishing Corporation. 2015: 986262. doi:10.1155/2015/986262. PMC 4561326. PMID 26380375.
  44. ^ a b "Monte-Carlo Tree Search for General Game Playing". ResearchGate. Retrieved 2016-04-01.
  45. ^ Finnsson, Hilmar (2012). "Generalized Monte-Carlo Tree Search Extensions for General Game Playing". Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence.
  46. ^ Frydenberg, Frederik; Anderson, Kasper R.; Risi, Sebastian; Togelius, Julian. "Investigating MCTS Modifications in General Video Game Playing" (PDF).
  47. ^ M. Swiechowski; J. Mandziuk; Y. S. Ong, "UCT 기반의 일반 게임 플레이 프로그램의 1인용 게임에 특화", IEEE Transactions on Computational Intelligence and AI in Games, vol.PP, No.99, 페이지 1-1 doi:10.1109/TCIAIG.2015.2391232
  48. ^ "Changing the root node from a previous game step". DBS: A Directed Breadth First Search (DBS) algorithm{{cite web}}: CS1 maint :url-status (링크)
  49. ^ a b Perez, Diego; Dieskau, Jens; Hünermund, Martin. "Open Loop Search for General Video Game Playing" (PDF).
  50. ^ Jesper Juul.Half-Real: 현실의 규칙과 허구의 세계 사이의 비디오 게임.MIT Press, 2005.

외부 링크

CS227B - General Game Playing 코스 페이지, GGP.org, GGP.org GitHub 페이지 및 games.stanford.edu도 참조하십시오.

비디오