-
Advanced Game Search Algorithms (1)
1. Introduction 이번 글에서는 게임 에이전트의 가장 단순한 형태인 Random Agent부터 시작하여 Greedy, Minimax, Alpha-Beta Pruning의 핵심 원리를 다룹니다. 이후 이어지는 글에서는 MCTS 등의 현대적인 탐색 기법을 알아보고, NNUE 등의 neural network를 이용한 평가 방법과 여러 search Pruning 방법을 살펴보겠습니다. 또한 에이전트의 성능을 객관적으로 평가하기 위해 SPRT(Sequential Probability Ratio Test)라는 평가 기법을 소개합니다. 이를 이용하면 통계적으로 두 에이전트 간의 실력 차이를 엄밀하게 검증할 수 있습니다. 이번 글에서 소개하는 방법론은 $2$인, 제로섬, 턴제, 완전정보, 결정론적 전이를...
-
Impartial Games
목차 $Impartial$ $game$ $Nim$ $game$ $Grundy$ $number$ 1. Impartial game $Impratial$ $game$ 이란 직역하면 공정한 게임이란 의미로, 게임 내에서 모든 플레이어가 동일한 조건으로 게임을 하는 것을 의미하는데, 이와 반대로 동일한 조건이 아닌 게임을 하는 것을 $Partisan$ $game$이라고 합니다. $Impartial$ $game$ 의 예로 우리가 흔히하는 베스킨라빈스 31이라는 게임이 있는데, 이 게임은 모든 플레이어가 동일하게 현재 숫자에서 1 ~ 3 사이의 수만큼 증가시키고 31이 될 경우 지게되는 게임이다. 이러한 $Impartial$ $game$에서 두 명의 플레이어가 있을 때 서로...