해결된 게임

Solved game

해결된 게임은 두 선수가 완벽하게 플레이한다고 가정할 때 어떤 위치에서든 승패 또는 무승부를 정확하게 예측할 수 있는 게임이다.이 개념은 보통 추상 전략 게임, 특히 기회가 없는 완전한 정보를 가진 게임에 적용됩니다. 이러한 게임을 해결하는 것은 조합 게임 이론 및/또는 컴퓨터 지원을 사용할 수 있습니다.

개요

2인용 게임은 몇 [1][2]가지 레벨로 해결할 수 있습니다.

초미약
양쪽에 완벽한 플레이가 주어졌을 때 첫 번째 선수가 처음 위치에서 이길지, 질지, 무승부를 기록할지를 증명한다.이것은 실제로 완벽한 플레이의 움직임을 결정할 필요가 없는 비건설적인 증거(전략적 주장을 수반할 수 있음)가 될 수 있습니다.
약한
게임 시작 시부터 한 명의 플레이어의 승리를 보장하거나, 상대의 가능한 움직임에 대해 무승부를 보장하는 알고리즘을 제공합니다.
강한.
한쪽 또는 양쪽에서 이미 오류가 발생한 경우에도 어떤 위치에서든 완벽한 동작을 생성할 수 있는 알고리즘을 제공합니다.

그들의 이름에도 불구하고, 많은 게임 이론가들은 "초약" 증거가 가장 깊고, 가장 흥미롭고, 가치 있다고 믿는다."초약" 증명은 게임의 추상적인 특성에 대해 학자가 추론하고, 완벽한 플레이가 [citation needed]실현되면 이러한 특성이 어떻게 특정한 결과로 이어지는지를 보여줄 것을 요구한다.

반면, "강력한" 증명은 종종 컴퓨터를 사용하여 게임 트리를 철저히 검색하여 완벽한 플레이가 실현되면 어떻게 되는지 알아내는 등 무차별적인 힘으로 진행됩니다.그 결과, 보드상의 모든 위치에 최적인 전략을 얻을 수 있습니다.하지만, 이러한 증명들은 왜 어떤 게임들은 무승부만큼 해결이 가능하고, 다른 비슷한 게임들은 승리만큼 해결이 되는지 더 깊은 이유를 이해하는 데 도움이 되지 않는다.

한정된 수의 포지션을 가진 어떤 2인용 게임의 규칙도 주어진다면, 게임 트리를 완전히 가로지르는 미니맥스 알고리즘을 언제든지 구축할 수 있다.그러나 많은 비사소한 게임에서 그러한 알고리즘은 주어진 위치에서 움직임을 생성하기 위해 실현 불가능한 시간을 필요로 하기 때문에, 알고리즘이 합리적인 시간 내에 기존 하드웨어에 의해 실행될 수 없는 한 게임은 약하게 또는 강하게 해결되는 것으로 간주되지 않는다.많은 알고리즘이 미리 생성된 거대한 데이터베이스에 의존하며 사실상 그 이상도 이하도 아닙니다.

강력한 해결책의 예로서, 틱택토 게임은 완벽한 플레이로 두 플레이어 모두 무승부로 해결할 수 있습니다(그 결과 초등학생이 수동으로 결정할 수도 있습니다.님과 같은 게임도 조합 게임 이론을 이용한 엄격한 분석을 인정합니다.

게임이 풀리는지 아닌지는 인간들에게 재미있는 게임으로 남아 있는지와 반드시 같은 것은 아니다.아무리 잘 풀린 게임이라도 해법이 너무 복잡해서 외울 수 없다면 흥미로울 수 있습니다. 반대로, 약하게 풀린 게임은 승리 전략이 기억하기에 충분히 간단하다면 매력(예: Maharahajah와 Sepoys)을 잃을 수 있습니다.초미약 솔루션(예를 들어 충분히 큰 보드의 Chomp나 Hex 등)은 일반적으로 플레이 능력에 영향을 주지 않습니다.

퍼펙트 플레이

게임 이론에서, 퍼펙트 플레이는 상대의 반응과 상관없이 그 플레이어를 위해 가능한 최선의 결과로 이끄는 플레이어의 행동이나 전략이다.게임의 완벽한 플레이는 게임이 [1]해결되면 알 수 있다.게임의 규칙에 따라 모든 가능한 최종 위치를 평가할 수 있습니다(승부, 패부, 무승부).역추론에 의해 비최종위치를 한 발짝 떨어진 위치와 동일하고 그 움직임이 있는 선수에게 가장 가치 있는 것으로 재귀적으로 평가할 수 있다.따라서 포지션 간 전환은 움직이는 선수에게 더 나은 평가를 가져올 수 없으며 포지션에서의 완벽한 이동은 동등하게 평가되는 포지션 간 전환이 될 것입니다.예를 들어, 무승부 포지션의 완벽한 선수는 항상 무승부를 얻거나 승리할 수 있으며 결코 패하지 않을 것이다.같은 결과를 가진 옵션이 여러 개 있는 경우, 완벽한 플레이는 좋은 결과로 이어지는 가장 빠른 방법 또는 나쁜 결과로 이어지는 가장 느린 방법으로 간주됩니다.

퍼펙트 플레이는 비퍼펙트 정보 게임으로 일반화될 수 있는데, 이는 상대의 전략에 관계없이 최소한의 기대 결과를 보장하는 전략이다.예를 들어, 가위바위보의 완벽한 전략은 각 옵션을 (1/3) 확률로 랜덤하게 선택하는 것입니다.이 예에서 단점은 이 전략이 상대의 비최적 전략을 이용하지 않는다는 것입니다.따라서 이 전략의 예상 결과는 항상 최소 예상 결과와 동일합니다.

게임의 최적 전략은 아직 알려지지 않았지만, 게임 플레이 컴퓨터는 여전히 특정 엔드게임 포지션(엔드게임 테이블베이스의 형태)에서 게임의 솔루션으로부터 이익을 얻을 수 있습니다.이것에 의해, 게임의 어느 시점 후에 완벽하게 플레이 할 수 있게 됩니다.컴퓨터 체스 프로그램은 이것을 하는 것으로 잘 알려져 있다.

해결된 게임

아와리
게임 엔딩 "그랜드 슬램"을 허용하는 오웨어의 변종은 네덜란드 암스테르담의 Vrije Universityit에서 Henri Bal과 John Romein에 의해 강하게 해결되었습니다(2002).어느 한 명의 선수가 경기를 강제로 무승부로 만들 수 있다.
젓가락들
완벽한 플레이어는 언제나 승리를 강요할 수 있다.만약 두 명의 선수가 완벽하게 경기를 한다면,[citation needed] 게임은 무기한으로 진행될 것입니다.
4개의 연결
Connect Four 게임이 해결되었습니다.
먼저 제임스 D에 의해 해결되었습니다.1988년 10월 1일 앨런, 그리고 [3]1988년 10월 16일 빅터 앨리스에 의해 독립적으로.첫 번째 선수가 강제로 이길 수 있습니다.John Tromp의 8개 데이터베이스[4](1995년 2월 4일)에 의해 강력하게 해결되었습니다.폭+높이가 최대 15(2015년 [3]후반에는 8×8)인 모든 보드 크기에 대해 약하게 해결되었습니다(2006년 2월 18일).
영어 드래프트(체커)
이 8×8 변형 드래프트는 2007년 4월 29일 Jonathan Schaeffer 팀에 의해 약하게 해결되었습니다.표준 출발 위치에서 두 선수 모두 완벽한 [5]플레이로 무승부를 보장할 수 있다.Checkers는 검색공간이20 [6]5×10으로 지금까지 해결된 게임 중 가장 큰 게임입니다.관련된 계산의 수는 10개였으며14, 18년 동안 수행되었다.이 프로세스에는 피크시 200대의 데스크톱 컴퓨터에서 50대 [7]안팎으로 감소하는 작업이 수반되었습니다.
파노로나
마튼 샤드가 약하게 해결했다.경기는 [citation needed]무승부입니다.
프리고모쿠
Victor Alis(1993)가 해결했다.첫 번째 선수는 규칙을 열지 않고 승리를 강요할 수 있다.
고스트
앨런 프랭크가 [citation needed]1987년에 공식 스크래블 플레이어 사전을 사용하여 해결했습니다.
16진수
  • Strategy-stealing 인수(John Nash가 사용)는 모든 정사각형 보드 크기를 첫 번째 플레이어가 잃을 수 없음을 보여줍니다.무승부가 불가능하다는 증거와 결합하면 첫 번째 선수의 승리로 경기가 초약체임을 알 수 있다.
  • 최대 6×6의 보드 크기로 여러 대의 컴퓨터에서 강력하게 해결됩니다.
  • Jing Yang은 보드 크기 7×7, 8×8 및 9×9에 대한 성공 전략(약점 솔루션)을 입증했습니다.
  • 7x7 보드의 경우 스와핑을 통한 Hex의 성공 전략이 알려져 있습니다.
  • 문제가 PSPACE-완전한 것으로 나타났기 때문에 N×N 보드에서 Hex를 강하게 푸는 것은 어려울 것 같습니다.
  • N×(N+1) 보드에서 헥스를 플레이하면 2위라는 단점에도 불구하고 연결 거리가 짧은 플레이어가 항상 간단한 페어링 전략으로 이길 수 있습니다.
  • 8×8 [8]보드의 모든 오프닝 동작에 대해 약한 솔루션이 알려져 있습니다.
헥사폰
3×3 변종은 검정색에 대한 승리로서 해결되었으며, 다른 몇 가지 더 큰 변종도 [9]해결되었습니다.
칼라
Geoffrey Irving, Jeroen Donkers 및 Jos Uiterwijk(2000)가 Kalah(6/6)를 제외하고 대부분의 변형을 해결했다.(6/6) 변종은 Anders Carstensen(2011)에 의해 해결되었다.대부분의 [10][11]경우 강력한 1인자 우위가 입증되었다.MD Gaithersburg의 Mark Rawlings는 (6/6) 변종(2015)에서 첫 번째 선수의 우승 규모를 측정했습니다.39GB의 엔드게임 데이터베이스를 만들고 총 106일의 CPU 시간과 55조 이상의 노드를 검색한 결과, 완벽한 플레이로 첫 번째 플레이어가 2대 2로 승리하는 것이 입증되었습니다.이 모든 결과는 Empty-pit Capture 변종과 관련이 있으므로 표준 게임에서는 매우 제한적인 관심사입니다.현재 표준규칙 경기 분석은 1위 8승의 칼라(6,4)와 1위 10승의 칼라(6,5)가 올라왔다.기준 룰로 칼라(6,6)에 대한 분석이 진행 중이지만 1위 선수에게 최소 4승 이상의 승리라는 것이 입증됐다.
L게임
간단하게 해결할 수 있습니다.어느 한 명의 선수가 경기를 강제로 무승부로 만들 수 있다.
체스의 패배
1. [12]e3부터 시작하는 화이트의 승리로서 약하게 해결.
마하라자와 세포이
이 비대칭 게임은 올바른 플레이를 가진 세포이의 승리이다.
님
강렬하게 해결되었다.
나인 모리스
Ralph Gasser(1993)가 해결했다.어느 한 명의 선수가 경기를 강제로 [13][14]무승부로 만들 수 있다.
질서와 혼돈
순서(첫 번째 선수)가 [15]이깁니다.
오발후
인간에 의해 약하게 해결되지만 컴퓨터에 의해 증명된다.(다콘은 실제로 드보그트가 관찰한 오발후와 동일하지 않다.)
팡키
Jason Doucette(2001)[16]에 의해 강력하게 해결되었다.경기는 무승부입니다.미러링된 위치를 폐기하는 경우 첫 번째 이동은 두 가지뿐입니다.한 명은 무승부를 강요하고, 다른 한 명은 15년 만에 상대에게 승리를 강요한다.
펜타고
NERSC의 슈퍼컴퓨터를 사용하여 Geoffrey Irving에 의해 강력하게 해결되었습니다.첫 번째 선수가 이깁니다.
펜토미노
H. K. Orman에 [17]의해 약하게 해결되었습니다.첫 번째 선수의 승리입니다.
쿼토
Luc Goossens(1998)에 의해 해결되었습니다.완벽한 두 선수는 항상 무승부를 기록한다.
큐빅
오렌 파타슈닉(1980)과 빅터 앨리스가 약하게 해결했다.첫 번째 선수가 이깁니다.
오픈 룰이 없는 런주 같은 게임
야노스 바그너와 이스반 비라그(2001)가 해결했다고 주장했다.1등 선수 승리.
심
약하게 해결: 두 번째 플레이어가 승리합니다.
티코
가이 스틸(1998)에 의해 해결되었다.변형에 따라 1등 선수의 승리와 [18]무승부 중 하나입니다.
세 남자 모리스
문제 해결 가능.어느 한 명의 선수가 경기를 강제로 무승부로 만들 수 있다.
삼총사
2009년 요하네스 라이어가 강하게,[19] 2017년 알리 엘랍리디가 약하게 해결했다.그것은 파란 조각(카디날 리슐리외의 부하들, 혹은 적)의 [20]승리이다.
틱택토
작은 게임 [21]트리 때문에 매우 강력하게 해결됩니다.첫 번째 동작에서 실수가 없을 경우 무승부입니다.
호랑이와 염소
유진림(2007)이 약하게 해결했다.경기는 [22]무승부입니다.
위토프 게임
강렬하게 해결되었다.

약한 솔루션

호랑이와 염소

유진림(2007)이 약하게 해결했다.경기는 [22]무승부입니다.

펜토미노

H. K. Orman에 [17]의해 약하게 해결되었습니다.첫 번째 선수의 승리입니다.

가세요

5×5 보드는 2002년의 [23]모든 오프닝 무브에 대해 약하게 해결되었습니다.7×7 보드는 2015년에 [24]약하게 해결되었습니다.인간은 보통 7×[25]7보다 145배 더 복잡한 19×19 보드 위에서 플레이합니다.

초취약 솔루션

부분적으로 해결된 게임

체스
주요 기사:체스 풀기
체스를 완전히 푸는 것은 여전히 어려운 일이며, 게임의 복잡성으로 인해 체스가 풀리지 않을 수도 있다고 추측된다.역행 컴퓨터 분석을 통해 엔드게임 테이블베이스(강력한 솔루션)가 3개에서 7개로 구성된 엔드게임 모두에 대해 발견되었으며 두 왕을 조각으로 간주합니다.
체스의 일부 변종들이 더 작은 판에 있는 피스 수를 줄여서 해결되었다.다른 인기 있는 변형들도 해결되었다. 예를 들어, 마하라자와 세포이에 대한 약한 해결책은 "세포이" 플레이어에게 승리를 보장하는 쉽게 기억할 수 있는 일련의 움직임이다.
가세요
5×5 보드는 2002년의 [23]모든 오프닝 무브에 대해 약하게 해결되었습니다.7×7 보드는 2015년에 [24]약하게 해결되었습니다.인간은 보통 7×[25]7보다 145배 더 복잡한 19×19 보드 위에서 플레이합니다.
국제 드래프트
각각 킹이 1명 이하인 4×4와 5×3 포지션, 남자 5명 대 남자 4명, 남자 5명 대 남자 3명 대 킹 1명, 남자 4명, 남자 1명 대 킹 4명 등 모든 엔드게임 포지션을 해결했다.2007년 미국의 Ed Gilbert가 최종 순위에서 해결했다.컴퓨터 분석 결과 두 선수 [26][better source needed]모두 완벽한 경기를 펼치면 무승부로 끝날 가능성이 높은 것으로 나타났다.
m, n, k 게임
두 번째 참가자가 절대 이길 수 없다는 것을 보여주는 것은 사소한 일이다. 전략 도용 논거를 참조하라.k ÷ 4에 대해 거의 모든 사례가 약하게 해결되었다. 일부 결과는 k = 5로 알려져 있다.경기는 8점 만점에 추첨된다.
리버시(오셀로)
1993년 7월 Joel [27]Feinstein에 의한 두 번째 우승으로 4×4 및 6×6 보드에서 약하게 해결되었습니다.8×8 보드(표준 보드)에서는 수학적으로 풀리지 않지만 컴퓨터 분석 결과에는 추첨 가능성이 있습니다.10×10 이상의 보드에서 선발 선수(검은색)의 확률이 높아지는 것 외에 강하게 상정되는 추정치는 존재하지 않습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Victor Allis (1994). "PhD thesis: Searching for Solutions in Games and Artificial Intelligence" (PDF). Department of Computer Science. University of Limburg. Retrieved 2012-07-14.
  2. ^ H. Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijk, 게임 해결: 현재와 미래의 인공지능 134 (2002) 277–311.
  3. ^ a b "John's Connect Four Playground". tromp.github.io.
  4. ^ "UCI Machine Learning Repository: Connect-4 Data Set". archive.ics.uci.edu.
  5. ^ Schaeffer, Jonathan (2007-07-19). "Checkers Is Solved". Science. 317 (5844): 1518–22. doi:10.1126/science.1144079. PMID 17641166. S2CID 10274228. Retrieved 2007-07-20.
  6. ^ "Project - Chinook - World Man-Machine Checkers Champion". Retrieved 2007-07-19.
  7. ^ Mullins, Justin (2007-07-19). "Checkers 'solved' after years of number crunching". NewScientist.com news service. Retrieved 2020-12-06.
  8. ^ P. 헨더슨, B.아르네손, 그리고 R.Hayward [ webdocs.cs.ualberta.ca/ ~hayward / papers / solve 8 . pdf , Resolving 8 x 8 Hex ], Proc.IJCAI-09 505-510 (2009) 2010년 6월 29일 취득.
  9. ^ Price, Robert. "Hexapawn". www.chessvariants.com.
  10. ^ Geoffrey Irving, Jeroen Donkers, Jos Uiterwijk의 Kalah 해결.
  11. ^ 해결(6,6)-Anders Carstensen의 Kalaha.
  12. ^ Watkins, Mark. "Losing Chess: 1. e3 wins for White" (PDF). Retrieved 17 January 2017.
  13. ^ Gasser, Ralph (1996). "Solving Nine Men's Morris". In Nowakowski, Richard (ed.). Games of No Chance (PDF). Vol. 29. Cambridge: Cambridge University Press. pp. 101–113. ISBN 9780521574112.
  14. ^ 나인맨즈 모리스는 랄프 가서가 그린 그림이다.
  15. ^ "solved: Order wins - Order and Chaos".
  16. ^ Jason Doucette에 의해 추첨으로 팡키는 강하게 해결되었다.
  17. ^ a b 힐러리 KOrman: Pentominoes: 기회가 없는 게임에서의 첫 번째 플레이어 승리, MSRI 출판물 - 제29권, 1996년, 339-344쪽.온라인: PDF.
  18. ^ 티코 by E.바이스타인
  19. ^ Elabridi, Ali. "Weakly Solving the Three Musketeers Game Using Artificial Intelligence and Game Theory" (PDF).
  20. ^ J. 르메르의 삼총사
  21. ^ Tic-Tac-Toe, R.먼로
  22. ^ a b 유진림.게임 트리 검색의 Forward Pruning(전송 플루닝)에 대해 설명합니다.2007년 싱가포르 국립대학교 박사학위 논문.
  23. ^ a b 5×5 바둑은 에릭 반 데 베르프에 의해 해결된다.
  24. ^ a b "首期喆理围棋沙龙举行 李喆7路盘最优解具有里程碑意义_下棋想赢怕输_新浪博客". blog.sina.com.cn. (즉, 7x7 솔루션은 약하게만 해결되어 아직 연구 중임을 나타냅니다.1. 올바른 코미는 9(4.5석), 2. 최적의 트리가 여러 개 있습니다.첫 번째 3개의 동작은 독특하지만 첫 번째 7개의 동작에는 최적의 트리가 5개 있습니다.3).결과에 영향을 주지 않는 플레이 방법은 여러 가지가 있습니다.)
  25. ^ a b Go Archived 2007-09-30의 Wayback Machine, Tromp 및 Farnebeck에서 법적 지위를 계산하여 2007-08-24에 액세스했습니다.
  26. ^ Ed Gilbert에 의한 9개의 최종 게임 테이블 베이스 중 일부
  27. ^ "6×6 Othello weakly solved". Archived from the original on 2009-11-01.

추가 정보

  • 알리스, 세계 챔피언을 물리친다고? 최첨단 컴퓨터 게임 플레이입니다.'보드 게임 연구의 새로운 접근법'을 소개합니다.

외부 링크