Minimax algorithm

알고리즘 2017.07.18 13:48

1. Game Tree


일반적으로 체스나 장기 바둑과 같은 1:1 보드게임에서의 인공지능에는 게임트리라는 개념이 사용이 된다. 그렇다면 게임트리가 무엇일까? 게임트리란 위의 1:1 보드게임 상황에서 각 경우의 수로 부터 얻는 점수등을 모두 나타내주는 것을 트리 형식으로 도식화 한 것을 말한다.  



2. Minimax algorithm


그리고 이러한 게임트리를 사용해서 가장 많이 1:1 보드게임의 인공지능에 사용이 되는 알고리즘이 바로 이 Minimax algorithm이다. Minimax 알고리즘은 이름 그대로 한번은 주는 점수가 min이 되는 수를 그 다음은 주는 점수가 max가 되는 수를 선택하므로써 결과적으로 가장 최선의 수를 인공지능이 선택할 수 있도록 도와주는 그런 알고리즘이다.



3. Minimax algorithm (detail)


위에서 설명한 Minimax 알고리즘에 대한 보충으로 조금 더 자세히 설명하자면 

 

 

<출처:http://en.wikipedia.org/wiki/Image:Minimax.svg>

 

 

그림을 잠시 설명하자면

 

1. 왼쪽 0~4까지의 숫자는 각각의 턴을 말한다.

2. 동그라미는 인공지능의 차례 네모는 상대방의 차례를 나타낸다.

3. 각각의 동그라미와 네모안에 적혀 있는 숫자는 해당 수를 두었을 때 인공지능이 얻게 되는 점수를 뜻한다.

 

이러한 게임트리를 토대로 Minimax 알고리즘은 우선 이 인공지능이 수를 둘 차례에서 게임 끝날 때(4번)까지의 경우의 수를 모두 계산해보고 그런 다음 마지막 수를 뒀을 때(마지막 수를 두는게 인공지능이던 상대이던) 본인(인공지능)이 얻는 점수를 기준으로 제일 높은 점수를 주는 수 혹은 가장 낮은 점수를 주는 수를 선택 후 Max 값 Min 값의 선택을 반복적으로 역으로 선택해가면서 결국 현재의 기로에서 가장 최선의 수를 선택할 수 있도록 도와준다. 이 Minimax 알고리즘을 사용할 때 생각해야 할 가장 중요한 점은 상대도 최선의 수를 선택한다는 것을 염두해둔다는 점이다.

 

4. 가지치기


Minimax 알고리즘은 너무나도 불필요하게 모든 경우의 수를 계산해서 자신의 수를 최종적으로 선택하게 되므로 이는 비효율적이다. 그래서 불 필요한 경우의 수는 계산하지 않는 즉, 가지치기를 하게 되는데 Minimax 알고리즘에서 주로 같이 쓰이는 가지치기 기법으로 alpha-beta prunning이라는 기법이 있다.

 

 




'알고리즘' 카테고리의 다른 글

Monte Carlo Tree Search(MCTS)  (0) 2017.07.18
Minimax algorithm  (0) 2017.07.18

WRITTEN BY
마팸
안녕하세요 컴퓨터를 잘하고 싶은 학생입니다. 이것저것 공부하고 그것들을 토대로 블로그를 작성중입니다. 틀린점이 있을 수 있으니 유의하시고 틀린점을 발견하셨다면 댓글을 통해 알려주세요! 정말 고마울 것 같습니다.

트랙백  0 , 댓글  0개가 달렸습니다.
secret