판 아래의 힌트와 자동 플레이 버튼은 정해진 조언을 돌려주는 것이 아닙니다. 지금 이 판 자체에 대해 브라우저 안에서 진짜 탐색을 하고, 가장 평가가 높은 수를 돌려줍니다. 힌트는 판 위에 화살표를 보여 주고, 자동 플레이는 게임이 끝날 때까지 그 수를 계속 둡니다. 서버로는 아무것도 보내지 않습니다.
빈 판에서 시작해 이 탐색에만 맡기면 91.4%의 판에서 2048 타일에 도달합니다. 여기서는 어떻게 거기까지 가는지 설명합니다.
게임 트리를 다루는 대표적인 도구는 미니맥스입니다. 상대가 최악의 응수를 고른다고 가정하고 그에 대비해 계획합니다. 하지만 2048에는 상대가 없습니다. 있는 것은 무작위로 나타나는 타일이고, 이 차이는 아주 큰 의미를 가집니다.
미니맥스로 생각하는 플레이어는 새 타일을 악의적인 것으로 보고, 4가 반드시 최악의 칸에 나타난다고 가정합니다. 그 결과 서른 번에 한 번 일어날까 말까 한 판에 대비하느라 계산을 모두 써 버리고, 의심 많고 수비에 치우친 플레이를 하게 됩니다. 익스펙티맥스는 대신 실제로 일어날 수 있는 모든 출현을 각각의 가능성으로 가중해 평균을 냅니다. 악몽이 아니라 확률에 따라 두는 것이고, 무작위에 악의가 없는 이상 이것이 올바른 모델입니다.
그래서 탐색은 두 종류의 노드를 번갈아 거칩니다. 플레이어 노드에서는 네 방향을 모두 시도해 가장 좋은 결과를 남깁니다. 확률 노드에서는 비어 있는 모든 칸에 가중치 0.9로 2를, 가중치 0.1로 4를 놓고, 각각을 평가해 평균을 냅니다. 게임 자체가 타일을 내놓을 때와 같은 90대 10 비율입니다.
게임이 끝날 때까지 트리를 탐색할 수는 없으므로, 솔버는 탐색의 맨 아래에서 판을 네 가지 지표로 채점하고 다음 가중치로 더합니다.
| 항목 | 가중치 | 측정하는 것 |
|---|---|---|
| 빈칸 | 2.7 | 비어 있는 칸의 수 그 자체. 단연 가장 무거운 항목입니다. 칸이 바닥나는 것이 지는 원인이기 때문입니다. |
| 단조성 | 1 | 행이나 열을 따라 숫자가 들쭉날쭉하지 않고 한 방향으로 고르게 커지는지 여부. |
| 구석 | 1 | 가장 큰 타일이 네 구석 중 하나에 있을 때 그 크기에 따라 더해지는 보너스. |
| 매끄러움 | 0.1 | 크기가 크게 차이 나는 타일끼리 이웃해 있을 때의 감점. 512 옆의 2는 결코 합쳐질 수 없고 짐일 뿐입니다. |
네 가지 중 세 가지는 사람들이 흔히 하는 조언을 계산식으로 옮긴 것에 불과합니다. 칸을 비워 두라, 정렬을 지키라, 큰 타일을 구석에 두라. 그 조언을 판단으로 바꾸는 것이 가중치입니다. 탐색은 빈칸이 충분히 늘어난다면 구석의 위치가 조금 나빠지는 것을 기꺼이 받아들입니다. 그리고 사람은 대개 이 거래를 거꾸로 잘못합니다.
모든 항목은 타일의 숫자 그 자체가 아니라 밑이 2인 로그를 씁니다. 그래서 2에서 4로의 차이가 1024에서 2048로의 차이와 똑같이 계산됩니다. 그렇지 않으면 판에서 가장 큰 타일이 다른 모든 것을 묻어 버립니다.
확률 노드는 빈칸 하나마다, 그것도 두 갈래씩 가지를 칩니다. 빈칸이 열 개인 넓은 판이라면 단계마다 가지가 스무 개이고, 빈칸이 세 개뿐인 꽉 찬 판이라면 여섯 개입니다. 둘을 같은 깊이까지 탐색하는 것은 앞뒤가 뒤바뀐 일입니다. 넓은 판은 살아남기는 쉬운데 탐색에는 품이 들고, 꽉 찬 판은 그 반대이기 때문입니다.
그래서 깊이는 판에 맞춰 바뀝니다.
| 빈칸 | 탐색 깊이 |
|---|---|
| 7개 이상 | 2수 앞까지 |
| 4~6개 | 3수 앞까지 |
| 3개 이하 | 4수 앞까지 |
넓은 판은 가볍게 훑고, 비좁아지면 훨씬 신중해진다. 강한 플레이어의 감각을 정확하게 옮겨 놓은 것입니다. 덕분에 게임의 어느 단계에서든 클릭한 뒤 화살표가 나오기까지 기다리는 시간이 쾌적한 범위에 머뭅니다.
500판의 완전한 게임에서 2048에 도달한 판은 91.4%, 점수 중앙값은 37,004점, 게임 길이의 중앙값은 1,943수였습니다. 비교 대상까지 담은 전체 결과에서 이 숫자들을 맥락 속에서 확인할 수 있습니다.
이것이 최첨단 2048 봇이 아니라는 점은 분명히 해 둘 가치가 있습니다. 공개된 솔버들은 비트보드 표현, 미리 계산한 이동표, 전치표 캐시를 써서 훨씬 깊이 탐색하고 32768에 도달합니다. 이 솔버는 브라우저의 메인 스레드에서 평범한 배열로 돌아가고, 수와 수 사이에 캐시를 두지 않으며, 페이지가 버벅이지 않도록 4수 앞까지로 제한되어 있습니다. 기록을 세우려는 것이 아니라 「여기서 뭘 둬야 하지?」라는 질문에 순식간처럼 느껴지는 속도로 답하려고 만든 것입니다.
힌트를 가장 잘 쓰는 법은 그것을 따르는 게 아닙니다. 먼저 자신의 수를 정하고, 그다음에 힌트를 누르세요. 화살표가 일치했다면 새로 배울 것은 없습니다. 하지만 어긋났다면 자신이 잘못 읽고 있는 판을 찾아낸 것이고, 실력이 느는 씨앗은 바로 거기에 있습니다.
자동 플레이는 구원 투수보다는 시범 경기로 쓰는 편이 더 유용합니다. 스스로 어렵다고 느낀 국면에서 돌려 보고, 어느 방향을 지키는지, 어떤 합체를 일부러 하지 않는지 지켜보세요. 화살표 키를 누르면 언제든 바로 조작을 되찾을 수 있습니다.
솔버는 의존성 없는 JavaScript 약 250줄로, /js/ai.js에 평범한 파일로 놓여 있습니다. 여기 적은 내용을 확인하고 싶다면 브라우저의 소스 보기로 그대로 읽을 수 있습니다.
이제 직접 해볼까요?
2048 플레이하기