Quoridor Pseudo Code

쿼리도

규칙

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

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

의사 코드 설명

Initial

FOR until game is over

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