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