전체 글 (2) 썸네일형 리스트형 MCTS - Tic Tac Toe (Python) 저번 포스트에서 말했던 Tic-Tac-Toe 게임을 하는 바닐라 MCTS를 Python을 통해 구현해 보았다. Tic-Tac-Toe란?Tic-Tac-Toe란, 오목과 비슷한 서양 게임이다. 3x3의 판에서 3개를 가로/세로/대각선 방향으로 연속 3개를 먼저 놓는 사람이 이긴다.굉장히 간단한 게임으로, 양 쪽 플레이어가 합리적인 판단만을 한다면 항상 무승부만 나오는 게임이고, "올바른" 수가 모든 상황에서 항상 존재하기 때문에 MCTS 알고리즘의 검증용으로는 좋을 것 같다.후술할 설명을 더 간결하게 하기 위해, Tic-Tac-Toe 보드의 각 자리를 다음과 같이 숫자를 통해 설명하겠다.[ 1 2 3 ][ 4 5 6 ][ 7 8 9 ] 먼저, 선공을 잡은 플레이어는 항상 5번 자리에 놓는 것이 후공의 이기는.. MCTS란? Monte Carlo Tree Search(MCTS)는 2006년 Rémi Coulom이란 사람이 Monte Carlo Method를 게임 tree search에 접목하면서 만든 용어이다. 여기서 Monte Carlo는 확률적인 문제에 모나코의 유명한 도박장 이름(Monte Carlo)을 따서 붙이는 관습에서 온 것으로 보인다. 쉽게 말해 확률적 Tree Search라고 보아도 무방하지 않을까?Monte Carlo Method는 Random sampling을 반복하여 deterministic(결정론적 문제)한 문제를 해결하는 방법이다. 즉, 특정한 규칙을 따르지만 수학적/알고리즘적으로 분석하여 구현하기에는 너무나도 복잡한 시스템에 대해, 여러번 맨땅에 헤딩하면서 대략적인 규칙을 찾아내어가는 방법이라고 할.. 이전 1 다음
