Minimax + 알파-베타 적용

실행 결과 핵심 두 가지:

빈 보드에서 점수 0. 양쪽이 최선을 두면 무승부.
O가 실수하니까 X가 (0,2)에 두면서 즉시 이김 결정. 이게 "응징" 동작.

💡 minimax_ab의 한 가지 추가

지난 챕터의 알파-베타는 점수만 반환했어. 여기서는 (점수, 최선의 수) 튜플 반환. 같은 알고리즘이지만 실전 사용에 필요한 정보 추가.

이 한 줄 추가가 "이론"에서 "실제 AI"로 가는 다리.

⚠️ 알파-베타 없이는 이게 가능할까

틱택토는 작아서 알파-베타 없이도 동작. 다만 노드 약 55만 개 봐야 함 (3초 정도). 알파-베타로는 1.8만 개 (0.1초). 사용성에 차이.

체스나 바둑이면 차이가 압도적. 알파-베타 없으면 1수에 며칠 걸림.

이제 진짜 AI 두 개를 서로 붙여보자. 항상 무승부 나와야 함.

PYTHON

# TicTacToe 클래스 위에 알파-베타 minimax를 입힌다.
# 결과: 완벽한 AI.

class TicTacToe:
    EMPTY, X, O = ' ', 'X', 'O'
    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 __init__(self, board=None, turn=None):
        self.board = board if board is not None else [self.EMPTY]*9
        self.turn = turn or self.X

    def show(self):
        for r in range(3):
            print(' | '.join(self.board[r*3:(r+1)*3]))
            if r < 2: print('-'*9)

    def possible_moves(self):
        return [i for i in range(9) if self.board[i] == self.EMPTY]

    def play(self, pos):
        nb = self.board[:]; nb[pos] = self.turn
        return TicTacToe(nb, self.O if self.turn == self.X else self.X)

    def winner(self):
        for a, b, c in self.LINES:
            if self.board[a] != self.EMPTY and self.board[a] == self.board[b] == self.board[c]:
                return self.board[a]
        if self.EMPTY not in self.board: return 'draw'
        return None

    def score(self):
        w = self.winner()
        return {self.X: 1, self.O: -1, 'draw': 0}.get(w)


# === 알파-베타 Minimax ===
def minimax_ab(game, alpha=-float('inf'), beta=float('inf')):
    """현재 game 상태의 minimax 값 + 최선의 수 반환"""
    score = game.score()
    if score is not None:
        return score, None  # 끝난 상태

    is_max = (game.turn == TicTacToe.X)
    best_pos = None

    if is_max:
        v = -float('inf')
        for pos in game.possible_moves():
            child_score, _ = minimax_ab(game.play(pos), alpha, beta)
            if child_score > v:
                v, best_pos = child_score, pos
            alpha = max(alpha, v)
            if beta <= alpha: break
        return v, best_pos
    else:
        v = float('inf')
        for pos in game.possible_moves():
            child_score, _ = minimax_ab(game.play(pos), alpha, beta)
            if child_score < v:
                v, best_pos = child_score, pos
            beta = min(beta, v)
            if beta <= alpha: break
        return v, best_pos


# === 검증 1: 빈 보드 평가 ===
print("=== 빈 보드 평가 ===")
g = TicTacToe()
score, best = minimax_ab(g)
print(f"점수: {score} (0=무승부 예상)")
print(f"최선의 첫 수: 자리 {best} = ({best//3},{best%3})")
print()

# === 검증 2: 상대 실수 응징 ===
print("=== 시나리오: 상대(O)가 실수했을 때 응징 ===")
print("X(0,0), O(1,1), X(0,1) 후 O 차례. O가 (0,2)를 막아야 하는데 (2,2)에 두는 실수")
g = TicTacToe()
g = g.play(0)  # X (0,0)
g = g.play(4)  # O (1,1)  
g = g.play(1)  # X (0,1)  ← X가 가로 위협
g = g.play(8)  # O (2,2)  ← 실수! (0,2)를 막았어야

print("현재 보드:")
g.show()
score, best = minimax_ab(g)
print(f"X의 다음 수: 자리 {best} = ({best//3},{best%3})")
print(f"예상 점수: {score} (1=X 승)")

출력

기대 출력:

=== 빈 보드 평가 ===
점수: 0 (0=무승부 예상)
최선의 첫 수: 자리 0 = (0,0)

=== 시나리오: 상대(O)가 실수했을 때 응징 ===
X(0,0), O(1,1), X(0,1) 후 O 차례. O가 (0,2)를 막아야 하는데 (2,2)에 두는 실수
현재 보드:
X | X |  
---------
  | O |  
---------
  |   | O
X의 다음 수: 자리 2 = (0,2)
예상 점수: 1 (1=X 승)

← 이전 게임 상태 클래스 다음 → AI vs AI — 항상 무승부