섀넌 번호

미국 수학자 클로드 섀넌의 이름을 딴 섀넌 숫자는 체스의 게임 트리 복잡도 10의¹²⁰ 보수적인 하한으로, 화이트의 움직임과 블랙의 움직임으로 이루어진 한 쌍의 움직임과 40쌍의 움직임으로 이루어진 전형적인 게임에 대한 평균 10개의³ 가능성에 기초한다.

섀넌 계산

Shannon은 1950년 논문 "Programming a Computer for Playing Chess"^[1]에서 체스의 게임 트리 복잡도 하한에 대한 계산을 보여주었고, 그 결과 약 10개의¹²⁰ 게임이 가능해졌다.

Shannon은 또한 "64${\displaystyle \frac{!}{}}$ ${\displaystyle \frac{32!}{}}$ ${\displaystyle \frac{{\mathrm{}!}^{}}{}}$ ${\displaystyle \frac{{}^{}{\mathrm{}!}^{}}{}}$ ${\displaystyle \frac{{\mathrm{}}^{}}{}}$\ $displaystyle \scriptstyle$\ $frac${ $64 !}$ {$32$! {$8$}"이라고 가능한 포지션의 수를 추정했다.$}^{2}{2!$$}^{6$ 또는⁴³ 약 10인치$.$여기에는 일부 불법 포지션(예: 1위 폰, 두 왕 모두 견제)이 포함되며 체포 및 승진에 따른 법적 포지션은 제외됩니다.

플라이 수 (반쪽 반쪽)	수 가능한 게임	수 체크메이트
1	20	0
2	400	0
3	8,902	0
4	197,281	8
5	4,865,609	347
6	119,060,324	10,828
7	3,195,901,860	435,767
8	84,998,978,956	9,852,036
9	2,439,530,234,167	400,191,963
10	69,352,859,712,417
11	2,097,651,003,696,806
12	62,854,969,236,701,747
13	1,981,066,775,000,396,239
14	61,885,021,521,585,529,237
15	2,015,099,950,053,364,471,960

각 플레이어가 한 피스를 5회(10플라이) 이동하면 69,352,859,712,417개의 게임을 실행할 수 있습니다.

더 엄격한 경계

위쪽의

Shannon의 숫자를 고려하여 Victor Allis는 포지션의 상한을 5×10으로⁵² 계산하고, 진수를 약 ^[2]10으로⁵⁰ 추정했다.최근^[3] 결과는 8.7x10의⁴⁵ 상한을 증명하고 프로모션이^[4][5] 없는 경우 4x10의³⁷ 상한을 나타내어 추정치를 개선했습니다.

더 낮게

Allis는 또한 "평균 분기 계수가 35이고 평균 게임 길이가 80인 것에 기초해" 게임 트리의 복잡성을 최소¹²³ 10으로 추정했다.비교하자면, 종종 비교되는 관측 가능한 우주의 원자의 수는 대략 10개로⁸⁰ 추정됩니다.

정확한 견적

존 트롬프와 피터 외스터룬드는 정수와 체스 ^[3]포지션 사이의 효율적인 계산 가능한 분사를 바탕으로 95% ${\displaystyle {\mathrm{신뢰수준}}^{}}$의 체스 포지션$수를 (4.822$ 0.$028$ $× 1044로 추정$했다$.{\displaystyle }$

센스 있는 체스 게임 수

샤논 숫자와 비교해 체스가 할 수 있는 "감지할 수 있는" 게임 수를 분석하면(보상 없이 여왕을 즉시 포로로 잡는 것과 같은 터무니없거나 명백한 게임 패전 동작은 세지 않음), 결과는 약 10게임에⁴⁰ 가깝다.이는 각 플라이에서 약 3개의 센스 있는 움직임(하프모브)을 선택하고 80플라이의 게임 길이(또는 동등하게 40개의 움직임)^[6]를 갖는 것에 기초한다.

「 」를 참조해 주세요.

• 체스 풀기
• 가서 수학해
• 게임의 복잡성

주 및 참고 자료

외부 링크

• 수학과 체스