📍1. 게임 프로그램
✔️ 게임의 조건
1️⃣ 두 명의 경기자
경기자들이 연합하는 경우는 다루지 않음
2️⃣ 제로썸 게임
한 경기자의 승리는 다른 경기자의 패배. 협동적인 승리는 없음
(e.g. 바둑, 체스)
3️⃣ 순차적 게임
차례대로 수를 두는 게임만을 대상으로 함
☑️Tic-Tac-Toe의 게임 트리
- 2인용 게임
- 두 경기자 MAX와 MIN
- 항상 MAX가 먼저 수를 둔다고 가정
✔️ Tic-Tac-Toe의 게임 트리의 크기
- 게임 보드는 3×3 크기
- 한 곳에 수를 놓으면 다른 사람이 놓을 수 있는 곳은 하나가 줄어듦
➡️ 9×8×7×...×1 = 9! = 362,880
하지만 대칭이나 반사를 제외하면 서로 다른 상태는 5478개뿐
📍2. 미니맥스 알고리즘
✔️ 상대방이 항상 최선의 수를 둔다고 생각
✔️ 틱택토 게임에서의 미니맥스
- 1은 승리, 2는 무승부, -1은 패배를 의미
✔️ 미니맥스 알고리즘
- 제일 깊은 곳까지 내려갔다가 다시 올라오는 형식
- 동작 방식은 DFS와 동일
function minimax(node, depth, maxPlayer)
if depth == 0 or node가 단말 노드 then
return node의 휴리스틱 값
if maxPlayer then
value ← −∞
for each child of node do # 모든 자식 노드에 대해 계산
value ← max(value, minimax(child, depth − 1, FALSE))
return value
else # 최소화 노드
value ← +∞
for each child of node do
value ← min(value, minimax(child, depth − 1, TRUE))
return value
✔️ 미니맥스 알고리즘의 분석
1️⃣ 완결성
미니맥스 알고리즘은 완결될 수 있음
유한한 탐색 트리 안에 해답이 존재하면 반드시 찾음
2️⃣ 최적성
미니맥스 알고리즘은 최적의 알고리즘임
3️⃣ 시간 복잡도
만약 트리의 최대 깊이가 m이고 각 노드에서의 가능한 수가 b개라면, 미니맥스 알고리즘의 시간 복잡도는 O(𝑏𝑚)
4️⃣ 공간 복잡도
미니맥스 알고리즘의 공간 복잡도 또한 O(𝑏𝑚)
📍3. Tic-Tac-Toe 게임 프로그래밍
✔️ 보드 구현
# 보드는 1차원 리스트로 구현한다.
game_board = [' ', ' ', ' ',
' ', ' ', ' ',
' ', ' ', ' ']
# 비어 있는 칸을 찾아서 리스트로 반환한다.
def empty_cells(board):
cells = []
for x, cell in enumerate(board): #enumerate(): index, 값을 출력하는 내장함수
if cell == ' ':
cells.append(x)
return cells
# 비어 있는 칸에는 놓을 수 있다.
def valid_move(x):
return x in empty_cells(game_board)
✔️ 보드 상태
# 위치 x에 놓는다.
def move(x, player):
if valid_move(x):
game_board[x] = player
return True
return False
# 현재 게임 보드를 그린다.
def draw(board):
for i, cell in enumerate(board):
if i%3 == 0:
print('\n----------------')
print('|', cell , '|', end='')
print('\n----------------')
# 보드의 상태를 평가한다.
def evaluate(board):
if check_win(board, 'X'):
score = 1
elif check_win(board, 'O'):
score = -1
else:
score = 0
return score
✔️ 승리 조건
def check_win(board, player):
win_conf = [
[board[0], board[1], board[2]], # 가로 한 줄이 완성되는 index
[board[3], board[4], board[5]],
[board[6], board[7], board[8]],
[board[0], board[3], board[6]], # tp로 한 줄이 완성되는 index
[board[1], board[4], board[7]],
[board[2], board[5], board[8]],
[board[0], board[4], board[8]], # 대각선 한 줄이 완성되는 index
[board[2], board[4], board[6]],
]
return [player, player, player] in win_conf # e.g.) 'x'가 이겼는지 궁금하면 player에 x 대입
# 1차원 리스트에서 동일한 문자가 수직선이나 수평선, 대각선으로 나타나면
# 승리한 것으로 한다.
def game_over(board):
return check_win(board, 'X') or check_win(board, 'O')
✔️ 게임 방식
def minimax(board, depth, maxPlayer):
pos = -1
# 단말 노드이면 보드를 평가하여 위치와 평가값을 반환한다.
if depth == 0 or len(empty_cells(board)) == 0 or game_over(board): # 빈칸 없음 or 둘 중 하나가 이김
return -1, evaluate(board)
if maxPlayer:
value = -10000 # 음의 무한대
# 자식 노드를 하나씩 평가하여서 최선의 수를 찾는다.
for p in empty_cells(board):
board[p] = 'X' # 보드의 p 위치에 'X'을 놓는다.
# 경기자를 교체하여서 minimax()를 순환호출한다.
x, score = minimax(board, depth-1, False)
board[p] = ' ' # 보드는 원 상태로 돌린다.
if score > value:
value = score # 최대값을 취한다.
pos = p # 최대값의 위치를 기억한다.
else:
value = +10000 # 양의 무한대
# 자식 노드를 하나씩 평가하여서 최선의 수를 찾는다.
for p in empty_cells(board):
board[p] = 'O' # 보드의 p 위치에 'O'을 놓는다.
# 경기자를 교체하여서 minimax()를 순환호출한다.
x, score = minimax(board, depth-1, True)
board[p] = ' ' # 보드는 원 상태로 돌린다.
if score < value:
value = score # 최소값을 취한다.
pos = p # 최소값의 위치를 기억한다.
return pos, value # 위치와 값을 반환한다.
✔️ 메인 프로그램
player='X'
# 메인 프로그램
while True:
draw(game_board)
if len(empty_cells(game_board)) == 0 or game_over(game_board):
break
i, v = minimax(game_board, 9, player=='X') # i는 위치, v는 기댓값
move(i, player)
if player=='X': # 한 수씩 번갈아가며
player='O'
else:
player='X'
if check_win(game_board, 'X'):
print('X 승리!')
elif check_win(game_board, 'O'):
print('O 승리!')
else:
print('비겼습니다!')
✔️ 출력 예시
----------------
| || || |
----------------
| || || |
----------------
| || || |
----------------
----------------
| X || || |
----------------
| || || |
----------------
| || || |
----------------
----------------
| X || || |
----------------
| || O || |
----------------
| || || |
----------------
...
----------------
| X || X || O |
----------------
| O || O || X |
----------------
| X || O || X |
----------------
비겼습니다!
📍4. 알파베타 가지치기(alpha-beta pruning)
✔️ 미니매스 알고리즘에서 형성되는 탐색 트리 중에서 상당 부분은 결과에 영향을 주지 않으면서 가지들을 쳐내는 것
✔️ 탐색 할 때 알파값과 베타값이 자식 노드로 전달
✔️ 자식 노드에서는 알파값과 베타값을 비교 ➡️ 쓸데없는 탐색을 중지 가능
✔️ MAX는 알파값만, MIN은 베타값만을 업데이트
✔️ 알파베타 알고리즘
function alphabeta(node, depth, α, β, maxPlayer)
if depth == 0 or node가 단말 노드 then
return node의 휴리스틱 값
if maxPlayer then # 최대화 경기자
value ← −∞
for each child of node do
value ← max(value, alphabeta(child, depth−1, α, β, FALSE))
α ← max(α, value)
if α ≥ β then
break #이것이 β 컷
# 현재 노드의 최대값이 부모 노드의 값(β)보다 커지게 되면 더 이상 탐색할 필요가 없음
return value
else # 최소화 경기자
value ← +∞
for each child of node do
value ← min(value, alphabeta(child, depth−1, α, β, TRUE))
β ← min(β, value)
if α ≥ β then
break #이것이 α 컷
# 현재 노드의 최소값이 부모 노드의 값(α)보다 작으면 되면 더 이상 탐색할 필요가 없음
return value
📍5. 불완전한 결정
✔️ 미니맥스 알고리즘은 탐색 공간 전체를 탐색하는 걸 가정하기에 크기가 매우 큼
✔️ 탐색을 끝내야 하는 시간에 도달하면 탐색을 중단하고 탐색 중인 상태에 대하여 휴리스틱 평가 함수(evaluation function)를 적용해야
➡️ 비단말 노드이지만 단말 노드에 도달한 것처럼 생각하는 것
'인공지능' 카테고리의 다른 글
[인공지능원론] 4. 전문가 시스템 (0) | 2025.04.14 |
---|---|
[인공지능원론] 2. 탐색(Search) - (2) (0) | 2025.04.14 |
[인공지능원론] 2. 탐색(Search) - (1) (0) | 2025.03.20 |
[인공지능원론] 1. 인공지능 소개 (1) | 2025.03.20 |