풀린 게임

3. 풀린 게임 목록

수학적, 전산학적 방법으로 해결된 다양한 게임들이 존재한다.

• 헥스: 존 내시가 고안한 따라하기 전략을 통해 정사각형 판에서 첫 번째 플레이어가 패배하지 않음을 증명했다. 무승부가 불가능하므로 첫 번째 플레이어가 승리한다. 정사각형이 아닌 판에서는 짧은 변을 연결해야 하는 플레이어가 승리한다.
• 오목: 아무런 제약 조건이 없고 렌주룰만 적용되는 경우 흑이 승리한다. 현재 15x15 크기의 판에서 흑이 승리한다는 것이 알려져 있다.
• 영국식 체커(체커): 2007년 4월 29일, 조나단 섀퍼 팀이 약하게 해결하였다. 표준 시작 위치에서 양쪽 모두 완벽하게 플레이하면 무승부가 보장된다.^[24] 체커는 5×10²⁰개의 가능한 게임 위치를 가지며,^[25] 계산 횟수는 10¹⁴에 달했다. 18년 동안 최대 200대의 데스크톱 컴퓨터가 사용되었고, 이후 약 50대로 줄었다.^[26]
• 파노로나: 마르텐 스카드에 의해 약하게 해결되었다. 게임은 무승부이다.^[27]
• 지는 체스: 2016년에 1. e3로 시작하는 백의 승리로 약하게 해결되었다.^[28]
• 오델로(리버시): 2023년 프리퍼드 네트웍스의 연구원 히로키 타키자와에 의해 약하게 해결되었다.^[29] 8×8 보드에서 표준 시작 위치에서 양쪽 모두 완벽하게 플레이하면 무승부가 된다. 오델로는 현재까지 해결된 게임 중 가장 큰 게임으로, 10²⁸개의 가능한 게임 위치를 갖는다.
• 펜토미노: H. K. 오르만에 의해 약하게 해결되었다.^[30] 첫 번째 플레이어가 승리한다.
• 큐빅: 오렌 파타시닉(1980)과 빅터 앨리스에 의해 약하게 해결되었다. 첫 번째 플레이어가 승리한다.
• 심: 약하게 해결됨: 두 번째 플레이어가 승리한다.
• 양과 호랑이: 예우 진 림(2007)에 의해 약하게 해결되었다. 게임은 무승부이다.^[31]
• 체스: 완전한 해결은 여전히 불가능하며, 게임의 복잡성 때문에 영원히 해결되지 못할 것이라는 추측도 있다. 역행 컴퓨터 분석을 통해 두 개의 킹을 포함하여 3~7개 기물의 모든 엔드게임에 대한 엔드게임 테이블베이스(강력한 솔루션)가 발견되었다. 일부 기물의 수를 줄인 작은 보드에서의 체스 변형이 해결되었다.
• 바둑: 2002년에는 5×5 보드가 모든 오프닝 수에 대해 약하게 해결되었다.^[32] 2015년에는 7×7 보드가 약하게 해결되었다.^[33] 인간은 일반적으로 19×19 보드에서 바둑을 두는데, 이는 7×7보다 145개 이상의 차수만큼 더 복잡하다.^[34]
• 헥스: 전략 훔치기 논증(존 내시가 사용)은 모든 정사각형 보드 크기가 첫 번째 플레이어에 의해 패배할 수 없음을 보여준다. 무승부의 불가능성에 대한 증명과 결합하여, 이것은 게임이 첫 번째 플레이어의 승리임을 보여준다(따라서 매우 약하게 해결되었다). 특정 보드 크기에 대해서는 더 많은 정보가 알려져 있다. 최대 6×6 보드 크기에 대해 여러 컴퓨터에 의해 강력하게 해결되었다. 약한 솔루션은 7×7(스왑 전략 사용), 8×8, 9×9 보드 크기에 대해 알려져 있다. 8×8의 경우, 모든 오프닝 수에 대한 약한 솔루션이 알려져 있다.^[35] ''N''×''N'' 보드에서 헥스를 강력하게 해결하는 것은 문제가 PSPACE-완전임이 밝혀졌기 때문에 어려울 것으로 보인다. 헥스가 ''N''×(''N'' + 1) 보드에서 진행되는 경우, 연결하는 거리가 짧은 플레이어는 두 번째로 플레이하는 불리함에도 불구하고 간단한 페어링 전략을 통해 항상 이길 수 있다.
• 국제식 드래프트: 2~7개 기물이 있는 모든 엔드게임 포지션, 각 측이 킹을 하나 이하로 가진 4×4 및 5×3 기물 포지션, 5 대 4 기물 포지션, 5 대 3 기물과 킹 하나 포지션, 4 기물과 킹 하나 대 4 기물 포지션이 해결되었다. 엔드게임 포지션은 2007년 미국의 에드 길버트에 의해 해결되었다. 컴퓨터 분석 결과 두 플레이어 모두 완벽하게 플레이하면 무승부로 끝날 가능성이 매우 높다는 것이 밝혀졌다.^[36]
• ''m'',''n'',''k''-게임: 두 번째 플레이어가 결코 이길 수 없다는 것을 증명하는 것은 사소하다. 전략 훔치기 논증을 참조하라. 거의 모든 경우에 대해 ''k'' ≤ 4인 경우 약하게 해결되었다. 일부 결과는 ''k'' = 5에 대해 알려져 있다. 게임은 ''k'' ≥ 8인 경우 무승부이다.

3. 1. 완전히 풀린 게임

• 아와리 (만칼라 계열의 게임): 네덜란드 암스테르담의 자유 대학교에서 앙리 발과 존 로메인이 2002년에 강력하게 풀었다. 어느 플레이어든 게임을 무승부로 이끌 수 있다.
• 젓가락: 강력하게 풀렸다. 두 플레이어 모두 완벽하게 플레이하면 게임은 무기한으로 진행된다.
• 커넥트 포: 1988년 10월 1일 제임스 D. 앨런에 의해, 그리고 1988년 10월 16일 빅터 앨리스에 의해 독립적으로 풀렸다.^[3] 선공이 승리할 수 있다. 존 트롬프의 8-ply 데이터베이스에 의해 강력하게 풀렸다^[4] (1995년 2월 4일). 너비+높이가 최대 15인 모든 보드 크기에 대해 약하게 풀렸고 (2015년 말에는 8×8도 풀렸다)^[3] (2006년 2월 18일). 2024년 5월 22일에 너비+높이가 16인 모든 보드 크기에 대해 풀렸다.^[5]

• 프리 고모쿠: 빅터 앨리스에 의해 풀렸다(1993). 선공은 오프닝 규칙 없이 승리할 수 있다.^[1]
• 고스트: 앨런 프랑크가 1987년에 ''공식 스크래블 플레이어 사전''을 사용하여 풀었다.^[6]
• 헥사폰: 3×3 변형은 흑의 승리로 풀렸고, 다른 여러 더 큰 변형도 풀렸다.^[7]
• 칼라: 제프리 어빙, 제룬 돈커스, 조스 위테르윅에 의해 대부분의 변형이 풀렸다(2000), 단 칼라(6/6) 제외. (6/6) 변형은 안데르스 카르스텐센에 의해 풀렸다(2011). 대부분의 경우 강력한 선공 이점이 증명되었다.^[8][9]
• L 게임: 쉽게 풀린다. 어느 플레이어든 게임을 무승부로 이끌 수 있다.
• 마하라자와 세포이: 이 비대칭 게임은 올바른 플레이를 하면 세포이 플레이어가 이긴다.
• 님: 강력하게 풀렸다.^[10]
• 나인 멘 모리스: 랄프 가서에 의해 풀렸다(1993). 어느 플레이어든 게임을 무승부로 이끌 수 있다.^[11][12]
• 오더 앤 카오스: 오더(선공)가 이긴다.^[13]
• 오발루: 인간에 의해 약하게 풀렸지만, 컴퓨터에 의해 증명되었다.
• 팡키: 제이슨 도세트에 의해 강력하게 풀렸다(2001).^[14] 게임은 무승부이다. 거울 대칭 위치를 버리면 고유한 첫 번째 수가 두 개뿐이다. 하나는 무승부를 강제하고, 다른 하나는 상대방에게 15수 만에 승리를 강제한다.
• 펜타고: NERSC의 슈퍼컴퓨터를 사용하여 제프리 어빙에 의해 강력하게 풀렸다. 선공이 이긴다.
• 콰르토: 루크 고센스에 의해 풀렸다(1998). 두 완벽한 플레이어는 항상 무승부가 된다.^{[15] [16][17]}
• 렌주와 유사한 게임 (오프닝 규칙 없음): 야노스 바그너와 이스트반 비라그에 의해 풀렸다고 주장되었다(2001).^[18] 선공 승리.
• 티코: 가이 스틸에 의해 풀렸다(1998). 변형에 따라 선공 승리 또는 무승부이다.^[19]
• 세 명의 모리스: 사소하게 풀린다. 어느 플레이어든 게임을 무승부로 이끌 수 있다.
• 세 무사: 2009년에 요하네스 라이레에 의해 강력하게 풀렸고, 2017년에 알리 엘라브리디에 의해 약하게 풀렸다.^[20] 파란색 말(추기경 리슐리외의 사람들, 즉 적)의 승리이다.^[21]
• 틱택토: 작은 게임 트리 때문에 사소하게 강력하게 풀린다.^[22] 실수가 없으면 게임은 무승부이며, 첫 수에는 실수가 있을 수 없다.
• 와이소프의 게임: W. A. 와이소프에 의해 강력하게 풀렸다(1907).^[23]

3. 2. 부분적으로 풀린 게임

• 체스: 역분석을 통해 킹을 포함하여 기물이 6개 이하인 경우 해결되었다.^[32]
• m,n,k-게임
• 체커: 미국식 룰에서는 무승부로 알려져 있다.

4. 한국의 풀린 게임

이전 출력에서는 원본 소스가 제공되지 않아 '한국의 풀린 게임' 섹션에 대한 내용을 작성할 수 없었습니다. 따라서, 주어진 지시사항에 따라 이전 출력을 수정할 내용이 없습니다. 빈 문자열을 출력합니다.

참조

_[1] 논문 Searching for Solutions in Games and Artificial Intelligence Rijksuniversiteit Limburg 1994-09-23
_[2] 논문 Games solved: Now and in the future https://web.archive.[...] 2002
_[3] 웹사이트 John's Connect Four Playground https://tromp.github[...]
_[4] 웹사이트 UCI Machine Learning Repository: Connect-4 Data Set https://archive.ics.[...]
_[5] 웹사이트 ChristopheSteininger/c4 https://github.com/C[...]
_[6] 간행물 Ghostbusters https://digitalcommo[...] 1987-08-01
_[7] 웹사이트 Hexapawn http://www.chessvari[...]
_[8] 문서 Solving Kalah http://graphics.stan[...]
_[9] 문서 Solving (6,6)-Kalaha http://kalaha.krus.d[...]
_[10] 간행물 Nim, ''a game with a complete mathematical theory'' https://archive.org/[...]
_[11] 서적 Games of No Chance http://library.msri.[...] Cambridge University Press 2022-01-03
_[12] 문서 Nine Men's Morris is a Draw http://www.ics.uci.e[...]
_[13] 웹사이트 solved: Order wins - Order and Chaos https://boardgamegee[...]
_[14] 문서 Pangki Pangki is strongly solved as a draw http://www.jasondouc[...]
_[15] 웹사이트 Quarto https://wouterkoolen[...] 2024-02-29
_[16] 웹사이트 414298141056 Quarto Draws Suffice! https://www.mathpage[...]
_[17] 웹사이트 Quarto http://ssel.vub.ac.b[...]
_[18] 웹사이트 Solving Renju http://www.sze.hu/~g[...] 2024-04-24
_[19] 문서 Teeko http://mathworld.wol[...]
_[20] 웹사이트 Weakly Solving the Three Musketeers Game Using Artificial Intelligence and Game Theory http://www.aui.ma/ss[...]
_[21] 문서 Three Musketeers https://github.com/j[...]
_[22] 문서 Tic-Tac-Toe https://xkcd.com/832[...]
_[23] 간행물 A modification of the game of nim https://archive.org/[...]
_[24] 간행물 Checkers Is Solved 2007-07-19
_[25] 웹사이트 Project - Chinook - World Man-Machine Checkers Champion http://www.cs.ualber[...] 2007-07-19
_[26] 웹사이트 Checkers 'solved' after years of number crunching https://www.newscien[...] NewScientist.com news service 2020-12-06
_[27] 간행물 Best Play in Fanorona leads to Draw http://schadd.com/Pa[...] 2015-04-08
_[28] 웹사이트 Losing Chess: 1. e3 wins for White http://magma.maths.u[...] 2017-01-17
_[29] arXiv Othello is Solved 2023-10-30
_[30] 문서 Pentominoes: A First Player Win http://www.msri.org/[...]
_[31] 논문 On Forward Pruning in Game-Tree Search http://www.yewjin.co[...] National University of Singapore 2007
_[32] 문서 5×5 Go is solved http://erikvanderwer[...]
_[33] 웹사이트 首期喆理围棋沙龙举行 李喆7路盘最优解具有里程碑意义_下棋想赢怕输_新浪博客 http://blog.sina.com[...]
_[34] 문서 Counting legal positions in Go http://homepages.cwi[...] 2007-08-24
_[35] 문서 Solving 8×8 Hex webdocs.cs.ualberta.[...] 2009
_[36] 웹사이트 Some of the nine-piece endgame tablebase http://edgilbert.org[...] Ed Gilbert
_[37] 논문 Searching for Solutions in Games and Artificial Intelligence http://fragrieu.free[...] Department of Computer Science, University of Limburg 1994
_[38] 논문 Games solved: Now and in the future 2002