[Farm System🪴] 인공지능 스터디 6주차(미니맥스와 가지치기)

🙌서론

이번 주차 스터디는 미니맥스 알고리즘에 대해 학습하였습니다.
이제 본격적으로 인공지능의 알고리즘에 대해 공부하게 되었군요.
이번주차 부터 인공지능 알고리즘에 대해 학습을 하게 될 것 같습니다. 그리고 가장 처음으로 배우는 알고리즘이 미니맥스 알고리즘입니다.

🕹️미니맥스 알고리즘이란

미니맥스(Minimax) 알고리즘은 게임 이론과 인공지능 분야에서 널리 사용되는 알고리즘으로, 2인 완전정보 턴제 게임(예: 틱택토, 체스, 오델로 등)에서 최적의 수를 선택하기 위해 사용된다.
즉, 두 참여자가 교대로 어떤 결정을 해가면서 진행되는 과정 등에서, 종료시점까지의 모든 과정을 내다보고 현시점에서 어떤 결정이 최선인지를 알아내는 알고리즘이다.
참여자의 선택에 무작위성이 개입하지 않고 모든 정보가 서로에게 공개되는 과정에 적합하다.

바둑을 예로 들면 내가 두는 수를 I라 하고 상대가 두는 수를 O라고 하면 시점 t에서 내가 선택할 수 있는 수들 It들 중 최선의 수 It*를 둬야 한다. 이때 모든 It를 평가하여 가장 점수가 높은 수(가장 나에게 유리한 수)를 고르면 될 것이다. 그런데, 이것은 근시안적이다.

한 수 앞 보기

한 수 앞, 즉 t+1의 시점에서 보는 것이다. 상대도 역시 상대가 둘 수 있는 모든 수 Ot+1들 중 최선의 수를 찾아 두려고 할 것이기 때문에 It에서 Ot+1*를 고려해서 나의 It*를 결정하겠다는 것이다.
시점 t에서 당장 나에게 큰 유리함을 주는 수라 할지라도 Ot+1*에 철저히 무력화 되어 오히려 상대에게 큰 유리함을 주는 악수로 봐야한다.

즉, 우리는 우리가 수를 두면 그 수에 대한 상대의 가장 강력한 대응을 고려하여 최대한 무력화 당하고 난 다음의 점수를 It의 점수로 봐야 한다. 그러니 점수는 상대가 가하는 무력화를 최대한 당한 다음의 점수이므로 그 수를 두었을 때 내가 얻을 수 있는 점수의 최소값이 된다.

두 수 앞 보기

그렇다면 한 수 앞 상대의 수 Ot+1는 어떻게 평가해야 할까? 상대도 나와 같은 생각을 할 것이라고 보면 된다. 즉, 상대는 t+2시점에서 내가 상대에게 가하는 무력화를 최소화 하는 수를 찾으려 할 것이다.
그런데 이는 상대 입장에서 최소화이지만 나의 입장에서는 최대화이므로 Ot+1*를 무력화하는 수 It+2*까지 고려해서 최선의 수를 It*로 하겠다는 것이다.

종료 시점까지 보기

이 방식으로 종료시점까지 반복하면 된다. 이것을 트리로 나타낼 수 있는데 최소화는 역삼각형으로, 최대화는 정삼각형으로 나타내면 된다. 이 같은 트리를 게임 트리라고 한다.

이 트리의 말단노드에는 구체적인 숫자 형태의 점수가 입력된다. 승리는 +1, 패배는 -1, 무승부는 0으로 할 수 있다. 그리고 트리의 깊이는 바둑의 경우 361, 틱택토는 9가 된다.

이 구조를 보면 알 수 있다시피 수 읽기 깊이가 깊어질 수록 계산해야 하는 경우의 수들이 급격히 증가한다는 단점을 가진다.

🖥️알고리즘 구현

가장 기본적인 방법

구조를 보면 알다시피 같은 알고리즘이 반복된다 봐도 된다. 이는 재귀를 이용하여 구현을 하면 편하다. 참고로 파이썬에서 재귀의 깊이는 1024까지로 제한된다.

틱택토용 미니맥스 함수

def get_minimax_score(state, player_type, terminal_score=1, minimizer=True):
	if state.check_if_win(player_type):
    	return terminal_score
    
    elif state.check_if_win(-player_type):
    	return -terminal_xcore
    
    elif state.check_if_game_finished():
    	return 0
    
    else:
    	if minimizer==True:
        	minimax_score = np.inf
            legal_actions = state.get_legal_actions()
            
            for action in legal_zctions:
            	next_state = state.get_next_state_from_action(action,-player_type)
                score = get_minimax_score( next_state, -player_type
                	    , -terminal_score, minimizer=False)
                
                if score < minimax_score:
                	minimax_score = score
        
        if minimizer==False:
        	minimax_score = -np.inf
            legal_actions = state.get_legal_actions()
           
            for action in legal_actions:
            	
                next_state = state.get_next_state_from_action(action, -player_type)
                score = get_minimax_score(next_state, -player_type,-terminal_score
                	    , minimizer=True)
                
                if score > minimax_score:
                	minimax_score = score
         
          return minimax_score

여기서 -부호가 끼여 있는 것은 최대값과 최소값을 구분해야 되기 때문이다(다음 수는 상대방이 둔다는 것을 알리기 위해).
5장에서 작성한 State 클래스의 state 인스턴스와 함수를 호출한 대국자가 선수[+1]인지 후수[-1]인지를 player_type으로 입력받도록 한다.

알파-베타 가지치기 알고리즘

미니맥스 알고리즘은 트리의 깊이가 증가함에 따라 탐색 공간의 크기가 급격히 증가하기 때문에 틱택토보다 복잡도가 조금만 더 증가하더라도 실질적인 목적으로 사용하기가 힘들다. 그래서 이에 대한 개선 방안 중의 하나인 알파-베타 가지치기 알고리즘이 있다. 이는 불필요한 계산을 하지 않게 함으로써 미니맥스 알고리즘의 계산 시간을 줄이는 방법이다.

예를 들면 최대화 함수 d는 말단 노드 값들 중 순서대로 본후 그 위의 노드로 큰 값을 결정할 것이다. 마찬가지로 그 옆 노드인 최대화 함수 e도 큰 값을 결정할 것인데 이들의 상위노드인 최소화 함수 b는 이들중 최소값을 결정할 것이다. 즉, d에서 결정한 값이 있으면 그 옆노드이며 상위노드가 같은 e에서 d에서 결정한 값보다 큰값이 하나라도 나오면 더 이상 e를 탐색할 필요가 없는 것이다. 즉 더 큰값이 나오면 e는 탐색을 종료한다. 이렇게 더 큰 값이 나와 e의 탐색을 종료하는 것을 베타 절단 이라고 한다.

반대로 최대화 함수와 최소화 함수가 바껴 더 작은 값이 나오면 탐색을 할 필요가 없을 텐데 이때 더 작은 값이 나오면 탐색을 종료하는 것을 알파 절단이라한다.

이러한 방식으로 게임 트리의 불필요한 부분들을 제거하는 것을 알파-베타 가지치기라 한다.

알파-베타 가지치기 알고리즘의 구현은 간단하다. get_minimax_score에 알파절단과 베타절단에 대한 부분만 추가하면 된다.

😀마무리

이렇게 스터디를 진행하며 가장 처음으로 인공지능 알고리즘을 학습했고 그것은 미니맥스 알고리즘이였다. 하면서 느낀점은 개념적인 부분은 이해가 된다. 하지만 파이썬에 미숙해서 그런지 구현은 쉽지 않다고 느꼈다. 아직은 학기 중이니 방학때 파이썬 공부를 열심히 해야겠다고 느꼈다.
이번주부터 기말시험기간이다.. 사실 이미 시험하나는 치뤘다. 점수는 어떻게 될지 모르겠지만..

나도 아래 커비 사진처럼 아무것도 안하고 아무 걱정없이 먹고 자고 놀기만 하고 싶다....
나머지 시험도 열심히 공부하러 가야겠다. 다들 화이팅:)