코드: 최선의 수 반환하기

best_move 함수가 추가된 게 핵심. minimax는 점수만 알려주는데, 실제로 두려면 "그 점수를 만드는 수"가 필요.

로직: 가능한 모든 수에 대해 minimax를 돌려본 뒤, 그중 가장 좋은 점수를 만드는 수를 고른다.

실행 결과를 보면 두 AI가 9수 끝까지 둬서 무승부. 예상 점수가 처음부터 끝까지 0 — 양쪽 다 처음부터 "비길 거라는 걸 알고" 둬.

💡 완벽한 정보 게임의 운명

완벽한 정보 게임(서로의 상태가 다 보이는 게임 — 바둑, 체스, 틱택토 등)에서는 양쪽이 최선을 두면 결과가 정해져 있어. 운이나 우연이 없거든. 그래서 두 사람이 둘 다 완벽하면 항상 같은 결과가 나와.

틱택토는 무승부. 체커도 무승부. 5x5 바둑은 흑 25집 승. 19x19 바둑은? — 모름. 너무 커서 못 풀어.

이제 또 한 가지 — minimax는 정말 모든 노드를 다 보나? 그렇지. 그래서 느려. 그런데 잠깐 — 진짜 다 봐야 할까? 다음 챕터에서 답이 나와.

PYTHON

# 위 코드는 점수만 반환. 실제 AI를 만들려면 "어떤 수를 둘지"도 알아야 함.
# best_move 함수를 추가하자.

EMPTY, X, O = ' ', 'X', 'O'

def initial_state(): return ([EMPTY]*9, X)

def possible_moves(state):
    board, turn = state
    return [((board[:i]+[turn]+board[i+1:], O if turn==X else X), i)
            for i in range(9) if board[i] == EMPTY]

def is_terminal(state):
    board, _ = state
    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)]
    for a, b, c in lines:
        if board[a] != EMPTY and board[a] == board[b] == board[c]:
            return True, board[a]
    if EMPTY not in board: return True, 'draw'
    return False, None

def minimax(state, is_max):
    terminal, winner = is_terminal(state)
    if terminal:
        if winner == X: return 1
        if winner == O: return -1
        return 0
    if is_max:
        return max(minimax(child, False) for child, _ in possible_moves(state))
    else:
        return min(minimax(child, True) for child, _ in possible_moves(state))


# === 최선의 수 찾기 ===
def best_move(state):
    """현재 상태에서 둘 최선의 수와 그 점수 반환"""
    _, turn = state
    is_max = (turn == X)
    best_score = -float('inf') if is_max else float('inf')
    best_pos = None
    for child, pos in possible_moves(state):
        score = minimax(child, not is_max)
        if is_max and score > best_score:
            best_score, best_pos = score, pos
        elif not is_max and score < best_score:
            best_score, best_pos = score, pos
    return best_pos, best_score


# === 시뮬레이션: 완벽한 AI vs 완벽한 AI ===
print("=== 완벽한 AI vs 완벽한 AI 시뮬레이션 ===")
state = initial_state()
move_num = 1
while True:
    terminal, winner = is_terminal(state)
    if terminal:
        print(f"\n=== 게임 종료: {winner} ===")
        break
    pos, score = best_move(state)
    board, turn = state
    r, c = pos // 3, pos % 3
    print(f"수 {move_num}: {turn}이 ({r},{c})에 둠 (예상 점수 {score:+d})")
    # 한 수 둠
    new_board = board[:]
    new_board[pos] = turn
    next_turn = O if turn == X else X
    state = (new_board, next_turn)
    move_num += 1

# 최종 보드 출력
print("\n최종 보드:")
board, _ = state
for r in range(3):
    print(' | '.join(board[r*3:(r+1)*3]))
    if r < 2: print('-' * 9)

출력

기대 출력:

=== 완벽한 AI vs 완벽한 AI 시뮬레이션 ===
수 1: X이 (0,0)에 둠 (예상 점수 +0)
수 2: O이 (1,1)에 둠 (예상 점수 +0)
수 3: X이 (0,1)에 둠 (예상 점수 +0)
수 4: O이 (0,2)에 둠 (예상 점수 +0)
수 5: X이 (2,0)에 둠 (예상 점수 +0)
수 6: O이 (1,0)에 둠 (예상 점수 +0)
수 7: X이 (1,2)에 둠 (예상 점수 +0)
수 8: O이 (2,1)에 둠 (예상 점수 +0)
수 9: X이 (2,2)에 둠 (예상 점수 +0)

=== 게임 종료: draw ===

최종 보드:
X | X | O
---------
O | O | X
---------
X | O | X

← 이전 깊이 제한 + Heuristic — 끝까지 못 갈 때 다음 → 확인 퀴즈