🔍 인공지능 탐색 알고리즘 - 게임 탐색 알고리즘

📌 1. 게임 탐색 알고리즘이란?

✅ 게임 탐색 알고리즘이란?

게임 탐색 알고리즘(Game Search Algorithm)은 AI가 게임 내에서 최적의 전략을 찾기 위해 가능한 모든 수를 탐색하고 평가하는 방식입니다.
이 알고리즘들은 상대방의 행동을 고려하여 최고의 결정을 내리는 데 사용됩니다.

📌 게임 탐색 알고리즘의 특징
✔ 적의 움직임을 예측하여 최적의 수를 찾음
✔ 승리 확률을 높이기 위해 다양한 경우의 수를 평가
✔ 완전한 탐색이 어려운 경우, 휴리스틱 함수를 활용하여 탐색을 최적화

📌 게임 탐색 알고리즘이 사용되는 분야

• 체스, 바둑, 장기 → 전략적인 턴 기반 게임

• 스타크래프트, 롤(LoL), Dota 2 → 실시간 전략 게임(RTS)

• 틱택토(Tic-Tac-Toe), 오목 → 간단한 게임 AI

📌 2. 미니맥스 알고리즘(Mini-Max Algorithm)

✅ 미니맥스 알고리즘이란?

미니맥스(Mini-Max) 알고리즘은 최적의 전략을 선택하기 위해 두 플레이어의 최선의 수를 가정하고 탐색하는 방법입니다.
즉, 내가 최선의 수를 선택하고, 상대방은 나에게 최악의 수를 선택한다고 가정하여 게임을 탐색합니다.

📌 미니맥스 알고리즘의 핵심 원리

• Max 플레이어 (AI) → 가장 높은 점수를 얻는 수를 선택

• Min 플레이어 (상대방) → AI가 가장 낮은 점수를 얻도록 방해하는 수를 선택

• 게임 트리를 탐색하여 최적의 수를 결정

🔍 미니맥스 알고리즘 동작 과정

1. 현재 상태에서 가능한 모든 수를 트리 형태로 확장

2. 최하단(리프) 노드에서 승패를 평가하여 점수를 부여

3. Min 레벨에서는 최솟값을 선택, Max 레벨에서는 최댓값을 선택

4. 루트 노드까지 반복하여 최적의 선택 결정

✅ 미니맥스 알고리즘 코드 구현 (Python)

def minimax(depth, node_index, maximizing_player, scores, height):
    if depth == height:
        return scores[node_index]

    if maximizing_player:
        return max(minimax(depth + 1, node_index * 2, False, scores, height),
                   minimax(depth + 1, node_index * 2 + 1, False, scores, height))
    else:
        return min(minimax(depth + 1, node_index * 2, True, scores, height),
                   minimax(depth + 1, node_index * 2 + 1, True, scores, height))

scores = [3, 5, 2, 9, 12, 5, 23, 23]
height = 3
print("최적의 값:", minimax(0, 0, True, scores, height))

📌 미니맥스 알고리즘 실행 결과 예시

최적의 값: 12

💡 미니맥스 알고리즘은 최적의 전략을 보장하지만, 게임 트리가 크면 연산량이 급격히 증가할 수 있음!

📌 3. 알파-베타 가지치기(α-β Pruning)

✅ α-β 가지치기란?

알파-베타 가지치기(Alpha-Beta Pruning)는 미니맥스 알고리즘에서 불필요한 탐색을 줄여 속도를 개선하는 방법입니다.
즉, 승패에 영향을 주지 않는 가지를 잘라내어 연산량을 줄입니다.

📌 알파(α)와 베타(β)의 개념

• 알파(α) → Max 플레이어(내가)에게 가장 좋은 값 (최댓값)

• 베타(β) → Min 플레이어(상대방)에게 가장 좋은 값 (최솟값)

• α ≥ β가 되는 경우 탐색을 중단 (가지치기 발생)

🔍 알파-베타 가지치기 동작 과정

1. 미니맥스 알고리즘과 동일한 방식으로 트리를 탐색

2. Max 노드에서 현재 최상의 선택(α)을 저장하고, 더 좋은 선택이 나타나면 업데이트

3. Min 노드에서 현재 최상의 선택(β)을 저장하고, 더 낮은 값이 나타나면 업데이트

4. 만약 α ≥ β가 되면 탐색을 중단(가지치기 수행)

✅ 알파-베타 가지치기 코드 구현 (Python)

def alpha_beta(depth, node_index, maximizing_player, scores, alpha, beta, height):
    if depth == height:
        return scores[node_index]

    if maximizing_player:
        max_value = float('-inf')
        for i in range(2):
            value = alpha_beta(depth + 1, node_index * 2 + i, False, scores, alpha, beta, height)
            max_value = max(max_value, value)
            alpha = max(alpha, max_value)
            if beta <= alpha:
                break  # 가지치기 발생
        return max_value
    else:
        min_value = float('inf')
        for i in range(2):
            value = alpha_beta(depth + 1, node_index * 2 + i, True, scores, alpha, beta, height)
            min_value = min(min_value, value)
            beta = min(beta, min_value)
            if beta <= alpha:
                break  # 가지치기 발생
        return min_value

# 예제 데이터
scores = [3, 5, 2, 9, 12, 5, 23, 23]
height = 3
print("최적의 값:", alpha_beta(0, 0, True, scores, float('-inf'), float('inf'), height))

📌 알파-베타 가지치기 실행 결과 예시

최적의 값: 12

💡 미니맥스보다 훨씬 빠르게 실행되며, 최적의 선택을 보장함!

📌 4. 몬테카를로 트리 탐색(Monte Carlo Tree Search, MCTS)

✅ MCTS란?

MCTS(몬테카를로 트리 탐색)는 무작위 시뮬레이션을 실행하여 승률이 높은 전략을 선택하는 방식입니다.
즉, 가능한 모든 수를 탐색하지 않고, 유망한 수를 시뮬레이션하여 최적의 전략을 결정합니다.
특히 바둑, 체스, 포커 등 확률과 전략이 중요한 게임에서 효과적으로 사용됩니다.

🔍 MCTS의 4단계 과정

1⃣ Selection (선택)

• 현재 상태에서 가장 유망한 노드(수)를 선택

• 탐색을 진행할 노드를 결정 (UCB1 공식 활용)

2⃣ Expansion (확장)

• 선택된 노드에서 새로운 가능한 수를 생성하여 확장

3⃣ Simulation (시뮬레이션)

• 무작위 플레이아웃(Random Rollout)을 수행

• 해당 수가 승리로 이어지는지 평가

4⃣ Backpropagation (역전파)

• 승패 결과를 부모 노드로 전파하여 각 수의 승률 업데이트

💡 이 과정을 반복하여 가장 승률이 높은 수를 선택!

✅ MCTS의 특징

✔ 완벽한 탐색이 어려운 게임에서 유용
✔ 실시간 학습 가능 (강화학습과 결합 가능)
✔ 바둑 AI (알파고, AlphaGo), 체스 AI 등에 활용
✔ 탐색할 가능성이 높은 부분에 집중하여 연산량 절약

✅ MCTS 코드 구현 (Python, 간단한 구조)

import math
import random

class Node:
    def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent
        self.children = []
        self.visits = 0
        self.value = 0

    def is_fully_expanded(self):
        return len(self.children) > 0

    def best_child(self, exploration_weight=1.0):
        return max(self.children, key=lambda c: c.value / (c.visits + 1e-6) + exploration_weight * math.sqrt(math.log(self.visits + 1) / (c.visits + 1e-6)))

def mcts_search(root, itermax=1000):
    for _ in range(itermax):
        node = root
        while node.is_fully_expanded():
            node = node.best_child()
        result = random.choice([-1, 1])  # 무작위 승패 시뮬레이션
        while node is not None:
            node.visits += 1
            node.value += result
            node = node.parent

    return root.best_child(exploration_weight=0)

# 예제 실행
root = Node("Root State")
best_move = mcts_search(root, 1000)
print("MCTS 선택된 최적 경로:", best_move.state)

📌 MCTS 실행 결과 예시

MCTS 선택된 최적 경로: Root State (시뮬레이션 기반 최적 수 선택)

🎯 마무리: 게임 탐색 알고리즘 비교

📌 게임 탐색 알고리즘은 게임의 특성에 맞게 선택해야 합니다!

• 미니맥스 알고리즘은 체스, 틱택토와 같은 정형화된 턴 기반 게임에서 사용됨

• 알파-베타 가지치기(α-β Pruning)는 미니맥스를 최적화하여 계산량을 줄이는 데 효과적

• 몬테카를로 트리 탐색(MCTS)은 바둑, 포커, 실시간 전략 게임(RTS)에서 확률 기반으로 효과적인 탐색 수행