🤖 AI

Strongly Solving 2048 4x3

본 논문은 1.15 조 개가 넘는 도달 가능한 상태라는 방대한 상태 공간을 관리하기 위해 연령 기반 분할 기법을 활용하여 확률적 게임 2048 의 4x3 변형에 대한 강한 해를 제시하며, 최적의 기대 점수를 약 50,724.26 으로 결정합니다.

원저자: Tomoyuki Kaneko, Shuhei Yamashita

게시일 2026-05-26

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Tomoyuki Kaneko, Shuhei Yamashita

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

2048이라는 인기 있는 퍼즐 게임을 상상해 보세요. 이 게임은 재료를 (타일) 결합하여 점점 더 큰 요리를 만들어 내는 거대하고 혼란스러운 주방과 같습니다. 표준 버전에서는 4x4 격자 (16 개 칸) 를 사용하지만, 이 논문에서 저자들은 주방을 **4x3 격자 (12 개 칸)**로 축소하여 더 빡빡하고 혼잡한 도전 과제로 만들었습니다.

다음은 그들이 무엇을 했는지, 어떻게 했는지, 그리고 무엇을 발견했는지를 일상적인 비유를 통해 간단히 정리한 내용입니다.

1. 큰 도전: 읽기엔 너무 거대한 도서관

저자들은 이 게임의 축소판을 '완벽하게 해결 (strongly solve)'하고자 했습니다. 게임 용어로 말하자면, 그들은 단순히 시작 단계에서의 최선의 수를 알고 싶은 것이 아니라, 게임이 도달할 수 있는 모든 가능한 상황에서의 완벽한 수를 알고 싶어 했습니다.

게임의 가능한 상황을 도서관으로 생각해 보세요.

원래의 3x3 버전 (Mini2048) 은 약 48,000 권의 책이 있는 작은 책장처럼 보였습니다. 읽기 쉽죠.
이 새로운 4x3 버전은 **1 조 1,500 억 권 이상의 책 (상태)**과 거의 7,400 억 권의 '중간' 책 (afterstates) 이 있는 거대한 도서관입니다.

이 도서관의 책을 하나씩 읽으려면 영원히 걸릴 것이며, 전 세계에 존재하는 것보다 더 많은 메모리가 필요한 컴퓨터가 필요할 것입니다. 저자들은 이 도서관을 몇 일 만에 일반적인 개인용 컴퓨터로 해결할 수 있도록 정리하는 마법의 트릭이 필요했습니다.

2. 마법의 트릭: 게임의 '나이 (Age)'

그들의 성공 열쇠는 그들이 **'나이 (Age)'**라고 부르는 개념에 있었습니다.

게임할 때마다 저울에 무게를 더한다고 상상해 보세요.

시작할 때, 당신은 두 개의 타일 (예: 두 개의 2) 을 가지고 있습니다. 이때 '나이'는 보드 위의 모든 숫자의 합 (2 + 2 = 4) 입니다.
타일을 밀어 합치면 숫자는 두 배가 되지만, 나이는 정확히 그대로 유지됩니다. (두 개의 2 를 합쳐 4 가 되어도 총합은 변하지 않습니다).
나이가 변하는 유일한 순간은 컴퓨터가 새로운 타일 (2 또는 4) 을 무작위로 떨어뜨릴 때입니다. 이때 나이에 2 또는 4 가 추가됩니다.

비유:
이 게임을 미로가 아니라 다층 건물로 생각해 보세요.

건물의 각 '층'은 특정 나이를 나타냅니다 (예: 4 층, 6 층, 8 층...).
같은 층에서는 자유롭게 이동할 수 있습니다 (타일을 밀고 합치는 것). 위나 아래로 이동하지 않고요.
컴퓨터가 새로운 타일을 떨어뜨릴 때만 다음 층으로 이동합니다.

게임이 항상 '나이' 측면에서 앞으로만 나아갑니다 (낮은 합으로 다시 돌아가지는 않음) 때문에, 저자들은 도서관을 층별로 처리할 수 있었습니다. 그들은 도서관 전체를 한 번에 머릿속에 담을 필요가 없었습니다. 현재 층, 다음 층, 그리고 그 다음 층만 기억에 보관하면 충분했습니다. 100 층에 대한 최선의 수를 계산하는 것을 마치면, 102 층을 위한 공간을 마련하기 위해 98 층의 데이터를 버릴 수 있었습니다.

3. 압축: 배낭에 고래 넣기

이 층별 트릭을 사용했음에도 불구하고 데이터는 여전히 거대했습니다. 모든 게임 상태를 종이에 적으려 한다면 약 4.4 테라바이트의 하드 드라이브 공간이 필요했을 것입니다 (거의 거대한 데이터 센터 크기).

이를 해결하기 위해 그들은 엘리어스 - 파노 (Elias-Fano) 코딩이라는 교묘한 데이터 압축 기술을 사용했습니다.

비유: 10 억 명의 사람 목록이 있는데, 모두 빨간 셔츠를 입고 있다고 상상해 보세요. 모든 이름 옆에 '빨간 셔츠'라고 적는 것 (공간 낭비) 대신, "이 목록의 모든 사람이 빨간 셔츠를 입고 있다"라고 말하는 특별한 코드를 작성합니다.
그들은 모든 가능한 게임 상태의 '신원증'을 약 1.4 테라바이트로 압축하는 방법을 찾았습니다. 만약 최선의 수에만 관심이 있다면 (원시 데이터는 무시하고), 이를 약 300 기가바이트 (고성능 노트북 하드 드라이브 크기) 로 더 줄일 수 있었습니다.

4. 결과: 무엇을 배웠는가?

게임을 해결함으로써 그들은 실수를 하지 않는 플레이어의 완벽한 기대 점수를 계산했습니다.

점수: 가장 일반적인 설정 (두 개의 2) 으로 시작하여 완벽하게 플레이한다면, 약 50,724 점을 얻을 것으로 예상됩니다.
'불운' 요인: 두 개의 2 대신 4 타일로 시작하는 것은 실제로 약간의 불리함 (약 4 점 낮음) 을 초래한다는 것을 발견했습니다. 마치 무거운 배낭을 메고 경주를 시작하는 것과 같습니다. 따라잡기 위해 더 열심히 노력해야 하죠.
'2048'의 언덕: 결과 그래프는 나이가 2048 의 배수에 도달할 때마다 '골짜기' (성능 저하) 를 보여주었습니다. 이는 많은 플레이어가 느끼는 감정을 확인시켜 줍니다. 작은 12 칸 보드에서 공간이 부족해지기 때문에 2048 타일을 만드는 것이 극도로 어려워진다는 것입니다. 모든 작은 숫자 (2, 4, 8... 1024 까지) 를 결합하기 전에 완벽하게 배치해야 합니다.

요약

저자들은 가능성의 수가 너무 방대하여 완전히 해결하기에는 너무 복잡해 보였던 게임을 가져왔습니다. 그들은 게임이 자연스럽게 '숫자의 합 (나이)'에 따라 조직된다는 것을 깨달았습니다. 거대한 꼬인 그물망이 아니라 일련의 층으로 게임을 취급하고, 초효율적인 파일 시스템 (압축) 을 사용하여 모든 가능한 수에 대한 완벽한 전략을 매핑해 냈습니다.

그들은 운과 직관에 의존하는 게임을 수학적으로 정복할 수 있음을 증명했습니다. 표준 컴퓨터와 몇 일간의 노력만으로도 말이죠.

기술적 요약: 4×3 보드에서의 2048 게임 완전 해결

문제 정의

본 논문은 확률적 단일 플레이어 게임 변형인 4×3 보드에서의 2048(2048 $^{4\times3}$ )의 "완전 해결 (strong solution)"을 다룹니다. 표준 4×4 버전과 달리, 이 변형은 12 개의 셀로 구성된 그리드를 사용합니다. 게임은 마르코프 결정 과정 (MDP) 으로 모델링되며, 에이전트는 인접한 동일한 값의 타일을 병합하기 위해 행동 (위, 아래, 왼쪽, 오른쪽) 을 선택합니다. 유효한 행동 후, 보드 상태는 결정적으로 "후행 상태 (afterstate)"(타일 슬라이딩 및 병합) 로 전이됩니다. 이후 환경은 확률적으로 새로운 타일 (90% 확률로 2, 10% 확률로 4) 을 무작위 빈 셀에 생성하여 다음 상태로 전이합니다.

목표는 도달 가능한 임의의 상태 $s$ 로부터의 기대 누적 보상을 나타내는 최적 정책 $\pi^*$ 과 최적 가치 함수 $v^*(s)$ 를 계산하는 것입니다. 주요 과제는 상태 공간의 크기입니다. 4×3 변형에는 약 $1.15 \times 10^9$ 개의 도달 가능한 상태와 $7.4 \times 10^8$ 개의 후행 상태가 포함되어 있습니다. 이 규모는 이전에 해결된 3×3 변형 (Mini2048) 보다 약 $10^4$ 배 크며, 표준 하드웨어에서는 단순한 열거 및 저장이 불가능합니다.

방법론

저자들은"연령 (age) 에 따른 상태 공간 분할"과압축된 데이터 표현에 기반한 해결책을 제안합니다.

1. 연령 기반 분할

핵심 혁신은 보드의 모든 타일 숫자의 합을 상태의 연령으로 정의하는 것입니다 ( $age(s) = \sum c_i$ ).

불변성: 유효한 행동 후 상태와 그 즉시 후행 상태 사이에서 연령은 일정하게 유지됩니다 (타일 병합은 값의 합을 보존하고 슬라이딩은 값을 변경하지 않기 때문입니다).
진행: 확률적 전이 (새 타일 생성) 동안 연령은 2 또는 4 씩 증가합니다.
알고리즘적 함의: 이 속성은 상태 공간을 연령에 따라 불연속적인 부분 집합으로 분할할 수 있게 합니다.
- 전진 통과 (열거): 연령 $n$ 의 유효한 상태는 연령 $n-2$ 와 $n-4$ 의 후행 상태로부터만 생성될 수 있습니다. 알고리즘은 증가하는 연령을 순회하며 메모리에 현재 연령, 연령 +2, 연령 +4 의 세 집합만 유지하여 모든 도달 가능한 상태와 후행 상태를 열거합니다.
- 후진 통과 (가치 계산): 최적 가치는 최대 연령에서 초기 연령으로 역순으로 순회하며 계산됩니다. 상태의 가치는 도달 가능한 후행 상태들의 최대 가치이며, 후행 상태의 가치는 도달 가능한 다음 상태들의 기대 가치 (생성 확률로 가중치 부여) 입니다.

2. 압축 표현

저장 요구 사항 (원시 48 비트 ID 의 경우 약 4.4 TiB 로 추정) 을 처리하기 위해 저자들은 고유 상태 ID 집합을 저장하기 위해 Elias-Fano 코드를 사용합니다.

구조: 정렬된 고유 ID 는 상위 비트 ( $h_i$ ) 와 하위 비트 ( $l_i$ ) 로 나뉩니다. 하위 비트는 연속된 비트 벡터에 저장되고, 상위 비트는 랭크 연산을 사용하여 희소 비트 벡터 $H$ 로 인코딩됩니다.
최적화:
- 대칭성 축소: ID 는 수평, 수직, 180 도 회전 대칭 중 최소 값으로 정규화됩니다.
- 기저 적응: 인코딩 기저는 특정 연령에 대한 최대 타일 값에 따라 조정됩니다.
- 셀 제거: 합 (연령) 이 전체를 제약하므로 인코딩 중 한 셀의 정보가 제거되어 나중에 완전한 재구성이 가능합니다.
효율성: 이는 모든 후행 상태 ID 에 대한 저장 공간을 약 4.4 TiB 에서 약 1.4 TiB로 줄이면서 효율적인 조회 기능을 유지합니다. 특히 최적 플레이의 경우, BuRR 알고리즘을 사용하는 전용 표현으로 요구 사항을 300 GiB 미만으로 줄입니다.

주요 결과

상태 공간 통계: 도달 가능한 상태의 총 수는 1,152,817,492,752개이며, 후행 상태의 수는 739,648,886,170개입니다.
최적 기대 점수: 가장 일반적인 초기 상태 (값이 2 인 두 타일) 의 경우, 최적 전략 하의 기대 점수는 약 50,724.26입니다.
- 4 타일이 있는 초기 상태 (연령 6) 는 약간 더 낮은 기대 점수 (~50,720.62) 를 냅니다.
- 두 개의 4 타일이 있는 초기 상태 (연령 8) 는 가장 낮은 점수 (~50,708.99) 를 내며, 고가치 타일로 시작하는 것이 약간 불리함을 나타냅니다.
상태 분포: 연령당 상태 수는 일반적으로 관리 가능한 수준 (연령당 $3 \times 10^6$ 미만) 이어서 알고리즘이 여러 연령 계층을 메모리에 유지할 수 있습니다.
종단 상태: 상태 수 분포의 "계곡 (valleys)"은 2048 의 배수인 연령에서 발생하며, 이는 제한된 보드 공간으로 큰 타일을 형성하는 어려움을 반영합니다. 특정 연령 (예: 8190, 12286) 은 해당 합을 형성하는 데 필요한 타일 수가 사용 가능한 12 개의 셀을 초과하므로 유효한 후행 상태가 없습니다.
행동 민감도: 최적 행동과 비최적 행동 간의 가치 차이는 연령 2048 및 4096 근처에서 정점에 도달하여, 큰 타일이 형성된 직후의 초기 결정이 중요함을 시사합니다.

중요성 및 주장

본 논문은 이전까지 상태 공간 크기로 인해 해결 불가능한 것으로 간주되었던 2048 $^{4\times3}$ 변형을 **완전히 해결 (strongly solved)**했다고 주장합니다. 이 연구의 중요성은 다음과 같습니다:

확장성: 게임 특유의 구조적 속성 (연령) 을 활용하여 무차별 대입 방식이 아닌 개인용 컴퓨터에서 수일 내에 $10^9$ 개 이상의 상태를 가진 게임을 해결할 수 있음을 입증했습니다.
방법론적 기여: "연령" 분할 기법의 도입은 상태 값이 기대치에 의존하는 확률적 MDP 의 열거 및 가치 계산을 가능하게 하여, 확률적 환경에서는 비효율적인 $\alpha\beta$ 가지치기의 필요성을 효과적으로 우회합니다.
데이터 가용성: 저자들은 최적 가치 함수와 상태 공간의 압축된 표현을 제공하여 향후 강화학습 연구 및 게임 분석을 위한 기준선으로 삼을 수 있게 했습니다.
저장 효율성: 방대한 게임 상태 집합을 약 1.4 TiB 로 압축하기 위해 Elias-Fano 코드를 성공적으로 적용함으로써, 중간 규모의 컴퓨팅 자원 (예: 4 TiB SSD) 을 가진 연구자들도 데이터셋에 접근할 수 있게 했습니다.

저자들은 주요 목표가 게임 해결이었지만, 결과적으로 생성된 데이터셋과 "연령" 개념은 확률적 게임 및 강화학습 평가에 대한 추가 연구의 기초가 될 수 있다고 언급합니다.