← 전체 글

사과게임 난이도를 측정하기 위한 Greedy Solver

사과게임 보드의 난이도를 추정하고 싶다고 해보자. 가장 직접적인 방법은 많은 사람에게 같은 보드를 플레이하게 한 뒤 점수를 평균내는 것이다. 하지만 이 방법은 비용이 크고 시간도 많이 든다. 반대쪽 극단에는 완전 탐색으로 이론적 최대 점수를 구하는 방법이 있다. 다만 보드 하나만 놓고 봐도 가능한 수순의 수가 너무 빠르게 불어나기 때문에, 현실적으로 쓰기 어렵다.

그래서 우리에게는 이 두 극단 사이 어딘가에 있는 방법이 필요했다. 빠르게 돌릴 수 있고, 일관성이 있으며, 임의의 보드에 대해 난이도와 관련된 점수 하나를 줄 수 있는 근사방법 말이다.

완벽한 Solver를 만들고 싶었던 것은 아니다. 인간의 사고 과정을 정교하게 흉내 내는 것도 목표가 아니었다. 우리가 원했던 것은 실행 비용이 낮고, 설명하기 쉽고, 여러 보드에 걸쳐 안정적으로 쓸 수 있는 단순한 기준선이었다. 보드마다 점수가 달라진다면, 그 차이는 복잡한 평가 방식이 아니라 보드 구조 자체에서 나와야 한다고 봤다.

이런 이유로 Greedy Solver를 선택했다.

알고리즘 설계에서 Greedy 방법이란, 미래 상태를 깊게 탐색하지 않고 매 단계마다 가장 좋아 보이는 지역적 선택을 하는 방식이다. 우리 Solver는 현재 보드를 보고, 가능한 유효한 수를 모두 찾은 뒤, 고정된 규칙에 따라 하나를 고르고, 해당 셀들을 제거한다. 그리고 더 이상 유효한 수가 없어질 때까지 이 과정을 반복한다. Backtracking도 없고, Search Tree도 없고, Probabilistic Sampling도 없다.

수를 고르는 규칙도 단순하다. 매 단계에서 Solver는 셀의 합이 10이 되는 모든 직사각형을 찾는다. 이것들이 유효한 수다. 이 중에서 가장 큰 단일 셀 값을 포함한 수를 우선 선택한다. 큰 값은 다른 값들과 유연하게 조합하기가 상대적으로 어렵기 때문에, 먼저 제거해두면 이후 보드가 더 다루기 쉬운 상태로 남는 경우가 많다고 봤다. 동점이라면 셀 수가 더 적은 직사각형을 고른다. 작은 직사각형일수록 이후를 위해 남겨지는 셀이 더 많기 때문이다.

얼핏 보면 이런 Greedy 방식은 문제가 많아 보일 수 있다. 하지만 난이도를 측정한다는 목적에는 오히려 이 점이 더 적합하다고 생각했다. 애초에 인간이 Greedy하게 사고하기 때문이다.

사과게임에는 2분의 시간 제한이 있다. 이 조건에서 20수 앞까지 내다보며 푸는 사람은 거의 없다. 많아야 한두 수 정도 앞을 보는 경우가 대부분이다. 우리가 측정하고 싶은 것도 Mathematical Optimality가 아니라 플레이어가 느끼는 체감 난이도이기 때문에, Greedy 접근은 꽤 합리적인 근사라고 볼 수 있다.

보통 플레이어 입장에서 진짜 어려운 부분은 장기 전략보다도, 현재 보드에서 남아 있는 유효한 수를 알아보는 것 자체에 있다. 많은 사람들은 가능한 직사각형을 전부 파악하는 것부터 어려워한다. 실제 플레이도 대체로 Greedy하게 흘러간다. 먼저 눈에 띄는 영역에서 시작해서 거기서 수를 두고, 그다음에는 가까운 쪽으로 시선과 선택이 이어진다. 매 턴마다 보드 전체를 Global Optimization하는 식으로 플레이하지는 않는다.

이런 점에서 우리가 만든 Solver는 사과게임을 몇 번 해봤고, 어느 정도 높은 점수에도 익숙한 플레이어와 비슷하게 동작한다고 볼 수 있다. 물론 고수는 아니고, 그렇다고 랜덤도 아니다. 연산은 정확하고 보드 전체도 빠짐없이 볼 수 있지만, 의사결정 규칙 자체는 여전히 근시안적이다. 그런데 바로 이런 조합이 기계적인 기준선으로서는 꽤 유용했다.

알고리즘을 쓰면 대략 이렇게 된다.

function SolveBoard(board): integer;
var
  validMoves: list of Move;
  bestMove: Move;
  totalScore: integer;
begin
  totalScore := 0;
while HasValidMove(board) do
begin
validMoves := FindAllRectanglesSummingTo10(board);
bestMove := SelectBestMove(validMoves);
RemoveRectangle(board, bestMove);
totalScore := totalScore + ScoreOf(bestMove);
end;
SolveBoard := totalScore;
end;
function SelectBestMove(validMoves): Move;
begin
SelectBestMove := move in validMoves
with maximum LargestCellValue(move),
and if tied, minimum CellCount(move);
end;

이게 Solver의 전부다. Deterministic하기 때문에 같은 보드라면 언제나 같은 결과를 낸다.

이 Solver의 가장 큰 장점은 속도와 일관성이다. 많은 보드를 빠르게 평가할 수 있고, 각 보드에 대해 반복 가능한 점수를 줄 수 있다. 이런 제한적인 Solver로도 높은 점수가 나오는 보드라면, 실제로도 쉬운 보드일 가능성이 높다. 반대로 Solver가 낮은 점수를 내는 보드는 흩어진 작은 값, 비효율적인 간격, 눈에 잘 들어오지 않는 기회처럼 인간 플레이어도 어려워하는 구조적 특성을 갖는 경우가 많다.

물론 한계도 분명하다. 이 Solver는 최적이 아니다. 앞을 내다보지 않기 때문에, 당장은 덜 좋아 보이는 수가 나중에 훨씬 좋은 결과를 가져오는 경우를 놓칠 수 있다. 어떤 보드는 비직관적인 희생이 보상되기도 하는데, Greedy Solver는 그런 선택을 의도적으로 하지는 못한다. 그래서 Solver 점수는 어디까지나 실질적인 하한 추정치에 가깝고, 달성 가능한 진짜 최대 점수는 아니다.

Heuristic이 흔들리는 Edge Case도 있다. 후보들이 서로 비슷비슷한 경우에는 Tie-breaking 규칙이 전체 결과에 꽤 큰 영향을 줄 수 있다. 또 특정 셀을 나중까지 남겨두는 것이 중요한 보드에서는, Greedy한 선택이 너무 이른 시점에 스스로를 막다른 길로 몰아넣을 수도 있다. 결국 Greedy하게 얻은 점수는 난이도의 절대적인 측정값이라기보다 대략적인 대리 지표에 가깝다.

그래도 애초의 목적을 생각하면 이 Trade-off는 충분히 받아들일 만하다. 우리에게 필요했던 것은 완벽한 플레이어가 아니라, 보드끼리 비교할 때 쓸 수 있는 단순하고 재현 가능한 기준선이었다. 그런 점에서 Greedy Solver는 자기 역할을 잘 해낸다. 투명하고, Deterministic하며, 실행 비용도 낮다.