게임 탐색

개념

게임 탐색은 상대가 있는 상황에서 좋은 수를 찾는 탐색이다. 혼자 목표 상태로 가는 탐색과 달리, 상대가 내게 불리한 선택을 한다고 가정해야 한다.

대표 알고리즘

• 미니맥스 알고리즘: 내가 유리한 수를 최대화하고 상대가 내 점수를 최소화한다고 가정
• 알파-베타 가지치기: 결과에 영향을 주지 않는 가지를 줄여 미니맥스 계산을 줄임
• MCTS: 많은 시뮬레이션을 통해 승률이 높은 수를 찾음

게임의 특징

틱택토는 3x3 격자에서 수평, 수직, 대각선으로 세 칸을 먼저 차지하면 이기는 게임이다. 상태 공간이 작아 완전 탐색으로 승리, 무승부, 패배를 평가할 수 있다. MCTS를 적용하면 가능한 수를 자식 노드로 만들고 여러 번 게임을 진행해 승률을 추정할 수도 있다.

체스나 바둑처럼 상태 공간이 크면 끝까지 탐색할 수 없으므로 휴리스틱 탐색이나 MCTS 같은 방법이 필요하다.

평균 분기 수가 $b$이고 탐색 깊이가 $d$이면 게임 트리의 노드 수는 대략 다음 규모로 증가한다.

$$1+b+b^2+\cdots +b^d=O(b^d)$$