Quoridor Pseudo Code

쿼리도

규칙

1. 자신의 앞줄 중간에 말을 놓는다.
2. $n$번째 플레이어가 말을 움직이거나 벽을 세운다.
3. $turnNum + 1$을 한다.
4. 2~3번 과정을 게임이 끝날때 까지 반복한다.

게임은 임의의 말이 반대편 첫줄에 도착하면 종료된다.

쿼리도 필승 전략

핵심 규칙은 상대방이 못움직이게 가두면 안된다는 것이다. -> 장애물을 놓을 때 최소 1칸의 움직일수 있는 공간을 남겨야 한다. 내 게임말 뒤에 장애물을 둔다면 내 경로에는 지장을 주지 않기 때문에 유리하다.

실러 오프닝: 상대방과 내가 모두 3칸을 전진했다면, 내 게임 말의 뒤에 세로로 장애물을 세우는 것이다. 게임말의 움직임: 무한히 사용할수 있는 자원이다. 장애물: 개수가 한정되어 있는 자원이다.

쿼리도의 승리 전략은 내가 움직여야하는 거리는 최소한으로 만들고 상대방이 움직여야 하는 거리는 늘리는 것이다.

장애물이 내 앞을 막았을 경우에는 남은 칸수가 홀수인 칸으로 이동하는 것이 유리하다. 홀수인 칸을 막기 위해서는 더 많은 장애물이 필요하기 때문이다. 이는 게임판은 가로 세로 9칸씩 존재하지만 장애물이 막을수 있는 칸 수는 2칸이기에 항상 한칸이 남게 되기에 남은 칸이 홀수인 곳으로 움직이는 것이 유리하다. 또 한칸인 칸을 막기 위해서는 장애물이 1개 이상 필요하기 때문에 상대방의 장애물 사용또한 압박 할수 있다.

따라서 선수를 잡았을 경우 실러 오프닝으로 시작하여 상대의 왼쪽 길을 차단한후 오른쪽 길을 압박하면 쉽게 이길수 있다.

의사 코드 설명

Initialize turnNum 0

FOR $until game is over, |n, N$:
  Set Player n%2
  Execute Player Action
  Add 1 to turnNum
END FOR

AI(DQN)

메커니즘

목적 보상을 극대화하기 위한 action을 예측한다.

$Q'(s,a) = \underset{\pi}{\max}\mathbb{E}\left[ r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + ... \vert s_t=s, a_t=a, \pi \right]$

이때 $r_t$는 보상을 의미하며 $\gamma$는 현재 상태에서 멀어지는 상태에 대한 action에 따른 보상에 대한 중요성을 낮추기 위한 감소요인으로 작용하며 $t$는 각 time step을 의미한다.
$\pi = P(a \vert s)$ 로 s상태가 일어났을때 action을 할 확률 즉 행동에 재한 정책을 나타내며 $s$는 관측값을 나타내고 $a$는 action을 나타낸다.
이때 $Q$함수를 파라미터화 시켜야 하는데 정책으로 부터 예측 되는 action을 파라미터화 하여 다음과 같이 나타낸다.

$Q(s,a; \theta_i)$

이때 $\theta$는 deep convolutional neural network에서 사용하는 파라미터이며 $\theta_i$ 는 $iteration$ $i$ 에서의 파라미터이다.

DQN알고리즘은 관측 시퀀스에 따른 상관관계를 없애기 위해 replay 방식의 학습을 진행하며
이때 각 관측경험 experience를 $e_t = \set{s_t, a_t, r_t, s_{t+1}}$ 로 나타낸다.
이 경험에 대한 데이터들은 $D_t = \set{e_1, ... , e_t}$ 에 저장된다.

이 에이전트를 학습 시키기 위해서는 손실합수(=비용함수)가 필요한데 이 비용함수는 다음과 같다.

$L_i\left(\theta_i\right)=\mathbb{E}_{\left(s,a,r,s'\right) \sim U(D)}\left[\left( r+\gamma \underset{a'}{\max}Q(s',a';\theta^-_i - Q(s,a;\theta_i)\right)^2\right]$

이 수식에서 $\gamma$는 현재 상태에서의 행동에 대한 보상의 예측값이 현재 상태와 멀어질수록 감소시키는 감소요인이 된다.
또한 $\theta^-_i$는 네트워크의 파라미터 이며 $target$값을 계산하기 위해 $iteration$ $i$에 사용된다.

의사 코드 설명

Algorithm: DQN with experience replay.
Initialize replay memory D to capacity N
Initialize target action-value function $Q$ with random weights $\theta$
Initialize action-value function $\hat{Q}$ with weights $\theta^- = \theta$
For $episode=1, M$ do
       Initailize sequence $s_1 = \set{x_1}$ and preprocessed sequence $\phi=\phi(s_1)$
       For $t=1, T$ do
               With probability $\mathcal{E}$ select a random action $a_t$
               otherwise select $a_t = argmax_a Q(\phi(s_t),a;\theta)$
               Execute action $a_t$ in emulator and observe reward $r_t$ and image $x_{t+1}$
               Set $s_{t+1}=s_t,a_t,x_{t+1}$ and preprocess $\phi_{t+1}=\phi(s_{t+1})$
               Store transition $\left( \phi, a_t,r_t,\phi_{t+1} \right)$ in $D$
               Sample random minibatch of transitions $\left( \phi_j,a_j,r_j,\phi_{j+1}\right)$ from $D$
               If episode terminates at step j+1: Set $y_j=r_j$
               Else: Set $y_j=r_j+\gamma max_a'\hat{Q}(\phi_{j+1},a';\theta^-)$
               Perform a gradient descent step on $(y_j-Q(\phi_j,a_j;\theta))^2$ with respect to the network parameters $\theta$
               Every $C$ steps reset $\hat{Q} = Q$
       End For
End For