← 전체 글

사과게임의 최적해를 찾을 수 있을까?

tl;dr - 일반적인 경우에는, 아마 효율적으로는 어렵다.

직사각형 하나의 합이 10인지 확인하는 일은 쉽다. 어떤 수순이 주어졌을 때 그것이 실제로 가능한지 검증하는 것도 쉽다. 어려운 부분은 최선의 수순을 찾는 일이다. 매번 한 수를 둘 때마다 이후에 가능한 수들의 집합이 바뀌기 때문이다. 이 때문에 탐색 트리가 커지고 문제를 깔끔하게 분해하기도 어렵다. 그래서 Exact Search는 금방 비싸진다. 작은 보드에서는 DFS with Branch and Bound 같은 방법이 가능하지만, 현실적인 보드 크기에서는 Heuristic Search가 더 실용적이다.

문제 설정

각 칸에 1부터 9까지의 값이 들어 있는 m x n 보드를 생각해보자. 합법적인 수는 셀들의 합이 정확히 10이 되는 축 정렬 직사각형 하나를 선택해, 그 셀들을 보드에서 제거하는 것이다.

목표는 제거한 셀의 총 개수를 최대화하는 것이다.

즉 문제는 다음과 같다: 초기 보드가 주어졌을 때, 최종 점수를 가장 높게 만드는 합법적인 수순을 찾아라.

What is easy

이 문제의 일부는 비교적 Straightforward하다.

직사각형 하나를 검사하는 일은 빠르게 할 수 있다. 2D Prefix Sum을 쓰면 O(mn) 전처리 이후 각 직사각형의 합을 O(1)에 계산할 수 있다. 만약 직사각형 안의 모든 셀이 아직 남아 있어야만 합법적인 수로 친다면, 살아 있는 셀에 대한 두 번째 Prefix Sum을 두는 것만으로도 그 조건을 확인할 수 있다.

현재 보드에서 가능한 모든 직사각형 후보를 나열하는 것도 관리 가능한 수준이다. 축 정렬 직사각형의 개수는 전체적으로 O(m^2 n^2)개이고, 각 직사각형은 빠르게 검사할 수 있다.

검증도 마찬가지다. 누군가 전체 수순을 하나 제시하면서 최소 K개의 셀을 제거할 수 있다고 주장하면, 그 수순을 그대로 Replay해서 그 주장이 맞는지 Polynomial Time 안에 확인할 수 있다.

병목은 Local Checking이 아니다. Global Search다.

Why exact search gets hard

어려움은 Move Dependence에서 나온다.

어떤 수는 이후의 기회를 없애버릴 수 있다. 반대로 남은 배치를 바꿔서 더 좋은 미래 기회를 만들 수도 있다. 그래서 어떤 수의 가치는 그 순간 당장 얻는 이득만으로 결정되지 않는다. 그 수가 남겨놓는 보드 상태까지 같이 봐야 한다.

이 때문에 Move Ordering이 핵심이 된다. 같은 보드에서 시작하더라도 어떤 순서로 수를 두느냐에 따라 최종 점수가 크게 달라질 수 있다.

평균 Branching Factor를 B, 게임이 지속되는 길이를 D라고 하면, Naive Search Tree의 크기는 대략 B^D 정도가 된다. 17 x 10 보드에서는 시작 시점의 B도 꽤 클 수 있고, D 역시 충분히 길어질 수 있어서 탐색 공간이 아주 빠르게 커진다.

이 점은 Dynamic Programming에도 제약을 준다. 문제를 강하게 분해할 수 있는 경우에는 State를 거의 독립적인 Subproblem으로 쪼갤 수 있기 때문에 DP가 잘 맞는다. 하지만 사과게임은 일반적으로 그렇게 동작하지 않는다. 특히 큰 직사각형이 허용되면, 한 영역에서의 제거가 다른 영역의 Future Feasibility를 바꿔버릴 수 있다.

NP-style Search와의 관계

복잡도 질문을 더 깔끔하게 쓰려면 Decision Problem 형태로 바꾸는 편이 좋다: 보드 하나와 정수 K가 주어졌을 때, 최소 K개의 셀을 제거하는 합법적인 수순이 존재하는가?

이 버전은 전형적인 NP-style 구조를 가진다. 어떤 후보 해답이 주어지면 Polynomial Time 안에 검증할 수 있지만, 그것을 찾는 일에는 큰 탐색 공간이 필요할 수 있다.

물론 이것이 NP-hardness의 증명은 아니다. 실제 증명을 하려면 알려진 NP-hard 문제로부터의 Reduction이 필요하다. 다만 구조만 보면, 이 문제는 단순한 Polynomial-time Exact Algorithm이 있을 것 같은 문제라기보다 Hard Combinatorial Search에 훨씬 더 가깝다.

Exact methods

작은 보드에서는 Exact Search가 가능하다.

가장 기본적인 방법은 DFS with Branch and Bound다. 깊이 우선으로 탐색하되, 어떤 Upper Bound를 기준으로 보았을 때 현재 Best Solution을 절대 넘지 못하는 Branch는 잘라낸다.

Memoization도 도움이 될 수 있다. 서로 다른 수순이 같은 보드 상태로 합쳐질 수 있기 때문이다. 고정된 초기 보드에서는 각 셀이 가질 수 있는 상태가 Present 아니면 Removed 둘뿐이다. 따라서 Reachable State 수의 Upper Bound는 10^(mn)이 아니라 2^(mn)이 된다. 그래도 17 x 10 보드에서는 Exhaustive State Caching을 하기에는 여전히 너무 크다.

Constraint Programming이나 ILP-style Formulation도 더 작은 인스턴스에서는 가능하다. 다만 Sequential Feasibility까지 정확히 모델링하려면 Encoding이 빠르게 커진다.

좁은 Special Case에서는 Dynamic Programming이 가능할 수도 있다. 예를 들어 1 x n 변형이나 그와 비슷하게 Geometry가 제한된 경우라면 Compact한 State Representation을 만들 여지가 있다. 하지만 일반적인 2D 경우에는 그렇지 않다.

Practical conclusion

작은 인스턴스에서는 Exact Optimization이 가능하다.

하지만 현실적인 보드 크기에서는 Exact Search가 금방 비싸진다. 실제로 가장 유망한 Exact Approach는 보통 DFS with Branch and Bound에 Good Move Ordering, Transposition Table, 그리고 남아 있는 Live Cell 수 같은 Cheap Admissible Upper Bound를 결합하는 방식이다.

목표가 Guaranteed Optimality가 아니라 충분히 좋은 성능이라면, 실용적인 선택은 Heuristic을 이용하는 것이다.

Heuristic search

Greedy Solver는 Local Rule에 따라 그 순간 가장 좋아 보이는 수를 고른다. 빠르고 구현도 쉽지만, 당장은 약해 보이는 수가 이후에 훨씬 더 좋은 이어짐을 만드는 경우를 놓칠 수 있다.

Beam Search는 한 경로만 따라가는 대신, 각 Depth마다 상위 k개의 Partial Solution을 유지한다. 여전히 Approximate Method이긴 하지만, Purely Greedy한 방법보다 탐색 공간의 더 넓은 부분을 볼 수 있다.

Heuristic은 Proxy Objective를 사용할 수도 있다. 예를 들어 즉시 얻는 이득만 최대화하는 대신, Future Option을 더 많이 남기거나 어려운 셀을 고립시키지 않는 수를 선호하도록 설계할 수 있다.

이런 방법들은 Optimum을 보장하지는 않지만, 실제 보드 크기에서는 훨씬 더 현실적이다.