게임 이론 알고리즘: Nash 균형과 Minimax, Alpha-Beta 가지치기

상대의 반응까지 모델에 넣는 알고리즘

게임 이론 알고리즘은 대립적 환경에서 상대의 선택을 고려해 자신의 행동을 결정하는 데 쓰인다. 보드게임 AI뿐 아니라 경매와 가격 전략, 보안 게임, 강화학습처럼 여러 참여자의 선택이 결과에 영향을 주는 문제에도 적용할 수 있다.

Nash Equilibrium은 각 참여자가 다른 참여자의 전략을 고정해 놓았을 때, 자신의 전략만 바꿔 보수를 더 높일 수 없는 전략 조합을 뜻한다. 순수 전략과 혼합 전략의 균형이 있으며, 일반 게임에서는 계산 복잡도가 높다. 제로섬 게임에서는 Minimax 정리와 연결되고, 균형값은 게임값과 일치한다.

Minimax는 완전정보 2인 제로섬 게임에서 상대가 가장 불리한 반응을 한다고 보고 손실을 최소화하는 절차다. 게임 트리를 끝까지 탐색할 수도 있고, 깊이를 제한한 뒤 평가 함수로 값을 근사할 수도 있다. 완전 탐색에서는 최적성이 보장되지만, 현실적인 상태 공간에서는 깊이 제한과 휴리스틱이 필요하다.

Alpha-Beta Pruning은 Minimax 탐색 중 α와 β 경계를 유지해 더 볼 필요가 없는 가지를 끊는다. 경계를 올바르게 유지한다는 전제 아래 최종 값은 바뀌지 않으며, 탐색 노드는 크게 줄어든다. 수순 정렬이 이상적이면 시간복잡도는 O(b^(d/2)) 수준까지 개선될 수 있다.

문제의 형태가 알고리즘 선택을 결정한다

먼저 정규형 게임과 전개형 게임을 구분해야 한다. 정규형은 전략과 보수 행렬로 표현하고, 전개형은 상태와 행동의 전이를 게임 트리로 다룬다.

모델에는 상태 공간, 합법 수, 전이 규칙, 보상 함수 또는 유틸리티가 들어간다. 제로섬인지 일반합인지, 완전정보인지 불완전정보인지, 동시 의사결정인지 순차 의사결정인지도 명시해야 한다.

정규형 게임에서는 베스트 리스폰스 반복, 이원행렬 게임을 위한 Lemke–Howson, 선형계획 기반 접근으로 균형을 계산할 수 있다. 트리 기반 문제에서는 Minimax의 역진 유도에 깊이 제한과 휴리스틱을 결합한다. Alpha-Beta의 효과는 수순 정렬의 품질에 크게 좌우된다.

깊이를 제한하면 평가 함수가 성능과 정확도의 균형을 결정한다. 가산형·비가산형 특징과 모노토닉·일관성은 평가 함수 설계에서 고려할 대상이다. 수평선 효과를 줄이기 위해 쿼이스센스 탐색, 캡처 또는 체크 연장 같은 보완도 필요하다.

탐색을 줄이면서 결과를 유지하는 흐름

⤢✕

입력은 상태, 깊이, α·β 경계, 플레이어 식별자다. 터미널 상태를 확인한 뒤 자식 상태를 생성하고 정렬하며, 재귀 호출 결과로 경계를 갱신한다. β가 α 이하가 되는 시점에는 해당 경로를 더 탐색하지 않는다. 시간 초과 시에는 현재 최선값을 반환하는 정책을 둘 수 있다.

균형 계산과 트리 탐색의 차이

지표	Nash Equilibrium	Minimax	Alpha-Beta Pruning
성능	일반 게임 계산 난해, 소규모/이원행렬에 적합	b^d로 급증, 깊이 제한 및 휴리스틱 필수	이상적 정렬 시 b^(d/2)까지 감소, 실전 체감 크다
확장성	플레이어/전략 증가 시 급격한 복잡도	큰 상태공간에서는 단독 사용 곤란	정렬·TT 결합 시 대규모 트리에도 실용
일관성	균형 개념상 안정적 해석 제공	완전탐색 시 최적성 보장	경계 유지 시 결과 불변, 근사 탐색과 병행 시 주의
안정성	다중 균형 존재 시 선택 민감	평가 함수/깊이 설정에 민감	수순 정렬 품질·해시 충돌 관리 필요
운영 편의	정규형 게임 도구 필요, 입력 제작 비용	구현 단순, 디버깅 용이	추가 구조(정렬·TT·시간관리) 요구

도메인에 따른 적용 방식

보드게임과 퍼즐 AI에서는 게임 규칙, 합법 수 생성기, 평가 함수의 특징 벡터를 준비한다. Minimax와 Alpha-Beta, 반복 심화, 시간 예산 기반 중단을 결합하고 Zobrist 해시, Transposition Table, 비트보드 최적화를 사용할 수 있다.

광고 입찰이나 B2B 가격 같은 경매·가격 전략에서는 수요 탄력성, 경쟁자 반응 모델, 비용 구조를 입력으로 둔다. 최적 반응 반복으로 혼합 전략 내쉬 균형을 근사하고 민감도를 분석한다. 선형·비선형 최적화, Lemke–Howson, 시뮬레이션이 여기에 쓰인다.

레드팀·블루팀과 패트롤 경로를 포함한 보안·적대적 계획은 자산 가치, 공격 확률, 순찰 제약을 모델에 넣는다. 최소최대 위험을 Minimax로 최적화하고 Stackelberg 변형을 적용할 수 있으며, 수리계획(MILP)과 샘플링 기반 시뮬레이션을 함께 사용한다.

Self-Play 강화학습에서는 정책·가치 신경망과 리플레이 버퍼를 기반으로 자가 대전을 수행한다. 이를 통해 근사 균형 수렴을 시도하며, 탐색 가이드에는 MCTS 또는 αβ 대체를 둘 수 있다. 분산 학습, 온폴리시·오프폴리시 혼합, 정규화·KL 패널티도 관련 도구다.

Alpha-Beta를 적용한 Tic-Tac-Toe

Python 3.11+ 환경과 외부 의존성 없이, 2인 제로섬 완전정보 게임을 가정한다. X는 MAX, O는 MIN으로 둔다.

from typing import List, Optional, Tuple

Player = str  # 'X' or 'O'
Board = List[str]  # length 9, each in {'X','O',' '}

WIN_LINES = [(0,1,2),(3,4,5),(6,7,8),
             (0,3,6),(1,4,7),(2,5,8),
             (0,4,8),(2,4,6)]

def winner(board: Board) -> Optional[Player]:
    for a,b,c in WIN_LINES:
        if board[a] != ' ' and board[a] == board[b] == board[c]:
            return board[a]
    return None

def terminal(board: Board) -> bool:
    return winner(board) is not None or all(c != ' ' for c in board)

def evaluate(board: Board) -> int:
    w = winner(board)
    if w == 'X': return 1
    if w == 'O': return -1
    return 0  # draw or non-terminal depth-limited case

def legal_moves(board: Board) -> List[int]:
    return [i for i,c in enumerate(board) if c == ' ']

def apply_move(board: Board, idx: int, p: Player) -> Board:
    nb = board.copy()
    nb[idx] = p
    return nb

def alphabeta(board: Board, depth: int, alpha: int, beta: int, player: Player) -> Tuple[int, Optional[int]]:
    if terminal(board) or depth == 0:
        return evaluate(board), None

    moves = legal_moves(board)
    # simple move-ordering: center > corners > edges
    order = sorted(moves, key=lambda m: (m != 4, m not in (0,2,6,8)))
    best_move = None

    if player == 'X':  # MAX
        value = -10**9
        for m in order:
            val, _ = alphabeta(apply_move(board, m, 'X'), depth-1, alpha, beta, 'O')
            if val > value:
                value, best_move = val, m
            alpha = max(alpha, value)
            if beta <= alpha:
                break
        return value, best_move
    else:  # MIN
        value = 10**9
        for m in order:
            val, _ = alphabeta(apply_move(board, m, 'O'), depth-1, alpha, beta, 'X')
            if val < value:
                value, best_move = val, m
            beta = min(beta, value)
            if beta <= alpha:
                break
        return value, best_move

def best_action(board: Board, player: Player, max_depth: int = 9) -> int:
    val, move = alphabeta(board, max_depth, -10**9, 10**9, player)
    assert move is not None, "No legal moves"
    return move

if __name__ == "__main__":
    # Example: X to play
    b = ['X','O','X',
         ' ','O',' ',
         ' ',' ',' ']
    move = best_action(b, 'X', max_depth=9)
    print("Best move index:", move)

시간 예산이 있는 환경에서는 반복 심화로 d=1→…→D까지 순차적으로 깊이를 늘리고, 타임아웃 시 마지막으로 완성한 깊이의 결과를 반환한다. 평가 함수에는 승·패·무승부 외에 두 줄 위협 같은 패턴을 가중치로 더할 수 있다. 입력 검증과 무효 상태 방지, 재현성을 위한 난수 사용 억제도 함께 다뤄야 한다.

탐색 비용과 운영 효율

b=35, d=8이라고 가정하면 완전탐색 노드 수는 ≈ 35^8 ≈ 2.25×10^12다. 이상적으로 수순을 정렬한 Alpha-Beta를 적용하면 ≈ 35^(8/2) = 35^4 ≈ 1.50×10^6까지 줄일 수 있다. 100k 노드/초 엔진 기준으로 완전탐색이 불가능한 문제를 약 15초 내에 의사결정할 수 있다.

내쉬 균형에 기반한 정책은 상대 반응을 고려한 일관된 전략을 제공한다. Minimax와 αβ는 최악 대응에 대비한 성능을 보장하고 변동성을 줄인다. 반복 심화와 TT를 결합하면 같은 시간 안에 더 깊은 탐색에 도달할 수 있으며, 수순 정렬과 캐시는 CPU·메모리 사용 효율도 높인다.