오목 AI

프로젝트 및 동작 설명

• 이 프로젝트는 컨볼루션 신경망과 몬테카를로 트리탐색을 활용한 오목 인공지능 프로그램이다.
• 네트워크는 예측 네트워크와 평가 네트워크이며 각각 오목 데이터를 이용하여 학습되었다.
• 예측 네트워크는 다음수를 예측하도록 학습되었으며 평가 네트워크는 현재의 상태에 대한 가치를 평가하도록 학습되었다.
• 트리탐색에서는 예측 네트워크를 이용하여 트리를 확장하고 평가 네트워크를 이용하여 노드를 평가한다.
• 그 결과 가치가 높은 노드, 두어질 확률이 높은 노드, 아직 많이 탐색해보지 않은 노드를 위주로 트리탐색이 이루어진다.
• 최종적으로 가장 많이 방문한 노드로 착수가 결정된다.
• 성능 향상을 위하여 트리탐색에서 43, 44와 같은 외통수 상태의 노드에서는 평가 네트워크의 추론 대신에 상황에 맞는 값이 노드에 메겨진다. (-1 혹은 1)
• 5목을 두거나 4목을 막거나 43, 44(외통수) 등의 몇몇 특정 상태에서는 실수를 방지하기 위해 자체 알고리즘을 통해 둔다.

진행과정 및 주요 코드 설명

• 우선 유연한 내부처리와 신경망과의 연동을 위해서 직접 오목 프로그램을 구현하였다. (오목에는 렌주룰이 적용되었다.)
• 그 다음으로는 오목 데이터에서 여러가지의 feature들을 추출하는 함수들을 구현하였다.
• 그 후에는 renju.net의 오목 데이터를 이용하여 신경망을 학습시켰다.
• 예측 네트워크는 (state,move) 쌍을 이용하여 categorical_crossentropy 방식으로 학습되었으며 평가 네트워크는 (state,result) 쌍을 이용하여 mse 방식으로 학습되었다.
• 렌주룰에서는 금수로 인하여 흑백의 플레이방식 및 전략이 다르므로 흑과 백의 네트워크를 따로 학습시켰다.
• 예측 네트워크의 추론 결과를 오목 프로그램의 gui에 시각화하는 작업과, 예측 네트워크를 기반으로 오목을 두는 ai를 구현하였다.
• 예측 네트워크를 기반으로 오목을 두는 ai는 predict.py 파일의 predict_p() 함수이다.
• 예측 네트워크만으로 착수를 하게 되면 중반 이후 실수할 가능성이 높아 몇몇 특정 상황에서는 자체 알고리즘에 따라 두게 된다. (5목을 두거나 4목을 막거나 43, 44(외통수) 등)
• 이후에는 앞서 학습시킨 두 신경망을 이용하는 트리탐색 알고리즘을 구현하였다.
• 트리탐색 과정에서는 평가값이 높은 노드를 선택하며 leaf 노드까지 내려간 뒤, 해당 노드의 가치를 평가하고 예측 네트워크를 이용하여 자식노드를 생성한다. (PRUNING_COUNT에 따라 가지치기)

  omok/mcts.py

  Line 166 in d7fd987

  def next_child_node(self):

• 평가값 계산식은 다음과 같다. (가치가 높은 노드, 두어질 확률이 높은 노드, 아직 많이 탐색해보지 않은 노드를 높이 평가)

  omok/mcts.py

  Line 179 in d7fd987

  pucb_values.append(a + C_PUCT * child_node.p * sqrt(t) / (1 + child_node.n))

• 노드의 가치평가는 자식노드가 없는 경우 평가 네트워크로 추론한 수치이며 자식노드가 있는 경우는 자식노드들의 가치를 방문 횟수만큼 각각 더한 뒤 자식노드 방문횟수의 합으로 나누어 평균을 낸 값이다.

  omok/mcts.py

  Line 161 in d7fd987

  value = -self.next_child_node().evaluate()

• 트리탐색도 마찬가지로 몇몇 특정 상황에서는 자체 알고리즘에 따라 둔다.
• 노드의 가치 평가에서 몇몇 특정 상태의 노드에서는 신경망의 추론 대신 자체적으로 수치를 대입한다. (5목을 두거나 4목을 막거나 43, 44(외통수) 등의)

결과

• 예측 네트워크의 시각화 결과는 현 문서 상단의 이미지와 같다.
• 예측 네트워크를 기반으로 착수하는 predict_p()와 트리 탐색을 기반으로 착수하는 mcts_action()간의 게임에서는 불과 트리탐색 횟수 10회로 테스트 하였음에도 트리 탐색 기반 AI가 26승3패1무로 우수한 성능을 보였다. (test.py 파일을 통해 테스트, mcts.py 파일의 MCTS_COUNT 값을 수정하여 트리탐색 횟수를 조절 가능)
• 사람과의 대결에서는 온라인 오목 어플에서 1급~2단 사이의 유저들을 상대로 3승2패를 거두었다. (트리탐색 횟수 120회 설정)

문제점 및 결론

• 평가 네트워크의 경우 트리탐색에서 성능향상을 보여주긴 했지만 상황별로 평가 네트워크의 출력값을 봤을 때 정확성이 부족한 것 같다는 느낌을 받았다. 학습 방식을 수정하여 loss 값을 더 줄인다면 트리탐색의 성능이 훨씬 개선될 것으로 보인다.
• 또한 학습에 사용한 데이터는 렌주룰을 기반으로 한 오프닝 룰(흑백이 초반 몇 수를 5대5의 진행으로 두게 됨, 따라서 흑이 선공의 이점을 살리지 않음)로 두어진 게임이기 때문에 초반의 몇 수는 최선의 수라고 보기 힘들다. 따라서 그 부분의 데이터는 제외하고 학습시킨 뒤, 초반의 전략들은 강화학습을 적용시켜 익히게 하면 성능이 더 개선될 것이다.

Requirements

• pygame, numpy, tensorflow (신경망 학습의 경우 케라스 일부가 필요할 수도 있음)
• renju.net의 오목 데이터