게임의 복잡성

Game complexity

조합 게임 이론은 게임의 복잡성 측정하는 가지 방법이 있습니다.이 기사에서는 상태-공간 복잡도, 게임 트리 크기, 의사결정 복잡도, 게임 트리 복잡도 및 계산 복잡도의 5가지에 대해 설명합니다.

게임 복잡도 측정

상태 공간의 복잡성

게임의 상태 공간 복잡도는 게임의 [1]초기 위치에서 도달 가능한 합법적인 게임 위치 수입니다.

이것이 계산하기 너무 어려운 경우, 종종 (일부) 불법 포지션을 카운트함으로써 상한을 계산할 수 있습니다. 즉, 게임 중에 절대 발생할 수 없는 포지션을 의미합니다.

게임 트리 크기

게임 트리 크기는 플레이할 수 있는 총 게임 수: 게임의 초기 위치에 뿌리를 둔 게임 트리 내의 리프 노드 수입니다.

게임 트리는 일반적으로 상태 공간보다 훨씬 더 큽니다. 왜냐하면 많은 게임에서 같은 위치가 다른 순서로 이동함으로써 발생할 수 있기 때문입니다(예를 들어, 보드 위에 2개의 X와 1개의 O가 있는 틱택토 게임에서 이 위치는 첫 번째 X가 배치된 위치에 따라 두 가지 다른 방법으로 도달할 수 있습니다).게임 트리의 사이즈의 상한은, 다루기 쉬워질 때까지, 게임 트리의 사이즈를 증가시키는 것(예를 들면, 부정 이동을 허가하는 것)만으로 게임을 간략화함으로써 계산되는 경우가 있다.

이동 수가 제한되지 않는 게임의 경우(예를 들어 보드의 크기 또는 위치 반복에 관한 규칙에 따라) 게임 트리는 일반적으로 무한합니다.

의사결정 트리

다음 두 가지 척도는 "선수 A가 승리", "선수 B가 승리", 또는 "추첨"으로 라벨이 지정된 각 포지션과 함께 게임 트리의 하위 트리인 의사결정 트리의 아이디어를 사용한다(단말 위치는 그래프 내의 다른 위치만 검사하여 해당 값(양쪽이 가장 잘 플레이한다고 가정함)을 입증할 수 있는 경우).선수 A가 이동해야 하는 위치는 A가 승리하는 경우 "선수 A가 승리한다"고 라벨 붙일 수 있으며, 모든 후계자 위치가 B가 승리하는 경우 "선수 B가 승리한다"고 라벨 붙일 수 있으며, 모든 후계자 위치가 추첨되거나 B가 승리하는 경우 "추첨"으로 라벨 붙일 수 있다.B가 있는 위치가 이동하는 것에 대응합니다.)

의사결정의 복잡성

게임의 결정 복잡도는 초기 위치의 값을 설정하는 최소 결정 트리의 리프 노드 수입니다.

게임 트리의 복잡성

게임의 게임 트리 복잡도는 초기 [1]위치의 값을 설정하는 최소 전체 폭의 결정 트리에서 리프 노드의 수입니다.전폭 트리는 각 깊이의 모든 노드를 포함한다.

이것은 초기 위치의 값을 결정하기 위해 미니맥스 검색에서 평가해야 하는 위치 수의 추정치입니다.

게임 트리의 복잡도를 추정하는 것조차 어렵지만, 일부 게임에서는 게임의 평균 분기 계수 b를 평균 게임 내 플레이 d의 거듭제곱으로 올리거나 다음과 같이 근사치를 구할 수 있습니다.

C d \ \ b^ {

계산의 복잡성

게임의 계산 복잡도게임이 임의로 커질 때 점근 난이도를 나타내며 빅 O 표기법이나 복잡도 클래스의 멤버십으로 표현됩니다.이 개념은 특정 게임에 적용되는 것이 아니라 일반적으로 n-by-n 보드에서 플레이함으로써 임의로 크게 만들 수 있도록 일반화된 게임에 적용됩니다.(계산 복잡성의 관점에서 보드의 고정 크기 상의 게임은 O(1)에서 해결할 수 있는 유한한 문제입니다. 예를 들어 p-look-up table에서 확인할 수 있습니다.각 포지션에서 최적의 이동으로 이행합니다.)

점근 복잡도는 게임을 해결하기 위해 가장 효율적인 (어떤 계산 자원을 고려하든 간에) 알고리즘에 의해 정의됩니다; 가장 일반적인 복잡도 측정(계산 시간)은 항상 점근 상태-공간 복잡도의 대수에 의해 하한을 가집니다. 왜냐하면 솔루션 알고리즘은 가능한 모든 s에 대해 작동해야 하기 때문입니다.게임의 테이트.게임 패밀리에 적합한 특정 알고리즘의 복잡성에 의해 상한선이 지정됩니다.두 번째로 많이 사용되는 복잡도 측정, 즉 계산에서 사용되는 공간 또는 컴퓨터 메모리 용량에도 유사한 설명이 적용됩니다.알고리즘이 게임 상태를 저장할 필요가 없기 때문에 일반적인 게임의 공간 복잡도에 하한이 있다는 것은 명백하지 않다; 그러나 많은 관심 게임들이 PSPACE-hard인 것으로 알려져 있고, 그들의 공간 복잡도는 점근 상태-공간 복잡성의 대수에 의해 하한이 될 것이다.바운드는 이 양의 다항식일 뿐이지만 일반적으로 선형으로 알려져 있습니다.)

  • 깊이 우선 미니맥스 전략은 전체 트리를 탐색해야 하기 때문에 게임의 트리 복잡도에 비례하는 계산 시간과 트리 복잡도의 로그에서 메모리 다항식을 사용합니다. 알고리즘은 항상 가능한 각 이동 깊이에서 트리의 노드 하나를 저장해야 하며 가장 이동 깊이에서 노드 수를 저장해야 하기 때문입니다.정확히는 나무 복잡성입니다.
  • 역유도에서는 상태 공간의 복잡도에 비례하는 메모리와 시간을 모두 사용합니다.는 가능한 각 위치에 대해 올바른 움직임을 계산하고 기록해야 하기 때문입니다.

예: tic-tac-toe (0과 크로스)

틱토우에서 상태 공간의 크기에 대한 단순 상한이 39 = 19,683이다(각 셀에는 3개의 상태가 있고 9개의 셀이 있다).이 카운트는 5개의 크로스가 있고 0이 없는 포지션이나 두 선수 모두 3개의 열을 가진 포지션과 같은 많은 불법 포지션을 포함한다.이러한 부정한 위치를 제거하고 더 주의 깊게 카운트를 하면 5,[2][3]478이 됩니다.그리고 위치의 회전과 반사가 동일한 것으로 간주될 때 기본적으로 다른 위치는 765개뿐입니다.

게임 트리를 바인딩하기 위해서는 9개의 초기 이동, 8개의 응답 등이 있으므로 최대 9! 또는 총 362,880개의 게임이 있습니다.그러나 게임은 해결하는데 9번 미만이 걸릴 수 있으며 정확한 열거는 255,168개의 가능한 게임을 제공합니다.포지션의 회전과 반사를 동일시할 경우 가능한 게임은 2만6830개에 불과하다.

tic-tac-toe의 계산 복잡도는 일반화된 방법에 따라 달라집니다.자연적 일반화는 m, n, k 게임: m by n 보드 위에서 플레이하고 우승자가 k를 연달아 얻은 첫 번째 선수가 됩니다.DSPACE(mn)에서 게임 트리 전체를 검색하면 이 게임을 해결할 수 있다는 것은 단적으로 알 수 있다.이것에 의해, 중요한 복잡도 클래스 PSPACE에 배치됩니다.좀 더 많은 작업을 수행하면 PSPACE-완전인 [4]것으로 보일 수 있습니다.

일부 유명한 게임의 복잡성

게임 복잡도의 크기가 크기 때문에 이 표는 로그의 상한선을 10으로 합니다(즉, 자릿수).다음의 모든 수치는 주의 깊게 고려되어야 한다: 게임의 규칙에 대한 겉보기에는 사소한 변경은 엄청난 요인에 의해 숫자를 바꿀 수 있다(어쨌든 대략적인 추정치이다). 이는 표시된 숫자보다 훨씬 더 클 수 있다.

주의: 게임 트리 크기별로 정렬

게임 보드 크기

(표준)

상태 공간의 복잡성

(베이스 10에 로그로)

게임 트리의 복잡성

(베이스 10에 로그로)

평균 게임 길이

(플라이)

분기 계수 참조 적합한 일반 게임의 복잡도 클래스
틱택토 9 3 5 9 4 PSPACE-완전[5]
15 3 8 14 3.7 PSPACE-완전[6]
펜토미노 64 12 18 10 75 [7][8] ? 단, PSPACE에서는
칼라[9] 14 13 18 50 [7] 일반화가 불명확하다
4개의 연결 42 13 21 36 4 [1][10] ? 단, PSPACE에서는
지배(8 × 8) 64 15 27 30 8 [7] ?(, PSPACE에서는 특정[11] 치수의 경우 P)
콩깍 14 15 33 [7]
영어 드래프트(8x8) (체커) 32 20 또는 18 40 70 2.8 [1][12][13] EXPTIME 완료[14]
아와리[15] 12 12 32 60 3.5 [1] 일반화가 불명확하다
큐빅 64 30 34 20 54.2 [1] PSPACE-완전[5]
더블더미브릿지[nb 1] (52) 17 미만 40 미만 52 5.6 PSPACE-완전[16]
파노로나 45 21 46 44 11 [17] ? 단, EXPTIME에서는
나인 모리스 24 10 50 50 10 [1] ? 단, EXPTIME에서는
탭루트 81 27 [18]
해외 드래프트 (10 x 10) 50 30 54 90 4 [1] EXPTIME 완료[14]
중국산 체커 (2세트) 121 23 180 [19] EXPTIME 완료
중국산 체커(6세트) 121 78 600 [19] EXPTIME 완료
리버시(오셀로) 64 28 58 58 10 [1] PSPACE-완전[21]
OnTop (2p 베이스 게임) 72 88 62 31 23.77 [22]
액션 라인 64 23 64 44 29 [23] ? 단, EXPTIME에서는
고모쿠(15×15, 프리스타일) 225 105 70 30 210 [1] PSPACE-완전[5]
16진수(11x11) 121 57 98 50 96 [7] PSPACE-완전[5]
체스 64 44 123 70 35 [24] EXPTIME-complete(50 이동 도면 [25]규칙 없음)
비쥬얼드캔디 크러쉬(8x8) 64 50 미만 70 [26] NP 하드
GIPF 37 25 132 90 29.3 [27]
접속 6 361 172 140 30 46000 [28] PSPACE-완전[29]
백개먼 28 20 144 55 250 [30] 일반화가 불명확하다
샹치 90 40 150 95 38 [1][31][32] ?, EXPTIME-complete라고 생각됩니다.
전복 61 25 154 87 60 [33][34] PSPACE 하드EXPTIME
하반나 271 127 157 66 240 [7][35] PSPACE-완전[36]
트위스트 572 140 159 60 452 [37]
장기 90 44 160 100 40 [32] ?, EXPTIME-complete라고 생각됩니다.
쿼리도르 81 42 162 91 60 [38] ? 단, PSPACE에서는
카르카손 (2p 베이스 게임) 72 40을 넘다 195 71 55 [39] 일반화가 불명확하다
Amazons (10 x 10) 100 40 212 84 374 또는[40] 299 [41][42] PSPACE-완전[43]
장기 81 71 226 115 92 [31][44] EXPTIME 완료[45]
스턴과 택시(2명) 33 66 240 56 879 [46]
시작(19x19) 361 170 360 150 250 [1][47][48] EXPTIME 완료[49]
아리마아 64 43 402 92 17281 [50][51][52] ? 단, EXPTIME에서는
스트래티고 92 115 535 381 21.739 [53]
무한 체스[nb 2] 인피니트 인피니트 인피니트 인피니트 인피니트 [56] 알 수 없지만 mate-in-n은 결정[57] 가능
매직: 개더링 [58] AH하드[59]

메모들

  1. ^ 더블 더미 브리지( 계약 브리지의 맥락에서 더블 더미 문제)는 적절한 보드 게임은 아니지만 유사한 게임 트리를 가지며 컴퓨터 브리지에서 연구된다.브릿지 테이블은 플레이어별로 1개의 슬롯과 카드 플레이 트릭이 있으며, 보드 사이즈 52에 대응한다.게임 트리의 복잡성은 매우 약한 상한입니다.합법성에 관계없이 4명의 플레이어의 파워에 13!입니다.상태-공간의 복잡성은 하나의 거래를 위한 것이며, 합법성에 관계없이 많은 전환이 제거되었습니다.마지막 4개의 플라이는 항상 분기 계수1과 함께 강제 이동됩니다.
  2. ^ 무한체스무한평면체스트라피스트-1[54][55]로 들 수 있는 게임의 한 종류이다.

레퍼런스

  1. ^ a b c d e f g h i j k l Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0.
  2. ^ "combinatorics - TicTacToe State Space Choose Calculation". Mathematics Stack Exchange. Retrieved 2020-04-08.
  3. ^ T, Brian (2018-10-20), Btsan/generate_tictactoe, retrieved 2020-04-08
  4. ^ Stefan Reisch (1980). "Gobang ist PSPACE-vollständig (Gobang is PSPACE-complete)". Acta Informatica. 13 (1): 59–66. doi:10.1007/bf00288536. S2CID 21455572.
  5. ^ a b c d Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Inform. (15): 167–191.
  6. ^ Slany, Wolfgang (26 October 2000). The Complexity of Graph Ramsey Games. Springer-Verlag. pp. 186–203. ISBN 9783540430803. Retrieved 12 April 2018 – via dl.acm.org.
  7. ^ a b c d e f H. J. van den Herik; J. W. H. M. Uiterwijk; J. van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence. 134 (1–2): 277–311. doi:10.1016/S0004-3702(01)00152-7.
  8. ^ 힐러리 KOrman: Pentominoes: 기회없는 게임에서의 첫 번째 플레이어 승리, MSRI 출판물 - 제29권, 1996년, 339-344쪽.온라인: PDF.
  9. ^ 규칙은 van den Herik et al.을 참조하십시오.
  10. ^ John Tromp (2010). "John's Connect Four Playground".
  11. ^ Michael Lachmann; Cristopher Moore; Ivan Rapaport (July 2000), Who wins domineering on rectangular boards?, vol. MSRI Combinatorial Game Theory Research Workshop
  12. ^ Jonathan Schaeffer; et al. (July 6, 2007). "Checkers is Solved". Science. 317 (5844): 1518–1522. Bibcode:2007Sci...317.1518S. doi:10.1126/science.1144079. PMID 17641166. S2CID 10274228.
  13. ^ 셰퍼, 조나단(2007년)."게임 오버: 체커에서 게임을 하고 그림을 그릴 수 있는 검정색"ICGA 저널. 30(4): 187~197.CiteSeerX 10.1.154.255.doi:10.323/ICG-2007-30402.
  14. ^ a b J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing. 13 (2): 252–267. doi:10.1137/0213018.
  15. ^ 규칙에 대해서는 Allis 1994를 참조해 주세요.
  16. ^ Bonnet, Édouard; Jamain, Florian; Saffidine, Abdallah (2013-08-03). On the complexity of trick-taking card games. AAAI Press. pp. 482–488. ISBN 9781577356332.
  17. ^ M.P.D. Schadd; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; M.H.J. Bergsma (2008). "Best Play in Fanorona leads to Draw" (PDF). New Mathematics and Natural Computation. 4 (3): 369–387. doi:10.1142/S1793005708001124.
  18. ^ Andrea Galassi (2018). "An Upper Bound on the Complexity of Tablut".
  19. ^ a b G.I. Bell (2009). "The Shortest Game of Chinese Checkers and Related Problems". Integers. 9. arXiv:0803.1245. Bibcode:2008arXiv0803.1245B. doi:10.1515/INTEG.2009.003. S2CID 17141575.
  20. ^ a b Takumi Kasai; Akeo Adachi; Shigeki Iwata (1979). "Classes of Pebble Games and Complete Problems". SIAM Journal on Computing. 8 (4): 574–586. doi:10.1137/0208046. 임의의 그래프에 대한 일반화의 완전성을 증명합니다.
  21. ^ S. Iwata; T. Kasai (1994). "The Othello game on an n*n board is PSPACE-complete". Theor. Comput. Sci. 123 (2): 329–340. doi:10.1016/0304-3975(94)90131-7.
  22. ^ Robert Briesemeister (2009). Analysis and Implementation of the Game OnTop (PDF) (Thesis). Maastricht University, Dept of Knowledge Engineering.
  23. ^ Mark H.M. Winands (2004). Informed Search in Complex Games (PDF) (Ph.D. thesis). Maastricht University, Maastricht, The Netherlands. ISBN 90-5278-429-9.
  24. ^ 체스를 위한 공간과 게임 나무의 크기 처음으로 클로드 섀넌(1950년)로 추산되었다."재생 체스를 위한 컴퓨터 프로그래밍"(PDF).철학 잡지이다. 41(314).2010-07-06에 있는 원본(PDF)에서 Archived.섀넌 1043년과 10120의 예상치는 각각 섀넌 번호에 자세히 나와 있윗목은 테이블에 묶여보다도 작은 주었다.
  25. ^ Aviezri Fraenkel; D. Lichtenstein (1981), "Computing a perfect strategy for n×n chess requires time exponential in n", J. Combin. Theory Ser. A, 31 (2): 199–214, doi:10.1016/0097-3165(81)90016-9
  26. ^ L. Gualà; S. Leucci; E. Natale (2014). "Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard". arXiv:1403.5830 [cs.CC].
  27. ^ Diederik Wentink (2001). Analysis and Implementation of the game Gipf (PDF) (Thesis). Maastricht University.
  28. ^ Chang-Ming Xu; Ma, Z.M.; Jun-Jie Tao; Xin-He Xu (2009). "Enhancements of proof number search in connect6". 2009 Chinese Control and Decision Conference. p. 4525. doi:10.1109/CCDC.2009.5191963. ISBN 978-1-4244-2722-2. S2CID 20960281.
  29. ^ Hsieh, Ming Yu; Tsai, Shi-Chun (1 October 2007). "On the fairness and complexity of generalized k -in-a-row games". Theoretical Computer Science. 385 (1–3): 88–100. doi:10.1016/j.tcs.2007.05.031. Retrieved 12 April 2018 – via dl.acm.org.
  30. ^ Tesauro, Gerald (1 May 1992). "Practical issues in temporal difference learning". Machine Learning. 8 (3–4): 257–277. doi:10.1007/BF00992697.
  31. ^ a b Shi-Jim Yen, Jr-Chang Chen; Tai-Ning Yang; Shun-Chin Hsu (March 2004). "Computer Chinese Chess" (PDF). International Computer Games Association Journal. 27 (1): 3–18. doi:10.3233/ICG-2004-27102. Archived from the original (PDF) on 2007-06-14.
  32. ^ a b Donghwi Park (2015). "Space-state complexity of Korean chess and Chinese chess". arXiv:1507.06401 [math.GM].
  33. ^ Chorus, Pascal. "Implementing a Computer Player for Abalone Using Alpha-Beta and Monte-Carlo Search" (PDF). Dept of Knowledge Engineering, Maastricht University. Retrieved 29 March 2012.
  34. ^ Kopczynski, Jacob S (2014). Pushy Computing: Complexity Theory and the Game Abalone (Thesis). Reed College.
  35. ^ Joosten, B. "Creating a Havannah Playing Agent" (PDF). Retrieved 29 March 2012.
  36. ^ E. Bonnet; F. Jamain; A. Saffidine (2014-03-25). "Havannah and TwixT are PSPACE-complete". arXiv:1403.6518 [cs.CC].
  37. ^ Kevin Moesker (2009). TWIXT: THEORY, ANALYSIS AND IMPLEMENTATION (PDF) (Thesis). Maastricht University, Faculty of Humanities and Sciences of Maastricht University.
  38. ^ Lisa Glendenning (May 2005). Mastering Quoridor (PDF). Computer Science (B.Sc. thesis). University of New Mexico. Archived from the original (PDF) on 2012-03-15.
  39. ^ Cathleen Heyden (2009). Implementing a Computer Player for Carcassonne (PDF) (Thesis). Maastricht University, Dept of Knowledge Engineering.
  40. ^ 하위 분기 계수는 두 번째 플레이어용입니다.
  41. ^ Julien Kloetzer; Hiroyuki Iida; Bruno Bouzy (2007), The Monte-Carlo Approach in Amazons, CiteSeerX 10.1.1.79.7640
  42. ^ P. P. L. M. Hensgens (2001). "A Knowledge-Based Approach of the Game of Amazons" (PDF). Universiteit Maastricht, Institute for Knowledge and Agent Technology.
  43. ^ R. A. Hearn (2005-02-02). "Amazons is PSPACE-complete". arXiv:cs.CC/0502013.
  44. ^ Hiroyuki Iida; Makoto Sakuta; Jeff Rollason (January 2002). "Computer shogi". Artificial Intelligence. 134 (1–2): 121–144. doi:10.1016/S0004-3702(01)00157-6.
  45. ^ H. Adachi; H. Kamekawa; S. Iwata (1987). "Shogi on n × n board is complete in exponential time". Trans. IEICE. J70-D: 1843–1852.
  46. ^ F.C. Schadd (2009). Monte-Carlo Search Techniques in the Modern Board Game Thurn and Taxis (PDF) (Thesis). Maastricht University. Archived from the original (PDF) on 2021-01-14.
  47. ^ John Tromp; Gunnar Farnebäck (2007). "Combinatorics of Go". 이 문서에서는 가능한 게임 수 N에 대해 범위 48 <log(log(N)> < 171을 도출합니다.
  48. ^ John Tromp (2016). "Number of legal Go positions".
  49. ^ J. M. Robson (1983). "The complexity of Go". Information Processing; Proceedings of IFIP Congress. pp. 413–417.
  50. ^ Christ-Jan Cox (2006). "Analysis and Implementation of the Game Arimaa" (PDF).
  51. ^ David Jian Wu (2011). "Move Ranking and Evaluation in the Game of Arimaa" (PDF).
  52. ^ Brian Haskin (2006). "A Look at the Arimaa Branching Factor".
  53. ^ A.F.C. Arts (2010). Competitive Play in Stratego (PDF) (Thesis). Maastricht.
  54. ^ 체스 온 어 인피니트 플레인 게임 규칙
  55. ^ 트래피스트-1 게임 규칙
  56. ^ CDA Evans and Joel David Hamkins (2014). "Transfinite game values in infinite chess". arXiv:1302.4377 [math.LO].
  57. ^ Stefan Reisch, Joel David Hamkins, and Phillipp Schlicht (2012). "The mate-in-n problem of infinite chess is decidable" (PDF). Conference on Computability in Europe: 78–88. arXiv:1201.5597.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  58. ^ Alex Churchill, Stella Biderman, and Austin Herrick (2020). "Magic: the Gathering is Turing Complete" (PDF). Fun with Algorithms. arXiv:1904.09828.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  59. ^ Stella Biderman (2020). "Magic: the Gathering is as Hard as Arithmetic". arXiv:2003.05119 [cs.AI].

「 」를 참조해 주세요.

외부 링크