도달 가능한 체스 포지션 중 218개 이상의 수를 둘 수 있는 경우는 없음

(lichess.org)

1964년 Nenad Petrović가 발표한 218수짜리 체스 포지션보다 많은 수를 둘 수 있는 포지션은 존재하지 않음
모든 포지션을 탐색하는 것은 현실적으로 불가능하므로, 수학적 최적화와 컴퓨터를 이용한 모델링 기법을 활용해 한계를 증명함
불필요한 말 제거, 부분적 말 배치 허용, 캐슬링 단순화 등으로 탐색 공간을 효과적으로 줄임
최종적으로 Gurobi 최적화 툴로 218수가 최대임을 확인, 144수(프로모션 제외) 등의 기록도 추가적으로 검증함
이 연구로 체스 엔진 및 압축 개발자들이 최대 수 제한에 대한 불확실성을 해소할 수 있게 됨

서론: 218수 체스 포지션 논쟁

1964년 체스 구성 그랜드마스터 Nenad Petrović가 218수짜리 포지션을 발표한 이후, 이 기록을 깨기 위한 시도가 이어졌음. 필자는 컴퓨터 과학자로서 모든 포지션을 컴퓨터를 통해 분석하며 이 질문에 종지부를 찍고자 했음. 약 4.8 × 10^44개에 달하는 도달 가능한 체스 포지션이 존재하지만, 그만큼의 방대한 탐색은 현실적으로 불가능함.

수학적 최적화의 도입

불필요한 말 및 조합 최소화

체스판에 검은 말(흑말) 이 추가적으로 이동의 수를 늘리는 경우는 한정적임
- 백 폰이 잡을 수 있게 되거나, 상대 킹에 대한 체크 상황을 회피시킬 때 등
검은말 대부분은 제거해도 최대 이동 수에 영향이 없음
말 수가 허용되는 한, 흑말을 약한 말로 교체하거나 일부 제약조건(핀 등) 하에서 배치 조정 가능
백말의 경우 반대로, 최적 포지션 구성 시 퀸 등 강한 말로 모두 대체하면 비합법 포지션이 발생 가능하므로 세밀한 조정이 필요함

체크 상황과 이동수 제한

흑킹이 체크된 상태는 합법 포지션이 아니기에 고려할 필요 없음
백킹이 체크일 때는 움직임이 심각히 제한됨(최대 120수), 218수에 절대 도달 불가
따라서 체크가 없는 포지션만을 대상으로 탐색 가능

부분적 말 배치와 수학적 모델링

조합의 복잡도를 줄이기 위해 부분적(fractional) 말 배치와 이동, 그리고 일부 체스 규칙을 완화한 모델로 접근

예시로, 한 말이 27.3% 확률로 e4에, 72.7%는 다른 위치에 존재
이 방식으로 Gurobi 등의 최신 최적화 툴에서 정수계획법(ILP, Integer Linear Programming) 형태로 구현
초기엔 메모리와 시간 한계(약 5만 5천 초 후 메모리 부족)에 부딪힘
탐색 공간을 간소화하기 위해 캐슬링 규칙, 체크 무시, 핀 무시, 앙파상 조건 단순화 등 추가 조치 적용

최적화 및 결론

최종적으로 불필요한 조합 탐색을 차단하는 보조 제약조건 도입 등 모델 개선 후, Gurobi 프로그램을 통해 최적화 완결

305수 → 271.67수 → 218수로 상한 점점 좁힘
대표적인 12개의 218수 가능 포지션만이 도달 가능함을 확인
이 포지션들은 증명 게임(proof game)으로 무리 없이 도달 가능한 합법 포지션임을 증명

또한, 프로모션 없이 최대 144수, 비합법 포지션에서 최대 288수, 도달할 수 없는 합법 포지션에서의 271수 기록도 검증 완료

결과 및 의의

이 연구 결과 덕분에, 체스 엔진 개발자, 압축 알고리듬 연구자는 메모리 설계 등에서 256수 제한으로 충분하다는 확신 가짐
합법적 경로로 218수 이상을 둘 수 있는 포지션은 존재하지 않음이 수학적으로 입증됨

FAQ 요약

체스 게임은 218수보다 더 길 수 있으나, 본 연구는 '한 턴에 가능한 선택지'의 최대 수를 다룸
일부 포지션이 도달 불가능해 보인다면, 이전 수가 잡기로 끝나는 경우 등 여러 경로가 있다고 언급
이 연구 방법은 방대한 조합공간에서 '절대적으로 불가능한 조합'을 신속히 거르는 수학적 오라클 기법을 적용
사용된 코드와 도출된 증거의 수학적 타당성까지 공개해 신뢰성 확보

향후 과제 및 추가 연구 제안

이 기법을 응용해 '최다 잡기 수', '최다 스테일메이트', '최다 체크', '최다 체크메이트', '최다 2수 메이트' 등 다양한 체스 문제에 도전 가능함. 단, 일부 경우는 별도의 창의적 최적화 알고리듬이 필요할 수 있음.

결론

218수가 체스 포지션에서 한 턴에 둘 수 있는 최대 공식 수
실용적 의미에서 체스 소프트웨어, 연구자들은 218(또는 256)에 맞춰 구조 설계 가능
관련 코드 및 최적화 결과는 GitHub에서 공개됨

참고

Nenad Petrović의 218수 포지션, Jenő Bán의 144수(프로모션 없음) 등 증명 게임 및 포지션 링크 포함
자세한 설명, 코드는 Github 저장소에서 확인 가능

▲

GN⁺ 7시간전 [-]

Hacker News 의견

그들이 직접적으로 표현하진 않았지만, 여기서 말하는 건 "이 포지션에서 플레이어가 선택할 수 있는 합법적인 수가 218개임"이라는 의미임
- 이 기사를 그동안 잘못 읽고 있었음에 놀람, 감사합니다. 저는 "어떤 체스 포지션에 도달하는 데 필요한 최대 수가 218개다"라고 이해했음. 그래서 왜 이 기사가 전혀 이해가 안 됐는지 궁금했었음
- 저는 "이 포지션에 도달하려면 게임에서 몇 번의 수가 필요한가?"라고 생각했었음
- 맞음, 기사에서 "possible moves(가능한 수)"라는 문구가 한 번도 나오지 않은 건 정말 이상한 일임. 키워드는 "possible"임. 기사는 계속 "수 있다(have moves)"는 식으로 표현하지만, 일반인에게는 익숙하지 않은 표현임 (체스 용어에선 더 일반적인 표현일 수 있음)
- 감사합니다. 이 기사에 대해 혼란스러웠음, 유일하게 가장 많은 수를 필요로 하는 포지션에 관한 줄 알았음
Lichess를 꼭 칭찬하고 싶음. 환상적인 서비스와 콘텐츠를 무료로 제공하며 Chess.com에서 유료로 제공하는 기능들도 무료로 이용 가능함. 다양한 변형 게임들도 정말 많음
Lichess에서 960이나 Crazyhouse 같은 변형 체스의 플레이 수준은 Chess.com보다 훨씬 높음
- 무료이고, 상업용 서버와 동일한 기능을 제공하며, 오픈소스고 개발자 친화적임. 광고도 없고(무료 계정에도 전혀 광고 없음), 프랑스 법하에 투명한 조직 구조를 가짐
  말 그대로 터무니없이 훌륭함. 가능하다면 후원 추천함
https://lichess.org/@/Tobs40/… 글에서는 작성자가 초기에 복잡한 룰을 일부 제거하고, 필요시(해결한 결과가 해당 규칙을 위반 시) 다시 도입할 의향이 있음을 설명함
흥미로운 점은, 혼합 정수 선형계획(MILP) 솔버가 이미 이러한 처리를 지원함. 기술용어로는 'row generation(행 생성)'이라고 불리며, 이는 대개 이 문제를 행렬 형태로 쓸 때 행이 제약조건, 열이 변수일 때 쓰임
(동적으로) 새로운 행을 추가하는 것은 위반된 경우에만 제약조건을 도입하는 것과 동일함
이 방식은 주로 외판원 문제(Traveling Salesman Problem) 해결에 활용됨
(참고로 위키피디아에는 Column generation이 있지만 row generation은 없음)
- 안녕하세요, Lichess 기사 작성자임
  체스규칙을 완화하거나 생략하는 것은 변수 선택에도 영향을 주었음. 수학 모델링에 들어가기 전, lazy constraints 같은 것을 시도했지만 유의미한 속도 개선이 없었음. 예를 들어 흰색 왕이 체크인지 고려하지 않는 것만으로도 많은 단순화가 일어났음
- 이런 방식은 lazy constraints라고 보통 더 많이 부름 (관련 설명)
- MILP 솔버가 (이 어마어마한 탐색 공간에서) 종료할 수 있을지 정말 궁금함, 제 추측은 불가능하다는 쪽임
솔직히 궁금해서 질문함: Gurobi의 정수계획 솔버가 218보다 좋은 해를 못 찾았으면, 그게 218보다 더 나은 해가 존재하지 않음을 보장하는 것인지? 그리고 이게 수학적 증명과 동등한 것인지 궁금함
(논의의 전제: Gurobi에 버그 없고, 작성자의 문제 정의와 구현에도 버그가 없음)
Gurobi가 국소최대치에 빠져 있을 수 있는 가능성이 있을지, 아니면 정말로 보편적인 최적 해임을 증명한 것인지 궁금함
- Gurobi는 지금까지 찾은 최고의 정수 해 뿐 아니라, 가능한 최적 해의 경계치도 함께 제공함. 이 경계치에는 문제의 선형 완화, 커팅 플레인 등 다양한 기법이 사용됨. 그래서 솔버에 버그 없다면 정말 최적 해임
- 작성자임!
  Gurobi와 제 코드가 의도대로 동작하고, 체스 모델 간소화 과정에서 논리적 오류 없었다면, 제가 한 결과는 "초기 포지션에서 합법적인 수열로 도달 가능한 체스 포지션 중 가능한 합법 수의 최대값이 상하한 모두 218임"을 증명한 것임. Gurobi가 탐색 공간 전체를 경계치로 "이보다 더 좋은 경우는 없음"으로 입증한 셈임
- Gurobi가 구체적으로 어떻게 적용된지는 모르지만, 일반적으로 이러한 조합 최적화 솔버는 변수 할당 어떤 경우에도 더 나은 해를 찾을 수 없음을 보여주는 증명 트리를 만듦. 단순한 경우라면 실제로 그 트리를 직접 확인해 모순 유도를 따라갈 수 있음. 본 기사 사례의 증명 트리는 어마어마하게 클 것으로 예상됨. 원한다면 검토는 가능함
- 이론적으로는 증명이 아니지만, 실제로는 마치 증명과 같음
도달 가능한 체스 포지션 중 218개를 초과하는 수는 없다
"앞으로 둘 수 있는 합법적인 수가 218개 이하다"라고 표현하는 게 훨씬 명확할 것임

약 8.7x10^45개의 도달 가능한 체스 포지션을 모두 확인?
이 수치는 실제로 과대 추정임
https://github.com/tromp/ChessPositionRanking에서 합법적인 체스 포지션 수를 약 4.8x10^44로 더 정확하게 추산함

그 추정값, 그냥 20배 정도 차이 아님? 이런 규모에서는 큰 차이 아닌 것 같음
하나는 "합법적인"이고, 다른 한 쪽은 "전체 문제 공간"임
컴퓨팅 관점에서는 전체 문제 공간이 더 중요함. 왜냐하면 합법적인지 여부를 따지기 전에 모두 "계산"해야 하기 때문임. 합법적인 포지션만 순회하는 간단한 방법은 없음
모두 안녕하세요
지인의 제보로 제 기사가 이곳에서 논의 중임을 알게 되었음
덜 명확한 제목을 선택해 죄송하며, 지금은 명확해졌길 바람. 피드백과 따뜻한 말들에 감사함
비슷한 체스 사실 증명 관련해서도 질문 있다면 답변해 드릴 수 있음 ^^
감사합니다
Tobi
- 그러면 확실히 하자면: 모든 보드 포지션에 대해 선택 가능한 수가 218개를 넘지 않는다는 의미인가? 이게 맞는 이해인가?
도달 가능한 체스 보드를 표현하는 데 필요한 최소 비트 수는 얼마일까?
업데이트: 기사에서는 약 8.7x10^45개의 도달 가능한 체스 포지션이 있다고 나오고, https://github.com/lechmazur/ChessCounter는 이 수를 상한으로 둠
(이건 약 153비트에 해당)
- 대략 4.8x10^44라면 그걸 log2(4.8x10^44)로 계산하면 149비트임
  하지만 효율적으로 디코딩하려면 ChessPositionRanking 프로젝트에서 추천하는 숫자(8726713169886222032347729969256422370854716254)의 log2 올림값으로 153비트가 필요함. ChessCounter는 효율적 디코딩 코드를 제공하지 않음
- 킹은 64개의 타일 어디든 갈 수 있음
  룩/퀸/나이트도 마찬가지지만 체스에서 잡혔을 수 있으니 총 65가지 상태가 각 5개의 말마다 필요함
  비숍은 그 중 절반 타일만 가므로 각 33가지 상태
  폰은 4가지 프로모션, 잡히거나, 경우에 따라 다르지만 대략 20~30개 포지션에서 폰 상태, 전체적으로 폰 하나당 약 290가지
  이렇게 하면 한 색(piece color)에서 보드 상태를 표현하는 데 약 112비트, 반올림하면 양쪽 모두 합쳐 224비트가 필요함
  앙파상(En Passant)과 캐슬링 제한(캐슬링 불가 등)은 반올림하면 추가 비트가 필요 없고, 이는 각 기물의 몇 가지 상태만 더하니 됨
  이게 아마도 고정 길이 보드 표현에서 가장 압축된 형태임
  희소(sparse) 표현이라면, 두 킹이 항상 존재하므로 살아 있는 기물들을 n자리 10진수와 n+2개의 64 비트 숫자로 위치를 나타내고 캐슬링, 앙파상 등은 추가 정보로 약간만 필요함. 대략 기물 절반이 사라진 경우 평균적으로 보드 상태 표현에 약 180비트가 듦
  수내역(move history)도 각 수마다 약 10비트 필요(흑/백 한쌍, 한 Ply는 5비트)하니 18수 정도까지 가능. 이건 평균 체스 게임 길이의 중간 지점보다 다소 짧음
  더 압축하려면 엄청난 크기의 사전을 구현해야 가능해 보임
- 기물 종류 및 색상은 4비트로 표현 가능
  그러니 전체 보드를 고정 길이로 인코딩하면 644=256비트=32바이트
  혹은, 기물만을 위한 가변 길이 표현이라면 각 64칸의 인덱스를 6비트로 하여, 개수10비트만큼 소요
  예시로 초기위치는 32*10=320비트=40바이트임
- 해당 GitHub의 8.7e45 "restricted" 값은 일부 폰 프로모션 패턴을 제한함
  5.68e50 "general"이 진정한 상한이며 모든 가능한 프로모션 허용
b2에 있는 블랙 폰이 다른 기물들의 가능한 수를 상당히 줄이고 있음
그 폰은 단 한 번(옆에 있는 나이트 잡기)만 가능함. 만약 그 폰이 없다면 네 개의 화이트 퀸과 나이트가 b2로 들어갈 수 있음. 그런데 실제로는 블랙 킹이 이미 체크메이트라 이러한 수들이 실제로 존재할 수 없음
그 e5의 퀸을 다른 곳에 놓아 즉시 체크메이트가 되지 않게 하면서 b2 칸을 더 개방하는 게 유혹적임
추신: 그 폰은 스테일메이트(무승부)를 막기 위해 그 자리에 살아남아야 할 것 같음
- b2의 블랙 폰은 White to move(백의 차례) 포지션에서는 움직일 수 없음
  만약 블랙 차례라면, e5의 화이트 퀸에 의해 킹이 묶여 있어서(핀에 걸려) 역시 이동할 수 없음. 만약 핀이 없다면 4번 움직일 수 있음. 언더프로모션도 가능함
- 저도 "블랙 기물이 쓸모 없음"이라는 표현이 헷갈렸음. 퀸 둘이 서로 쳐다보게 할 대신 하나를 블랙으로 바꿔서 둘이 서로 잡아먹는 수를 만들 수도 있을 텐데… 하지만 결국 "오직 한 쪽만 움직일 수 있다"는 점을 깨달았음
- 작성자임
  포지션은 White to move임. 설령 b2 폰이 화이트 퀸에 의해 킹이 핀에 걸리지 않았다 해도, 블랙 폰은 움직일 수 없음
  b2 폰은 블랙 킹을 체크로부터 보호하기 위해 반드시 필요함. 그렇지 않으면 포지션 자체가 합법적이지 않음
  모든 걸 정말 꼼꼼히 점검했으니 안심해도 됨, 화이트 기준 218개를 넘는 수를 만드려는 시도는 불가능했음. 그래도 많은 분들이 제 기사에 관심 가져줘서 놀랍고 감사함, 하하 ^^
- 화이트 차례임. 블랙이 체크된 상태에서 화이트 차례라면 합법적이지 않고, 도달 불가능한 상태임. 이전 블랙 턴에서 합법적으로 만들 수 있는 가능성이 없음
  블랙 폰 중 하나를 화이트 나이트로 바꿔서 수를 늘릴 수 있을 것 같지만 이미 두 나이트 모두 있고, 모든 폰이 프로모션된 상태라 가능하지 않음. (두 폰 모두 바꾸면 블랙이 전 턴에 이 상태에 도달하는 게 불가능해짐)
헷갈림. 근데 271개짜리 모델 이후, 무슨 변경을 하면 최적 솔루션을 얻었는지 궁금함. "이 개선된 모델로..."라고만 적혀 있음
- 작성자임!
  전체 기사 읽어봤는지?
  271이 아니라, 271.666...임 :) 이 수치는 모든 결정(0 또는 1)을 연속값(0.0~1.0 및 그 사이 값)으로 완화(relax)한 모델에서 나옴. 즉, 어떤 말이 0.23만큼 있다고 가정할 수 있음. 특정 수를 둘 수 있는 확률도 0.843 등으로 처리.
  이런 일종의 '블랙 매직'을 쓰면 계산 속도가 훨씬 빨라지고, 실제 있는 수보다 많은 수를 산출할 수 있음.
  그래서 이 방법을 활용해 가능한 나쁜 부분해 부분 공간을 빨리 배제할 수 있음. 이런 테크닉 없으면, 전체 탐색 공간을 전수조사하는 건 불가능함
제가 뭔가 놓치고 있는지요, 아니면 초반에 제시된 포지션 자체가 실제로는 도달할 수 없는 상태 아닌가요? 화이트 차례인데, 블랙 폰들이 시작 위치에 있고 킹은 인접한 빈칸도 없으며, 기물과 폰들에 갇혀 있어서 이 포지션에 도달할 수 없어 보임
- 해당 포지션에서 실제로 도달 가능하다는 증명이 여기 있음: https://lichess.org/study/PLtuv3v5/zWPNxbSA
  참고로, 블랙 폰들이 시작 위치에 있다고 오해하신 것 같음. 실제로는 블랙 폰이 보드 반대편까지 이동한 것임(화이트 진영)
- 블랙 폰은 화이트 진영(1~2번째 랭크)에 있음

답변달기