인공지능(4) - Minimax

- 탐색(Search)란?

• 주어진 조건을 만족하는 데이터를 찾아내는 것

 

• A game of tic-tac-toe between two players, "MAX" and "MIN"
  
  • MAX (X) 플레이어가 이기면 +1점을 주고, X플레이어에 대해서는 최대값으로 가게끔 학습
  • MIN (O) 플레이어가 이기면 -1점을 주고, O플레이어에 대해서는 최소값으로 가게끔 학습

 

MINIMAX 알고리즘은 최대,최소 전략을 사용하여 게임이론과 인공지능에서 사용되는 의사 결정 알고리즘이다. 완전 정보 게임에서 최적의 수를 찾는 데 사용된다. 주로 체스, 장기, 오목, 틱택토 같은 턴 기반 전략 게임에서 활용된다.

tic-tac-toe를 해결하려 mimimax알고리즘을 실행할 때 모든 미래의 상태를 시각화하여 작동하고 이를 트리 형태로 구성한다. 현재 상태가 알고리즘(트리의 루트)에 주어질 때, n가지로 분할된다. 이러한 새 상태 중 하나가 최종 상태인 경우 이 상태에 대해 더 이상 분할이 수행되지 않고 위처럼 점수가 할당된다.

MIN은 숫자가 작을 수록 이기고 MAX는 숫자가 클수록 이길 확률이 높다.

아래서 부터 보면 3과 5중 작은 숫자인 3을 고르고 2와 9 중 작은 숫자인 2를 고른다.

MAX에서는 큰 수를 고르기 때문에 3과 2중 큰 숫자인 3을 선택한다.

 

import numpy as np

# 현재 게임 보드를 그린다
def draw(board):
    for i, cell in enumerate(board):
        if i % 3 == 0:
            print('\n-------------------')
        print('|', cell if cell != '' else ' ', '|', end=' ')
    print('\n-------------------')

# 비어 있는 칸을 찾아서 리스트로 반환한다
def empty_cells(board):
    cells = []
    for x, cell in enumerate(board):
        if cell == ' ':
            cells.append(x)
    return cells

# 보드의 상태를 평가한다.
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]],
        [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

# 게임 종료 조건 체크
def game_over(board):
    return check_win(board, 'X') or check_win(board, 'O')

# 알파-베타 알고리즘을 구현한다.
def alpha_beta(board, depth, alpha, beta, maxPlayer):
    pos = -1
    if depth == 0 or len(empty_cells(board)) == 0 or game_over(board):
        value = evaluate(board)
        return -1, value
    
    if maxPlayer:
        value = -10000  # 음의 무한대
        for p in empty_cells(board):
            board[p] = 'X'  # 보드의 p 위치에 'X'를 놓는다.
            _, score = alpha_beta(board, depth - 1, alpha, beta, False)
            board[p] = ' '  # 보드를 원 상태로 돌린다.
            if score > value:
                value = score
                pos = p
            alpha = max(alpha, value)  # 알파 값 갱신
            if beta <= alpha:  # 베타 가지치기
                break

    else:
        value = 10000  # 양의 무한대
        for p in empty_cells(board):
            board[p] = 'O'  # 보드의 p 위치에 'O'를 놓는다.
            _, score = alpha_beta(board, depth - 1, alpha, beta, True)
            board[p] = ' '  # 보드를 원 상태로 돌린다.
            if score < value:
                value = score
                pos = p
            beta = min(beta, value)  # 베타 값 갱신
            if beta <= alpha:  # 알파 가지치기
                break

    return pos, value  # 위치와 값을 반환한다.

# 유효한 움직임 체크
def valid_move(x):
    return x in empty_cells(game_board)

# 이동을 수행
def move(x, player):
    if valid_move(x):
        game_board[x] = player
        return True
    return False

# 보드는 1차원 리스트로 구현한다.
player = 'X'
game_board = [' ', ' ', ' ',
              ' ', ' ', ' ',
              ' ', ' ', ' ']

while True:
    draw(game_board)
    if len(empty_cells(game_board)) == 0 or game_over(game_board):
        break
    i, v = alpha_beta(game_board, 9, -10000, 10000, player == 'X')
    move(i, player)

    # 플레이어 전환
    player = 'O' if player == 'X' else 'X'

draw(game_board)

if check_win(game_board, 'X'):
    print('X 승리')
elif check_win(game_board, 'O'):
    print('O 승리')
else:
    print('비김')

 

- Alpha Beta Pruning

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

 

• Alpha
  • Alpha is the best choice or the highest value that we have found at any instance along the path of Max Player.
  • The initial value for alpha is -∞
• Beta
  • Beta is the best choice or the lowest value that we have found at any instance along the path of Min Player.
  • The initial value for alpha is +∞
• Alpha-beta Prunung condition
  • α ≥ β
• Rules
  • MAX will update only alpha values and MIN will update only beta values
  • Alpha and Beta values only be passed to child nodes
  • The node values will be passed to upper nodes instead of values of alpha and beta during go into reverse of tree

 

Alpha-Beta pruning 예시

 

https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning