한양과학기술고등학교

완벽한 AI와 틱택토 대결

게임 트리에서 점수 끌어올리기

핵심 아이디어 3가지

알파-베타 미니맥스 (핵심 로직)

def minimax(state, depth, alpha, beta, maximizing):
    if depth == 0 or state.is_over():
        return state.evaluate()          # 잎의 점수

    if maximizing:                          # 내 차례 → 최댓값
        value = -INF
        for move in state.moves():
            value = max(value, minimax(state.play(move), depth-1, alpha, beta, False))
            alpha = max(alpha, value)
            if alpha >= beta:
                break                          # β 컷 — 남은 형제 가지치기
        return value
    else:                                   # 상대 차례 → 최솟값
        value = INF
        for move in state.moves():
            value = min(value, minimax(state.play(move), depth-1, alpha, beta, True))
            beta = min(beta, value)
            if alpha >= beta:
                break                          # α 컷
        return value

# 첫 호출: best = argmax_move  minimax(root.play(move), D, -INF, +INF, False)

• 결과는 동일: 알파-베타는 미니맥스와 정확히 같은 수를 고른다. 단지 볼 필요 없는 가지를 건너뛸 뿐이다.
• 탐색 순서가 중요: 좋은 수를 먼저 보면 컷이 빨리 일어난다. 이상적으로는 트리 크기가 b^d → b^(d/2) 로 줄어 같은 시간에 2배 깊이를 본다.
• 깊이 제한 + 평가 함수: 체스·바둑은 트리가 무한히 커서 몇 수만 내다보고 evaluate() 로 국면을 점수화한다.
• 승리에 10 - depth 처럼 깊이를 섞으면 "이왕 이길 거 빨리, 이왕 질 거 늦게"를 선호하게 된다.

어디에 쓰이나