게임 설명 언어
Game Description LanguageGDL(Game Description Language)은 Michael Genesret가 캘리포니아 스탠포드 대학의 General Game Playing Project의 일부로 설계한 논리 프로그래밍[1] 언어입니다.GDL은 게임의 상태를 일련의 사실로 표현하고 게임 역학을 논리적 규칙으로 표현합니다.이로써 GDL은 게임 이론상의 문제에 대한 [2]대체 표현 중 하나이다.
GDL의 목적
뉴사이언티스트 기사에서 인용한 제네세레스는 딥 블루가 그랜드마스터급으로 체스를 둘 수는 있지만 전문 게임 [3]플레이어이기 때문에 체커 게임을 전혀 할 수 없다고 지적했다.체스와 체커는 모두 GDL로 기술할 수 있습니다.이것에 의해, GDL로 기술할 수 있는 게임과 그 외의 게임을 모두 플레이 할 수 있는 일반 게임 플레이어를 만들 수 있습니다.
사양
구문
GDL은 Datalogger의 변형이며 구문은 거의 동일합니다.보통 프리픽스 표기법으로 표시됩니다.변수는 "로 시작합니다.?"[4]
키워드
다음으로 GDL 내의 키워드 목록과 그 기능의 개요를 나타냅니다.
distinct- 이 술어는 두 용어가 구문적으로 달라야 할 때 사용됩니다.
does- 술어
does(?r,?m)그 플레이어(또는 역할)를 의미합니다.?r움직이다?m현재 게임 상태에서.
goal- 술어
goal(?r,?n)목표값을 정의하는 데 사용됩니다.?n역할의 경우 (통상 0에서 100 사이의 자연수)?r현재 상태에서는
init- 이 술어는 초기 게임 상태에 대한 진정한 사실을 나타냅니다.
legal- 술어
legal(?r,?m)라는 의미이다?m역할을 위한 법적 조치이다?r현재 상태에서는
next- 이 술어는 다음 게임 상태에 대한 진정한 사실을 나타냅니다.
role- 이 술어는 플레이어의 이름을 추가하는 데 사용됩니다.
terminal- 이 술어는 현재 상태가 terminal임을 나타냅니다.
true- 이 술어는 현재 게임 상태에 대한 진정한 사실을 나타냅니다.
규칙.
GDL의 게임 설명은 게임의 다음 요소 각각에 대한 완전한 규칙을 제공합니다.
플레이어
게임에서의 역할을 정의하는 사실.다음 예는 2인용 게임 Tic-tac-toe의 GDL 설명에서 나온 것입니다.
(역할 xplayer) (역할 oplayer)
초기 상태
초기 게임 상태에 대한 모든 사실을 포함하는 규칙입니다.예를 들어 다음과 같습니다.
(init(셀 1 1 공백))... (init(셀 3 3 공백))(init(컨트롤 xplayer))
법적 조치
플레이어가 취할 수 있는 현재 포지션의 조건에 따라 각 움직임을 설명하는 규칙입니다.예를 들어 다음과 같습니다.
(<=>(합법적인 플레이어 (마크. ?m ?n)) (진실의 (감방 ?m ?n 백지)) (진실의 (통제 플레이어))) 게임 상태 업데이트
현재 상태 및 플레이어의 움직임과 관련된 다음 상태에 대한 모든 사실을 설명하는 규칙입니다.예를 들어 다음과 같습니다.
(<=>(다음 분. (감방 ?m ?n x)) (한다 x플레이어 (마크. ?m ?n))) (<=>(다음 분. (감방 ?m ?n o)) (한다 플레이어 (마크. ?m ?n))) 종료
현재 상태가 터미널 상태임을 나타내는 규칙.예를 들어 다음과 같습니다.
(<= 단자(x선))(<= 단자(o선))(<= 단자가 보드를 열지 않음)
목표 상태
터미널 상태에 있는 각 플레이어의 목표값.예를 들어 다음과 같습니다.
(<=>(목표 x플레이어 100) (선 x)) (<=>(목표 플레이어 0) (선 x)) 내선번호
GDL-II
GDL을 사용하면 임의의 수의 플레이어로 유한한 게임을 기술할 수 있습니다.그러나, GDL은 우연의 요소를 포함하는 게임(예: 주사위 굴리기)이나 플레이어가 게임의 현재 상태에 대한 불완전한 정보를 가지고 있는 게임(예: 많은 카드 게임에서는 상대의 카드가 보이지 않음)을 설명할 수 없다.GDL-II는 불완전한 정보 게임을 위한 게임 기술 언어로서 우연의 요소 및 불완전한 [5]정보를 기술할 수 있도록 GDL을 2개의 키워드로 확장합니다.
sees- 술어
sees(?r,?p)그 역할을 의미한다?r인식하다?p다음 게임 상태에서.
random- 이 상수는 무작위로 이동을 선택하는 미리 정의된 플레이어를 나타냅니다.
다음은 Texas hold'em 카드게임의 GDL-II 설명의 예입니다.
(<=>(보다 플레이어 카드) (한다 랜덤 (deal_face_down(면 아래로) 플레이어 카드))) (<=>(보다 ?r 카드) (역할. ?r) (한다 랜덤 (del_river 카드))) GDL-III
Michael Thielscher는 또한 불완전한 정보와 자기 성찰이 있는 일반적인 게임 기술 언어인 GDL-II를 추가 확장하여 인식론적 게임(플레이어의 [6]지식에 의존하는 규칙)의 지정을 지원합니다.
게임 표현을 위한 기타 형식 및 언어
고전 게임 이론에서 게임은 광범위하고 정상적인 형태로 공식화될 수 있습니다.협동 게임 이론에서는 게임을 특징적인 함수로 표현한다.일부 게임 하위 클래스는 간결한 게임이라고도 하는 더 작은 크기의 특별한 표현을 허용합니다.게임의 일부 하위 클래스나 학제간 연구의 필요에 따라 조정된 표현을 표현하기 위한 형식주의와 언어의 새로운 발전 중 일부는 다음 [7]표와 같이 요약된다.이러한 대체 표현 중 일부는 시간 관련 측면도 인코딩합니다.
| 이름. | 연도 | 수단 | 게임의 종류 | 시간을 |
|---|---|---|---|---|
| 폭주 게임[8] | 1973 | 기능들 | n인용 게임의 서브셋, 동시 이동 | 아니요. |
| 시퀀셜[9] 폼 | 1994 | 매트릭스 | 불완전한 정보의 2인용 게임 | 아니요. |
| 시간[10][11] 제한 게임 | 1994 | 기능들 | 2인용 게임 | 네. |
| 갈라[12] | 1997 | 논리 | 불완전한 정보의 n인칭 게임 | 아니요. |
| 로컬 이펙트[13] 게임 | 2003 | 기능들 | n인용 게임의 서브셋, 동시 이동 | 아니요. |
| 게임 페트리넷[14] | 2006 | 페트리넷 | 결정론적 n-person 게임, 동시 이동 | 아니요. |
| 연속[15] 게임 | 2007 | 기능들 | 불완전한 정보의 2인용 게임 서브셋 | 네. |
| PNSI[16][17] | 2008 | 페트리넷 | 불완전한 정보의 n인칭 게임 | 네. |
| 액션 그래프[18] 게임 | 2012 | 그래프, 함수 | n인용 게임, 동시 이동 | 아니요. |
| 그래픽 게임[19] | 2015 | 그래프, 함수 | n인용 게임, 동시 이동 | 아니요. |
적용들
![[icon]](/wiki/File:Wiki_letter_w_cropped.svg){kind=small} |
2016년 논문은 "GDL에서 일반적인 게임 기술을 편집한 다단계 알고리즘을 낮은 수준의 언어로 최적화된 이성자로 기술한다."[20]
2017년 논문은 GDL을 사용하여 두 당사자 간의 분쟁을 해결하는 과정을 모델링하고,[21] 이를 위해 이용 가능한 정보를 효율적으로 사용하는 알고리즘을 제시했다.
「 」를 참조해 주세요.
레퍼런스
- ^ "Game Definition Language". games.stanford.edu.
- ^ Tagiew, Rustam (2011). Averkin, Alexey N.; Ignatov, Dmitry I.; Mitra, Sushmita; Poelmans, Jonas (eds.). "Beyond Analytical Modeling, Gathering Data to Predict Real Agents' Strategic Interaction" [Soft Computing Applications and Knowledge Discovery] (PDF). CEUR Workshop Proceedings. Moscow, Russia. 758: 113–124.
- ^ Biever, Celeste (2006-07-29). "Producing the ultimate game-playing bots - tech - 29 July 2006 - New Scientist Tech". Archived from the original on 11 August 2007.
- ^ Love, N; Genesereth, M; Hinrichs, T (2006). "General game playing: game description language specification. Tech. Rep. LG-2006-01" (PDF). Stanford University. Stanford University, Stanford. Retrieved 1 July 2019.
- ^ Thielscher, M (2010). Fox, M; Poole, D (eds.). "A general game description language for incomplete information games". Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010. Atlanta: AAAI Press. Retrieved 1 July 2019.
- ^ Thielscher, Michael (2017). "GDL-III: A Description Language for Epistemic General Game Playing" (PDF). Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. IJCAI. ISBN 978-0-9992411-0-3. Retrieved 1 July 2019.
- ^ Tagiew, Rustam (3 May 2011). "If more than Analytical Modeling is Needed to Predict Real Agents' Strategic Interaction". arXiv:1105.0558 [cs.GT].
- ^ Rosenthal, Robert W. (December 1973). "A class of games possessing pure-strategy Nash equilibria". International Journal of Game Theory. 2 (1): 65–67. doi:10.1007/BF01737559. S2CID 121904640.
- ^ Koller, Daphne; Megiddo, Nimrod; von Stengel, Bernhard (1994). "Fast algorithms for finding randomized strategies in game trees". STOC '94: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing: 750–759. doi:10.1145/195058.195451. ISBN 0-89791-663-8. S2CID 1893272.
- ^ Alur, Rajeev; Dill, David L. (April 1994). "A theory of timed automata". Theoretical Computer Science. 126 (2): 183–235. doi:10.1016/0304-3975(94)90010-8.
- ^ Tomlin, C.J.; Lygeros, J.; Shankar Sastry, S. (July 2000). "A game theoretic approach to controller design for hybrid systems". Proceedings of the IEEE. 88 (7): 949–970. doi:10.1109/5.871303. S2CID 1844682.
- ^ Koller, Daphne; Pfeffer, Avi (1997). "Representations and solutions for game-theoretic problems" (PDF). Artificial Intelligence. 94 (1–2): 167–215. doi:10.1016/S0004-3702(97)00023-4.
- ^ Leyton-Brown, Kevin; Tennenholtz, Moshe (2003). "Local-effect games". IJCAI'03: Proceedings of the 18th International Joint Conference on Artificial Intelligence.
- ^ Clempner, Julio (2006). "Modeling shortest path games with Petri nets: a Lyapunov based theory". International Journal of Applied Mathematics and Computer Science. 16 (3): 387–397. ISSN 1641-876X.
- ^ Sannikov, Yuliy (September 2007). "Games with Imperfectly Observable Actions in Continuous Time" (PDF). Econometrica. 75 (5): 1285–1329. doi:10.1111/j.1468-0262.2007.00795.x.
- ^ Tagiew, Rustam (December 2008). "Multi-Agent Petri-Games". 2008 International Conference on Computational Intelligence for Modelling Control Automation: 130–135. doi:10.1109/CIMCA.2008.15. ISBN 978-0-7695-3514-2. S2CID 16679934.
- ^ Tagiew, Rustam (2009). "On Multi-agent Petri Net Models for Computing Extensive Finite Games". New Challenges in Computational Collective Intelligence. Studies in Computational Intelligence. Springer. 244: 243–254. doi:10.1007/978-3-642-03958-4_21. ISBN 978-3-642-03957-7.
- ^ Bhat, Navin; Leyton-Brown, Kevin (11 July 2012). "Computing Nash Equilibria of Action-Graph Games". arXiv:1207.4128 [cs.GT].
- ^ Kearns, Michael; Littman, Michael L.; Singh, Satinder (7 March 2015). "Graphical Models for Game Theory". arXiv:1301.2281 [cs.GT].
- ^ Kowalski, Jakub; Szykuła, Marek (2013). "Game Description Language Compiler Construction". AI 2013: Advances in Artificial Intelligence: 26th Australasian Joint Conference, Dunedin, New Zealand, December 1-6, 2013. Proceedings. pp. 234–245. Retrieved 1 July 2019.
- ^ de Jonge, Dave; Trescak, Tomas; Sierra, Carles; Simoff, Simeon; López de Mántaras, Ramon (2017). "Using Game Description Language for mediated dispute resolution". AI & Society. Springer. 2017 (4): 767–784. doi:10.1007/s00146-017-0790-8. S2CID 22738517.
