Researches on the Artificial Intelligence has been explosively activated in various fields since the advent of AlphaGo. Particularly, researchers on the application of multi-layer neural network such as deep learning, and various machine learning algorithms are being focused actively. In this paper,...
Researches on the Artificial Intelligence has been explosively activated in various fields since the advent of AlphaGo. Particularly, researchers on the application of multi-layer neural network such as deep learning, and various machine learning algorithms are being focused actively. In this paper, we described a development of an artificial intelligence Janggi game based on reinforcement learning algorithm and MCTS (Monte Carlo Tree Search) algorithm with accumulated game data. The previous artificial intelligence games are mostly developed based on mini-max algorithm, which depends only on the results of the tree search algorithms. They cannot use of the real data from the games experts, nor cannot enhance the performance by learning. In this paper, we suggest our approach to overcome those limitations as follows. First, we collects Janggi expert's game data, which can reflect abundant real game results. Second, we create a graph structure by using the game data, which can remove redundant movement. And third, we apply the reinforcement learning algorithm and MCTS algorithm to select the best next move. In addition, the learned graph is stored by object serialization method to provide continuity of the game. The experiment of this study is done with two different types as follows. First, our system is confronted with other AI based system that is currently being served on the internet. Second, our system confronted with some Janggi experts who have winning records of more than 50%. Experimental results show that the rate of our system is significantly higher.
Researches on the Artificial Intelligence has been explosively activated in various fields since the advent of AlphaGo. Particularly, researchers on the application of multi-layer neural network such as deep learning, and various machine learning algorithms are being focused actively. In this paper, we described a development of an artificial intelligence Janggi game based on reinforcement learning algorithm and MCTS (Monte Carlo Tree Search) algorithm with accumulated game data. The previous artificial intelligence games are mostly developed based on mini-max algorithm, which depends only on the results of the tree search algorithms. They cannot use of the real data from the games experts, nor cannot enhance the performance by learning. In this paper, we suggest our approach to overcome those limitations as follows. First, we collects Janggi expert's game data, which can reflect abundant real game results. Second, we create a graph structure by using the game data, which can remove redundant movement. And third, we apply the reinforcement learning algorithm and MCTS algorithm to select the best next move. In addition, the learned graph is stored by object serialization method to provide continuity of the game. The experiment of this study is done with two different types as follows. First, our system is confronted with other AI based system that is currently being served on the internet. Second, our system confronted with some Janggi experts who have winning records of more than 50%. Experimental results show that the rate of our system is significantly higher.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 연구에서 개발한 알고리즘의 성능을 평가하기 위하여 현재 온라인 서비스되는 장기 AI와 테스트를 진행하였다. 테스트 결과 [Table 4]와 같이 무승부를 제외하고 약 59%의 승률을 확인할 수 있었다.
본 연구에서는 기보를 이용한 학습 과정에서 다음 식 (1)과 같이 MDP State Value Function 학습 알고리즘을 장기에 맞게 적용하여 각 상태의 가치를 조절하고자 한다(Feinberg and Shwartz, 2002). 수식에서 R은 해당 State의 기댓값이며 r0, r1, .
본 연구에서는 생성된 그래프와 학습이 완료된 그래프의 현재 상태를 유지하여 다음 대국에 활용하기 위하여, 전체 그래프를 객체 직렬화(Object Serialization) 방식을 사용하여 저장하였다. 객체 직렬화는 [Figure 9]와 같이 메모리에 있는 정보들을 연속적인 바이트로 변환하고, 변환된 바이트를 다시 원래의 객체로 복원하는 방법을 말한다.
, 2016). 본 연구에서는 우선 게임의 기본이 되는 보드게임의 학습 알고리즘 개발을 통해 성능을 테스트 뒤, 해당 알고리즘을 다른 게임에 적용할 방법을 발전적으로 연구하고자 한다.
본 연구에서는 이러한 기존 연구들의 장점과 또한 제한점을 분석 하여, 보다 우수한 승률을 얻고자 다음과 같이 접근하고자 한다. 첫째, 단순히 트리탐색 알고리즘에 의존적이 아닌 장기 우승자들의 누적된 기보를 활용한 학습방식을 적용함으로 더 풍부한 실전 결과를 반영할 수 있게 한다.
본 연구에서는 이러한 문제점들을 극복하기 위하여, 학습 데이터가 비교적 충분히 존재하고, 수많은 실전 대국을 통하여 해당 데이터들의 신뢰도가 어느 정도 확보된 장기 기보들을 수집하여 강화학습과 Monte Carlo Tree Search(MCTS) 알고리즘(Browne et al., 2012)을 적용하는 인공지능 장기게임을 개발하고자 한다. 장기와 같은 보드게임은 인공지능 분야에서 알고리즘의 성능을 가시적으로 확인할 수 있고 게임 종류에 따라 다양한 복잡도를 가지고 있어 알고리즘 수행 시간과 복잡도의 관계를 확인하기 위한 테스트를 진행할 수 있어 연구목적으로 많이 사용되어 왔다(Kulsinskas et al.
객체 직렬화는 [Figure 9]와 같이 메모리에 있는 정보들을 연속적인 바이트로 변환하고, 변환된 바이트를 다시 원래의 객체로 복원하는 방법을 말한다. 본 연구에서는 이렇게 생성된 구조를 바탕으로 학습 정책과 알고리즘을 테스트하였다.
본 연구에서는 학습 알고리즘의 연구를 위해 장기소프트웨어를 개발하였으며, 연구의 주요 관점은 다음과 같다. 첫째, 단순 트리탐색 알고리즘에 의존하지 않고 장기 전문가들의 누적된 데이터를 활용함으로서 시스템개발에 보다 풍부한 실전결과를 반영할 수 있다.
제안 방법
셋째, 대전을 반복 할수록 우수한 승률을 얻기 위해 보드상황에 따라 강화학습 알고리즘과 MCTS 알고리즘을 응용함으로서 합리적 시간 내에 가장 좋은 다음수를 선택할 수 있다. 넷째, 이러한 대량의 데이터는 실시간으로 분석하고 처리하기 어렵기 때문에 해쉬 알고리즘을 다중 처리하여 해결하였다. 다섯째, 또한 학습된 그래프를 객체 직렬화 방식으로 저장하여 게임의 지속성을 제공하게 하였다.
넷째, 이러한 대량의 데이터는 실시간으로 분석하고 처리하기 어렵기 때문에 해쉬 알고리즘을 다중 처리하여 해결하였다. 다섯째, 또한 학습된 그래프를 객체 직렬화 방식으로 저장하여 게임의 지속성을 제공하게 하였다. 마지막으로, VR기기를 이용해 인터페이스를 개발함으로써 사용자 친화적 인터페이스 기능을 제공하였다.
두 번째 학습 방식은 [Figure 8]과 같이 가장 하위 노드에서 승/패를 판단한 뒤 0.5의 Discount 값을 이용하여 강화학습 중 MDP State Value Function을 이용한다. 승자일 경우에는 현재 노드점수를 현재 노드 점수+(하위 노드 점수×0.
첫째, 단순히 트리탐색 알고리즘에 의존적이 아닌 장기 우승자들의 누적된 기보를 활용한 학습방식을 적용함으로 더 풍부한 실전 결과를 반영할 수 있게 한다. 둘째, 기존 연구들에서 트리구조를 사용한 것과는 달리, 장기의 특성상 같은 상태를 중복시키지 않기 위하여 기보를 그래프 구조로 생성하여 사용하고자 한다. 셋째, 대전을 반복할수록 보다 우수한 승률을 얻기 위하여 보드 상황에 따라 강화 학습알고리즘을 수행하며, 학습된 그래프 상에서 MCTS 알고리즘을 응용하여 합리적인 시간 내에 가장 좋은 다음 수를 선택하게 된다.
첫째, 단순 트리탐색 알고리즘에 의존하지 않고 장기 전문가들의 누적된 데이터를 활용함으로서 시스템개발에 보다 풍부한 실전결과를 반영할 수 있다. 둘째, 장기 게임의 특성상 같은 상태가 중복시키지 않기 위한 그래프 구조를 사용하였다. 셋째, 대전을 반복 할수록 우수한 승률을 얻기 위해 보드상황에 따라 강화학습 알고리즘과 MCTS 알고리즘을 응용함으로서 합리적 시간 내에 가장 좋은 다음수를 선택할 수 있다.
그래프의 중복 검사는 수백만 개에 대해 진행되어야 하므로 선형적으로 찾기에는 제한이 있다. 따라서 본 연구에서는 해쉬(Hash) 알고리즘을 적용함으로써 속도를 향상시킬 수 있도록 한다. 본 연구의 해쉬 알고리즘은 [Figure 5]와 같이 3번의 단계를 거친다.
다섯째, 또한 학습된 그래프를 객체 직렬화 방식으로 저장하여 게임의 지속성을 제공하게 하였다. 마지막으로, VR기기를 이용해 인터페이스를 개발함으로써 사용자 친화적 인터페이스 기능을 제공하였다.
본 연구에서는 그래프 생성 과정과 학습 과정, 수 선택 알고리즘 과정 등에서 일치하는 상태 노드를 빠르게 찾기 위해 해쉬 알고리즘을 사용하였다. 아래 [Table 3]과 같이 해쉬 알고리즘을 단계적으로 추가 적용하며 테스트한 결과 해쉬 함수를 사용하지 않았을 때와 비교하여 약 194.
본 연구에서는 장기 게임을 구현하여 학습 알고리즘의 성능을 확인하였고 실험 방식은 현재 서비스 되고 있는 다른 인공지능 및 온라인 장기 사용자들과 대국을 통해 진행하였다.
본 연구에서는 학습 과정과 수를 선택하는 일련의 과정에서 MCTS의 각 과정을 나누어 필요한 부분에 적용함으로써 각 상태의 가치를 조절하고 수를 선택할 수 있도록 적용한다.
본 연구의 결과를 사용자 입장의 인터페이스 시스템을 구축하기 위해 유니티 엔진을 이용하여 구현하였다. 처음 게임이 시작되면 상차림을 선택할 수 있고, 움직일 수 있는 말을 선택하였을 때는 [Figure 10]과 같이 2D 상태로 말을 움직일 수 있는 위치를 표시해 준다.
본 연구의 실험은 현재 온라인 또는 모바일상에서 서비스 되고 있는 장기 인공지능과 본 연구의 시스템이 대국을 하거나, 또는 온라인상의 장기고수들과 본 연구의 시스템이 대국을 하는 방식으로 알파고의 진행과 유사하게 대국을 하게 된다. 시스템의 성능평가는 이러한 방식으로 대국을 진행한 결과를 통하여 누적된 승률을 산출하여 평가할 수 있다.
학습 프로그램은 생성된 그래프와 기보 파일을 이용하며, 학습은 다음 2번의 과정을 통해 이루어진다. 첫째, 각 노드에서 움직임에 따라 가치를 조정하고, 둘째, 전체 게임에서 승/패에 따라 강화학습 방식을 적용한다. 학습 적용 전 각 말 가치의 초기 값은 [Table 1]과 같이 장기 협회에서 지정한 기물 점수를 적용한다.
대상 데이터
본 연구의 시스템은 [Figure 1]과 같이 크게 서버 엔진, 사용자 인터페이스 엔진으로 구성된다. 서버 엔진은 다수의 세부 모듈로 구성되며 시스템의 주 알고리즘을 수행하게 된다.
이론/모형
, 2010; Wu and Tao, 2016). 학습의 방식도 일부 사용하였으나 대부분 알고리즘을 이용한 학습이 아니라 개발된 AI끼리 지속적인 대국을 통해 패배한 경로를 다시 가지 않도록 구현하는 방식(Ong et al., 2007)을 사용하였다. 이러한 연구는 정교한 알고리즘의 성능으로 가시적인 성과를 보이고 있으나, 기존의 트리탐색의 범위를 벗어나지 못하는 제한점이 있다.
성능/효과
무승부는 게임 대결 시 장기 게임의 특징인 같은 수의 반복이 일어나는 경우 게임을 종료한 경우이다. 또한, 온라인 서비스를 통해 장기게임 사용자들과 테스트를 진행한 결과 무승부를 제외하고 약 85.4%의 승률을 확인할 수 있었다. 테스트 대상자는 장기 초보자가 아니고 중수 급 이상의 실력자임을 확인하기 위하여 300전 이상,승률 50% 이상인 경우에만 테스트를 진행하였다.
또한, 본 연구에서 개발한 알고리즘과 단순 MIN/MAX 알고리즘과의 비교 실험을 진행하고자 하였으나 장기의 특성상, 계속해서 같은 수를 반복하는 문제로 인하여 불가능하였고, 또한 상대적인 비교를 위해 같은 온라인 AI를 상대로 테스트를 진행하고자 하였으나 단순 MIN/MAX 알고리즘으로는 온라인 AI와의 대결에서 승률이 저조하기 때문에 비교 대결이 무의미하였다. 반면 학습 알고리즘을 적용한 결과가 훨씬 더 우수한 성능을 가진다는 결과를 간접적으로 확인할 수 있었다.
둘째, 장기 게임의 특성상 같은 상태가 중복시키지 않기 위한 그래프 구조를 사용하였다. 셋째, 대전을 반복 할수록 우수한 승률을 얻기 위해 보드상황에 따라 강화학습 알고리즘과 MCTS 알고리즘을 응용함으로서 합리적 시간 내에 가장 좋은 다음수를 선택할 수 있다. 넷째, 이러한 대량의 데이터는 실시간으로 분석하고 처리하기 어렵기 때문에 해쉬 알고리즘을 다중 처리하여 해결하였다.
둘째, 기존 연구들에서 트리구조를 사용한 것과는 달리, 장기의 특성상 같은 상태를 중복시키지 않기 위하여 기보를 그래프 구조로 생성하여 사용하고자 한다. 셋째, 대전을 반복할수록 보다 우수한 승률을 얻기 위하여 보드 상황에 따라 강화 학습알고리즘을 수행하며, 학습된 그래프 상에서 MCTS 알고리즘을 응용하여 합리적인 시간 내에 가장 좋은 다음 수를 선택하게 된다.
본 연구에서는 그래프 생성 과정과 학습 과정, 수 선택 알고리즘 과정 등에서 일치하는 상태 노드를 빠르게 찾기 위해 해쉬 알고리즘을 사용하였다. 아래 [Table 3]과 같이 해쉬 알고리즘을 단계적으로 추가 적용하며 테스트한 결과 해쉬 함수를 사용하지 않았을 때와 비교하여 약 194.28배의 성능 향상 결과를 얻을 수 있었다.
본 연구에서는 학습 알고리즘의 연구를 위해 장기소프트웨어를 개발하였으며, 연구의 주요 관점은 다음과 같다. 첫째, 단순 트리탐색 알고리즘에 의존하지 않고 장기 전문가들의 누적된 데이터를 활용함으로서 시스템개발에 보다 풍부한 실전결과를 반영할 수 있다. 둘째, 장기 게임의 특성상 같은 상태가 중복시키지 않기 위한 그래프 구조를 사용하였다.
본 연구에서는 이러한 기존 연구들의 장점과 또한 제한점을 분석 하여, 보다 우수한 승률을 얻고자 다음과 같이 접근하고자 한다. 첫째, 단순히 트리탐색 알고리즘에 의존적이 아닌 장기 우승자들의 누적된 기보를 활용한 학습방식을 적용함으로 더 풍부한 실전 결과를 반영할 수 있게 한다. 둘째, 기존 연구들에서 트리구조를 사용한 것과는 달리, 장기의 특성상 같은 상태를 중복시키지 않기 위하여 기보를 그래프 구조로 생성하여 사용하고자 한다.
본 연구에서 개발한 알고리즘의 성능을 평가하기 위하여 현재 온라인 서비스되는 장기 AI와 테스트를 진행하였다. 테스트 결과 [Table 4]와 같이 무승부를 제외하고 약 59%의 승률을 확인할 수 있었다. 무승부는 게임 대결 시 장기 게임의 특징인 같은 수의 반복이 일어나는 경우 게임을 종료한 경우이다.
후속연구
현재 구현된 시스템은 신경망을 이용한 알파고와 객관적인 성능을 비교하였을 때 부족한 알고리즘의 성능을 보인다. 따라서, 향후 연구에서는 첫째, 신뢰성이 있는 기보를 추가적으로 확보하고, 둘째, 학습 알고리즘을 다양하게 융합하여 접근해볼 것이며, 셋째, 알파고와 같이 자체 시스템끼리 테스트가 가능하도록 시스템의 성능을 향상할 수 있도록 할 것이다.
, 2007)을 사용하였다. 이러한 연구는 정교한 알고리즘의 성능으로 가시적인 성과를 보이고 있으나, 기존의 트리탐색의 범위를 벗어나지 못하는 제한점이 있다. 또한 알고리즘의 범위 내에서만 처리되기 때문에 시스템의 성능을 스스로 향상시키지 못하는 제한점이 있다.
질의응답
핵심어
질문
논문에서 추출한 답변
MIN MAX 알고리즘이란?
MCTS 알고리즘은 기존의 MIN MAX 알고리즘의 한계를 극복하기 위한 접근 방식이다. MIN MAX 알고리즘은 각 상태에서 나올 수 있는 모든 다음 상태를 계속 이어나가며 지정된 깊이까지 모든 상태를 만든 뒤 계층별로 가장 가치가 높은 값/가장 가치가 낮은 값을 번갈아 가며 선택하여 현재상태에게 가장 유리한 수를 찾는 방식이다(Rivest, 1987). 그러나 MIN MAX 알고리즘은 모든 경우의 수를 판단해야 하기 때문에 깊이를 깊게 보거나 바둑과 같이 경우의 수가 커질 경우 실행 시간이 길어지기 때문에 성능 향상을 시키는데 한계를 가지고 있었다.
강화학습이란?
강화학습은 현재 상태(State)에서 어떤 행동(Action)을 취하는 것이 최적인지 학습하는 방식이다. 행동 결과에 따라 보상(Reward) 값을 줌으로써 옳은 행동일 경우 플러스 점수를 얻게 되고 잘못된 행동일 경우 마이너스 점수를 주는 방식으로 구현한다.
강화학습은 어떠한 방식으로 구현하는가?
강화학습은 현재 상태(State)에서 어떤 행동(Action)을 취하는 것이 최적인지 학습하는 방식이다. 행동 결과에 따라 보상(Reward) 값을 줌으로써 옳은 행동일 경우 플러스 점수를 얻게 되고 잘못된 행동일 경우 마이너스 점수를 주는 방식으로 구현한다. 일반적으로 유한한 상태일 경우 MDP(Markov Decision Process)로 표현이 가능하며 이미 존재하는 상태의 데이터와 존재하지 않는 상태와의 균형을 잡는 데 적합하다.
참고문헌 (18)
Bang, J.S., D.C. Lee, S.H. Seo, Y.J. Kim, H.J. Lee, and W.H. Son, "Trends of VR/AR Game Technology", Electronics and Telecommunications Trends, Vol.31, No.1, 2016, 146-156. (방준성, 이동춘, 서상현, 김용준, 이헌주, 손욱호, "VR/AR 게임기술 동향", 전자통신동향분석, 제31권, 제1호, 2016, 146-156.
Browne, C., E. Powley, D. Whitehouse, S. Lucas, P. Cowling, and P. Rohlfshagen, "A Survey of Monte Carlo Tree Search Methods", IEEE Transactions on Computational Intelligence and AI in Games, Vol.4, No.1, 2012, 1-49.
Cho, B.H. and C.J. Park, "Research Trends in Game AI", Electronics and Tellecommunications Trends, Vol.23, No.4, 2008, 115-121. (조병헌, 박창준, "게임 인공지능 연구동향", 전자 통신동향분석, 제23권, 제4호, 2008, 115-121.)
Fan, Y.F., X.J. Bai, R.Y. Lui, and S. Xing, "The Research of Chinese Chess Based on Database with Self Learning", Proceedings of the Ninth International Conference on Machine Learning and Cybernetics, 2010, 319-322.
Feinberg, E. and A. Shwartz, Handbook of Markov Decision Processes, Kluwer, Boston, MA, 2002.
Ingram, J. and J. Mcgregor, "A Look at the Future of Autonomous Connected Vehicle Systems", Proceedings of International Conference on Software Engineering and Data Engineering, Vol.23, 2015, 162-177.
Kim, S.W., S.W. Ahn, and H.S. Choo, "Artificial Intelligence of AlphaGo", SPRi Issue Report, 2016-001, Vol.1, 2016. (김석원, 안성원, 추형석, "AlphaGo의 인공지능", SPRi Issue Report, 제2016-001호, 제1호, 2016.)
Kulsinskas, A., C. Balan, N. Bukdahl, and A. Brooks, "Augmentation of Board Games Using Smartphones", Lecture Notes in Computer Science, Vol.2015, No.9177, 2015, 483-492.
Mandziuk, J., Knowledge-Free and Learning-based Methods in Intelligent Game Playing, Springer, Berlin, 2010.
Millington, I. and J. Funge, Artificial Intelligence for Games, Elsevier Inc., Berlington, MA, 2009.
Ong, C., H. Quek, K. Tan, and A. Tay, "Dis covering Chinese Chess Strategies through Co-evolutionary Approaches," IEEE Symposium on Computational Intelligence and Games, 2007, 360-367.
Park, D.S., "ICT Convergence Industry Outlook in the Era of Artificial Intelligence," 2017 ICT Industry Outlook Conference, 2016. (박대수, "인공지능 시대의 ICT융합 산업 전망", 2017 ICT산업 전망 컨퍼런스, 2016.)
Park, H.S. and K.J. Kim, "Latest Research Trend of Artificial Intelligence in Games", Journal of Korean Institute of Information Scientists and Engineers(KIISE), Vol.31, No.7, 2013, 8-15. (박현수, 김경중, "게임 인공지능 최신 연구동향", 정보과학회지, 제31권, 제7호, 2013, 8-15.)
Rivest, R., "Game Tree Searching by Min/Max Approximation", Artificial Intelligence, Vol. 34, No.1, 1987, 77-96.
Robilliard, D. and C. Fonlupt, "Towards Human-Competitive Game Playing for Complex Board Games with Genetic Programming", Lecture Notes in Computer Science, Vol.2016, No.9554, 2015, 123-135.
Spencer, P. and J. Oommen, "Novel AI Strategies for Multi-Player Games at Intermediate Board States", Lecture Notes in Computer Science, Vol.2015, No.9101, 2015, 33-42.
Silver, D., A. Huang, C. Maddison, A. Guez, L. Sifre, and G. Driessche, "Mastering the Game of Go with Deep Neural Networks and Tree Search", Nature, Vol.529, 2016, 484-489.
Wu, G. and J. Tao, "Chinese Chess Algorithm Design and Implementation in the Computer Games", Proceedings of the 35th Chinese Control Conference, 2016, 10380-10384.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.