-
A game of cops and robbers on planar graph
A game of cops and robbers on planar graph “Cops and Robbers” 게임은 그래프 $G$ 상에서 정의되는 추격-회피 문제의 한 유형이다. 이 게임은 두 명의 플레이어, ‘Cop’ (C)와 ‘Robber’ (R)가 참여한다. 게임의 규칙은 다음과 같다. 먼저 Cop이, 그 다음 Robber가 그래프 상의 정점을 선택하여 위치한다. 이후 두 플레이어는 교대로 인접한 정점으로 이동한다. Cop이 Robber와 동일한 정점을 차지하게 되면 Cop의 승리로, Robber가 이러한 상황을 무한히 회피할 수 있다면 Robber의 승리로 규정된다. 본 논의는 Robber가 현재 위치에...
-
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$인, 제로섬, 턴제, 완전정보, 결정론적 전이를...
-
Ladder Decomposition
개요 트리의 Ladder Decomposition은 Heavy-Light Decomposition과 유사하게, 트리를 경로들의 집합으로 분해하는 기법이다. 이번 글에서는 Ladder Decomposition의 정의와 알고리즘, 그리고 이를 응용해서 풀 수 있는 문제에 대해 알아보고자 한다. 정의 Ladder Decomposition를 한 문장으로 줄여 말하면 ‘HLD인데, subtree의 크기가 아니라 높이를 대신 본 것’ 이다. 구체적으로, Ladder Decomposition은 다음과 같은 알고리즘으로 구할 수 있다. 먼저 $h(u)$ 를 정점 $u$를 루트로 하는 서브트리의 높이라 정의하자. 루트부터 DFS를 실행하면서 정점 $v$에 도달 했을 때, $v$의 자식들이 $c_1$, $c_2$,...
-
Zip Tree
서론 Zip Tree는 Robert Tarjan, Caleb Levy, Stephen Timmel이 제시한 랜덤 기반의 Binary Search Tree의 일종이다. 논문에서는 Rotate연산 대신 Zip과 Unzip연산을 통해 트리의 균형을 맞춘다고 소개되어 있지만, 이는 사실 기존에 Treap 자료구조에 대해 다룬 논문에 기재된 Split과 Join연산의 구현과 구조가 동일하다. 본 글에서는 그럼에도 Zip Tree가 널리 알려진 Treap의 형태와 어떤 차이점이 있는지 소개하고, 얻을 수 있는 기대효과를 분석해 보고자 한다. Skip List vs Zip Tree Zip Tree는 Skip List를 Balanced Binary Search Tree로 변환한...
-
Lawson Algorithm을 통한 Delaunay triangulation 구하기
Lawson Algorithm을 통한 Delaunay triangulation 구하기 본 글은 평면 위 점들의 집합을 가장 안정적이고 균일한 삼각형들로 분할하는 Delaunay Triangulation을 종합적으로 탐구한다. 먼저 보로노이 다이어그램과의 관계 및 ‘빈 외접원 속성’을 통해 들로네 삼각분할의 수학적 정의를 명확히 하고, 이어서 고전적인 구축 방법인 Lawson’s algorithm을 분석한다. 마지막으로 이 알고리즘이 왜 항상 정확한 결과를 보장하는지를 증명하기 위해 2차원에서의 문제를 3차원으로 lifting하는 우아한 기법을 사용한다. 1. Delaunay triangulation의 정의와 최적성 평면에 분포된 유한한 점의 집합을 겹치지 않는 삼각형들로 분할하는 triangulation은...