[인공지능원론] 3. 게임트리

📍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)를 적용해야

➡️  비단말 노드이지만 단말 노드에 도달한 것처럼 생각하는 것