강화학습을 통한 윷놀이 최적 전략의 학습 및 윷놀이에 대한 고찰

게임에 참여하고 있는 두 플레이어를 각각 A와 B라고 칭한다. 시점 t에서의 윷놀이 게임 상태 s_t는 현재 턴의 소유자(현 시점에 말을 움직일 권한을 가진 플레이어)를 표현하는 상태변수 w_t ∈ {A,B}, 플레이어 A의 말들의 위치를 표현하는 상태 변수 $$ l_t^A$$, 플레이어 B의 말들의 위치를 표현하는 상태변수 $$ l_t^B$$, 현재 사용 가능한 사위들을 표현하는 상태 변수 y_t, 그리고 현재 턴의 소유자가 윷가락을 던져야 하는 상황인지 표현하는 상태 변수 c_t ∈ {0,1}로 기술될 수 있다.

• ∙ 상태 변수 $$ l_t^A\in {\left\{0,\cdots ,30\right\}}^4$$는 플레이어 A가 소유한 4개 말들의 위치를 <Figure 1>에 표기된 정수값들로 표현한다. 상태 변수 $$ l_t^B\in {\left\{0,\cdots ,30\right\}}^4$$도 마찬가지로 정의된다.
• ∙ 상태 변수 $$ y_t\in {\mathbb{Z}}^6$$는 현재 플레이어 w_t가 사용 가능한 사위들(아직 사용하지 않은 윷 던짐 결과들)의 개수를 뒷도, 도, 개, 걸, 윷, 모의 순서로 표현한다. 예를 들어, 새로운 턴에서 윷가락을 던져서 (윷, 윷, 개)가 나온 상황은 y_t = (0,0,1,0,2,0)로 표현된다.
• ∙ 상태 변수 c_t ∈ {0,1}은 현재 플레이어(w_t)가 윷가락을 던져야 하는 상황인지 나타낸다. 예를 들어, 직전 시점에 상대 플레이어의 턴이 종료되어 현재 플레이어가 새로 윷가락을 던져야 하는 상황 혹은 상대 플레이어의 말을 잡아 윷가락을 추가적으로 던져야 하는 상황이라면 c_t = 1로 표현된다.

게임 초기 상태는 모든 말들이 0번 위치에 있기에 $$ l_1^A=l_1^B=\left(\mathrm{0,0},\mathrm{0,0}\right)$$로, 사용 가능한 사위는 아직 없지만 새로 윷을 던져야 하기에 y₁ = (0,0,0,0,0,0) 및 c₁ = 1로 표현된다.

게임 상태 $$ s_t=\left(w_t, l_t^A, l_t^B, y_t, c_t\right)$$가 주어졌을 때, 현재 플레이어 w_t가 취할 수 있는 액션과 그에 따른 게임 상태 변화에 대하여 기술한다. 시점 t에서 취할 수 있는 액션들의 집합을 𝒜t (혹은 𝒜(s_t))로 표현한다.

우선 현재 플레이어가 윷가락을 던져야 하는 상황인 경우(c_t = 1), 플레이어가 의사결정을 내릴 사항은 없으며(𝒜_t = ϕ), 윷가락을 던져 얻게 되는 결과에 따라 게임 상태가 업데이트된다. 예컨대, y_t = (0,0,0,0,0,1), c_t = 1인 상황에서 윷을 던져 (윷, 윷, 개)가 나왔다면 y_t+1 = (0,0,0,0,2,1) 및 c_t+1 = 0로 업데이트되며 나머지 상태 변수들의 값은 현재 값을 유지한다.

윷가락을 던져야 하는 상황이 아닌 경우(c_t = 0), 현재 플레이어는 어떤 사위를 사용하여 어떤 말을 움직일지 결정해야 한다. 즉, 액션 a_t은 사용하고자 하는 사위 $$ a_t^y\in \left\{\text{뒷도, }\cdots ,\text{ 모}\right\}$$ 및 움직이고자 하는 말 $$ a_t^l\in \left\{\mathrm{1,2},\mathrm{3,4}\right\}$$로 표현되며, 엄밀하게는 뒷도를 사용할 때 다음 위치에 대한 선택권이 생기는 예외적인 상황이 있기에 지름길로 돌아갈지 선택하는 액션 변수 $$ a_t^b\in \left\{\mathrm{0,1}\right\}$$가 추가된다. 이러한 액션의 결과로 (1) 두 플레이어의 말의 위치 $$ l_t^A, l_t^B$$가 2절에서 기술된 윷놀이 규칙에 따라 변경되고, (2) 사용 가능한 사위들 중 하나를 소비하게 되며($$ y_{t+1}=y_t-e_{a_t^y}$$), (3) 윷이나 모가 아닌 사위로 상대 말을 잡은 경우 새로 윷가락을 던질 기회를 얻게 된다(c_t+1 = 1). 현재 플레이어에게 허용된 액션 집합 𝒜_t의 크기는 사용 가능한 사위의 종류 수(y_t에서 0이 아닌 요소의 개수) 와 현재 움직일 수 있는 말 개수의 곱으로 결정된다. 이때 시점 t에서 사용 가능한 사위가 하나밖에 없고($$ \sum _{i=1}^6{y}_{t,i}=1$$) 그 사위를 사용했을 때 새로 윷가락을 던질 기회를 얻지 못한다면 이는 턴의 종료를 의미한다. 따라서 턴의 소유자가 변경($$ w_{t+1}\ne w_t$$)되며 상대 플레이어가 새로 윷가락을 던질 기회를 얻는다(c_t+1 = 1).

본 논문에서는 상태 변수 c_t를 도입하여 윷가락을 던져야 하는 상황(c_t = 1)과 의사결정을 내려야 하는 상황(c_t = 0)을 분리하여 고려하고 있으며, 따라서 후자의 상황(c_t = 0)에서 의사결정 직후의 게임 상태 s_t+1는 확률적 요소의 개입 없이 오직 현재 상태 s_t와 현재 액션 a_t으로만 결정된다. 이러한 설정은 후술한 전략 구현 및 학습에 있어서 많은 편의성을 가져다준다.

게임 종료 시점에, 승리한 플레이어에게 +1의 보상이, 패배한 플레이어에게 -1의 보상이 주어지며, 게임 진행 과정 도중에는 보상이 발생하지 않는다. 이때 플레이어 A 입장에서의 가치함수 V^A(s_t)는 s_t로 특정되는 게임 상황에서 플레이어 A의 총 미래 보상의 기댓값로 정의되며, 이는 A가 이길 확률을 -1과 1 사이의 값으로 나타내는 것과 같다. 제로섬 게임이기에 플레이어 A의 가치함수는 플레이어 B의 가치함수를 유일하게 결정짓는다(V^B = -V^A).

보다 구체적으로, 현재 상태 $$ s_t=\left(w_t, l_t^A, l_t^B, y_t, c_t\right)$$가 주어졌을 때 플레이어 A 입장에서의 인코딩 $$ {\widehat{s}}_t^A$$은 다음과 같이 결정된다. 첫 124(4 × 31)개의 값 $$ {\widehat{s}}_{t,1:124}^A$$은 본인 말들의 위치 $$ l_t^A$$를, 그 다음 124개의 값 $$ {\widehat{s}}_{t,125:248}^A$$은 상대 말들의 위치 $$ l_t^A$$를 one-hot vector로 인코딩한다. 그 다음 6개의 값 $$ {\widehat{s}}_{t,249:254}^A$$은 본인이 현재 사용 가능한 사위들의 개수를 표현하는데, 현재 턴의 소유자가 본인이라면 y_t값을, 아니라면 0의 값을 갖도록 한다. 마지막 3개의 값 $$ {\widehat{s}}_{t,255:257}^A$$은 다음 3가지 상황을 구분하는 one-hot vector로 주어진다 - 상대가 윷을 던져야 하는 상황(c_t = 1,w_t = B), 본인이 말을 놓아야 하는 상황(c_t = 0,w_t = A), 본인이 윷을 던져야 하는 상황 (c_t = 1,w_t = A). 플레이어 B 입장에서의 인코딩 $$ {\widehat{s}}_t^B$$도 마찬가지 방식으로 규정된다.

Figure 2.

Game State Encoding for Each Player

Value network $$ {\widehat{V}}_{\theta }\left(\cdot \right)$$는 인코딩된 게임 상태를 입력 받아 -1과 1 사이의 값을 출력하며, 가치 함수를 표현하는 것을 목표로 한다($$ {\widehat{V}}_{\theta }\left({\widehat{s}}_t^A\right)\approx V^A\left(s_t\right), {\widehat{V}}_{\theta }\left({\widehat{s}}_t^B\right)\approx V^B\left(s_t\right)$$). <Figure 3>과 같이 257개의 유닛을 가진 input layer, 각각 256개의 유닛을 가진 2개의 hidden layer로 구성하였고, hidden layer 유닛의 activation function으로는 ReLU를, output function으로는 tanh를 채택하였다. Value network를 구성하는 총 132,097개의 파라미터를 θ로 표기한다.

Figure 3.

Value Network Architecture

Value network의 학습 데이터 생성을 위해 사용하는 행동 전략으로써 현재까지 학습된 value network에서 파생되는 greedy policy를 이용한다. 보다 구체적으로, $$ {\widehat{V}}_{\theta }$$에서 파생되는 행동 전략 π_θ은 매 의사결정 시점에 다음과 같은 방식으로 액션을 선택한다: $$ a_t=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{ }{\text{max}}_{a\in A\left(s_t\right)}{\widehat{V}}_{\theta }\left({\widehat{s}}_{t+1}^{w_t}\left(s_t,a\right)\right).$$

여기서 𝒜(s_t)는 현재 게임 상태 s_t에서 취할 수 있는 액션들의 집합을 의미하며, $$ {\widehat{s}}_{t+1}^{w_t}\left(s_t,a\right)$$는 액션 a를 취한 직후의 게임 상태 인코딩을 의미한다. 이때 의사결정을 내려야 하는 상황(c_t = 0)은 윷가락을 새로 던져야 하는 상황(c_t = 1)과 분리되어 있기 때문에 직후의 게임 상태 s_t+1(s_t,a)는 확률적 요소의 개입 없이 현재 상태와 액션만으로 결정된다.

파라미터 학습 방식으로 target network(Hasselt et al., 2016)를 동반한 temporal difference method(Tesauro, 1995)를 적용하였다. i-1번째 epoch을 마친 뒤의 모델 파라미터를 θ_i-1라고 할 때, i번째 epoch에서는 다음 과정을 통해 파라미터를 업데이트한다.

먼저 현재까지 학습된 value network $$ {\widehat{V}}_{{\theta }_{i-1}}$$에서 파생되는 행동 전략 π_θㅑ-1을 자가대결(self-play)시켜 게임 데이터를 생성·수집한다. 한 번의 경기를 통해 게임 상태 궤적 (s₁,...,s_T)와 승패 여부에 따른 보상값r^A 및 r^B 를 수집하게 되고, 이를 두 플레이어 각각의 입장에서 인코딩하여 $$ {\xi }^A=\left({\widehat{s}}_{1,\dots }^A,{\widehat{s}}_T^A,r^A\right)$$와 $$ {\xi }^B=\left({\widehat{s}}_{1,\dots }^B,{\widehat{s}}_T^B,r^B\right)$$를 얻는다. 매 epoch마다 총 1,024판의 자가대결을 진행하며, 따라서 2,048개의 학습데이터를 얻는다.

다음으로 32번의 iteration을 거쳐 파라미터 업데이트를 진행한다. 매 itertaion마다 2,048개의 학습데이터 중 64개를 무작위로 선택하여 minibatch를 구성하고, minibatch에서 발생하는 loss의 총합을 줄이는 방향으로 value network 파라미터 θ를 업데이트한다. 이 과정에서 하나의 학습데이터 ξ^A(혹은 ξ^B)가 만들어내는 loss는 다음과 같이 주어진다:

플레이어는 c_t = 0인 시점 t에서만 액션을 필요로 하고, 이 때 액션을 취하기 위해서 액션을 취한 직후의 게임 상태 인코딩인 $$ {\widehat{s}}_{t+1}^A$$의 가치만을 이용한다. 따라서 c_t = 0인 t에 대해 $$ {\widehat{V}}_{\theta }\left({\widehat{s}}_{t+1}^A\right)$$를 정확하게 평가하는 것이 중요하고, 이를 위해 액션을 취한 직후의 게임 상태만을 사용해 위와 같이 loss를 구성하였다.

여기서 θ^target은 target network의 파라미터이다. 모든 iteration을 마치고 i번째 epoch가 끝나는 시점에서, 그때의 value network 파라미터를 θ_i라고 할 때, θ^target은 다음과 같이 업데이트된다.

Value network의 minibatch 업데이트 과정에서 사용되는 optimizer로 Adam을 채택했으며, learning rate는 10^-3으로 설정하였다.

Value network 학습이 완료된 이후 성능을 분석하는 단계에서 성능 향상을 꾀하기 위해, 매 의사 시점에 그 다음 한 수를 더 고려해보는 one-step look-ahead 전략을 고안하였다.⁵⁾ 이 전략은 행동 전략 (1)과 유사하게 다음과 같은 액션 선택 방식을 구현한다.

여기서 $$ {\widehat{V}}_{\theta }^{LA}\left(s_{t+1}\right)$$은 액션 a를 취한 직후의 게임 상태 s_t+1의 가치를 평가함에 있어서 그 다음 한 단계를 더 진행한 게임 상태 s_t+2를 추가로 고려한다 :

다음 게임 상태 s_t+1가 한 번 더 의사결정을 해야 하는 상황(c_t+1 = 0)이라면 다음 시점에 취할 수 있는 최선의 액션 및 그 액션의 가치를 산출하게 되고, 윷을 새로 던져야 하는 상황(c_t+1 = 1)이라면 새로 얻게 될 사위들의 확률 분포(위 식에서 Y로 표현된 random vector의 확률 분포)를 고려하여 윷을 던진 후의 게임 상태 가치의 기댓값을 산출하게 된다.

강화학습 진행 과정 중 성능 향상 정도를 파악하기 위하여, 매 10번의 epoch마다 점수 기반 휴리스틱 전략을 상대로 게임 시뮬레이션을 1,000회 반복하여 승률을 집계하였다. 해당 휴리스틱 전략은 말들의 현재 위치에서 골인 지점까지 거리를 기반으로 게임 상태에 대한 점수를 부여하고 이 점수를 최대화시키는 수를 선택하는 전략으로, 자세한 내용은 부록에서 서술한다.

<Figure 4>는 승률 추이를 보여준다. 학습 초기 30%의 승률에서 시작하여 약 200회의 epoch 이후에는 65%의 승률을 기록하며 상대 전략보다 월등히 좋은 성능을 보여주었다. 추가적으로 Monte-Carlo(MC) 학습 방식 및 target network를 사용하지 않는 temporal difference(TD without target) 학습 방식도 구현하여 비교하였다. 본 논문에서 채택한 학습 방식(TD with target)이 학습 극초반에는 상대적으로 저조한 승률을 보였지만, 이내 가파르게 상승하며 80회의 epoch 이후에는 세 가지의 학습 방식 중 가장 높은 성능을 보였다.

Figure 4.

Win Rate Against the Score-based Heuristic Strategy Throughout the Training Procedure

총 500 epoch를 거치면서 생성된 500개의 전략들 중 점수 기반 휴리스틱 전략 상대로 승률이 가장 높았던 전략을 최종 전략으로 선택하였고, 해당 전략의 성능을 다른 휴리스틱 전략들 및 사람을 상대로 측정하였다. 이때 선공 여부 및 우연적 요소에 의하여 승패가 결정되는 현상의 영향을 최소화하기 위하여, 선공과 후공 플레이어가 얻게 될 윷 사위들을 개별적으로 무작위 생성하여 놓고, 선후공 순서만 바꾸어 매번 두 판의 경기를 진행하였다. 이러한 집계 방식 하에서 특정 전략을 자가 대결(self-play)시켰을 경우 승률이 정확히 50%로 측정된다.

각 휴리스틱 전략을 대상으로 10,000판씩 그리고 10명의 사람을 대상으로 10판씩 경기를 진행하였고, 그 결과를 <Table 2>에 나타내었다. 괄호 안에 표기된 숫자는 같은 사위 결과들에서 선후공 순서만 바꾸었을 때 승패가 뒤바뀌는 경우를 제외하고 집계된 승률을 나타낸다. ‘Random’는 아무 말이나 무작위로 선택하여 움직이는 전략, ‘Last’는 가장 뒤쳐져있는 말을 움직이는 전략, ‘Score-based’는 앞서 언급된 점수 기반 휴리스틱 전략을 의미하며, 이 전략들을 상대로 압도적인 우위를 보였다. ‘No Lookahead’는 동일한 value network을 사용하되 3.2절에서 기술된 one-step look-ahead 방식이 적용되지 않은 전략을 의미하며, look-ahead 방식이 성능을 근소하게 개선시킴을 확인할 수 있다. 나아가, 사람을 상대로도 우위를 보임이 확인된다.

Table 2.

Win Rate Against the other Strategies and Human Players

특정한 상황들을 가정하여 학습된 전략이 합리적 판단을 내리는지 검토하였다. 예시로, 아래 <Figure 5>은 같은 사위가 주어졌더라도 말들의 위치에 따라 다른 선택을 내린다는 것을 보여준다. 두 상황 모두 뒷도가 사위로 주어진 상황을 고려하는데, 첫 번째 상황의 경우 6번에 위치한 말을 5번으로 옮기는 것 보다 1번에 위치한 말을 29번으로 옮겨 말을 골인 시키는 선택이 더욱 높은 가치를 가지는 것으로 나타났다. 두 번째 상황에서는 뒷도를 이용해 5번에 위치한 상대방의 말을 잡는 것이 가능하며, 이로 인해 6번에 위치한 말을 이동시키는 것이 더 높은 가치를 가지는 것으로 나타났다. 학습된 전략이 실제 사람과 유사하고 매우 합리적인 판단을 하고 있음을 알 수 있다.

Figure 5.

Simple Simulation of Value Network

아래 <Figure 6>은 ‘Lookahead’ 전략과 ‘No Lookahead’ 전략이 다른 결정을 내리는 상황을 예시로 보여준다. 상대방의 말이 6칸 앞에 있고 윷과 개가 사위로 주어진 상황이며, 이때 Lookahead 전략은 두 단계 앞의 수까지 보기 때문에 윷과 개를 모두 활용하여 말 a를 움직여 상대방의 말을 잡는 선택을 보여주었다. 하지만 No Lookahead 전략의 경우 바로 직후의 상태만을 고려하기 때문에 말 a를 2칸 움직여 지름길인 5번 위치로 이동하고, 남은 사위인 윷으로 b를 이동시키는 모습을 보여주었다. 두 개의 선택 모두 어느 정도 타당성이 있는 움직임이나, Lookahead 전략이 근소하게 더 좋은 선택을 하므로 <Table 2>에서와 같은 성능 차이가 나타난 것으로 예측된다.

Figure 6.

Difference between ‘Lookahead’ and ‘No Lookahead’

개별적인 사례 분석에서 나아가, 자가 대결 시뮬레이션 결과를 통계적으로 분석하여 합리적인 윷놀이 전략에 관하여 고찰한다. 매 의사 결정 시점마다 취할 수 있었던 액션들과 전략이 실제로 취한 액션을 집계하여 분석하였다.

학습된 전략이 이미 출발하여 판에 나와 있는 말을 전진시키는 대신 새로운 말을 출발시키는 선택을 하는 비율을 각 사위별로 집계하여 <Table 3>에 나타내었다. 예를 들어, ‘도를 이용하여 출발 지점에 위치한 말을 1번 위치로 이동’과 ‘도를 이용하여 기존 말을 한 칸 전진’이라는 선택지가 주어져 있던 상황들 중 63.1%의 경우 학습된 전략은 전자를 선택하였음을 의미한다. 괄호 안의 숫자는 그러한 선택을 내린 경우들 중 상대의 말을 잡게 되었던 경우의 비율을 나타낸다.

Table 3.

Likelihood of the Trained Strategy Deciding ‘Advancing a New Mal’ Against ‘Advancing a Mal already on Board’ Given a Yut Score Outcome when Both Actions are Available, where the Numbers in the Parenthesis Represent the Probability of Catching an Opponent's Mal in Such Moves

다른 윷사위들에 비하여 도의 출발 선택 비율이 유난히 높은데, 이는 기존 말을 한 칸 전진하는 것에 비하여 새로운 말을 출발시키는 것이 위험 부담이 적으면서도 상대방의 새로운 말 출발도 견제할 수 있는 이점을 가지고 있기 때문이라고 해석된다. 또한 개나 걸로 출발을 선택하는 경우의 약 40% 정도는 상대방 말을 잡는 경우라고 파악되는데, 다시 말해 상대방 말을 잡는 경우가 아니라면 굳이 개나 걸로 새로운 말을 진출시키지 않는 것이 좋다고 할 수 있다. 앞서 언급된 첫 윷사위 결과에 따른 승률에 대한 해석과 일치하는 결과라고 할 수 있다.

위와 마찬가지로 학습된 전략이 상대 말을 잡는 선택, 본인 말을 업는 선택 및 새로운 말을 출발시키는 선택을 하는 비율을 산출하였다. 구체적인 상황에 따라 다르겠지만, ‘잡기’는 거의 대부분의 경우 최선의 결정이며, ‘업기’는 평균적으로 최선의 결정, ‘출발’은 평균적으로 최선이 아닌 결정임을 알 수 있다. 추가로 ‘업기’와 ‘잡기’ 선택지가 모두 주어진 상황에서는, 업는 선택보다 잡는 선택을 약 7배 더 많이 하는 것으로 관찰되었다.

Table 4.

Likelihood of The Trained Strategy Deciding to Move a Mal to Carry Another Mal, to Catch an Opponent's Mal, or to Start a New Run, when other Alternative Actions are Available

게임 당 턴(turn) 수, 윷을 던진 횟수, 말을 이동시킨 횟수(의사 결정 횟수), 본인 말을 업은 횟수 및 상대 말을 잡은 횟수에 대한 요약 통계를 <Table 5>에 기재하였다. 예를 들어, 윷을 한 번 던질 때마다 10초, 의사 결정을 한 번 내릴 때마다 10초가 소요된다면, 윷놀이 한 판을 진행하는 데 평균 14분이 소요된다고 할 수 있다.

Table 5.

Game Statistics in the Self-play of the Trained Strategy

선공 플레이어의 가장 첫 번째 윷사위 결과 별로 승률을 측정하여 <Table 6>에 정리하였다. 뒷도의 경우 말의 이동 없이 즉시 후공 플레이어의 턴으로 넘어가기에 제외하였다.

Table 6.

Win Rate of the First Player Given the First Yut-score Outcome

우선 선공의 승률이 50.11%로, 아주 근소한 우위를 가진다는 것을 확인할 수 있다. 첫 윷사위로 도가 나온 경우 53.1%로 상당히 높은 승률을 보여주며, 오히려 개나 걸이 나온 경우 승률이 50%를 넘지 못하는 것으로 확인되는데, 이는 개나 걸의 경우 다음 턴에 후공 플레이어가 매우 높은 확률(34.6%)로 선공 플레이어의 말을 잡게 되기 때문이라고 해석 가능하다.

각 플레이어의 골인 지점에 도착한 말의 개수에 따른 선공 플레이어의 승률을 측정하여 <Table 7>에 나타내었다. 예를 들어, 어느 한 게임 진행 과정 중에 (선공의 골인한 말의 개수, 후공의 골인한 말의 개수)가 (0,0) → (1,0) → (1,2) → (1,3) → (4,3)의 순서로 변화하였다면(선공의 모든 말이 먼저 골인하였으므로 선공 승리), 아래 표에서 (0,0), (1,0), (1,2), (1,3), (4,3)에 해당하는 부분에서 선공이 승리한 경기로 집계되며, 나머지 부분에서는 집계되지 않는다.

Table 7.

Win Rate of the First Player Given the Number of Mals that Completed Running

하나의 말이 골인 지점에 도착할 때마다 해당 플레이어의 승률이 대략 10% 상승하는 것을 확인할 수 있다. 본인의 말은 모두 남아있고 상대의 말은 하나만 남아있는 매우 불리한 상황에서도 승률이 20% 정도로 유지되는 것으로 관찰되며, 이는 윷놀이에서 역전이 매우 빈번하게 일어난다는 점을 시사한다.