사과게임 난이도 분석

1. 개요

생성된 보드의 난이도를 어떻게 구할 수 있을까? 어떤 보드가 주어질 때 이 보드에서 얻을 수 있는 최대 득점값을 구하는 것은 NP-Hard에 가까운 문제로, 정확한 난이도를 대량으로 구하는 것은 현실적으로 불가능하다. 또한 이렇게 구한 최대 득점값이 높다고 해서 플레이 시 느끼는 난이도가 무조건 쉽다고 느껴진다는 보장도 없다. 보통은 잘 하지 않는 수를 처음에 둬야만 그런 고득점이 가능하다던가 하는 특수한 케이스들이 분명 존재할테니 말이다.

하지만 우리는 그래도 개략적인 난이도를 polynomial time 내에 추정할 수 있는 방법을 찾고 싶었고, 이를 위해 원본 게임의 500개 보드 데이터를 가지고 분석해 보았다.

우선, 유저가 느낄 난이도의 참값은 greedy solver가 얻은 득점 가능 점수에 따라 정해진다고 가정하고, 적은 연산량으로 계산할 수 있는 10가지의 지표에 대해 통계적으로 비교해 보았다.

2. 난이도 측정 방법

난이도 측정을 위해, 간단한 Greedy Algorithm을 사용했다. 이 알고리즘은 눈이 매우 좋고 손이 매우 빠르지만, 생각을 거의 안하는 플레이어처럼 행동한다. 구체적으로는:

1. 보드에서 합이 10인 모든 직사각형 영역을 찾는다
2. 그 중 가장 큰 숫자를 포함하는 조합을 우선 선택 (같으면 칸 수가 적은 것 우선)
3. 선택된 영역의 숫자를 지운다
4. 더 이상 지울 조합이 없을 때까지 반복

간단하게 말해서 현재 가능한 것들 중 가장 큰 숫자를 없애는 방식으로 작동한다.

3. 난이도 측정 결과

Figure 1. 점수 분포

점수는 69~149 범위에 분포하며, 평균 113.1, 표준편차 15.4이다.

4. 난이도 추정 지표

모든 보드에 대해 greedy algorithm을 적용하기는 어려우므로, 난이도를 추정할 수 있는 더 간단한 지표를 찾아본다.

4.1 보드 총합

총합이 클수록 큰 숫자가 많다는 뜻이고, 큰 숫자는 짝을 찾기 어렵다. 따라서 총합이 높을수록 점수가 낮아진다.

Figure 2. 보드 총합 vs 점수 (r = -0.751)

r² = 0.564이면, 점수 변동의 약 56%를 보드 총합 하나로 설명할 수 있다.

4.2 숫자별 상관

어떤 숫자가 많을수록 점수가 올라가고, 어떤 숫자가 많을수록 내려가는지 확인했다.

Figure 3. 숫자별 개수와 점수의 상관계수

작은 숫자(1, 2, 3)가 많을수록 점수가 높고, 큰 숫자(7, 8, 9)가 많을수록 점수가 낮다. 특히 9의 상관이 가장 강한 음수인데, 9는 오직 1과만 짝이 되기 때문이다.

4.3 다른 지표들과 비교

보드 총합 외에 난이도를 예측할 수 있는 다른 지표들도 조사했다.

Figure 4. 지표별 점수 예측력 비교

총합이 |r| = 0.751로 가장 높다. 이는 당연한데, 총합은 사실상 모든 숫자의 가중합이기 때문이다. 개별 숫자 중에서는 9의 개수가 가장 강한 예측력을 보인다.

흥미로운 점은 인접 쌍의 수(Adjacent Pairs)의 상관이 비교적 낮다는 것이다. 인접 쌍이 많으면 쉬워 보이지만, 실제로는 쌍의 수보다 어떤 숫자들인지가 점수에 더 큰 영향을 준다.

Figure 5. 상위 4개 지표의 점수 산점도

5. 추정 난이도 예상 방법

보드 총합 구간에 따라 6단계 난이도를 부여했다.

Figure 6. 총합 분포와 등급 경계

Figure 7. 등급별 평균 점수

등급이 올라갈수록 평균 점수가 뚜렷하게 떨어진다. ☆☆☆☆☆과 ★★★★★의 평균 점수 차이는 35점에 달한다.

6. 결론

500판의 원본 보드를 greedy solver로 풀어본 결과, 보드의 난이도는 숫자 분포와 강한 상관 관계가 있다. 특히나, 보드 숫자의 총합만으로도 보드의 난이도를 어느 정도 추정할 수 있다. 또한 다음과 같은 사실들을 확인할 수 있었다.

• 보드 총합 하나로 점수 변동의 56%를 설명할 수 있다. 총합이 크면 큰 숫자가 많고, 짝을 맞추기 어렵다.
• 개별 숫자 중에서는 9의 개수가 난이도에 가장 큰 영향을 준다. 9는 1과만 짝이 되기 때문이다. 반대로 1의 개수가 많을수록 쉬워지는데, 1은 9와 짝이 되는 것은 물론이고 다른 숫자들과도 유연하게 조합을 만들 수 있기 때문이다.
• 반면 인접 쌍의 수나 5의 개수 같은 지표는 직관과 달리 예측력이 낮다.
• 흥미롭게도 8의 개수가 9보다 점수와 더 강한 음의 상관을 보였다 (r = -0.392 vs -0.309). 이 solver는 큰 숫자부터 처리하므로 9는 보드가 빽빽할 때 1과 빠르게 짝지어지지만, 8은 9를 모두 처리한 후에야 차례가 오고 그때쯤 보드에 빈 칸이 많아 유효한 직사각형을 찾기 더 어렵기 때문으로 보인다. 8을 먼저 처리하는 전략이라면 결과가 달라질 수 있으며, 이는 추후 연구 과제로 남긴다.

결과적으로, 우리는 보드 숫자의 총합을 기준으로 ☆☆☆☆☆~★★★★★ 6단계의 '추정 난이도' 등급을 부여했으며, 이를 통해 아주 적은 연산으로도 어느 정도 설득력 있는 난이도를 제시할 수 있게 되었다. 실제 플레이한 유저들의 반응을 보아도, 가끔 별 개수가 낮은데 너무 어려웠다는 등의 의견이 있었지만, 대부분의 보드에서 난이도 등급에 대해 긍정하는 의견이 많았다.