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

목차

1. 게임 프로그램
2. MiniMax 알고리즘
3. Tic-Tac-Toe 게임 프로그래밍
4. alpha beta-가지치기
5. 불완전한 결정

---

1. 게임 프로그램

• 인공지능과 게임
  • 게임은 예전부터 인공지능의 매력적인 연구 주제였다.
  • Tic-Tac-Toe, 체스, 바둑과 같은 게임은 추상적으로 정의할 수 있고 지적 능력과 연관이 있는 것으로 생각되었다.
  • 이들 게임은 비교적 적은 수의 연산자들을 가진다.
  • 연산의 결과는 엄밀한 규칙으로 정의된다.
• 게임의 조건
  • 두 명의 경기자 - 경기자들이 연합하는 경우는 다루지 않는다.
  • 제로썸 게임 - 한 경기자의 승리는 다른 경기자의 패배이다. >> 협동적인 승리는 없다.
  • 차례대로 수를 두는 게임만을 대상으로 한다. (순차적인 게임)
  • 설명의 단순화를 위해 "게임 프로그램이 위의 룰을 따른다"고 가정하며 바둑과 체스가 여기에 속한다.
• 게임의 정의
  • 2인용 게임
  • 두 경기자를 MAX와 MIN으로 부르자.
  • 항상 MAX가 먼저 수를 둔다고 가정한다. 
• Tic-Tac-Toe 게임의 크기
  • Tic-Tac-Toe의 게임 트리는 크기가 얼마나 될까?
  • Tic-Tac-Toe 게임 보드는 3*3 크기를 가지고 있고 한 곳에 수를 놓으면 다른 사람이 놓을 수 있는 곳은 하나가 줄어들게 된다.
  • 9*8*7*...*1 = 9! = 362880
  • 보드의 크기가 n일 때 n!이 된다.

2. MiniMax 알고리즘

• 안전하게 하려면 상대방이 최선의 수를 둔다고 생각하면 된다.
• MIN에서는 작은 것을 선택, MAX에서는 큰 것을 선택

Minimax 알고리즘의 Pseudo code

function minimax(node, depth, maxPlayer) if depth == 0 or node가 단말 노드 then return node의 휴리스틱 값 if maxPlayer then value << -inf for each child of node do value << max(value, minimax(child, depth -1, FALSE)) return value else // 최소화 노드 value << +inf for each child of node do value << min(value, minimax(child, depth - 1, TRUE)) return value

• Minimax 알고리즘의 시간 복잡도
  • Minimax 알고리즘은 게임 트리에 대하여 완벽한 깊이 우선 탐색을 수행한다.
  • 만약 트리의 최대 깊이가 m이고 각 노드에서의 가능한 수가 b개라면 Minimax 알고리즘의 시간 복잡도는 O(b^m)이다.
  • 바둑은 경우의 수가 약 316!이다.
  • 이것을 계산해보면 약 10^761로 추산된다. 전체 우주는 약 10^80갸의 원자만을 포함하는 것으로 추정된다.

3. Tic-Tac-Toe 게임 프로그래밍

# 보드는 1차원 리스트로 구현한다 game_board = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '] # 비어 있는 칸을 찾아서 리스트로 반환한다. def empty_cells(board): cells = [] # 비어 있는 리스트 생성 for x, cell in enumerate(board): # board 의 원소를 순회한다. if cell == ' ': # 만약 board 의 x 번째 원소가 공백이라면 cells.append(x) # x 를 cells 에 추가한다. return cells # cells 를 반환하여 빈 칸의 목록을 반환한다. # 비어 있는 칸에 놓을 수 있다. def valid_move(x): return x in empty_cells(game_board) # 유효한 move 인지 판단하여 x 를 리턴한다. # 위치 x에 놓는다. ### x: 0 to 8 ### player: 'X', 'O' def move(x, player): # 위치 x 와 현재 player 를 받는다. if valid_move(x): # 만약 move 가 유효하다면 game_board[x] = player # 현재의 게임보드의 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'): # 'X' 가 이기는 경우 score 에 1 을 대입 score = 1 elif check_win(board, 'O'): # 'O' 가 이기는 경우 score 에 -1 을 대입 score = -1 else: # 비기는 경우 score 에 0 을 대입 score = 0 return score # 1차원 리스트에서 동일한 문자가 수직선이나 수평선, 대각선으로 나타나면 승리한 것으로 한다. # 수직선이나 수평선, 대각선에서 누가 이겼는지를 확인한다. def check_win(board, player): win_conf = [ [board[0], board[1], board[2]], [board[3], board[4], board[5]], [board[6], board[7], board[8]], [board[0], board[3], board[6]], [board[1], board[4], board[7]], [board[2], board[5], board[8]], [board[0], board[4], board[8]], [board[2], board[4], board[6]], ] return [player, player, player] in win_conf # 누가 이겼는지를 반환한다. player 는 'O', 'X' 이기 때문이다. # 1차원 리스트에서 동일한 문자가 수직선이나 수평선, 대각선으로 나타나면 승리한 것으로 한다. def game_over(board): return check_win(board, 'X') or check_win(board, 'O') # 미니맥스 알고리즘을 구현한다. # 이 함수는 순환적으로 호출된다. # -1 을 리턴한다면 더이상 놓을 곳이 없다는 뜻이다. def minimax(board, depth, maxPlayer): pos = -1 # 단말 노드이면 보드를 평가하여 위치와 평가값을 반환한다. # 게임의 depth 가 0 이라면 = 더이상 놓을 공간이 없다면 = 단말 노드라면 # 보드의 공백의 길이가 0 이라면 = 더이상 놓을 공간이 없다면 = 단말 노드라면 # 게임이 끝났다면 if depth == 0 or len(empty_cells(board)) == 0 or game_over(board): return -1, evaluate(board) # 현재의 위치와 현재의 스코어를 반환한다. # maxPlayer 는 함수가 재귀적으로 호출되면서 바뀌어간다. True, False 둘 중 하나이다. 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: # 현재의 game_board 를 그린다. 맨 처음에는 공백이다. draw(game_board) # 만약 game_board 에 더 놓을 자리가 없거나 게임이 끝났다고 판단된다면 while 문을 중단시킨다. if len(empty_cells(game_board)) == 0 or game_over(game_board): break # minimax 에 현재의 game_board(공백) 를, depth 는 9를, 선 플레이어를 'X'로 한다. # minimax 는 유효한 포지션과 값을 반환한다. i, v = minimax(game_board, 9, player == 'X') # i에 현재 플레이어를 이동시킨다. 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('비겼습니다!')

4. alpha beta-가지치기

* 노드들은 내림차순으로 정렬되어 있다고 가정한다.

• Minimax 알고리즘에서 형성되는 탐색 트리 중에서 상당 부분은 결과에 영향을 주지 않으면서 가지들을 쳐낼 수 있다.
• 이것을 alpha-beta 가지치기라고 한다.
• 탐색을 할 때 alpha 값과 beta 값이 자식 노드로 전달된다.
• 자식 노드에서는 alpha 값과 beta 값을 비교하여서 쓸 데 없는 탐색을 중지할 수 있다.
• MAX는 alpha 값만을 업데이트한다. MIN은 beta 값만을 업데이트한다.

alpha-beta 알고리즘 Pseudo code

function alphabeta(node, depth, alpha, beta, maxPlayer) if depth == 0 or node가 단말 노드 then return node의 휴리스틱 값 if maxPlayer then // 최대화 경기자 value << -inf for each child of node do value << max(value, alphabeta(child, depth-1, alpha, beta, FALSE)) alpha << max(alpha, value) if alpha >= beta then break // 이것이 beta 컷이다. 현재 노드의 최대값이 부모 노드의 값 beta보다 커지게 되면 더이상 탐색할 필요가 없음 return value else // 최소화 경기자 value << +inf for each child of node do value << min(value, alphabeta(child, depth-1, alpha, beta, TRUE)) beta << min(beta, value) if alpha >= beta then break // 이것이 alpha 컷이다. 현재 노드의 최소값이 부모 노드의 값 alpha보다 작게 되면 더이상 탐색할 필요가 없음 return value

5. 불완전한 결정

• MiniMax 알고리즘과 불완전한 결정
  • MiniMax 알고리즘은 탐색 공간 전체를 탐색하는 것을 가정한다. 하지만 실제로는 탐색 공간의 크기가 무척 커서 우리는 그렇게 할 수 없다. 실제로는 적당한 시간 안에 다음 수를 결정하여야 한다. 어떻게 하면 될까?
  • 이때는 탐색을 끝내야 하는 시간에 도달하면 탐색을 중단하고 탐색 중인 상태에 대하여 휴리스틱 평가 함수(evaluation function)를 적용해야 한다. 즉 비단말 노드이지만 단말 노드에 도달한 것처럼 생각하는 것이다.
  • evaluation function의 조건
    • 승리하는 경우가 비기는 경우보다 높은 점수를 준다.
    • 비기는 경우가 패배하는 경우보다 높은 점수를 준다.
    • evaluation function 계산에 적은 시간이 소모되어야 한다.