오목 AI 제작 - MIN_MAX 전략을 통한 필승 수 구현
탐색을 적용시킨 오목 AI를 구현해보고 싶어서 3일동안 AI 제작을 진행하게 됐습니다.
먼저 19*19 바둑판 맵을 다 탐색을 하여 돌의 연결상태를 확인한 후 각 돌의 연결 상황마다 가중치를 부여했습니다.
그 후 Search 함수를 통해 탐색 과정에서 AI끼리 각자 가지치기 방식으로 최적의 수를 두어나갑니다.
탐색 중 상대방이 이기는 경우가 발생 하면 return 하여 가지가 갈라지는 분기점으로 돌아가 재 탐색을 시작합니다.
그렇게 탐색하는 도중 자신의 AI가 이기는 상황이 발생하면 맨 처음 좌표값을 저장한 후 그 이후부터는 모든 상황에 대해 return하여 탐색을 종료시켜 제작하였습니다.
최대 깊이 탐색은 현재 시점으로부터 30수까지 설정해 놓았습니다. 그 이유는 웬만하면 승부가 나는 시점까지 도달하고 탐색시간이 오래 걸리지 않았기 때문입니다.
그리고 탐색을 하는 도중에 각각의 AI의 입장에서 가장 최선의 수를 두어나가는 방식이므로 MIN_MAX 전략이라고 할 수 있겠습니다. 아군 AI입장에서는 적군 AI가 이기는 상황은 피하면서(MIN) 현재 자신에게 필요한 최적 수(MAX)를 두어 나가기 때문입니다.
다음은 탐색과정과 필승 수를 찾아가는 과정입니다.
위의 영상대로 가장 높은 가중치를 따라서 쭉쭉 진행하다가
이와 같이 빨간색으로 표시한 가중치값이 동일한 분기점에 도달하게 됩니다 (가지치기의 시작)
가장 왼쪽에 있는 곳부터 가장 최선의 수를 두어가며 다시 탐색을 시작합니다.
그러다가 상대방이 이기는 상황이 찾아오게 됩니다.
AI는 이 길은 잘 못된 경로라는 것을 인지하고 다시 분기점으로 되돌아 가고 두번째 경로를 선택하여 동일한 방식으로 탐색을 진행합니다.
해당 경로에서는 상대 AI(2) 가 계속해서 막기만하다가 자신의 AI(1)가 이기는 상황이 찾아옵니다.
AI는 이 경로가 필승 수가 되는 경로임을 파악하고
맨 처음 이 경로의 시작점인 (8,9)의 값으로 착수를 결정하게됩니다.
이와 같은 방식으로 진행한 전체 플레이 영상입니다.
다음은 소스코드 입니다.