체스 풀기

Solving chess

체스를 푸는 것은 체스 게임을 위한 최적의 전략을 찾는 것을 의미합니다. 즉, 한 명의 플레이어(흰색 또는 검정색)가 항상 승리를 강요하거나 무승부를 강요할 수 있는 전략을 찾는 것입니다.이것은 또한 카파블랑카 체스와 무한 체스와 같은 체스 같은 게임(완벽한 정보의 조합 게임)을 보다 일반적으로 해결하는 것을 의미합니다.체스의 정리에 따르면 체스와 체스 같은 게임을 위해 결정 가능한 최적의 전략이 존재해야 한다.

더 약한 의미에서 체스를 푸는 것은 최적의 [1]전략 자체를 드러내지 않고 세 가지 가능한 결과 중 어느 것이 두 명의 완벽한 선수의 결과인지를 증명하는 것을 의미할 수 있다.

두 가지 감각 중 어느 쪽이든 체스에 대한 완전한 해결책은 알려져 있지 않으며, 가까운 미래에 체스가 해결될 것으로 기대되지도 않는다.현재의 계산 능력의 기하급수적인 성장이 언젠가 모든 가능성을 확인하는 등 "뇌력적인 힘"으로 해결할 수 있을 만큼 충분히 오래 지속될지에 대해서는 의견이 분분합니다.

지금까지의 진전은 극히 한정되어 있습니다.소수의 피스만으로 완벽한 엔드 게임을 할 수 있는 테이블 베이스가 있습니다.또, 체스와 같은 변종도 적어도 약하게 해결되고 있습니다.체스의 게임 트리 복잡도와 상태 공간 복잡도에 대한 계산된 추정치는 게임을 해결하기 위해 필요할 수 있는 계산 작업의 조감도를 제공합니다.

부분 결과

게임 종료 테이블 베이스

abcdefgh
8
Chessboard480.svg
a7 black rook
h7 black knight
c6 white queen
f4 black king
d3 white king
h2 white knight
d1 black bishop
h1 black queen
8
77
66
55
44
33
22
11
abcdefgh
로모노소프 7피스 테이블 베이스에 있는 메이트인-546 위치.이동할 흰색입니다(이 예에서는 8번째 조각에 간단한 첫 번째 이동 캡처가 추가됩니다).

엔드게임 테이블베이스는 컴퓨터화된 데이터베이스로 미리 계산된 완전 분석 위치가 포함되어 있으며, 보드에는 소량의 부품이 남아 있습니다.테이블베이스는 7개 이하의 피스 또는 폰(두 [2]왕 포함)을 가진 모든 사소한 엔드게임을 포함하여 많은 엔드게임에서 완벽한 플레이를 결정하면서 체스를 제한적으로 해결했다.

7개의 게임으로 구성된 테이블 베이스를 개발하는 것의 한 가지 결과는 흥미로운 이론적인 체스 엔딩이 많이 발견됐다는 것이다.50무브 [3]규칙을 무시하고 546무브에 강제체크메이트를 하는 'mate-in-546' 포지션이 대표적이다.이러한 위치는 인간이 해결할 수 있는 능력을 넘어서는 것이며, 어떤 체스 엔진도 테이블 베이스에 접근하지 않고 올바르게 플레이할 수 없습니다.

체스의 변종

섀넌이 처음 기술한 변형은 체스의 게임 이론 가치에 대한 논쟁을 제공한다: 그는 "통과"의 이동을 허용하는 것을 제안한다.이 변형에서는 첫 번째 선수가 최소한 무승부를 기록한다는 전략을 통해 입증할 수 있습니다. 첫 번째 선수가 승리할 경우, 경기를 하게 하고, 그렇지 않으면 패스를 합니다.두 번째 플레이어는 보드의 미러 이미지 대칭으로 인해 동일한 상황에 직면하게 됩니다. 첫 번째 플레이어가 첫 번째 인스턴스에서 승부수가 없었으면 두 번째 플레이어는 현재 승부수가 없습니다.따라서 두 번째 선수는 기껏해야 추첨할 수 있고, 첫 번째 선수는 최소한 추첨할 수 있기 때문에 완벽한 게임은 첫 번째 선수가 이기거나 추첨을 하게 된다.[4]

체스보다 간단한 체스 변종들이 몇 가지 해결되었다.마하라자와 세포이의 흑인에 대한 승리 전략은 쉽게 기억될 수 있다.5×5 Gardner의 미니체스 변형은 [5]무승부로 약하게 해결되었습니다.체스를 8x8 보드로 플레이하지만, 체스의 강제 포획 규칙은 복잡함을 크게 제한하고, 계산 분석은 이 변종을 [6]백인의 승리로 약하게 해결하는데 성공했습니다.

대형 체스 변형이나 무한 [7]체스와 같이 보드 크기가 커짐에 따라 개별적이고 구체적인 체스 같은 게임을 해결하는 것은 더욱 어려워집니다.

체스의 복잡성

1950년 정보 이론가인 Claude Shannon은 완벽한 게임을 하기 위한 이론적인 절차(즉, 체스 문제 해결)를 개략적으로 설명했다.

"체스를 사용하면 원칙적으로 다음과 같이 완벽한 게임을 하거나 기계를 만들 수 있습니다.주어진 위치에서 가능한 모든 동작을 고려한 다음, 상대편 등을 위한 모든 동작을 게임이 끝날 때까지(각 변동에서).제한적인 수의 이동 후에 게임의 규칙에 따라 종료를 해야 한다(50회 이동 추첨 규칙을 기억한다).이러한 변화는 각각 승패 또는 무승부로 끝납니다.마지막부터 역방향으로 움직이면 강제승부가 있는지, 무승부가 되는지, 패자가 되는지 판단할 수 있다고 말했다.

그리고 나서 Shannon은 그 절차에 따라 체스를 풀려면 약 10개의120 가능한 게임 변형을 비교하거나 약 10개의43 가능한 보드 위치 각각에 대해 최적의 움직임을 나타내는 "사전"을 보유해야 한다고 추정했다(현재 약 [4]5x10으로44 알려져 있다.그러나 체스를 푸는 데 필요한 수학적 연산의 수는 체스의 전체 게임 트리를 만드는 데 필요한 연산의 수와 크게 다를 수 있습니다.특히 White가 강제적인 승리를 거둔 경우, 게임 트리의 하위 집합만 평가하여 강제적인 승리가 존재하는지 확인합니다(즉, Black의 반박이 없음).게다가, 체스의 복잡도에 대한 섀넌의 계산은 평균 게임 길이를 40으로 가정하지만, 어느 한쪽의 강제적인 승리가 이 게임 길이와 관련이 있다고 말할 수 있는 수학적인 근거는 없다.실제로 전문가 수준의 게임(그랜드마스터급 플레이)은 16개 정도로 짧았다.이러한 이유로, 수학자들과 게임 이론가들은 체스를 푸는 것이 다루기 힘든 [4][9]문제라고 단정적으로 말하는 것을 꺼려왔다.

체스가 언제 또는 해결될지에 대한 예측

1950년에 Shannon은 게임 트리의 복잡도 10과120 1메가헤르츠로 작동하는 컴퓨터(당시 큰 범위: 1951년에 도입된 UNIVAC 1은 초당 최대 2000회의 작업을 수행할 수 있거나 2킬로헤르츠)를 바탕으로 터미널 노드를 1마이크로초에 평가할 수 있는 데 10년이 걸릴90 것으로 계산했습니다.그러므로 체스를 푸는 것은 그 당시에 가능한 어떤 기술도 넘어선 것처럼 보일 것이다.

버클리 캘리포니아 대학의 수학 및 생물물리학 교수인 한스 요아힘 브레머만은 1965년 논문에서 "미래 컴퓨터 기기의 속도, 메모리 및 처리 능력은 특정한 물리적 장벽, 즉 빛 장벽, 양자 장벽, 열역학적 장벽에 의해 제한된다"고 추가로 주장했다.예를 들어, 이러한 제한은 어떤 컴퓨터도 체스 게임의 가능한 움직임 시퀀스의 트리 전체를 조사할 수 없다는 것을 의미합니다."그럼에도 불구하고 브레머만은 언젠가 컴퓨터가 체스를 풀 수 있을 것이라는 가능성을 배제하지 않았다.그는 이렇게 썼다. "컴퓨터가 완벽하거나 거의 완벽한 게임을 하기 위해서는, 게임을 완전히 분석하는 것이 필요할 것이다.또는 대략적인 방법으로 게임을 분석하여 제한된 양의 트리 검색과 결합할 수도 있습니다.그러나 이러한 휴리스틱 프로그래밍에 대한 이론적 이해는 여전히 [10]매우 부족합니다."

최근의 과학적 진보는 이러한 평가를 크게 바꾸지 않았다.체커 게임은 2007년에 [11](약하게) 해결되었지만, 체스 포지션의 대략적인 제곱근을 가지고 있다.이 노력을 이끈 과학자 조나단 쉐퍼는 체스를 풀기 전에 양자컴퓨팅과 같은 돌파구가 필요할 것이라고 말했지만, 그는 16년 동안 체커를 풀면서 배운 한 가지는 "기술의 진보를 결코 과소평가하지 않는 것"[12]이라고 말하며 가능성을 배제하지 않고 있다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Allis, V. (1994). "PhD thesis: Searching for Solutions in Games and Artificial Intelligence" (PDF). Department of Computer Science. University of Limburg. Retrieved 2012-07-14.
  2. ^ "Lomonosov Tablebases". Retrieved 2013-04-24.
  3. ^ "이 퍼즐에서 누가 이길까?"546 체스 포지션(Post 1: Position, Post 7: Playable).
  4. ^ a b c Shannon, C. (March 1950). "Programming a Computer for Playing Chess" (PDF). Philosophical Magazine. 7. 41 (314). Archived (PDF) from the original on 2010-07-06. Retrieved 2008-06-27.
  5. ^ Mhalla, Mehdi; Prost, Frederic (2013-07-26). "Gardner's Minichess Variant is solved". arXiv:1307.7118 [cs.GT].
  6. ^ Watkins, Mark. "Losing Chess: 1. e3 wins for White" (PDF).
  7. ^ 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
  8. ^ John Tromp (2021). "Chess Position Ranking". GitHub.
  9. ^ http://www.chessgames.com Magnus Carlson vs Viswanathlan Anand, King's Indian Attack:Double Pianchetto (A07), 1/2-1/2, 16 무브.
  10. ^ Bremermann, H.J. (1965). "Quantum Noise and Information". Proc. 5th Berkeley Symp. Math. Statistics and Probability. Archived from the original on 2001-05-27.
  11. ^ Schaeffer, Jonathan; Burch, Neil; Björnsson, Yngvi; et al. (14 September 2007). "Checkers Is Solved". Science. 317 (5844): 1518–1522. Bibcode:2007Sci...317.1518S. doi:10.1126/science.1144079. PMID 17641166. S2CID 10274228.(설명 필요)
  12. ^ Sreedhar, Suhas. "Checkers, Solved!". Spectrum.ieee.org. Archived from the original on 2009-03-25. Retrieved 2009-03-21.

외부 링크