헥스 규칙과 이기는 법 — 무승부가 없는 보드게임

헥스는 11×11 육각 판에 돌을 번갈아 놓아, 검은 돌은 위아래 변을 붉은 돌은 좌우 변을 먼저 이으면 이기는 보드게임입니다. 규칙이 두 줄입니다 — 빈 칸에 놓는다, 자기 색 두 변이 이어지면 이긴다. 잡는 것도 물러나는 것도 지나가는 것도 없습니다.

무승부가 존재할 수 없습니다

이 게임에는 비기는 자리가 없습니다. 판이 다 차면 반드시 한쪽이 이어져 있다는 것이 증명돼 있습니다 — 검은 돌이 위아래를 못 이었다면, 그 길을 막고 있는 붉은 돌이 좌우로 이어져 있을 수밖에 없습니다. 브라우어 부동점 정리와 동치인 성질로도 알려져 있습니다.

그래서 이 게임에서는 막는 것과 잇는 것이 같은 일입니다. 상대의 길을 끊는 수가 곧 내 길을 잇는 수입니다. 오목처럼 공격과 수비를 나눠 생각하면 오히려 헷갈립니다.

이웃은 여섯 방향입니다

육각 판을 마름모로 눕혀 놓았기 때문에 좌우 두 칸과 위 두 칸, 아래 두 칸이 이웃입니다. 화면의 가로줄에서 바로 옆은 이웃이지만, 위아래로는 한 칸이 어긋나 있습니다. 처음에는 이 어긋남 때문에 이어진 줄이 끊겨 보이는데, 몇 판만 두면 눈에 익습니다.

다리 — 한 칸 띄워 두는 것이 붙여 두는 것보다 강합니다

내 돌 두 개가 한 칸을 비워 두고 비스듬히 놓여 있고, 그 사이를 이을 수 있는 빈 칸이 두 개면 상대는 그 연결을 끊을 수 없습니다. 하나를 막으면 다른 하나로 이으면 되기 때문입니다. 이렇게 사실상 이어진 관계를 다리라고 부릅니다.

• 다리는 끊기지 않으므로 상대가 그 칸에 두면 나는 남은 칸에 두기만 하면 됩니다 — 급하게 메우지 말고 다른 곳을 먼저 두는 편이 낫습니다.
• 다리를 여러 개 이어 붙이면 사다리가 됩니다. 판 한쪽 끝에서 다른 끝까지 다리로만 이어 두면 그 판은 이미 이긴 것입니다.
• 변 쪽에서도 같습니다. 변에서 한 칸 떨어진 자리는 변과 두 칸으로 이어지므로 변에 딱 붙여 둘 이유가 없습니다.

짧은 대각선을 잡습니다

판의 중앙을 지나는 짧은 대각선 — 내가 이어야 하는 두 변을 최단으로 잇는 선 — 위의 칸들이 가장 값이 큽니다. 첫 수를 판 가운데에 두는 것이 정석인 이유이고, 상대의 짧은 대각선을 가로지르는 자리가 곧 막는 자리입니다.

AI는 평가하지 않고 끝까지 채워 봅니다

헥스에서 좋은 모양을 점수로 적는 일은 사람도 어렵습니다. 그래서 위의 성질을 대신 씁니다 — 남은 칸을 무작위로 다 채우면 반드시 승자가 나오므로, 한 수를 두어 보고 나머지를 무작위로 여러 번 채워 이기는 비율이 높은 수를 고릅니다. 평가 함수 없이도 꽤 둡니다.

• 쉬움 — 굴려 보지 않고 무작위로 둡니다. 다만 한 수로 이기는 자리와 상대가 이기는 자리는 봅니다.
• 보통 — 빈 칸마다 20판씩 굴려 봅니다.
• 어려움 — 빈 칸마다 140판씩 굴려 봅니다. 어려움과 쉬움을 붙여 보니 162판에서 어려움이 전승했습니다.

선공이 유리하지만 생각보다 적습니다

같은 난이도끼리 329판을 두어 보니 선공이 169판(51.4%), 후공이 160판을 이겼습니다. 무승부는 한 판도 없었습니다 — 규칙대로 구현했다면 나올 수 없는 값입니다. 판은 평균 65.7수에 끝났는데, 121칸이니 절반 조금 넘게 채우면 승부가 갈린다는 뜻입니다.

이론적으로는 선공이 반드시 이기는 게임이라고 알려져 있습니다. 다만 그 이기는 수를 아는 것은 다른 문제라서, 실제로 두면 이 정도 차이로 나옵니다.