15개의 검은 말이 모두 16번으로 이동한 후 빠져나오면 검은 말이 이기고, 빨간 말이 1924로 이동한 후 먼저 빠져나와면 빨간 말이 이깁니다.
주사위를 굴려 나온 수만큼 한 개의 말을 이동시킬 수 있습니다. 주사위는 2번 던져 서로 다른 말에 적용시킵니다. 하지만 24번의 검은말 하나가 주사위 5가 나와 빨간말로 꽉 찬 19번으로 이동할 수 없습니다. 막는 것이 일종의 전략이 될 수 있습니다.
또한 빨간말이 하나뿐이라면 검은 말이 빨간 말을 잡을 수 있습니다.
잡은 말은 바깥에 두었다가 처음 위치에서 다시 시작해야 합니다.
서로 다른 상태가 10^20개 이상 있으므로 근사 가치함수를 사용합니다.
은닉층이 하나인 MLP를 사용하였고,
검은 말, 빨간 말이 놓인 위치를 표현하기 위해 24개 위치 각각에 노드를 4개씩 배정하였습니다.
2 * 24 * 4 = 192개의 노드가 사용됩니다.
또한 시간차 알고리즘을 사용해서 TD-gammon이라 불립니다.(Tesauro, 1995)
TD-gammon은 사람의 전략을 가르쳐 주지 않은 채 프로그램 2개가 겨루는 과정에서 학습하는 self-play 방식입니다.
승패의 여부에 따라 상태에 +1, -1 보상을 부여하고 보상이 TDL 알고리즘을 통해 이전 상태로 파급됩니다.
TD-gammon은 지도학습을 전혀 이용하지 않고 자가 플레이로 세계 챔피언 수준에 도달하였습니다.
강화학습과 보드게임
틱택토(tic-tac-toe), checkers, 체스, 장기, 바둑입니다.
보드게임을 가장 잘하기 위한 강화학습 연구가 진행되었고 가장 어려운 바둑에서 세계 챔피언 수준의 이세돌을 4:1로 이기는 성과를 기록합니다.
틱택토는 상태의 수가 3^9=19,6833^9=19,683 정도로 근사 가치함수를 사용하지 않더라도 쉽게 최적 정책을 알아낼 수 있습니다.
틱택토는 새로운 프로그램을 테스트하는 용도로 자주 쓰입니다.
checkers는 열약한 하드웨어에서도 체커 게임을 해결하는 시도를 하였습니다.(Samuel, 1959)
체스는 Deepblue라는 프로그램이 세계 챔피언을 이겼습니다.(Campbell, 2002)
당시 VLSI칩은 딥블루라는 슈퍼컴퓨터로 발전하였고, 당시에는 기계 학습 알고리즘보다 하드웨어 속도를 향상시켜 높은 수준을 달성하였습니다. 장기도 이와 마찬가지입니다.
바둑은 훨씬 탐색 공간이 커서 고성능 하드웨어에도 한계가 있었습니다. alphago는 몬테카를로 트리탐색, 프로기사들의 기보를 활용한 지도학습, self-play를 활용한 강화학습, CNN 적용, 고성능 하드웨어와 결합하여 세계 챔피언을 이길 수 있었습니다.(Silver, 2016)
2) DQN: Atari video game
므니 등은 Atari 2600 게임 49종에서 자동으로 플레이하는 프로그램을 개발하였습니다. (Mnih et al., 2015)
다양한 게임 해서 동일한 입력, 신경망 구조, 하이퍼 파라미터를 사용하여 전문 플레이어 수준을 달성하였습니다. 29종에서 좋은 성능을 보였습니다.
CNN과 Q-Learning을 결합한 DQN으로 상태를 입력하고, 게임 종류마다 필요한 만큼 출력 노드를 정합니다.
