헥스는 329판을 두어도 한 번도 비기지 않습니다 — 무승부가 0%인 게임 넷을 비교했습니다
핵심 요약 — 헥스 AI 대국 329판에서 무승부가 0건이었고, 끝나지 않은 판도 0건이었습니다. 헥스는 판이 다 차면 반드시 한쪽이 이어져 있다는 것이 증명된 게임이라 비기는 것이 규칙상 불가능합니다. 그런데 우리 사이트에서 무승부 0%인 게임은 넷이고, 이유가 전부 다릅니다. 반대편 끝에는 틱택토가 있습니다 — 228판 중 158판(69.3%)이 무승부였습니다.
헥스를 새로 붙이면서 AI끼리 붙여 봤습니다. 무승부가 한 번도 안 나왔습니다. 예상한 결과였지만, 그 김에 다른 게임들의 무승부 비율도 함께 재 보니 더 재미있는 그림이 나왔습니다.
헥스에서 잰 것
같은 난이도끼리 240초 동안 붙였습니다.
| 값 | |
|---|---|
| 돈 판 수 | 329판 |
| 무승부 | 0판 (0.0%) |
| 끝나지 않은 판 | 0판 |
| 평균 길이 | 65.7수 |
| 선공 승률 | 51.4% |
두 번째 줄과 세 번째 줄을 함께 봐야 합니다. 무승부가 0인 것과 판이 다 끝난 것이 동시에 성립해야 의미가 있습니다.
무승부 0%가 네 게임이나 됩니다
여기서 처음 생각과 달라졌습니다. 헥스만 0%일 줄 알았는데 아니었습니다.
| 게임 | 판 수 | 무승부 | 미완 |
|---|---|---|---|
| 헥스 | 329 | 0.0% | 0 |
| 윷놀이 | 58,339 | 0.0% | 0 |
| 다이아몬드 게임 | 7,529 | 0.0% | 5 |
| 따내기 바둑 | 3,624 | 0.0% | 0 |
| 구슬 삼목 | 321 | 0.0% | 42 |
| 사목 | 619 | 2.3% | 0 |
| 오델로 | 521 | 2.5% | 0 |
| 만칼라 | 2,003 | 7.4% | 0 |
| 선 잇기 | 24,584 | 8.5% | 0 |
| 틱택토 | 228 | 69.3% | 0 |
0%가 다섯 줄이지만 이유가 세 갈래입니다.
하나. 먼저 도착하면 끝나는 경주 — 윷놀이와 다이아몬드 게임입니다. 말을 먼저 다 옮긴 쪽이 이깁니다. 동시에 도착할 방법이 없으니 비길 자리가 없습니다. 따내기 바둑도 같은 결입니다 — 정해진 수를 먼저 따낸 쪽이 이깁니다.
둘. 비길 수가 없다는 것이 증명된 게임 — 헥스입니다. 아래에 따로 씁니다.
셋. 규칙에는 무승부가 있는데 안 나온 것 — 구슬 삼목입니다. 여기서 미완 42판을 봐야 합니다. 321판 중 42판(13.1%)이 최대 수에 걸려 끝나지 않았습니다. 서로 밀을 열었다 닫으며 버티느라 판이 끝나지 않은 것이지, 비길 수 없어서 0%인 것이 아닙니다. 같은 0%인데 성격이 정반대입니다.
헥스가 비길 수 없는 이유
판을 끝까지 채운다고 해 봅시다. 흑은 위아래를, 백은 좌우를 이으려 합니다.
흑이 위아래를 못 이었다면, 흑의 돌만으로는 위에서 아래로 가는 길이 없다는 뜻입니다. 그러면 그 길을 막고 있는 무언가가 판을 가로로 가로질러 있어야 합니다. 그 막이 곧 백의 돌로 된 좌우 연결입니다.
거꾸로도 같습니다. 그래서 둘 중 정확히 하나는 반드시 이어져 있습니다. 둘 다 이어질 수도 없습니다 — 위아래 길과 좌우 길은 어디선가 반드시 만나는데, 한 칸이 두 색일 수는 없기 때문입니다.
이건 육각 판이라서 성립합니다. 사각 판이었다면 대각선으로 스쳐 지나갈 수 있어 둘 다 끊기는 배치가 생깁니다.
규칙 구현을 검사할 때도 이 성질을 씁니다. 판을 무작위로 가득 채운 뒤 승자를 물어봐서 한 번이라도 "무승부"가 나오면 이웃 관계나 승리 판정이 틀린 것입니다. 500판을 채워 확인하는 검사가 테스트에 들어 있습니다.
그래서 두는 법이 달라집니다
비길 수 없다는 것은 비기려고 두는 수가 존재하지 않는다는 뜻입니다.
오목이나 사목에서는 불리해지면 판을 막아 비기는 쪽으로 끌고 갈 수 있습니다. 헥스에는 그 선택지가 없습니다. 상대의 길을 막는 수는 동시에 내 길을 잇는 수가 됩니다 — 상대를 가로막으려면 내 색으로 가로줄을 만들어야 하고, 그것이 곧 내 연결이기 때문입니다.
공격과 수비가 같은 수라는 것, 이게 헥스가 규칙 두 줄짜리 게임인데도 안 질리는 이유입니다.
선공은 51.4%였습니다
이론상 헥스는 선공이 이깁니다. 증명 방식이 재미있는데, "후공에게 이기는 방법이 있다고 치면 선공이 그 방법을 훔쳐 쓸 수 있으므로 모순"이라는 식입니다. 다만 이 증명은 이긴다는 것만 알려 주고 어떻게 이기는지는 알려 주지 않습니다.
우리 AI는 선공 승률이 51.4%(169승 160패)였습니다. 이론값(100%)과 한참 떨어져 있습니다.
이 차이가 곧 AI가 최선에서 얼마나 떨어져 있는지입니다. 헥스 AI는 판을 평가하는 함수를 쓰지 않고, 남은 칸을 무작위로 끝까지 채워 보고 이기는 비율이 높은 자리를 고릅니다. 무승부가 없다는 성질 덕분에 이 방법이 통합니다 — 끝까지 채우면 언제나 승자가 나오니 "비겼을 때"를 다룰 필요가 없습니다. 오목이었다면 이 방법이 안 통합니다.
반대편 끝, 틱택토
228판 중 158판이 무승부였습니다. 69.3%입니다.
틱택토는 게임 트리가 작아 AI가 모든 수를 다 읽습니다. 그래서 어려움끼리 붙이면 서로 최선을 다하고, 서로 최선을 다한 틱택토는 무승부입니다. 남은 30.7%는 난이도가 낮은 쪽이 일부러 두는 헛수에서 나온 것입니다.
같은 "완전히 읽히는 게임"인데 결론이 정반대인 것이 흥미롭습니다. 틱택토는 최선끼리 비기고, 헥스는 최선끼리 두면 선공이 이깁니다. 그리고 헥스는 판이 너무 커서 그 최선을 아무도 모릅니다.
재현 방법. 이 글의 숫자는 npx tsx scripts/sim-board.ts 240으로 나온 값입니다. 판 수가 게임마다 다른 것은 시간으로 끊기 때문입니다 — 한 판의 값이 게임마다 백 배 넘게 갈려서, 같은 판 수를 주면 싼 게임은 남아돌고 비싼 게임은 끝나지 않습니다. 그래서 실제로 돈 판 수를 함께 적었습니다.