조합론의 대양

깊이는 분기점이지, 말의 수가 아닙니다

1950년, 클로드 섀넌, 의 아버지 정보 이론, 의 아버지는 체스의 가능한 게임 수가 얼마나 되는지 추정했습니다. 그의 답, 대략 10¹²⁰, 은 섀넌 수가 되었으며, 그 이후로 우리의 직관을 뒷받침해 왔습니다.¹ 그것은 물리적 우주조차 부끄럽게 할 만큼 거대한 숫자이며, 우주에는 고작 약 10⁸⁰ 개의 원자만 존재한다.⁶ 모든 원자에게 각자 하나의 체스판을 나눠주어도, 모든 게임을 다 펼치기에는 판이 부족하다.

체스는 이를 정당하게 얻는다. 개시 단계에서부터 백은 20개의 수를 두고, 흑은 20개로 응수하며, 이미 400 단 한 번의 교환 이후의 포지션이 존재한다. 반수(반수) 여섯 수째에 이르면 그 수는 1억 1,900만을 넘어서고, 열 수째에 도달한다 69조.⁴ 플레이어들은 이를 분기 계수라고 부르며, 이는 매 턴마다 가능한 합법적 선택지의 수를 의미한다. 체스에서 이는 평균 약 35.² 이다. 그 소박한 숫자가 수를 거듭할수록 복리로 쌓이며, 게임의 신비로움의 엔진이 된다. 처음 20수 동안에는 대략 10⁶⁰ 개의 게임이 생성된다. 체스의 깊이의 원천은 말들이 아니다. 그것은 분기다.

400, 혹은 1조

체스의 초기 수(手) 수는 정확히 알려져 있습니다. WordChess의 수는 추정치이지만, 두 게임의 격차는 한 턴 만에 확연히 벌어져 그 차이를 의심할 여지가 없습니다.⁴

체스의 수치는 정확한 수 생성 카운트입니다(perft).⁴ WordChess의 수치는 각 측이 약 100만 개의 합법적인 오프닝 배치와 그 이후에 보수적으로 1,000개를 가정하며, 방법 노트.

모든 플레이어가 전체 가방을 가진다

WordChess는 격자 위의 단어 게임으로, 십자말풀기에 더 가깝고 칼부림에는 더 먼, 더 온화한 사촌처럼 보입니다. 그 인상은 정확히 틀렸으며, 그 이유는 규칙의 한 줄에 있습니다: 모든 플레이어가 100개의 타일 풀 전체를 가진다.⁷

7타일 랙도, 뽑기의 운도, 모음을 기다릴 필요도 없습니다. 어떤 턴이든, 플레이어는 사전의 거의 모든 148,941 단어, 최대 25글자까지의 단어,를 손에 잡고 그것을 놓을 곳을 찾을 수 있습니다.⁷ Scrabble, 무작위로 뽑힌 7개의 타일에 의해 제약을 받아, 분기 계수는 대략 35, 체스와 거의 같습니다.⁵ WordChess는 그 병목을 완전히 제거합니다.

그 결과는 격렬합니다. 첫 번째 수만으로도 100만에서 200만 개 사이의 합법적 배치, 즉 단어, 방향, 그리고 넓게 펼쳐진 25×25 보드 위의 위치가 열립니다. 두 플레이어가 모두 한 번씩만 움직인 시점에도, 게임은 대략 1조 개에 달하는 위치로 분기됩니다. 체스는 동일한 교환 후 400개입니다.³

규칙은 더 단순합니다. 그러나 가능성의 공간은 그렇지 않습니다.

점심 식사 전, 체스 한 판 전체

판이 차오르면서 체스의 분기 계수는 35로 올라가며 그 수준을 유지한다. WordChess의 분기 계수는 수천에 달하며, 이미 사용된 모든 단어가 새로운 고리가 되어 붙잡을 수 있게 되고, 전체 타일 풀을 고려하면 유일한 실질적 한계는 사전이 허용하는 교차 방식뿐이다.⁷

이것을 앞으로 돌려보자. 의도적으로 보수적으로 매 수 1,000개의 합법적 수를 가정하면, WordChess는 10¹²⁰, 즉 한 판의 전체 체스 게임의 복잡성인 섀넌 수에, 그 첫 스물 수이내에 도달한다. 매 수 10,000개의 수를 허용해도 여전히 합리적이며, 스물 수는 10¹⁶⁰으로 올라간다: 체스의 10⁶⁰.¹

추정치를 줄여 가다가, 플레이어가 발견하는 것이 300 턴당 합법적 수의 수는 실제 수의 극히 일부이며, 20수만으로도 10⁹⁹. 여전히 체스보다 40개 자릿수 이상 크다. 이 결론은 당신이 제시할 수 있는 모든 비관적 가정을 견뎌낸다.¹

복잡도는 하나의 선택에서 얼마나 많은 미래가 갈라지는지를 의미한다

체스는 당신을 제약한다: 나이트는 나이트처럼 움직이고, 폰은 한 칸씩 기어가고, 당신의 선택지는 풍부하지만 유한하고 익숙하다. WordChess는 당신에게 언어 전체와 기판 전체를 주고 선택을 요구한다. 이것이 디자인이 만든 거래이며, 친근한 격자가 조합론적 대양을 감추고 있는 이유이다.

이 모든 것이 WordChess를 더 어렵게 만드는 것은 아니다 잘, 더 큰 탐색 공간은 더 깊은 전략과 같은 것이 아니며, 체스의 천재성은 좁은 분기에서 얼마나 많은 의미를 뽑아내느냐에 있다. 그러나 단어 게임을 경량 옵션으로 상상하는 사람은 수학적으로 정확히 반대로 이해하고 있다. 처음 20수 동안, WordChess는 왕들의 위대한 게임을 거의 작아 보이게 만든다.