체스를위한 완벽한 알고리즘이 있습니까? [닫은]
나는 최근에 코더가 아닌 사람과 체스 컴퓨터의 가능성에 대해 논의했습니다. 나는 이론에 정통하지는 않지만 충분히 알고 있다고 생각합니다.
나는 체스에서 항상이기거나 찌르는 결정 론적 튜링 머신이 존재할 수 없다고 주장했다. 나는 당신이 player1 / 2 움직임의 모든 조합의 전체 공간을 검색하더라도, 컴퓨터가 각 단계에서 결정하는 단일 움직임은 휴리스틱에 기초한다고 생각합니다. 휴리스틱 기반이기 때문에 상대방이 할 수있는 모든 동작을 반드시 이길 수는 없습니다.
내 친구는 반대로 컴퓨터가 "실수"한 행동을하지 않으면 항상 이길 것이라고 생각했다 (그러나 당신은 그것을 정의하겠습니까?). 그러나 CS를 선택한 프로그래머라면, 현명한 상대를 고려한 당신의 좋은 선택조차도 결국 "실수"행동을 강요 할 수 있다는 것을 알고 있습니다. 모든 것을 알더라도 휴리스틱과 일치하는 다음 행동은 욕심입니다.
대부분의 체스 컴퓨터는 가능한 최종 게임을 진행중인 게임과 일치 시키려고합니다. 다시 말하지만 문제의 최종 게임은 피할 수 있습니다.
편집 : 흠 ... 여기 깃털을 뻗은 것처럼 보입니다. 잘 됐네요
다시 생각하면 체스와 같은 유한 게임을 해결하는 데 이론적 인 문제가없는 것 같습니다. 나는 체스가 체커의 숫자보다 소진되는 것이 아니라 배우자에 의해 반드시 승리한다는 점에서 체스가 체커보다 조금 더 복잡하다고 주장합니다. 나의 원래 주장은 아마도 틀렸을 것입니다. 그러나 나는 아직 (공식적으로) 만족스럽게 증명되지 않은 것을 지적했다고 생각합니다.
내 생각 실험은 트리의 브랜치가 찍힐 때마다 알고리즘 (또는 암기 된 경로)이 상대 이동의 가능한 브랜치에 대한 메이트 경로를 찾아야한다는 것입니다. 토론 후에, 우리가 상상할 수있는 것보다 더 많은 메모리가 주어지면이 모든 길을 찾을 수 있다고 생각합니다.
"저는 체스에서 항상이기거나 찌르는 결정 론적 튜링 머신이 존재할 수 없다고 주장했습니다."
당신은 옳지 않습니다. 그런 기계가있을 수 있습니다. 문제는 검색해야 할 상태 공간의 거 대성입니다. 유한하기 때문에 정말 큽니다.
그렇기 때문에 체스는 휴리스틱으로 돌아갑니다. 상태 공간이 너무 크지 만 유한합니다. 모든 가능한 게임의 모든 과정에서 완벽한 움직임을 찾기 위해 훨씬 적은 수의 열거를하는 것은 매우 큰 검색 문제가 될 것입니다.
오프닝은 "강한"위치를 제공하는 게임 중반으로 안내합니다. 알려진 결과가 아닙니다. 적은 수의 조각이있는 최종 게임조차도 최고의 다음 움직임을 결정하기가 어렵습니다. 기술적으로 그들은 유한합니다. 그러나 대안의 수는 엄청납니다. 2 명의 루크 + 킹조차도 22 개의 다음 움직임이 가능합니다. 짝짓기까지 6 번의 움직임이 필요한 경우 12,855,002,631,049,216 개의 움직임을보고 있습니다.
움직임을 여는 것에 대한 수학을하십시오. 약 20 개의 오프닝 움직임이 있지만 30 번 정도의 두 번째 움직임이 있으므로 세 번째 움직임으로 360,000 개의 대체 게임 상태를보고 있습니다.
그러나 체스 게임은 (기술적으로) 유한합니다. 거대하지만 유한하다. 완벽한 정보가 있습니다. 정의 된 시작 및 종료 상태가 있습니다. 코인 토스 또는 주사위 롤이 없습니다.
나는 체스에서 실제로 발견 된 것에 대해 아무것도 모른다. 그러나 수학자로서 여기 내 추론이 있습니다.
먼저 우리는 화잇이 먼저 가야한다는 사실을 기억해야합니다. 어쩌면 블랙에게 이점을 줄 수도 있습니다.
이제 블랙에 대한 완벽한 전략 이 없다고 가정 해보자 . 이것은 블랙이 무엇을하든 화이트가 이길 수있는 전략이 있다는 것을 의미합니다. 잠깐 -이 방법이 입니다 화이트를위한 완벽한 전략!
이 두 선수 중 적어도 하나는 것을 우리에게 알려줍니다 않는 그 플레이어는 항상이기거나 그릴 수있는 완벽한 전략을 가지고있다.
그러면 세 가지 가능성 만 있습니다.
- 그가 완벽하게 연주하면 흰색이 항상 이길 수 있습니다.
- 그가 완벽하게 연주하면 블랙은 항상 이길 수 있습니다
- 한 플레이어가 완벽하게 플레이하면이기거나 무승부 할 수 있습니다 (두 플레이어가 완벽하게 플레이하면 항상 교착 상태가됩니다).
그러나이 중 실제로 올바른 것은 우리가 알지 못할 수도 있습니다.
이 질문에 대한 답은 ' 그렇다'이다 . 최소한 두 명의 플레이어 중 한 명에게는 체스를위한 완벽한 알고리즘이 있어야한다.
프로그램이 항상 게임에서이기거나 묶을 수 있다는 것이 체커 게임 에서 입증되었습니다 . 즉, 한 플레이어가 다른 플레이어를 잃게 만들 수있는 움직임을 선택할 수 없습니다.
연구자들은 거의 20 억 년 동안 5 천억 개의 가능한 체커 포지션을 거쳤으며, 이는 여전히 체스 포지션 수의 무한한 작은 부분입니다. 체커의 노력에는 연구팀 프로그램이 성공 또는 실패로 분류하는 소프트웨어로 경험 규칙을 검사하는 데 도움을 준 최고 선수가 포함되었습니다. 그런 다음 연구원들은 매일 평균 50 대의 컴퓨터에서 프로그램을 실행했습니다. 며칠 동안 프로그램은 200 대의 컴퓨터에서 실행되었습니다. 연구원들은 진행 상황을 모니터링하고 그에 따라 프로그램을 조정했습니다. 실제로 치누크는 1994 년 체커 월드 챔피언십에서 우승하기 위해 인간을 이겼습니다.
그렇습니다, 당신은 체스를 해결할 수 있습니다. 아니, 당신은 곧있을 것입니다.
이것은 컴퓨터에 관한 질문이 아니라 체스 게임에 관한 것입니다.
문제는 절대로 게임을 잃지 않는 안전 전략이 있습니까? 이러한 전략이 존재하면 모든 것을 알고있는 컴퓨터는 항상이 전략을 사용할 수 있으며 더 이상 휴리스틱이 아닙니다.
예를 들어 게임 틱택 토는 일반적으로 휴리스틱을 기반으로 재생됩니다. 그러나 페일 세이프 전략이 있습니다. 상대방이 무엇을하든, 처음부터 바로 게임을한다면 항상 게임에서 패하는 것을 피할 수있는 방법을 찾을 수 있습니다.
따라서 이러한 전략이 체스에도 존재하는지 여부를 증명해야합니다. 기본적으로 동일합니다. 가능한 이동 공간이 훨씬 더 큽니다.
나는이 스레드에 매우 늦게 왔으며, 이미 몇 가지 문제를 깨달았습니다. 그러나 전직 마스터이자 전직 전문 체스 프로그래머로서 몇 가지 유용한 사실과 수치를 추가 할 수 있다고 생각했습니다. 체스 의 복잡성을 측정하는 몇 가지 방법이 있습니다 .
- 체스 게임의 총 수는 약 10 ^ (10 ^ 50)입니다. 그 숫자는 상상할 수 없을 정도로 큽니다.
- 40 개 이하의 체스 게임 수는 약 10 ^ 40입니다. 그것은 여전히 엄청나게 큰 숫자입니다.
- 가능한 체스 위치의 수는 약 10 ^ 46입니다.
- 전체 체스 검색 트리 (Shannon 번호)는 평균 분기 계수 35와 평균 게임 길이 80을 기준으로 약 10 ^ 123입니다.
- 비교를 위해 관측 가능한 우주의 원자 수는 일반적으로 약 10 ^ 80으로 추정됩니다.
- 6 개 이하의 모든 최종 게임이 대조되어 해결되었습니다 .
결론 : 체스는 이론적으로 해결할 수 있지만 돈, 동기 부여, 컴퓨팅 능력 또는 스토리지를 보유 할 수는 없습니다.
실제로 일부 게임이 해결되었습니다. Tic-Tac-Toe는 항상이기거나 묶을 AI를 만들기에 매우 쉬운 방법입니다. 최근에 Connect 4도 해결되었습니다 (완벽한 플레이로 인해 패배하게되므로 두 번째 플레이어에게는 불공평 한 것으로 나타남).
그러나 체스는 해결되지 않았으며 그것이 공정한 게임이라는 증거가 없다고 생각합니다 (즉, 완벽한 플레이가 무승부인지 여부). 이론적 관점에서 엄격히 말하면 체스는 가능한 많은 수의 조각 구성을 가지고 있습니다. 따라서 검색 공간은 유한합니다 (아마도 크지 만). 따라서 완벽하게 연주 할 수있는 결정적인 튜링 머신이 존재합니다. 그러나 건설이 가능한지 여부는 다른 문제입니다.
평균 $ 1000 데스크톱은 2040 년까지 5 초만에 체커를 해결할 수 있습니다 (5x10 ^ 20 계산).
이 속도로도 체스를 풀려면 이 컴퓨터 100 대가 약 6.34 x 10 ^ 19 년 이 걸립니다 . 여전히 가능하지 않습니다. 근처에도 안.
2080 년경에 평균 데스크톱은 초당 약 10 ^ 45 번 계산됩니다. 단일 컴퓨터는 약 27.7 시간 내에 체스를 해결할 수있는 계산 능력을 갖습니다. 지난 30 년 동안 컴퓨팅 성능이 계속 향상되는 한 2080 년까지는 확실히 이루어질 것입니다.
2090 년까지, 약 1 초 안에 체스를 해결하기에 충분한 계산 능력이 $ 1000 데스크탑에 존재할 것입니다. 그래서 그 날짜까지는 아주 사소합니다.
을 감안할 때 체커는 2007 년에 해결되었다, 그리고, 우리는 아마 수 1 초를 해결하기 위해 연산 능력은 33 ~ 35에 대한 년으로 지연됩니다 대략 체스 2,055에서 2,057 사이 사이 어딘가를 해결할 수 추정하고있다. 더 많은 계산 능력을 사용할 수있게되면 (45 년 후) 더 빨리이 같은 프로젝트에 더 많은 노력을 기울일 수 있습니다. 그러나, 나는 가장 빠른 2050, 가장 최근에는 2060이라고 말할 것입니다.
2060 년에는 체스를 풀기 위해 평균 데스크탑 3.17 x 10 ^ 10 년이 소요됩니다. 가격 대비 성능이 향상됨에 따라 더 큰 시스템과 슈퍼 컴퓨터를 사용할 수있을 것입니다. 또한, 계산 능력의 크기가 더 빠른 속도로 증가합니다. 이제 슈퍼 컴퓨터가 초당 2.33 x 10 ^ 15 계산을 수행 할 수 있고 $ 1000 컴퓨터가 약 2 x 10 ^ 9를 수행 할 수 있다고 가정하십시오. 이에 비해 10 년 전의 차이는 10 ^ 6 대신 10 ^ 5였습니다. 2060 년까지 크기 차이는 아마도 10 ^ 12가 될 것이며, 심지어 예상보다 빠르게 증가 할 수 있습니다.
이것의 대부분은 우리 인간이 체스를 풀기위한 추진력을 가지고 있는지의 여부에 달려 있지만, 계산 능력은이시기에 (우리의 페이스가 계속되는 한) 실현 가능할 것입니다.
또 다른 메모에서, 훨씬 더 간단한 Tic-Tac-Toe 게임은 2,653,002 개의 계산이 가능합니다 (개방형 보드 사용). Tic-Tac-Toe를 약 250 (초당 백만 계산) 초로 해결하는 계산 능력은 1990 년에 달성되었습니다.
1955 년에는 컴퓨터가 1 개월 만에 Tic-Tac-Toe를 풀 수있는 힘을 가졌습니다 (초당 1 회 계산). 다시 말하지만, 이것은 컴퓨터에 패키지 할 수 있다면 (1955 년에 1000 달러짜리 데스크탑이 없었 음) 1000 달러를 얻을 수있는 것을 기반으로하며 , 이 컴퓨터는 Tic-Tac-Toe를 해결하는 데 전념했을 것입니다 .... Tic-Tac-Toe가 컴퓨터에 의해 "해결 된"것으로 여겨지는 날짜는 없지만, 나는 계산이 비싸고이 목적으로 사용되지 않았을 것입니다. 실제 계산 능력보다 뒤쳐져 있는지 확인하십시오.
또한 45 년 만에 $ 1000를 고려하면 현재보다 약 4 배 적은 가치가있을 것이므로 이와 같은 프로젝트에 훨씬 더 많은 돈을 투자 할 수있는 반면 계산 능력은 계속 저렴 해집니다.
실제로 가능하다 두 선수가 더 잘 주문 무한 게임에서이기는 전략을 가지고하는; 그러나 체스는 질서 정연합니다. 실제로, 50 이동 규칙 으로 인해 게임이 가질 수있는 이동 수의 상한이 있으므로, 가능한 많은 체스 게임 만이 가능합니다 (정확히 해결하기 위해 열거 할 수 있음). 적어도 :)
당신의 주장의 끝은 현대 체스 프로그램이 현재 작동하는 방식에 의해 뒷받침됩니다 . 그들은 결정 론적으로 작동하기 위해 체스 프로그램을 코딩하기에는 너무 많은 자원 집약적이기 때문에 그렇게 작동합니다. 항상 그런 식으로 작동 하지는 않습니다 . 체스가 언젠가 해결 될 가능성이 있으며, 그렇게되면 컴퓨터에 의해 해결 될 것입니다.
For the record, there are computers that can win or tie at checkers. I'm not sure if the same could be done for chess. The number of moves is a lot higher. Also, things change because pieces can move in any direction, not just forwards and backwards. I think although I'm not sure, that chess is deterministic, but that there are just way too many possible moves for a computer to currently determine all the moves in a reasonable amount of time.
난 당신이 죽은 것 같아요. Deep Blue 및 Deep Thought과 같은 컴퓨터에는 사전 정의 된 여러 게임으로 프로그래밍되어 있으며 트리를 해당 게임의 끝으로 구문 분석하는 영리한 알고리즘이 있습니다. 물론 이것은 과도하게 단순화 된 것입니다. 게임이 진행되는 동안 항상 컴퓨터를 "이길"기회가 있습니다. 이것은 컴퓨터가 최적이 아닌 움직임 (무엇이든)을 움직이게하는 움직임을 의미합니다. 컴퓨터가 이동 제한 시간 전에 최적의 경로를 찾을 수없는 경우 바람직하지 않은 경로 중 하나를 선택하여 실수를 할 수 있습니다.
실제 기계 학습 또는 유전자 프로그래밍 / 진화 알고리즘을 사용하는 다른 종류의 체스 프로그램이 있습니다. 일부 프로그램은 진화되어 신경망 등을 사용하여 결정을 내립니다. 이런 경우 컴퓨터가 "실수"를하더라도 여전히 승리를 거둘 수 있다고 생각합니다.
이 GP 유형에는 Blondie24 라는 흥미로운 책이 있습니다. 체커에 관한 것이지만 체스에도 적용될 수 있습니다.
이 질문에 관한 게임 이론에서 대답은 그렇습니다. 체스는 완벽하게 연주 될 수 있습니다. 게임 공간은 알려져 있고 예측 가능하며, 만약 당신이 손자의 양자 컴퓨터를 가지고 있다면 아마도 모든 휴리스틱을 제거 할 수있을 것입니다.
오늘날 스크립팅 언어로 완벽한 틱택 토 머신을 작성할 수 있으며 실시간으로 완벽하게 재생됩니다.
Othello는 현재 컴퓨터에서 쉽게 완벽하게 재생할 수있는 또 다른 게임이지만 컴퓨터의 메모리와 CPU에는 약간의 도움이 필요합니다.
체스는 이론적으로는 가능하지만 실제로는 불가능합니다 (2008 년)
i-Go는 까다 롭습니다. 가능성의 공간이 우주의 원자 수를 넘어 서기 때문에 완벽한 i-Go 기계를 만드는 데 시간이 걸릴 수 있습니다.
체스는 매트릭스 게임의 한 예입니다. 정의에 따르면 최적의 결과를 얻습니다 (내쉬 평형을 생각하십시오). 플레이어 1과 2가 각각 최적의 움직임을 취한다면, 어떤 결과는 항상 도달 할 것입니다 (승인 손실 여부는 여전히 알 수 없음).
1970 년대의 체스 프로그래머로서 저는 이것에 대해 분명히 의견을 가지고 있습니다. 내가 약 10 년 전에 썼던 것은 오늘날에도 여전히 기본적으로 사실입니다.
당시에는 적절하게 수행하면 일반적으로 체스를 해결할 수 있다고 생각했습니다.
Checkers는 최근에 해결되었지만 (Yay, University of Alberta, Canada !!!) 효과적으로 Brute Force를 수행했습니다. 일반적으로 체스를하려면 똑똑해야합니다.
물론, 양자 컴퓨팅 이 현실이 되지 않는 한 . 그렇다면 체스는 Tic-Tac-Toe처럼 쉽게 해결됩니다.
1970 년대 초 Scientific American에서 짧은 패러디가 내 관심을 끌었습니다. 그것은 체스 게임이 러시아 체스 컴퓨터에 의해 해결되었다는 발표였습니다. 양측의 완벽한 플레이로 승리를 보장 할 수있는 완벽한 화이트 무브가 하나 있다고 결정했고, 그 무브는 1. a4!
여기에 많은 답변이 중요한 게임 이론 포인트를 만듭니다.
- 체스는 게임 상태에 대한 완전한 정보가있는 유한하고 결정적인 게임입니다.
- 당신은 유한 게임을 해결하고 완벽한 전략을 식별 할 수 있습니다
- 그러나 체스는 무차별 대입 방법으로 완전히 해결할 수 없을 정도로 충분히 크다.
그러나 이러한 관찰은 중요한 실제 요점을 놓치고 있습니다. 탁월한 기계를 만들기 위해 완전한 게임을 완벽하게 해결할 필요는 없습니다 .
실제로 가능한 상태 공간의 작은 부분조차 검색하지 않고도 탁월한 체스 머신을 만들 수 있습니다 (즉, 절대 잃지 않고 항상 승리 또는 무승부).
예를 들어 다음 기술은 모두 필요한 검색 공간을 크게 줄입니다.
- 알파 / 베타 또는 MTD-f 와 같은 트리 정리 기술은 이미 검색 공간을 크게 줄입니다.
- 가능한 승리 위치. 많은 결말이이 범주에 속합니다. 예를 들어 KR vs K를 검색 할 필요가 없습니다. 이는 입증 된 승리입니다. 일부 작업을 통해 더 많은 보장 된 승리를 증명할 수 있습니다.
- Almost certain wins - for "good enough" play without any foolish mistakes (say about ELO 2200+?) many chess positions are almost certain wins, for example a decent material advantage (e.g. an extra Knight) with no compensating positional advantage. If your program can force such a position and has good enough heuristics for detecting positional advantage, it can safely assume it will win or at least draw with 100% probability.
- Tree search heuristics - with good enough pattern recognition, you can quickly focus on the relevant subset of "interesting" moves. This is how human grandmasters play so it's clearly not a bad strategy..... and our pattern recognition algorithms are constantly getting better
- 위험 평가-위치의 "위험성"에 대한 더 나은 개념은 결과가 더 불확실한 상황에 컴퓨팅 능력을 집중함으로써 훨씬 더 효과적인 검색을 가능하게합니다 (이것은 정지 검색 의 자연스러운 확장입니다 ).
위의 기술을 올바르게 조합하면 "무적의"체스 게임기를 만들 수 있다고 확신합니다. 우리는 아마도 현재 기술에 그리 멀지 않을 것입니다.
Note that It's almost certainly harder to prove that this machine cannot be beaten. It would probably be something like the Reimann hypothesis - we would be pretty sure that it plays perfectly and would have empirical results showing that it never lost (including a few billion straight draws against itself), but we wouldn't actually have the ability to prove it.
Additional note regarding "perfection":
I'm careful not to describe the machine as "perfect" in the game-theoretic sense because that implies unusually strong additional conditions, such as:
- Always winning in every situation where it is possible to force a win, no matter how complex the winning combination may be. There will be situations on the boundary between win/draw where this is extremely hard to calculate perfectly.
- Exploiting all available information about potential imperfection in your opponent's play, for example inferring that your opponent might be too greedy and deliberately playing a slightly weaker line than usual on the grounds that it has a greater potential to tempt your opponent into making a mistake. Against imperfect opponents it can in fact be optimal to make a losing if you estimate that your opponent probably won't spot the forced win and it gives you a higher probability of winning yourself.
Perfection (particularly given imperfect and unknown opponents) is a much harder problem than simply being unbeatable.
if you search the entire space of all combinations of player1/2 moves, the single move that the computer decides upon at each step is based on a heuristic.
There are two competing ideas there. One is that you search every possible move, and the other is that you decide based on a heuristic. A heuristic is a system for making a good guess. If you're searching through every possible move, then you're no longer guessing.
"Is there a perfect algorithm for chess?"
Yes there is. Maybe it's for White to always win. Maybe it's for Black to always win. Maybe it's for both to always tie at least. We don't know which, and we'll never know, but it certainly exist.
See also
I found this article by John MacQuarrie that references work by the "father of game theory" Ernst Friedrich Ferdinand Zermelo. It draws the following conclusion:
In chess either white can force a win, or black can force a win, or both sides can force at least a draw.
The logic seems sound to me.
It's perfectly solvable.
There are 10^50 odd positions. Each position, by my reckoning, requires a minimum of 64 round bytes to store (each square has: 2 affiliation bits, 3 piece bits). Once they are collated, the positions that are checkmates can be identified and positions can be compared to form a relationship, showing which positions lead to other positions in a large outcome tree.
Then, the program needs only to find the lowest only one side checkmate roots, if such a thing exists. In any case, Chess was fairly simply solved at the end of the first paragraph.
I'm only 99.9% convinced by the claim that the size of the state space makes it impossible to hope for a solution.
Sure, 10^50 is an impossibly large number. Let's call the size of the state space n.
What's the bound on the number of moves in the longest possible game? Since all games end in a finite number of moves there exists such a bound, call it m.
Starting from the initial state, can't you enumerate all n moves in O(m) space? Sure, it takes O(n) time, but the arguments from the size of the universe don't directly address that. O(m) space might not even be very much. For O(m) space couldn't you also track, during this traversal, whether the continuation of any state along the path you are traversing leads to EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin, or BlackMayWinOrForceDraw? (There's a lattice depending on whose turn it is, annotate each state in the history of your traversal with the lattice meet.)
Unless I'm missing something, that's an O(n) time / O(m) space algorithm for determining which of the possible categories chess falls into. Wikipedia cites an estimate for the age of the universe at approximately 10^60th Planck times. Without getting into a cosmology argument, let's guess that there's about that much time left before the heat/cold/whatever death of the universe. That leaves us needing to evaluate one move every 10^10th Planck times, or every 10^-34 seconds. That's an impossibly short time (about 16 orders of magnitude shorter than the shortest times ever observed). Let's optimistically say that with a super-duper-good implementation running on top of the line present-or-forseen-non-quantum-P-is-a-proper-subset-of-NP technology we could hope to evaluate (take a single step forward, categorize the resulting state as an intermediate state or one of the three end states) states at a rate of 100 MHz (once every 10^-8 seconds). Since this algorithm is very parallelizable, this leaves us needing 10^26th such computers or about one for every atom in my body, together with the ability to collect their results.
I suppose there's always some sliver of hope for a brute-force solution. We might get lucky and, in exploring only one of white's possible opening moves, both choose one with much-lower-than-average fanout and one in which white always wins or wins-or-draws.
We could also hope to shrink the definition of chess somewhat and persuade everyone that it's still morally the same game. Do we really need to require positions to repeat 3 times before a draw? Do we really need to make the running-away party demonstrate the ability to escape for 50 moves? Does anyone even understand what the heck is up with the en passant rule? ;) More seriously, do we really need to force a player to move (as opposed to either drawing or losing) when his or her only move to escape check or a stalemate is an en passant capture? Could we limit the choice of pieces to which a pawn may be promoted if the desired non-queen promotion does not lead to an immediate check or checkmate?
I'm also uncertain about how much allowing each computer hash-based access to a large database of late game states and their possibly outcomes (which might be relatively feasible on existing hardware and with existing endgame databases) could help in pruning the search earlier. Obviously you can't memoize the entire function without O(n) storage, but you could pick a large integer and memoize that many endgames enumerating backwards from each possible (or even not easily provably impossible, I suppose) end state.
I know this is a bit of a bump, but I have to put my 5 cents worth in here. It is possible for a computer, or a person for that matter, to end every single chess game that he/she/it participates in, in either a win or a stalemate.
To achieve this, however, you must know precisely every possible move and reaction and so forth, all the way through to each and every single possible game outcome, and to visualize this, or to make an easy way of analyising this information, think of it as a mind map that branches out constantly.
The center node would be the start of the game. Each branch out of each node would symbolize a move, each one different to its bretheren moves. Presenting it in this manor would take much resources, especially if you were doing this on paper. On a computer, this would take possibly hundreds of Terrabytes of data, as you would have very many repedative moves, unless you made the branches come back.
To memorize such data, however, would be implausable, if not impossible. To make a computer recognize the most optimal move to take out of the (at most) 8 instantly possible moves, would be possible, but not plausable... as that computer would need to be able to process all the branches past that move, all the way to a conclusion, count all conclusions that result in a win or a stalemate, then act on that number of wining conclusions against losing conclusions, and that would require RAM capable of processing data in the Terrabytes, or more! And with todays technology, a computer like that would require more than the bank balance of the 5 richest men and/or women in the world!
So after all that consideration, it could be done, however, no one person could do it. Such a task would require 30 of the brightest minds alive today, not only in chess, but in science and computer technology, and such a task could only be completed on a (lets put it entirely into basic perspective)... extremely ultimately hyper super-duper computer... which couldnt possibly exist for at least a century. It will be done! Just not in this lifetime.
There are two mistakes in your thought experiment:
If your Turing machine is not "limited" (in memory, speed, ...) you do not need to use heuristics but you can calculate evaluate the final states (win, loss, draw). To find the perfect game you would then just need to use the Minimax algorithm (see http://en.wikipedia.org/wiki/Minimax) to compute the optimal moves for each player, which would lead to one or more optimal games.
There is also no limit on the complexity of the used heuristic. If you can calculate a perfect game, there is also a way to compute a perfect heuristic from it. If needed its just a function that maps chess positions in the way "If I'm in this situation S my best move is M".
As others pointed out already, this will end in 3 possible results: white can force a win, black can force a win, one of them can force a draw.
The result of a perfect checkers games has already been "computed". If humanity will not destroy itself before, there will be also a calculation for chess some day, when computers have evolved enough to have enough memory and speed. Or we have some quantum computers... Or till someone (researcher, chess experts, genius) finds some algorithms that significantly reduces the complexity of the game. To give an example: What is the sum of all numbers between 1 and 1000? You can either calculate 1+2+3+4+5...+999+1000, or you can simply calculate: N*(N+1)/2 with N = 1000; result = 500500. Now imagine don't know about that formula, you don't know about Mathematical induction, you don't even know how to multiply or add numbers, ... So, it may be possible that there is a currently unknown algorithm that just ultimately reduces the complexity of this game and it would just take 5 Minutes to calculate the best move with a current computer. Maybe it would be even possible to estimate it as a human with pen & paper, or even in your mind, given some more time.
So, the quick answer is: If humanity survives long enough, it's just a matter of time!
It just might be solvable, but something bothers me: Even if the entire tree could be traversed, there is still no way to predict the opponent's next move. We must always base our next move on the state of the opponent, and make the "best" move available. Then, based on the next state we do it again. So, our optimal move might be optimal iff the opponent moves in a certain way. For some moves of the opponent our last move might have been sub-optimal.
I just fail to see how there could be a "perfect" move in every step.
For that to be the case, there must for every state [in the current game] be a path in the tree which leads to victory, regardless of the opponent's next move (as in tic-tac-toe), and I have a hard time figuring that.
Mathematically, chess has been solved by the Minimax algorithm, which goes back to the 1920s (either found by Borel or von Neumann). Thus, a turing machine can indeed play perfect chess.
However, the computational complexity of chess makes it practically infeasible. Current engines use several improvements and heuristics. Top engines today have surpassed the best humans in terms of playing strength, but because of the heuristics that they are using, they might not play perfect when given infinite time (e.g., hash collisions could lead to incorrect results).
The closest that we currently have in terms of perfect play are endgame tablebases. The typical technique to generate them is called retrograde analysis. Currently, all position with up to six pieces have been solved.
Yes , in math , chess is classified as a determined game , that means it has a perfect algorithm for each first player , this is proven to be true even for infinate chess board , so one day probably a quantom AI will find the perfect strategy, and the game is gone
More on this in this video : https://www.youtube.com/watch?v=PN-I6u-AxMg
There is also quantom chess , where there is no math proof that it is determined game http://store.steampowered.com/app/453870/Quantum_Chess/
and there you are detailed video about quantom chess https://chess24.com/en/read/news/quantum-chess
Of course There's only 10 to the power of fifty possible combinations of pieces on the board. Having that in mind, to play to every compibation, you would need make under 10 to the power of fifty moves (including repetitions multiply that number by 3). So, there's less than ten to the power of one hundred moves in chess. Just pick those that lead to checkmate and you're good to go
64bit math (=chessboard) and bitwise operators (=next possible moves) is all You need. So simply. Brute Force will find the most best way usually. Of course, there is no universal algorithm for all positions. In real life the calculation is also limited in time, timeout will stop it. A good chess program means heavy code (passed,doubled pawns,etc). Small code can't be very strong. Opening and endgame databases just save processing time, some kind of preprocessed data. The device, I mean - the OS,threading poss.,environment,hardware define requirements. Programming language is important. Anyway, the development process is interesting.
참고URL : https://stackoverflow.com/questions/297577/is-there-a-perfect-algorithm-for-chess
'Programming' 카테고리의 다른 글
| 기존 프로젝트를 복사하여 붙여 넣거나 복제하려면 어떻게해야합니까? (0) | 2020.08.07 |
|---|---|
| Microsoft Roslyn과 CodeDom (0) | 2020.08.06 |
| Objective-C Split ()? (0) | 2020.08.06 |
| HTTPPOST, 사전 또는에서 양식 값을 검색하는 방법은 무엇입니까? (0) | 2020.08.06 |
| Gradle을 사용하여 종속성이있는 jar 작성 (0) | 2020.08.06 |