Minimax 알고리즘

 Minimax 알고리즘이란, 최대 최소 전략을 사용해 최선의 의사결정을 하는 데 사용되는 알고리즘으로, 상대가 최선의 수를 둔다고 가정하고, 그 상황에서 내가 얻을 수 있는 최선의 결과를 선택하는 알고리즘이다. 다시 말해, 상대가 최선을 다할 것이라고 가정하고, 그 상황에서도 나의 최선을 선택하는 전략이다.

 상대방은 나에게 최대한 불리한 점수(최소 점수)를 선택하고, 나는 그 중에서도 가능한 한 최대 점수를 얻는 선택을 하므로 최소를 최대화한다는 의미에서 Minimax 알고리즘이라고 불린다. (MAX는 자신의 점수를 최대화하고,
MIN은 상대의 점수를 최소화한다. (다시 말해, MAX의 손해를 극대화하는 것이다))

• 미니맥스 알고리즘은 유한한 탐색 트리 안에 해답이 존재하면 반드시 찾을 수 있으므로 완결될 수 있다.
• 미니맥스 알고리즘은 최적성을 지닌다.
• 트리의 최대 값이가 m이고, 각 노드에서 가능한 수가 b개일 때, 시간 복잡도와 공간 복잡도는 $O(b^m)$이며, 모든 경우의 수를 탐색하기에 시간 복잡도가 지수적으로 증가하므로 이를 줄이기 위해 알파-베타 가지치기(Alpha-Beta Pruning)가 등장했다.

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


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

# 비어 있는 칸에는 놓을 수 있다.
def valid_move(x):
    return x in empty_cells(game_board) # x가 비어있는 셀 안에 포함되어 있으면 True / else False

# 위치 x에 놓는다.
def move(x, player):
    if valid_move(x): # 비어있는 칸이면
        game_board[x] = player # 위치 x에 놓고
        return True
    return False # 아니면 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

# 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' or 'X'이고, 이거에 포함되면 True

# 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): # depth=0이거나 비어있는 칸이 없거나 둘 중 한명이 이긴 경우
        return -1, evaluate(board)

    if maxPlayer:
        value = -10000  # 음의 무한대
        # 자식 노드를 하나씩 평가하여서 최선의 수를 찾는다.
        # 모든 비어있는 셀 p에 대해서 평가해 최선의 위치를 찾음.
        for p in empty_cells(board):
            board[p] = 'X'		# 보드의 p 위치에 'X'을 놓는다.

            # 경기자를 교체하여서 minimax()를 순환호출한다.
            x, score = minimax(board, depth-1, False) # depth-1은 재귀호출이니까 depth 점차 줄여나가는 거 / 제한하지 않으면 계속 찾아서 들어감
            board[p] = ' '		# 재귀 반복이 끝나면 보드는 원 상태로 돌린다.

            if score > value:
                value = score 	# 최대값을 취한다.
                pos = p		# 최대값의 위치를 기억한다.
    else: # if minPlayer
        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') # 최대 or 최소 위치와 값을 반환하면
    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('비겼습니다!')

알파베타 가지치기 (Alpha-Beta Pruning)

 Minimax의 성능을 향상시키기 위한 최적화 기법으로, 더 이상 유망하지 않은 가지는 탐색하지 않고 잘라내는 방식으로 작동한다.

 알파-베타 가지치기의 핵심 아이디어는, 탐색 트리의 어떤 부분은 제외하여도 결과에 영향을 주지 않는다는 것이다. 따라서 탐색을 더 깊게 진행할 필요가 없을 때 탐색을 중단(알파-베타 컷 오프)하여도 결과는 Minimax 알고리즘에서의 결과와 동일하다.

 알파-베타 가지치기(Alpha-Beta Pruning)의 핵심은 필요없는 분기를 미리 배제함으로써 탐색 범위를 줄이는 것이다. 이를 위해 두 가지 값을 유지한다.

• Alpha : MAX가 현재까지 선택한 최댓값 (이 값보다 낮으면 볼 필요가 없음)
• Beta : MIN이 현재까지 선택한 최솟값 (이 값보다 높으면 볼 필요가 없음)
• β ≤ α이면, 이후 탐색은 무의미하므로 가지치기함.

 트리를 탐색하며 MAX는 Alpha 값을, MIN은 Beta 값을 갱신하며, Beta ≤ Alpha가 되는 시점부터 해당 노드의 탐색을 중지한다. 따라서 전체 트리 탐색 과정 중 많은 부분을 스킵할 수 있고, 시간 복잡도 또한 $O(b^{d/2})$까지 개선이 가능하다.

# 주요 변경 사항은 minimax 함수에 추가된 alpha와 beta 매개변수와
# 해당 함수 내에서 alpha와 beta 값을 업데이트하는 코드입니다.
# 이로 인해 알파베타 가지치기가 가능해져, 탐색 트리의 일부 브랜치를 건너뛰게 됩니다.

import random

game_board = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']

def empty_cells(board):
    cells = []
    for x, cell in enumerate(board):
        if cell == ' ':
            cells.append(x)
    return cells

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

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'):
        return 1
    elif check_win(board, 'O'):
        return -1
    return 0

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 minimax(board, depth, alpha, beta, maxPlayer):  # 알파와 베타 매개변수 추가
    pos = -1
    if depth == 0 or len(empty_cells(board)) == 0 or game_over(board):
        return -1, evaluate(board)

    if maxPlayer:
        value = -10000
        for p in empty_cells(board):
            board[p] = 'X'
            x, score = minimax(board, depth-1, alpha, beta, False)
            board[p] = ' '
            if score > value:
                value = score
                pos = p
            # Alpha = MAX가 현재까지 선택한 최댓값 (이 값보다 낮으면 볼 필요가 없음)
            alpha = max(alpha, value)  # 알파 업데이트
            # β ≤ α이면, 이후 탐색은 무의미하므로 가지치기
            if alpha >= beta:  # 알파-베타 가지치기 조건
                break
    else:
        value = +10000
        for p in empty_cells(board):
            board[p] = 'O'
            x, score = minimax(board, depth-1, alpha, beta, True)
            board[p] =  ' '
            if score < value:
                value = score
                pos = p
            # Beta = MIN이 현재까지 선택한 최솟값 (이 값보다 높으면 볼 필요가 없음)
            beta = min(beta, value)  # 베타 업데이트
            # β ≤ α이면, 이후 탐색은 무의미하므로 가지치기
            if alpha >= beta:  # 알파-베타 가지치기 조건
                break

    return pos, value

player = random.choice(['X', 'O']) # 플레이어 랜덤 선택
first_move = True

while True:
    draw(game_board)
    if len(empty_cells(game_board)) == 0 or game_over(game_board):
        break
    if first_move:
        move(random.choice(empty_cells(game_board)), player) # 첫 번째 수 무작위, 첫 번째 플레이어 수 둔 것
        first_move = False
    else:
        # 최적의 수를 찾아 이동
        i, v = minimax(game_board, len(empty_cells(game_board)), -10000, 10000, player == 'X')  # 알파와 베타 값 초기화
        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('비겼습니다!')