홀덤 승률 몬테카를로 시뮬레이션 성능 개선

몬테카를로 시뮬레이션 횟수를 늘리면 Unity 게임이 눈에 띄게 느려지는 성능 문제가 생겼다.

문제 상황

증상

• 시뮬레이션 10회: 정상 동작
• 시뮬레이션 1000회: 게임이 눈에 띄게 느려짐
• 승률 계산 중 프레임 드롭 발생

영향 범위

• MonteCarloSimulator.cs
• HoldemGame.cs
• 플레이어 4명 기준 시뮬레이션 로직

발생 원인

1. O(n²) 복잡도의 카드 조회

GenerateAvailableCards 메서드 내부 코드:

// GenerateAvailableCards 메서드 내부
if (!usedCards.Any(c => c.Suit == card.Suit && c.Rank == card.Rank))
{
    availableCards.Add(card);
}

• LINQ .Any()가 매번 사용한 카드 리스트 전체를 순회한다.
• 52장을 만드는 이중 루프 안에서 호출되므로, 덱 크기를 n, 사용한 카드 수를 m이라 하면 한 번 호출에 O(n·m)이다.
• 4명 기준 사용한 카드는 홀 카드 8장이라, 시뮬레이션 한 번에 52 × 8 = 416번 비교한다. 1000번 시뮬레이션이면 416,000번이다.

2. 반복적인 전체 덱 생성

private List<Card> GenerateAvailableCards(List<Card> usedCards)
{
    var availableCards = new List<Card>();

    // 매번 52장의 카드를 처음부터 생성
    for (int suit = 0; suit < 4; suit++)
    {
        for (int rank = 0; rank < 13; rank++)
        {
            var card = new Card((Suit)suit, (Rank)rank);
            // ... O(n) 조회
        }
    }
}

• 시뮬레이션마다 52장의 덱을 처음부터 다시 만든다.
• 1000번 시뮬레이션 시 52,000장의 카드 객체가 생성된다.

3. 과도한 객체 할당(GC 압박)

// Line 115, 128: 매 반복마다 새 List 생성
var communityCards = GenerateRandomCommunityCards();

// Line 227, 256: 매 반복마다 새 usedCards List 생성
var usedCards = new List<Card>();

// Line 194, 230, 259: 불필요한 ToList() 호출
var holeCards = _virtualPlayers[i].HoleCards.ToList();

• 시뮬레이션마다 List<Card> 객체를 여러 개 만든다.
• 1000번 시뮬레이션 시 약 5,000개 이상의 List가 할당된다.
• GC 압박이 커져 프레임 드롭으로 이어진다.

4. 연산량 요약(4명 기준)

시뮬레이션 횟수	카드 생성	LINQ 비교	List 할당	총 연산
10회	520장	4,160번	~50개	적음
1000회	52,000장	416,000번	~5,000개	매우 많음

해결 방법

1. HashSet을 사용한 O(1) 카드 조회

변경 전:

// O(n) 조회 - 리스트 전체 순회
if (!usedCards.Any(c => c.Suit == card.Suit && c.Rank == card.Rank))

변경 후:

// O(1) 조회 - HashSet 사용
private struct CardKey : IEquatable<CardKey>
{
    public readonly Suit Suit;
    public readonly Rank Rank;

    public override int GetHashCode()
    {
        return ((int)Suit << 16) | (int)Rank;  // 빠른 해시 계산
    }
}

// 사용
var usedCardKeys = new HashSet<CardKey>();
if (!usedCardKeys.Contains(cardKey))  // O(1) 조회

효과: 카드 하나의 사용 여부 확인이 O(m)에서 O(1)로 바뀌어, 한 번 호출이 O(n·m)에서 O(n)이 된다. 시뮬레이션 한 번에 리스트 비교 416번이 HashSet 조회 52번으로 바뀐다(1000번 기준 416,000번 → 52,000번).

2. 불필요한 ToList() 호출 제거

변경 전:

var holeCards = _virtualPlayers[i].HoleCards.ToList();  // 불필요한 복사
var hand = _cardEvaluator.EvaluateHand(holeCards, communityCards);

변경 후:

// IReadOnlyList를 직접 전달
var hand = _cardEvaluator.EvaluateHand(_virtualPlayers[i].HoleCards, communityCards);

효과: 1000번 시뮬레이션 시 10,000번의 ToList() 호출이 사라진다.

3. List 용량 사전 할당

변경 전:

var communityCards = new List<Card>();  // 기본 용량
var hands = new List<Hand>();           // 기본 용량

변경 후:

var communityCards = new List<Card>(5);              // 5장 사전 할당
var hands = new List<Hand>(_virtualPlayers.Count);  // 플레이어 수만큼 사전 할당
var availableCards = new List<Card>(52 - usedCardKeys.Count);  // 예상 용량 할당

효과: 동적 배열 재할당을 막아 메모리 재할당 횟수를 최소화한다.

4. 효율적인 카드 수집 로직

변경 전:

var usedCards = new List<Card>();
for (int i = 0; i < _virtualPlayers.Count; i++)
{
    var holeCards = _virtualPlayers[i].HoleCards.ToList();  // ToList() 복사
    usedCards.AddRange(holeCards);
}

변경 후:

var usedCardKeys = new HashSet<CardKey>();
for (int i = 0; i < _virtualPlayers.Count; i++)
{
    var holeCards = _virtualPlayers[i].HoleCards;  // 직접 참조
    for (int j = 0; j < holeCards.Count; j++)
    {
        usedCardKeys.Add(new CardKey(holeCards[j]));  // 구조체 생성
    }
}

효과: 리스트 복사를 없애고 HashSet을 써서 메모리 사용량과 연산이 함께 줄어든다.

최적화 세부 내용

수정한 파일

1. MonteCarloSimulator.cs
   • CardKey 구조체 추가
   • GenerateAvailableCards 최적화
   • GenerateRandomCommunityCards 최적화
   • GenerateRandomTurnRiverCards 최적화
   • RunSingleSimulation 최적화
2. HoldemGame.cs
   • 시뮬레이션 횟수 변경: 10 → 1000

최적화 요약

최적화 항목	변경 전	변경 후	개선 효과
카드 조회 복잡도(호출당)	O(n·m) LINQ Any()	O(n) HashSet Contains()	카드당 확인이 O(m) → O(1)
카드 확인 횟수(1000회)	리스트 비교 416,000번	HashSet 조회 52,000번	1/8
카드 객체 생성	52,000장	52,000장	동일(불가피)
List 할당	~5,000개	~1,000개	80% 감소
ToList() 호출	10,000번	0번	100% 제거
메모리 재할당	빈번함	최소화	사전 할당으로 개선

성능 개선 결과

최적화 전

시뮬레이션 10회:  정상 동작 ✅
시뮬레이션 1000회: 매우 느림 ❌ (게임 플레이 불가능)

연산량:
- 카드 비교: 416,000번
- 객체 할당: ~5,000개
- ToList() 호출: 10,000번

최적화 후

시뮬레이션 10회:  빠름 ✅
시뮬레이션 1000회: 빠름 ✅ (게임 플레이 가능)

연산량:
- 카드 확인: HashSet 조회 52,000번 (리스트 비교 416,000번 대체)
- 객체 할당: ~1,000개 (80% 감소)
- ToList() 호출: 0번 (100% 제거)

효과

• GC 압박: List 할당 80% 감소
• 프레임 드롭: 해결

결론

개선 사항

1. 카드 조회를 O(n·m)에서 O(n)으로 개선(HashSet 사용)
2. 불필요한 객체 할당 80% 감소(ToList() 제거와 사전 할당)
3. 시뮬레이션 횟수 100배 증가(10회 → 1000회)
4. 표본 수 증가로 승률 계산의 통계적 신뢰도 향상

배운 점

• 이번 문제에서 성능에 가장 큰 영향을 준 것은 알고리즘 복잡도였다.
• 불필요한 객체 할당은 GC 압박을 일으켜 프레임 드롭으로 이어진다.
• 구조체 키와 HashSet을 조합하면 카드 조회가 O(1)이 된다.

팁

성능은 Unity Profiler로 측정한다.