Min-Max 알고리즘

본 포스팅에서는 턴제 게임과 같은 곳에서 활용될 수 있는 MinMax알고리즘에 대해 포스팅 해 보겠습니다.

 

Min-Max 알고리즘는 최대 최소전략을 사용하여 턴제 게임(체스, 오목, 바둑)등과 같은 프로그램에서 의사결정에 주로 사용되는 알고리즘입니다. 여기서 최대 최소 전략이란, 어떠한 계획의 성공을 통한 효과를 고려하는것보다 실패했을 떄의 손실을 고려해서 그 손실이 최소가 되도록 계획을 세우는 전략입니다. MinMax 알고리즘은, 최대 최소 전략의 원리에 따라 실패했을 때 어떻게 될지를 생각하여 그 손실이 최소가 되도록 합니다.

 

예를들어 Tic-tac-toe와 같은 게임에서는 다음 수를 예측하기 위해서는 수읽기를 통해 가장 승률이 높은 수를 선택해야 합니다. A와 B가 게임을 한다고 가정해보면, A에게 유리한 수는 B에게 불리한 수로 작용됩니다. 즉, 상대의 이익을 최소화하고 자신의 이익을 최대화하는 것이 게임에서 승리하는 방법이기 때문에, 이 경로를 찾는 것이 tic-tac-toe와 같은 턴제 게임 프로그램의 핵심입니다.

 

Min-Max 알고리즘의 트리 탐색 과정은 깊이 우선 탐색을 수행한 후, 서브 트리의 탐색이 끝나면 기존에 탐색 된 노드들을 역으로 거슬러 올라가면서 상위노드로 평갓값을 반영합니다. 이때, 최댓값과 최솟값은 교대로 비교하며 최종 서브 트리를 선택하고, 평갓값이 자식 노드에서 상위 노드로 전파될 때마다 해당 상위 노드의 자식 노드 간의 비교를 진행하고, 나의 수에서는 가장 큰 값을, 상대의 수에서는 가장 작은 값을 선택합니다.

 

하지만, Min-max 알고리즘의 경우 트리의 모든 노드를 탐색해야 하기 때문에 트리의 깊이가 많아질수록 계산 시간을 늘어난다. 탐색복잡도가 큰 게임인 체스같은 경우, 한 판에 대한 완전한 탐색 그래프를 만드려면 약 10^22세기가 걸린다고 한다. 휴리스틱 탐색 기법도 실질적인 분기 계수를 도움이 될 만큼 충분히 줄이지는 못하므로, 복잡한 게임을 끝까지 탐색한다는 것을 불가능하다는 것을 받아들여야 한다. 이론 문제를 해결하기 위해 어느 정도 깊이의 수까지 탐색한 후 판정하는 휴리스틱이나 탐색할 필요가 없는 노드를 탐색에서 제외하는 기법인 Alpha-beta pruning(알파-베타 가지치기)를 사용하기도 합니다. Alpha-beta pruning(알파-베타 가지치기)의 경우 조금 있다가 다시 설명드리도록 하겠습니다.

Min-Max 알고리즘의 pseudo code

function minimax(node, depth, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
        return value
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
        return value

 

Min-Max 알고리즘 통한 Tic-tac-toe 게임 구현(Python)

이제 MinMax를 사용해서 tic-tac-toe 게임을 구현하여 보도록 하겠습니다. 일단 먼저 생성자을 생성해줍니다.

import time

class Game:
    def __init__(self):
        self.initialize_game()

    def initialize_game(self):
        self.current_state = [['.','.','.'],
                              ['.','.','.'],
                              ['.','.','.']]
        self.player_turn = 'X'

    def draw_board(self):
        for i in range(0, 3):
            for j in range(0, 3):
                print('{}|'.format(self.current_state[i][j]), end=" ")
            print()
        print()

 

그리고 움직임이 적당한? legal한 움직임인지 확인하는 함수 역시 생성해줍니다.

def is_valid(self, px, py):
        if px < 0 or px > 2 or py < 0 or py > 2:
            return False
        elif self.current_state[px][py] != '.':
            return False
        else:
            return True

 

그다음엔, tic-tac-toe게임에서 이길수 있는 조건에 대한 함수 생성을 해줍니다.

def is_end(self):
        for i in range(0, 3):
            if (self.current_state[0][i] != '.' and
                self.current_state[0][i] == self.current_state[1][i] and
                self.current_state[1][i] == self.current_state[2][i]):
                return self.current_state[0][i]
    
        for i in range(0, 3):
            if (self.current_state[i] == ['X', 'X', 'X']):
                return 'X'
            elif (self.current_state[i] == ['O', 'O', 'O']):
                return 'O'
    
        if (self.current_state[0][0] != '.' and
            self.current_state[0][0] == self.current_state[1][1] and
            self.current_state[0][0] == self.current_state[2][2]):
            return self.current_state[0][0]
    
        if (self.current_state[0][2] != '.' and
            self.current_state[0][2] == self.current_state[1][1] and
            self.current_state[0][2] == self.current_state[2][0]):
            return self.current_state[0][2]
    
        for i in range(0, 3):
            for j in range(0, 3):
                # There's an empty field, we continue the game
                if (self.current_state[i][j] == '.'):
                    return None
    
        return '.'

 

이제 프로그램이 자신의 점수를 최대화 하면서 상대방의 점수를 최소화하는 max()와 min() 함수를 생성해 줍니다. 여기서 max()의 경우, 자신의 점수를 최대화 하는 함수이며, min()의 경우 상대방의 점수를 최소화 한다는 것을 의미합니다.

    def max(self):    
        px = None
        py = None
    
        result = self.is_end()
        if result == 'X':
            return (-1, 0, 0)
        elif result == 'O':
            return (1, 0, 0)
        elif result == '.':
            return (0, 0, 0)
    
        for i in range(0, 3):
            for j in range(0, 3):
                if self.current_state[i][j] == '.':
                    self.current_state[i][j] = 'O'
                    (m, min_i, min_j) = self.min()
                    if m > maxv:
                        maxv = m
                        px = i
                        py = j
                    self.current_state[i][j] = '.'
        return (maxv, px, py)
        
    def min(self):
        minv = 2
        qx = None
        qy = None
        result = self.is_end()
    
        if result == 'X':
            return (-1, 0, 0)
        elif result == 'O':
            return (1, 0, 0)
        elif result == '.':
            return (0, 0, 0)
    
        for i in range(0, 3):
            for j in range(0, 3):
                if self.current_state[i][j] == '.':
                    self.current_state[i][j] = 'X'
                    (m, max_i, max_j) = self.max()
                    if m < minv:
                        minv = m
                        qx = i
                        qy = j
                    self.current_state[i][j] = '.'
    
        return (minv, qx, qy)

 

이제 프로그램과 게임을 할 수있게 loop를 생성해주겠습니다.

def play(self):
        while True:
            self.draw_board()
            self.result = self.is_end()
    
            if self.result != None:
                if self.result == 'X':
                    print('X가 승리하였습니다')
                elif self.result == 'O':
                    print('O가 승리하였습니다')
                elif self.result == '.':
                    print("동점입니다")
    
                self.initialize_game()
                return
    
            if self.player_turn == 'X':
    
                while True:
                    start = time.time()
                    (m, qx, qy) = self.min()
                    end = time.time()
                    print('Evaluation time: {}s'.format(round(end - start, 7)))
                    print('Recommended move: X = {}, Y = {}'.format(qx, qy))
    
                    px = int(input('X 좌표 입력: '))
                    py = int(input('Y 좌표 입력: '))
    
                    (qx, qy) = (px, py)
    
                    if self.is_valid(px, py):
                        self.current_state[px][py] = 'X'
                        self.player_turn = 'O'
                        break
                    else:
                        print('다시시도해주세요.')
    
            else:
                (m, px, py) = self.max()
                self.current_state[px][py] = 'O'
                self.player_turn = 'X'

 

이제 main 함수를 구성해준뒤 프로그램을 작동시켜봅시다.

def main():
    g = Game()
    g.play()

if __name__ == "__main__":
    main()

 

 

Alpha-beta pruning(알파-베타 가지치기)

먼저 Alpha-beta의 기원을 살펴보면, John McCarthy는 1956년 Dartmouth Workshop에서 Alex Bernstein의 Chess Program을 발표한 후 Alpha-Beta 라는 아이디어를 제안했습니다. Alpha-Beta pruning의 장점으로는 탐색 트리의 가지를 쳐낼 수 있다는 점 입니다. 이런 경우 탐색은 같은 시간안에 더 깊은 노드 까지 탐색 할 수 있습니다. Alpha-Beta pruning는 다음과 같이 요약 할 수 있습니다.

• Alpha-beta pruning은 선택되지 않을 움직임의 하위 트리 검색을 피하면서 최적의 minimax 솔루션을 찾는 방법입니다.
• β은 가능한 솔루션의 최소 상한입니다.
• α는 가능한 모든 솔루선들의 maximum lower bound 입니다.
•  따라서, 새로운 노드가 솔루션에 대한 가능한 경로로 간주될 때 아래와 같은 경우에만 작동할 수 있습니다.
  $$α ≤ N ≤ β$$
  여기서 N은, 노드 값의 현재 추정치입니다.

즉, 아래의 그림을 살펴보면, α는 현재 경로에서 지금까지 발견된 max값 입니다. 여기서, V가 α보다 나쁘면 max는 회피, 하게되는데 이는 해당 가지를 잘라내는것을 의미합니다. Min에대해서도 max에서 적용됬던 방법과 유사하게 β를 정의 하면됩니다.

α–β (Alpha-beta pruning) pseudo code

이제 알파베타 가지치기의 의사코드를 살펴보겠습니다.

function alphabeta(node, depth, α, β, maximizingPlayer)
     if depth = 0 or node is a terminal node
         return the heuristic value of node
     if maximizingPlayer
         v := -∞
         for each child of node
             v := max(v, alphabeta(child, depth - 1, α, β, FALSE))
             α := max(α, v)
             if β ≤ α
                 break (* β cut-off *)
         return v
     else
         v := ∞
         for each child of node
             v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
             β := min(β, v)
             if β ≤ α
                 break (* α cut-off *)
         return v

•  α와 β는 가능한 솔루션 값의 하한 및 상한을 나타내는 매개변수입니다.
• 검색 트리를 통해 이동하면서 이러한 경계가 점점 더 가까워집니다.
• 노드를 평가하는 어느 시점에서 우리는 알파와 베타의 범위가 더 이상 겹치지 않는 경계 중 하나를 찾을 수 있습니다. 이 노드는 우리가 고려할 솔루션 경로가 될 수 없습니다.
• 자식 생성을 중지하고 부모 노드로 돌아가서 다른 경계를 초과하는 변경한 값을 부모에게 전달합니다.

α–β pruning(Alpha-beta pruning)을 통한 Tic-tac-toe 게임 구현(Python)

좀 전에 생성했던 MinMax 알고리즘에서 구현했던 tic-tac-toe 부분에서 min()함수와 max()함수에 대해 alpha-beta pruning을 적용해서 수정해 보겠습니다.

def max_alpha_beta(self, alpha, beta):
        maxv = -2
        px = None
        py = None

        result = self.is_end()

        if result == 'X':
            return (-1, 0, 0)
        elif result == 'O':
            return (1, 0, 0)
        elif result == '.':
            return (0, 0, 0)

        for i in range(0, 3):
            for j in range(0, 3):
                if self.current_state[i][j] == '.':
                    self.current_state[i][j] = 'O'
                    (m, min_i, in_j) = self.min_alpha_beta(alpha, beta)
                    if m > maxv:
                        maxv = m
                        px = i
                        py = j
                    self.current_state[i][j] = '.'

                    if maxv >= beta:
                        return (maxv, px, py)

                    if maxv > alpha:
                        alpha = maxv

        return (maxv, px, py)
        
def min_alpha_beta(self, alpha, beta):

        minv = 2
        qx = None
        qy = None

        result = self.is_end()

        if result == 'X':
            return (-1, 0, 0)
        elif result == 'O':
            return (1, 0, 0)
        elif result == '.':
            return (0, 0, 0)

        for i in range(0, 3):
            for j in range(0, 3):
                if self.current_state[i][j] == '.':
                    self.current_state[i][j] = 'X'
                    (m, max_i, max_j) = self.max_alpha_beta(alpha, beta)
                    if m < minv:
                        minv = m
                        qx = i
                        qy = j
                    self.current_state[i][j] = '.'

                    if minv <= alpha:
                        return (minv, qx, qy)

                    if minv < beta:
                        beta = minv

        return (minv, qx, qy)

이제 게임을 다시 구성해보겠습니다.

def play_alpha_beta(self):
     while True:
        self.draw_board()
        self.result = self.is_end()

        if self.result != None:
            if self.result == 'X':
                print('X가 승리하였습니다')
            elif self.result == 'O':
                print('O가 승리하였습니다')
            elif self.result == '.':
                print(동점입니다")
                
            self.initialize_game()
            return

        if self.player_turn == 'X':
            while True:
                start = time.time()
                (m, qx, qy) = self.min_alpha_beta(-2, 2)
                end = time.time()
                print('Evaluation time: {}s'.format(round(end - start, 7)))
                print('추천 좌표: X = {}, Y = {}'.format(qx, qy))

                px = int(input('X 좌표 입력: '))
                py = int(input('Y 좌표 입력: '))

                qx = px
                qy = py

                if self.is_valid(px, py):
                    self.current_state[px][py] = 'X'
                    self.player_turn = 'O'
                    break
                else:
                    print('다시시도해주세요')

        else:
            (m, px, py) = self.max_alpha_beta(-2, 2)
            self.current_state[px][py] = 'O'
            self.player_turn = 'X'

 

 

실제로 코드구현 이후 두 알고리즘에 대한 time을 고려해보면 alpha-beta pruning을 사용했을 때 시간이 줄어든 것을 확인 할 수 있습니다. 본 포스팅에서는 3x3의 간단한 tic-tac-toe게임을 구현해봤지만, 계산량이 큰 게임을 구현했을떄의 alpha-beta pruning는 트리를 평가하는 데 큰 차이를 만들것 입니다.

 

참고

https://stackabuse.com/minimax-and-alpha-beta-pruning-in-python/