Artificial Intelligence (AI) defeated many perfect information games such as checkers, chess, backgammon, othello, scrabble, and so on. In addition the game of Go is the most challengeable perfect information game. Recently, AlphaGo won human champion, Sedol Lee. Through this work, AI can be applied to solve games given perfect information entirely.
Next goal of AI is imperfect information game. Major difference between perfect information games and imperfect information games are whether there are hidden information or not. Leading approach of imperfect information games is Nash equilibrium. But, this method has large computational costs in some cases.
To overcome this, we propose a new approach which predicts hidden information by using observable data. Information of positions and the kinds of tiles are used as input. If hidden information were perfectly predicted, we don’t need to find Nash equilibrium. Also our model can combine with other existing algorithm using perfect information games.
To evaluate our approach, Japanese Mahjong is selected between several imperfect information games. Because, there are usable public data. The prediction accuracy in training is almost 100 percent and the prediction accuracy in test is about 86.5 percent. By using given observable information, three opponent players’ private hand tiles are predicted successfully.
본 논문에서는 불완전 정보 게임에서 존재하는 숨겨진 정보를 획득 가능한 공개된 정보를 활용하여 예측하였다. 일반적으로 불완전 정보 게임을 해결하기 위한 접근 방법은 내쉬 평형상태이다. 첫째로, 본 게임을 전략적으로 유사하지만 더 작은 게임으로 추상화시킨다. 그 후, 추상화된 게임에서 내쉬 평형상태를 찾는다. 마지막으로, 찾아낸 내쉬 평형상태를 본 게임으로 되돌린다. 하지만, 경우에 따라 이것은 많은 계산 시간을 요구한다. 만약 숨겨진 정보를 거의 완벽하게 예측할 수 있다면, 기존에 완전 정보 게임의 강력한 해결 알고리즘을 사용할 수 있게 된다. 이것을 보이기 위해, 여러 불완전 정보 게임 중에서 일본 마작을 선택하였다. 일본 온라인 마작 사이트에서 공개된 게임 기록을 구할 수 있으며 주어진 관측 가능한 정보가 있기 때문이다.
여러 방식의 입력과 출력이 제안되었다. 기본적으로 위치와 해당 위치에서 어떤 종류의 패가 있는지에 대한 정보가 사용되었다. 그것이 가장 기본적인 정보이기 때문이고 알파고 또한 위치와 해당 위치에서 돌 색깔 정보만을 이용해서 상당히 좋은 성능을 첫 번째 단계에서 획득하였기 때문이다. 제안된 여러 입출력 방식 중에서 첫 번째 방식의 변형이 선택되었다. 이 방식은 첫 번째 방식의 장점인 입력 데이터의 특성이 균일하다는 점을 가지면서, 출력에서 유사한 패의 집합이 서로 다른 패턴을 만드는 문제를 약화시켰다. 이 방식을 사용했을 때, 다른 방식에 비해서 더 좋은 성능을 얻을 수 있었다.
학습 단계에서 상대방 패에 대한 예측 성능은 거의 100%에 도달했다. 테스트 단계에서의 예측 성능은 약 86.5%에 도달했다. 이 수치는 기본적으로 상대방 비공개 손패의 개수인 13개의 패 중에 약 11개 이상의 패를 정확하게 예측했음을 의미한다. 이 정도 수준의 정확도로 예측된 정보를 가지고 게임을 하는 것은 그렇지 않을 때에 비해 난이도가 굉장히 낮아짐에 틀림없다. 이러한 성공적인 결과는 비단 일본 마작뿐만 아니라 경매, 협상, 보안 등과 같은 다른 분야에서도 적용될 수 있다.
첫 번째 방식의 변형을 사용함으로써 좋은 성능을 얻을 수 있었지만, 입력 차원이 너무 큰 문제가 있다. 입력 데이터의 특성을 균일하게 하면서 입력 차원의 크기를 줄이는 방법이 필요하다. 큰 입력 차원은 학습 시간을 길게 하고 학습시켜야 할 파라미터를 증가시킨다. 이것을 극복하기 위해, 합성곱 신경 회로망을 적용해 볼 수 있다. 일본 마작에서, 세 개의 동일한 패와 세 개의 연속한 패가 중요한 의미를 가진다. 합성곱 신경 회로망의 필터가 이러한 모양을 찾아낼 수 있을 것이다. 또한 본 논문에서는 긴 학습 시간으로 인해 학습과 테스트에 오직 2009년도 데이터만 사용하였다. 이로 인해, 학습 데이터로 백만 개의 데이터를 사용하였다. 하지만 알파고는 첫 번째 단계에서 약 3천만 개의 데이터를 사용하였다. 본 논문에서 사용하지 않은 2010년도부터 2015년도까지의 데이터를 모두 사용한다면 훨씬 많은 데이터를 학습과 테스트에 사용할 수 있다. 만약 모든 데이터를 사용한다면 성능을 더 향상시킬 수 있을 것이다.
또한, 몇몇 구역에서 낮은 테스트 성능이 관측되었다. 그 이유는 입력 데이터가 공개된 패의 개수에 따라 다른 특성을 가지기 때문으로 추정된다. 만약 공개된 패의 개수에 따라 여러 네트워크를 학습시킨다면, 이 문제를 해결할 수 있을 것이다. 그렇다면 전체 테스트 성능 또한 증가할 것이다.
