탐욕에서 스마트로: Block Blast Solver의 스코어링 엔진 최적화

Source: Dev.to

저는 Block Blast용 솔버를 만든 이유에 대해 글을 썼습니다 – 공간과 전략에 대해 놀라운 교훈을 주는 단순하고 탐욕적인 알고리즘이었습니다. 좋은 시작이었지만 큰 결함 하나가 있었습니다: 단기적인 시야만 가졌다는 점이죠.

탐욕적인 솔버는 다음 한 수만을 신경썼습니다. 즉시 제거된 라인과 대략적인 “빈 공간” 수를 기준으로 배치를 점수 매기고, 가장 높은 점수를 받은 옵션을 선택해 진행했습니다. 어느 정도는 동작했지만… 종종 지금 두 줄을 지우면서도 두 블록 뒤에 불가능한 보드 상태를 만들곤 했습니다. 전투는 이기고 전쟁은 지는 셈이었습니다.

그래서 저는 단순히 풀기만 하는 것을 멈추고 생각하기 시작했습니다: 전략적인 수는 어떤 모습일까? 어떻게 하면 알고리즘이 보드를 정적인 셀로 보지 않고, 미래 가능성의 시스템으로 인식하도록 가르칠 수 있을까요?

단순 탐욕 봇의 한계

여기 내 초기 점수 함수의 핵심이 있었다. 순진했지만 시작이었다:

// The Old, Greedy Way
function simpleScore(newBoard) {
    let score = 0;
    score += countClearedLines(newBoard) * 100;   // Clear lines = good!
    score -= countIsolatedCells(newBoard) * 20;   // Holes = bad!
    return score;
}

이 논리는 미묘한 방식으로 실패했다. 즉시 라인을 제거하는 것을 좋아했으며, 그 결과 한 구석에 블록을 높이 쌓아도 괜찮았다. 단일 셀 구멍을 싫어했지만, 큰 3×3 블록을 놓을 수 없는 미래 영역을 만드는 데는 눈이 멀었다. 다음 수를 잃지 않으려는 플레이는 했지만, 다음 열 수에 대한 계획은 없었다.

전략적 휴리스틱 구축

목표는 무차별적인 앞선 탐색이 아니었습니다(그것은 향후 미니맥스 실험을 위한 것입니다). 목표는 한 번의 평가로 보드의 장기적인 건강 상태를 추정할 수 있는 더 똑똑한 점수 휴리스틱, 즉 함수를 만드는 것이었습니다.

저는 **“보드 건강”**을 구체적이고 정량화 가능한 요소들로 나눴습니다:

새로운 점수 함수는 이러한 전략적 요소들의 가중합이 되었습니다:

// The New, Strategic Heuristic
function strategicBoardScore(newBoard, nextBlockShapes) {
    let score = 0;

    // Core Strategy Weights
    score += calculateFlexibilityScore(newBoard, nextBlockShapes) * 0.4; // 40 % weight on future options
    score += calculateComboPotential(newBoard) * 0.3;                    // 30 % on setting up big plays
    score -= calculateBoardDanger(newBoard) * 0.2;                     // -20 % for creating risk
    score -= calculateInaccessibleAreas(newBoard) * 0.1;                 // -10 % for trapping spaces

    // Bonus for immediate clears (but less important)
    score += countClearedLines(newBoard) * 50;

    return score;
}

이 가중치들(0.4, 0.3 등)을 조정하는 데는 수많은 게임을 플레이하는 솔버를 관찰하며 온종일 시행착오를 겪어야 했습니다. 코딩이라기보다 아주 단순한 AI를 훈련시키는 느낌이었습니다.

코드에서의 “아하!” 순간

실제 테스트는 최종 점수가 아니라 특정 보드 상태였습니다. 오래된 탐욕형 봇은 선택에 직면했습니다:

• Option A: L‑모양을 배치해 즉시 1줄을 제거합니다.
• Option B: 같은 L‑모양을 다른 곳에 배치해 현재는 0줄을 제거합니다.

즉시 제거에 집착하던 옛 로직은 항상 Option A를 선택했습니다. 하지만 Option A는 오른쪽에 높은 스택을 만들게 됩니다.

새로운 휴리스틱은 다른 것을 보았습니다. Option B는 아무 것도 제거하지 않지만 보드를 완전히 평평하게 유지하고 아름다운 4×2 직사각형을 남겼습니다. calculateFlexibilityScore()는 큰 점수를 부여했고, calculateBoardDanger()는 Option A를 위험하다고 표시했습니다.

처음으로 솔버는 즉각적인 보상을 포기하고 장기적인 건강을 선택했습니다. 인내심 있는 인간 같은 결정을 내렸습니다. 이것이 바로 “아하!” 순간이며, 알고리즘이 게임의 핵심 원칙을 학습한 것이었습니다.

결과 및 라이브 플레이그라운드

차이는 뚜렷했다. 전략적 솔버는 일관되게 30‑40 % 더 오래 살아남았으며, 평균 점수도 크게 상승했다. 움직임이 단순히 반응하는 것이 아니라 목표를 향해 나아가는 듯 의도적으로 보이기 시작했다.

이 원리를 실제로 확인하거나 보드 상태를 직접 분석하고 싶다면, 내 사이트의 실시간 버전을 사용해 보세요: Block Blast Solver. 까다로운 보드를 선택하고 위의 휴리스틱을 기반으로 솔버의 “추론”을 추측해 보세요. 자신의 직관을 역공학하는 흥미로운 방법입니다.

다음은? 미니맥스 지평선

전략적 휴리스틱은 큰 도약이지만 여전히 근사치에 불과합니다. 진정한 최전선은 프루닝이 포함된 미니맥스 알고리즘을 구현하는 것으로, 이를 통해 풀이기가 실제로 2, 3, 혹은 4수 앞까지 시뮬레이션하고 결정할 수 있습니다.

그것이 다음 장입니다. 계산량이 더 무거운 도전이지만, 좋은 휴리스틱의 힘을 본 뒤 나는 이것이 진정 최적의 플레이를 열어주는 열쇠라고 확신합니다. 탐욕에서 스마트로의 여정은 이제 시작일 뿐입니다.

Tags: javascript #algorithms #gamedev #optimization #puzzle