두 합치기 게임, 하나의 질문. 둘 중 어느 하나라도 흠 없이 플레이할 수 있을까? 답은 보드의 구석, 끝내 나타나지 않는 상대, 그리고 지수 열일곱 층 높이의 수를 거쳐 갑니다.
영어로 집필하고 편집했습니다. 이 한국어 판은 기계 번역으로 만들어졌으며, 정확성이 중요한 경우에는 영어 원문이 기준이 됩니다. 영어 원문 읽기 →
모두가 아는 게임부터 시작해 봅시다. 네 방향, 4×4 격자, 닿으면 두 배가 되는 타일로 이루어진 2048은 엄밀히 말해 풀리지 않았습니다. 이 게임을 완벽하게 플레이하는 알고리즘을 작성한 사람은 아무도 없습니다. 우리가 가진 것은 매우 강력한 근사치입니다. 여덟 수가량 앞을 내다보고 빈칸, 한쪽 가장자리에 고정된 큰 타일, 매끄러움 같은 몇 가지 손으로 조정한 휴리스틱으로 각 보드에 점수를 매기는 expectimax 탐색은 3분의 1이 넘는 게임에서 32768 타일에 도달하며, 1 공개된 가장 강한 엔진은 몇 퍼센트의 확률로 65536 타일에 닿습니다. 2 m×n 보드로 일반화하면, 목표 타일에 도달할 수 있는지를 판정하는 것만으로도 NP-난해입니다. 3 강하다는 것은 풀렸다는 것과 같지 않습니다.
타일 하나는 얼마나 높이 올라갈 수 있을까요? 열여섯 칸에서 그 답은 작고 우아한 셈 한 조각입니다. 보드를 내림차순 계단으로 늘어놓아 보십시오. 65536, 32768, 16384, 그리고 쭉 내려가 외톨이 2까지. 각 타일은 이웃보다 정확히 2의 거듭제곱 한 단계 아래이므로, 서로 다른 열여섯 개의 거듭제곱 21부터 216까지가 보드를 빈틈없이 채우고, 꼭대기에는 65536 = 216이 앉습니다. 칸 하나당 지수 하나입니다. 이것이 게임이 오직 2만 건네줄 때의 천장입니다. 하지만 2048은 열 번에 한 번 4를 낳으며, 절묘한 때에 나온 4 하나가 열일곱 번째 지수를 몰래 들여와 진짜 최댓값을 131072 = 217로 끌어올립니다. 타일 열일곱 개 분량의 거듭제곱이 열여섯 칸에 담기는 것입니다. 4 이를 만들어 낸 사람은 없으며, 몇몇 AI가 그 언저리를 스쳤을 뿐입니다.
왜 이런 보드는 가장 큰 타일을 구석에 밀어 넣는 것을 보상할까요? 가운데 있는 타일은 네 방향으로 밀릴 수 있어서, 짝지어지고 싶은 타일들과 자꾸 떨어지게 됩니다. 구석 타일은 두 벽에 닿아 있습니다. 이미 붙어 있는 벽 쪽으로 밀어서는 움직일 수 없으므로, 그 벽에서 멀어지는 쪽으로 밀지만 않으면 다른 모든 것이 그 주위에 정리되는 동안 제자리에 머뭅니다. 나머지를 단조로운 뱀 모양으로 잇고, 가장 큰 것을 구석에 두어 내림차순으로 이리저리 접어 나가면, 한 번의 밀기로 연쇄 합치기를 일으킬 수 있습니다. 1 이것이 일반 사람들의 플레이를 지배하는 휴리스틱이며, AI에게 스스로 가중치를 조정하게 하면 AI가 다시 발견해 내는 것도 거의 이것입니다.
무작위로 타일이 생기는 합치기 게임에는 상대가 없고, 날씨만 있을 뿐입니다. 그것을 “푼다”는 것은 정신을 이기는 것이 아니라 평균적으로 주사위를 이기는 것입니다.
이제 보드를 3차원으로 기울여 봅시다. 3927은 2048의 정육면체 사촌입니다. 27칸짜리 3×3×3 격자, 네 방향 대신 여섯 방향의 밀기, 그리고 셋씩 융합하는 타일(3에서 9, 27, 81로)이 있어, 2048이 2진법인 자리에 3진법이 들어섭니다. 5 구석 쌓기는 추가된 차원에서도 살아남을까요? 정육면체에는 구석이 여덟 개 있고, 이제 구석 칸은 두 면이 아니라 세 면에 닿습니다. 세 벽이 동시에 붙잡아 주니 한층 더 안정적이어야 하지만, 여섯 방향은 보드가 여러분의 구조를 흔들어 풀어 버릴 방법도 더 많이 줍니다. 뱀은 세 층을 모두 꿰는 접힌 경로가 됩니다. 제가 찾아본 한, 이 유비가 실제로 성립하는지 밝혀낸 사람은 없습니다. 이것은 측정이 아니라 추론입니다.
그렇다면 천장은? 칸당 지수 하나라는 규칙은 느슨한 상한으로 327 ≈ 7.6조를 시사할 것입니다. 하지만 이 유비는 심하게 해어집니다. 2048의 추가 지수는 운 좋은 4에서 나왔지만, 3927은 언제나 가장 작은 타일인 맨 3만 낳으므로 보너스가 없습니다. 더 나쁜 것은, 세 개 합치기에는 한 줄로 늘어선 타일 세 개가 필요한데 3×3×3 정육면체의 모든 행, 열, 기둥은 정확히 세 칸 길이라서 모든 합치기가 줄 하나를 통째로 소모한다는 점입니다. 이 제약은 평면 게임의 어떤 것보다 훨씬 세게 물어뜯으며, 실제 최댓값을 327보다 한참 아래로 끌어내릴 것이 거의 확실합니다. 그 진짜 수가 얼마인지 계산된 곳을 저는 어디에서도 찾지 못했습니다. (분명히 추론으로 표시한 내용이며, 위의 메커니즘은 게임의 설계 문서에서 확인한 것입니다.)
“완벽한 플레이”를 미끄러운 개념으로 만드는 미묘한 점이 여기 있습니다. 무작위로 타일이 생기는 합치기 게임은 1인 확률 게임으로, 결투가 아니라 주사위를 상대로 하는 혼자 놀이입니다. 여러분을 망치려고 최악의 타일을 고르는 존재는 없으며, 무심한 난수 생성기가 있을 뿐입니다. 그러므로 최적 플레이의 올바른 개념은 expectimax, 즉 타일 생성 분포에 대한 기댓값 결과를 최대화하는 것입니다. 그것은 단연코 minimax가 아닙니다. minimax는 적수를 전제하며, 실제로 적수에게 모든 타일을 놓게 하면(“악마의 2048”) 게임은 강제로 질 수도 있는 더 잔혹한 것이 됩니다. 주사위는 원리상 어떤 순서든 내줄 수 있으므로, 특정 타일을 보장하는 전략은 아예 존재하지 않을 수도 있습니다. 따라서 “완벽한 전략이 있는가?”에 대한 정직한 답은, 확률 게임에서 정의할 수 있는 최선조차 평균적으로 최선인 전략뿐이며, 그것을 정확히 계산하는 일은 2048에서는 손이 닿지 않고 6 3927에서는 완전히 열려 있는 문제라는 것입니다.