Python으로 배우는 탐색과 게임 AI: A*와 미니맥스

쉬운 말로 이해하는 개념

고전 AI는 가능한 상태들을 탐색하여 문제를 풉니다. A*는 지금까지의 비용에 남은 비용의 추정치를 더해 가장 저렴한 경로를 찾고, 미니맥스는 상대가 잘 둔다고 가정하고 2인 게임의 수를 고릅니다.

A* 탐색으로 격자에서 최단 경로를 찾고, 미니맥스로 게임에서 최선의 수를 고릅니다.

핵심 아이디어

추정치(휴리스틱)가 실제 비용을 절대 넘지 않으면 A*는 최적의 경로를 찾습니다.
미니맥스는 정해진 깊이나 게임이 끝날 때까지 게임 트리를 탐색합니다.
알파-베타 가지치기는 결정을 바꿀 수 없는 가지를 건너뜁니다.
유전 알고리즘은 다른 방식으로 탐색하며, 후보 해의 집단을 진화시킵니다.

언제 사용하나요?

신경망과 AI 라이브러리 내부에서 무슨 일이 일어나는지 이해합니다.
해당 챌린지에서 직접 구현하기 전에 아이디어를 익힙니다.
머신러닝 강의, 면접, 프로젝트를 준비합니다.

직접 움직여 보기

재생을 누르면 A*가 격자를 탐색합니다. 칸을 클릭해 벽을 추가하거나 없앨 수 있습니다. 게임 트리에서는 잎을 클릭해 점수를 바꿀 수 있습니다.

예제 코드

코드 실행 →

main.py

import heapq

# A* finds the cheapest path using cost so far + a guess of the cost left.
grid = ["S..#",
        ".#..",
        "...G"]
start, goal = (0, 0), (2, 3)
guess = lambda r, c: abs(r - goal[0]) + abs(c - goal[1])   # Manhattan distance

frontier = [(guess(*start), 0, start, [start])]
seen = set()
while frontier:
    _, cost, (r, c), path = heapq.heappop(frontier)
    if (r, c) == goal:
        print("path:", path, "cost:", cost)
        break
    if (r, c) in seen:
        continue
    seen.add((r, c))
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 4 and grid[nr][nc] != "#":
            heapq.heappush(frontier, (cost + 1 + guess(nr, nc), cost + 1, (nr, nc), path + [(nr, nc)]))

# Minimax: the maximizer assumes the opponent always picks the worst for it.
def minimax(node, maximizing):
    if isinstance(node, int):
        return node
    values = [minimax(child, not maximizing) for child in node]
    return max(values) if maximizing else min(values)

tree = [[3, 5], [2, 9], [0, 7]]   # our move, then the opponent's reply
print("best guaranteed score:", minimax(tree, True))

예상 출력

path: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3)] cost: 5
best guaranteed score: 3

작동 원리

우선순위 큐는 항상 "비용 + 추정치"가 가장 작은 칸을 확장하며, 추정치는 목표까지의 맨해튼 거리이므로 A*는 벽을 돌아 5단계 만에 G에 도착합니다. minimax()는 내 차례에서는 최댓값을, 상대 차례에서는 최솟값을 고릅니다. 첫 번째 수는 3을 보장하며, 이는 세 가지 최악의 경우 중 가장 좋은 값입니다.

값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.

연습 문제

입력값과 경계 조건을 바꾸고 더 큰 데이터에서도 동작을 확인하세요.

입력이나 가중치를 바꾸고 실행하기 전에 출력을 예상해 보세요.
중간 값을 출력해 계산의 각 단계를 따라가 보세요.
아래에 연결된 챌린지를 풀며 아이디어를 직접 구현해 보세요.

Python IDE에서 실행 →

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지