게임이 풀렸다는 말의 뜻
게임이 풀렸다는 것은 시작 위치에서 두 사람이 모두 완벽하게 두었을 때의 결과가 알려져 있다는 뜻이에요. 보통 세 단계가 있어요. 「초약한」 해법에서는 누가 이기는지, 또는 비기는지만 알고 전략은 몰라요. 「약한」 해법에서는 처음부터 그 결과를 보장하는 전략도 알아요. 「강한」 해법에서는 가능한 모든 위치에서의 최선의 결과를 알아요.
7열 6행의 기본 판에서 사목 게임의 결과는 분명해요. 완벽하게 두면 먼저 두는 사람이 이겨요. 그렇다고 실제로 항상 이긴다는 뜻은 아니에요. 그러려면 매 턴 정확한 수를 찾아야 하는데, 사람 사이의 대국은 실수로 가득하니까요.
누가, 언제 풀었나
이 이야기에는 두 주인공이 있어요. 두 사람은 1988년 10월에 서로 독립적으로 같은 결론에 이르렀어요. 첫 번째는 제임스 도 앨런으로, 1988년 10월 1일에 rec.games.programmer 토론 그룹에 올린 글로 해법을 발표했어요. 15일 뒤인 10월 16일에 네덜란드 연구자 빅터 알리스가 자신의 해법을 발표했어요. 암스테르담 자유대학교의 논문 「A Knowledge-based Approach of Connect-Four」에 설명되어 있어요.
알리스의 방법은 「지식 기반」이었어요. 모든 위치를 살펴보는 대신 어떤 칸을 차지하는 게 좋은지, 어떤 위협이 중요한지 같은 전략 규칙을 만들고 이를 탐색과 결합해서 먼저 두는 사람이 승리를 강제할 수 있음을 증명했어요. 나중에는 위치 데이터베이스와 강력한 컴퓨터를 써서 무차별 대입으로도 같은 결과에 이르렀어요. 프로그래머 존 트롬프는 돌이 8개 놓인 모든 위치의 데이터베이스를 만들었고, 그것이 출발점이 됐어요. 두 길은 서로 일치해요.
오프닝의 핵심: 가운데 열
아무 첫 수나 되는 건 아니에요. 결과는 먼저 두는 사람이 시작하는 열에 따라 달라져요.
| 첫 수 | 완벽하게 두었을 때의 결과 |
|---|---|
| 가운데 열(4열) | 먼저 두는 사람이 이겨요 |
| 가운데 옆 열(3열과 5열) | 무승부 |
| 바깥 열(1, 2, 6, 7열) | 나중에 두는 사람이 이겨요 |
「먼저 두는 사람이 이긴다」는 실전에서 무슨 뜻일까
이론상 먼저 두는 사람이 이긴다고 해도, 상대가 잘 두면 아무것도 보장되지 않아요. 이점은 현실이지만 정확함이 필요해요. 그래도 먼저 두면 구체적인 두 가지를 얻어요. 첫째는 주도권이에요. 먼저 두고, 상대는 대개 내 위협에 대응해야 해요. 둘째는 홀짝이에요. 플레이어들 사이에 널리 알려진 실용 규칙이에요. 판이 6행(짝수)이고 번갈아 두기 때문에 홀수 행(아래에서부터 세어 1, 3, 5행)의 칸은 먼저 시작한 사람에게, 짝수 행의 칸은 나중에 두는 사람에게 돌아가는 경향이 있어요. 그래서 홀수 행의 위협은 대개 먼저 두는 사람에게 더 값져요.
중앙이 그렇게 가치 있는 이유
가운데 열의 디스크는 다른 어떤 열보다 더 많은 가능한 줄에 참여해요. 가운데에서는 가로, 세로, 두 대각선으로 사목을 많은 조합으로 만들 수 있어요. 가장자리의 디스크는 거의 한두 방향에만 쓸모가 있어요. 그래서 강한 프로그램은 중앙에서 바깥쪽으로 수를 정렬하고, 오프닝 책도 4열에서 시작해요.
내가 쓸 실용 규칙은 간단해요. 분명히 더 좋은 수가 없다면 가운데에 가까운 열을 고르세요. 상대가 먼저 가운데를 차지해도 당황하지 마세요. 옆 열도 여전히 아주 좋아요.
사람을 상대로 더 많이 이기는 요령
- 먼저 두면 가운데 열에서 여세요. 완벽하게 두었을 때 이기는 유일한 오프닝이에요.
- 이중 위협을 노리세요. 마무리 칸이 열려 있는 세 개짜리 줄 두 개를 동시에 만드는 거예요. 상대는 하나만 막을 수 있어요. 사람을 상대로 가장 흔하게 이기는 방법이에요.
- 「공중」에 있는 위협을 생각하세요. 아래에 디스크가 하나 모자라서 마지막 칸에 아직 닿을 수 없는 세 개짜리 줄이에요. 그 칸이 홀짝상 나에게 유리한 행에 있다면, 상대는 언젠가 그 아래에 두어서 나에게 칸을 내줘야 해요.
- 디스크를 떨어뜨리기 전에 바로 위 칸이 어떻게 되는지 보세요. 상대에게 줄을 완성할 칸을 선물하면 진 거예요.
- 양쪽이 열린 세 개짜리 줄은 만들어지기 전에 막으세요. 확실한 패배예요. 한 턴 앞서 예측하세요.
- 마지막에는 누가 안전한 수가 떨어지는지가 중요해요. 위험 없이 둘 수 있는 열을 아껴 두세요.
- 나중에 두는 쪽이라면 짝수 행의 칸을 노리고, 홀수 행의 모든 위협을 서두르지 말고 막으세요. 무승부나 상대의 실수로 가는 가장 좋은 길이에요.
그럼 컴퓨터는 질 수 없나요?
처음부터 완벽하게 두고 먼저 시작하는 프로그램은 절대 지지 않아요. 하지만 그건 게임의 이론적 해법에 대한 이야기이지 모든 프로그램에 대한 이야기가 아니에요. 시작 위치에서 대국 전체를 푸는 데는 엄청난 계산이 필요하고, 한 수에 겨우 1.5초 걸리는 브라우저에서는 이루어지지 않아요.
그래서 우리 사목 게임의 「무적」 난이도는 있는 그대로 소개해요. 가장 강한 난이도예요. 반복 심화를 쓰는 알파-베타 탐색, 이미 본 위치를 기억하는 표, 중앙에서 시작하는 열 순서, 아주 짧은 오프닝 책을 사용해요. 많은 수를 미리 분석해서 실수를 거의 놓치지 않지만 이길 수 없다고 약속하지는 않아요. 이긴다면 진짜로 이긴 거예요.
연습하는 방법
실력을 키우는 좋은 방법은 「어려움」 난이도의 컴퓨터와 하고 그다음 「무적」과 하면서 누가 먼저 둘지 번갈아 하는 거예요. 졌을 때는 대국을 복기하고 어느 턴에 이중 위협이 나타났는지 찾아보세요. 거의 항상 앞선 조용한 수 하나까지 거슬러 올라갈 수 있어요. 더 큰 판이나 팝아웃 모드 같은 변형도 해 보면 좋아요. 다르게 생각하게 하고 판을 보는 눈을 길러 줘요.
자주 묻는 질문
사목 게임이 풀렸다는 걸 누가 증명했나요?
제임스 도 앨런이 1988년 10월 1일에 발표했고, 독립적으로 빅터 알리스가 1988년 10월 16일에 자신의 해법을 발표했어요. 그 뒤 무차별 대입으로 확인되기도 했어요.
완벽하게 두면 사목 게임에서 누가 이기나요?
첫 디스크를 기본 7×6 판의 가운데 열에 두는 먼저 두는 사람이에요. 가운데 옆 열에서 시작하면 이론상 무승부이고, 바깥쪽 네 열 중 하나에서 시작하면 나중에 두는 사람이 이겨요.
먼저 두는 사람이 항상 이긴다는 뜻인가요?
아니요. 아무도 실수하지 않을 때의 결과예요. 실제로는 매 턴 계속 정확해야 하고 사람은 실수해요. 먼저 두는 것은 이점이지 보장이 아니에요.
다른 크기의 판도 풀렸나요?
많은 판이 풀렸지만 결과는 크기에 따라 달라요. 예를 들어 존 트롬프는 8×8 판이 나중에 두는 사람의 승리라고 보고했어요. 이 글은 7열 6행의 기본 판만 다뤄요.
「무적」 난이도는 절대 지지 않나요?
그렇게 약속하지는 않아요. 우리가 제공하는 가장 강한 난이도로, 깊은 탐색과 한 수당 많은 계산을 쓰지만 주어진 시간 안에 대국 전체를 풀지는 않아요. 기본 7×6 판에만 있어요.
사목 게임의 위치는 몇 개인가요?
7×6 판에서 합법적인 위치 4,531,985,219,092개를 셌고, 이 수치는 2008년에 스테판 에델캠프와 페터 키스만이 독립적으로 확인했어요.