Unity 카드 배틀 AI를 위한 MCTS 분석: 선택·확장·시뮬레이션·역전파 구현법

핵심 답변

MCTS(Monte-Carlo Tree Search)는 모든 수를 완전히 탐색하기 어려운 카드 배틀에서 유망한 행동에 시뮬레이션 예산을 집중하는 게임 AI 알고리즘이다. Unity에서는 게임 오브젝트를 직접 복제하지 말고 순수 C# 게임 상태를 복제해 선택 → 확장 → 시뮬레이션 → 역전파를 반복하면 된다. 실전 품질은 UCT 탐색 상수, 롤아웃 정책, 상태 복제 비용, 한 턴당 계산 시간 제한이 좌우한다.

카드 배틀 AI에 MCTS가 적합한 이유는 무엇인가?

체스처럼 행동 수가 비교적 일정한 게임과 달리 카드 배틀은 손패, 비용, 대상 선택, 랜덤 효과, 생성 카드 때문에 매 턴 행동 공간이 크게 달라진다. 미니맥스는 깊이를 고정하면 중요한 조합을 놓치기 쉽고 깊이를 늘리면 분기 수가 빠르게 폭증한다.

MCTS는 사전에 완벽한 평가 함수를 만들기보다 실제 게임을 여러 번 빠르게 진행해 행동의 기대 승률을 추정한다. 따라서 다음 조건에서 특히 잘 맞는다.

게임 조건	MCTS 적합성	구현 시 주의점
행동 수가 턴마다 달라짐	높음	가능한 행동 생성기를 정확히 구현한다.
카드 효과가 조합을 만듦	높음	무작위 롤아웃 대신 간단한 휴리스틱을 섞는다.
숨은 정보가 없음	높음	현재 상태를 그대로 트리에 사용한다.
손패·덱이 비공개	보통	determinization 또는 정보 집합 MCTS를 검토한다.
한 수 제한 시간이 짧음	보통	반복 횟수 대신 시간 예산으로 종료한다.

MCTS가 카드 행동 후보를 선택하고 시뮬레이션 결과를 역전파하는 과정

MCTS의 네 단계는 어떻게 동작하는가?

1. 선택: UCT 점수가 가장 높은 노드를 고른다

루트에서 시작해 이미 확장된 자식 중 UCT(Upper Confidence Bound for Trees) 점수가 가장 높은 노드를 계속 선택한다.

UCT_i = \frac{W_i}{N_i} + C \sqrt{\frac{\ln N_p}{N_i}}

$W_i$ : 자식 노드의 누적 보상
$N_i$ : 자식 노드 방문 횟수
$N_p$ : 부모 노드 방문 횟수
$C$ : 탐험 강도. 보통 $\sqrt{2}$ 에서 시작해 게임에 맞춰 조정한다.

첫 항은 승률이 높은 행동을 활용하고 둘째 항은 아직 충분히 시험하지 않은 행동을 탐험한다. 방문 횟수가 0인 노드는 UCT 계산 대신 즉시 선택해 0으로 나누는 문제를 피한다.

2. 확장: 아직 시도하지 않은 행동 하나를 트리에 추가한다

선택한 노드에 미확장 행동이 있다면 그중 하나를 적용해 새 자식 노드를 만든다. 한 번에 모든 행동을 확장하면 대규모 손패나 대상 선택에서 메모리와 시간이 낭비된다. 기본 MCTS는 반복마다 행동 하나만 확장한다.

3. 시뮬레이션: 종료 또는 깊이 제한까지 빠르게 플레이한다

새 상태에서 양측의 행동을 선택해 승패 또는 보상을 얻는다. 완전 무작위 롤아웃은 구현이 쉽지만 약한 공격, 확정 처치, 치명적인 방어 누락을 같은 확률로 선택한다.

카드 배틀에서는 다음 정도의 가벼운 정책이 비용 대비 효과적이다.

즉시 승리하거나 상대를 처치하는 행동을 우선한다.
가능한 공격 행동 중 예상 피해가 큰 행동을 우선한다.
남은 행동은 합법 행동에서 무작위로 선택한다.
최대 턴 또는 최대 행동 수에 도달하면 상태 평가값을 사용한다.

4. 역전파: 결과를 루트까지 누적한다

롤아웃 결과를 현재 노드에서 루트까지 전달한다. 보상은 루트 플레이어 관점으로 고정하는 방식이 단순하다. 승리는 1, 패배는 0, 무승부는 0.5로 두면 각 노드의 평균 보상이 루트 플레이어 승률이 된다.

flowchart LR
    A[루트 게임 상태] --> B[선택: 최고 UCT 자식]
    B --> C[확장: 미방문 행동 1개]
    C --> D[시뮬레이션: 빠른 롤아웃]
    D --> E[역전파: 방문·보상 누적]
    E --> B

Unity C#에서 MCTS 노드는 어떻게 구현할까?

AI 탐색은 MonoBehaviour, GameObject, 애니메이션 상태와 분리한다. 전투 규칙을 담은 불변에 가까운 BattleState와 화면 표현을 분리해야 수천 번의 시뮬레이션이 안전하고 빠르다.

using System;
using System.Collections.Generic;
using System.Linq;

public sealed class MctsNode
{
    public MctsNode Parent { get; }
    public BattleState State { get; }
    public CardAction ActionFromParent { get; }
    public List<MctsNode> Children { get; } = new();
    public List<CardAction> UntriedActions { get; }
    public int Visits { get; private set; }
    public float TotalReward { get; private set; }

    public MctsNode(BattleState state, MctsNode parent = null, CardAction action = default)
    {
        State = state;
        Parent = parent;
        ActionFromParent = action;
        UntriedActions = state.GetLegalActions().ToList();
    }

    public bool IsTerminal => State.IsGameOver;

    public MctsNode Expand(Random random)
    {
        int index = random.Next(UntriedActions.Count);
        CardAction action = UntriedActions[index];
        UntriedActions.RemoveAt(index);

        var child = new MctsNode(State.Apply(action), this, action);
        Children.Add(child);
        return child;
    }

    public MctsNode SelectChild(float exploration)
    {
        return Children.MaxBy(child =>
        {
            if (child.Visits == 0) return float.PositiveInfinity;
            float exploit = child.TotalReward / child.Visits;
            float explore = exploration * MathF.Sqrt(MathF.Log(Visits) / child.Visits);
            return exploit + explore;
        });
    }

    public void Backpropagate(float reward)
    {
        for (MctsNode node = this; node != null; node = node.Parent)
        {
            node.Visits++;
            node.TotalReward += reward;
        }
    }
}

BattleState.Apply()는 현재 상태를 바꾸지 않고 다음 상태를 반환해야 한다. 예를 들어 HP, 마나, 손패, 덱 인덱스, 필드 유닛 배열, 현재 플레이어, 난수 시드가 모두 상태에 포함되어야 한다. UI가 참조하는 ScriptableObject 카드 정의는 공유해도 되지만 전투 중 변하는 값은 상태에 직접 보관한다.

MCTS AI를 Unity 게임 루프에 어떻게 연결할까?

1. 게임 규칙을 화면 코드에서 분리한다

GetLegalActions(), Apply(CardAction), IsGameOver, GetWinner()를 BattleState에 둔다. 이 네 가지가 서로 다른 규칙을 사용하면 MCTS의 시뮬레이션 결과가 실제 전투와 달라진다.

2. 시간 예산 안에서 반복한다

프레임을 오래 점유하지 않도록 반복 횟수보다 시간 예산을 사용한다. 예를 들어 일반 난이도에서는 30ms, 높은 난이도에서는 150ms를 줄 수 있다. Unity 메인 스레드에서 실행한다면 한 프레임에 전부 계산하지 말고 코루틴 또는 작업 분할로 처리한다.

public static class MctsSearch
{
    public static CardAction FindBestAction(BattleState rootState, int iterations, int seed)
    {
        var random = new Random(seed);
        var root = new MctsNode(rootState);
        const float exploration = 1.41421356f;

        for (int i = 0; i < iterations; i++)
        {
            MctsNode node = root;

            while (!node.IsTerminal && node.UntriedActions.Count == 0)
                node = node.SelectChild(exploration);

            if (!node.IsTerminal && node.UntriedActions.Count > 0)
                node = node.Expand(random);

            float reward = Rollout(node.State, rootState.CurrentPlayer, random);
            node.Backpropagate(reward);
        }

        return root.Children
            .OrderByDescending(child => child.Visits)
            .First().ActionFromParent;
    }

    private static float Rollout(BattleState state, int rootPlayer, Random random)
    {
        const int maxActions = 80;
        for (int i = 0; i < maxActions && !state.IsGameOver; i++)
            state = state.Apply(state.GetRolloutAction(random));

        if (state.IsGameOver)
            return state.GetWinner() == rootPlayer ? 1f : 0f;

        return 0.5f + Math.Clamp(state.Evaluate(rootPlayer) / 200f, -0.5f, 0.5f);
    }
}

3. 가장 많이 방문한 루트 행동을 선택한다

최종 행동은 평균 보상이 아니라 방문 횟수가 가장 많은 자식을 선택하는 것이 일반적이다. UCT의 탐험 보너스는 탐색 중에만 필요하며 실제 플레이에서는 가장 많은 탐색 예산을 받은 행동이 더 안정적이다.

MCTS 성능 병목은 왜 발생하며 어떻게 줄일까?

가장 흔한 병목은 노드 객체 수보다 BattleState 복제와 GetLegalActions()의 반복 할당이다. Unity Profiler에서 GC.Alloc이 반복마다 증가한다면 탐색 품질보다 먼저 상태 표현을 줄여야 한다.

병목	원인	최소한의 개선
GC 스파이크	`List`, LINQ, 문자열을 매 시뮬레이션 생성	롤아웃 경로에서는 재사용 가능한 버퍼와 `struct` 행동을 사용한다.
느린 상태 복제	필드·손패 컬렉션을 깊게 복사	고정 크기 배열 또는 복사 비용이 작은 값 타입 상태를 사용한다.
행동 수 폭증	대상 조합과 선택 순서가 많음	명백히 지배당하는 행동을 규칙 기반으로 제거한다.
약한 플레이	무작위 롤아웃	처치, 피해, 생존을 우선하는 간단한 정책을 넣는다.
결정성 부족	전역 난수 사용	탐색마다 `System.Random(seed)`를 만들고 리플레이에 시드를 기록한다.

성능 개선은 다음 순서가 안전하다.

Unity Profiler에서 GC.Alloc, BattleState.Apply, 행동 생성 시간을 측정한다.
실제 전투 규칙과 시뮬레이션 규칙이 같은지 자동 테스트로 확인한다.
그다음에만 풀링, 배열화, 병렬 탐색을 적용한다.

Task 병렬화는 상태가 완전히 독립적이고 Unity API에 접근하지 않을 때만 고려한다. 공유 트리를 잠그는 병렬 MCTS는 잠금 비용과 재현성 문제가 생기므로 먼저 독립 트리를 여러 개 돌린 뒤 루트 통계를 합치는 방식이 구현 난도가 낮다.

Unity Profiler에서 MCTS 상태 복제와 행동 생성의 GC 할당량을 비교하는 화면

카드 배틀의 랜덤성과 숨은 정보는 MCTS에서 어떻게 처리할까?

카드 뽑기, 치명타, 랜덤 대상 같은 확률 사건은 행동 노드와 별도로 확률 노드로 모델링할 수 있다. 다만 모든 결과를 트리에 펼치면 분기 수가 증가하므로 초기 구현에서는 롤아웃 중 시드 기반 난수로 결과를 샘플링하는 편이 현실적이다.

상대 손패와 덱 순서가 숨겨진 게임은 현재 보이는 정보만으로 하나의 상태를 만들면 안 된다. 관측 가능한 정보와 모순되지 않는 상대 손패·덱을 하나 샘플링한 뒤 MCTS를 실행하는 determinization을 여러 번 수행한다. 이 방식은 구현이 단순하지만 정보 집합 문제를 완전히 해결하지는 않으므로 경쟁 수준 AI가 필요할 때 ISMCTS(Information Set MCTS)를 검토한다.

자주 묻는 질문 (FAQ)

MCTS 반복 횟수는 몇 번이 적당한가?

고정 숫자보다 기기별 시간 예산이 낫다. 먼저 목표 프레임과 AI 대기 시간을 정하고 그 안에서 가능한 반복 횟수를 측정한다. 수백 회로 시작해 전투 로그와 승률을 보며 늘린다.

UCT 탐색 상수 C는 얼마로 시작해야 하는가?

보상 범위가 0~1이면 $\sqrt{2}$ 인 약 1.414를 기준값으로 쓴다. AI가 같은 수만 반복하면 값을 높이고 의미 없는 수를 너무 오래 시험하면 낮춘다.

미니맥스보다 MCTS가 항상 좋은가?

아니다. 행동 수가 작고 평가 함수가 신뢰할 수 있으며 짧은 전술을 정확히 읽어야 하는 게임은 알파-베타 가지치기 미니맥스가 더 예측 가능할 수 있다. 카드 생성과 확률, 가변 분기 수가 큰 경우에 MCTS의 장점이 커진다.

정리

MCTS의 핵심은 복잡한 카드 배틀을 완벽히 해석하는 것이 아니라 제한된 시간 안에 좋은 행동을 더 많이 시험하는 데 있다. Unity 구현에서는 순수 C# 상태 모델을 먼저 만들고 UCT 선택과 가벼운 롤아웃 정책을 붙인 뒤 Profiler로 상태 복제 비용을 줄이는 순서가 가장 안정적이다.