DKT의 결과를 어떻게 활용할것인가?에 대한 의문이 들어 논문에서 언급한 Expectimax Search algorithm에 대해 알아보려고한다.

Game Tree Search algorithm

Minmax Search

GAN을 공부하면서 처음봤던 이론이다. 두 요소가 경쟁하면서 서로 최선의 선택하며 탐색하는 알고리즘이다.

간단하게 1vs1 격투 게임을 시뮬레이션 하는 튜토리얼을 넣어보자고 한다면 player는 User(CPU)와 Opponent(CPU)로 나뉘게 된다. 여기서 User의 선택을 (예를 들어 발차기 버튼을 누른다, 뒤로 이동한다 등등) 방해하는 쪽으로 Opponent는 행동을 결정하게 된다.

이때 User와 Opponent가 서로 최선의 선택을 하면서 경쟁을 하게 되는데 이를 많이 들어본 Adversary search라고 한다.

이를 그래프로 나타내면 다음과 같이 표현할 수 있다.

graph TB

A(User):::User

B(Opponent):::Opponent
C(Opponent):::Opponent
D(Opponent):::Opponent

A -->|뒤로 물러서기| C
A -->|발차기| B
A -->|점프| D

E[Score: 5]
F[Score: 10]
G[Score: 8]
H[Score: 9]
I[Score: 12]
J[Score: 4]

B -->|반격| E
B -->|가만히 있기| F
C -->|따라오기| G
C -->|점프| H
D -->|숙이기| I
D -->|공중 공격| J

classDef User fill:#6fe468,stroke:#199812,stroke-width:2px;
classDef Opponent fill:#f96,stroke:#ff5b00,stroke-width:2px;

위 트리구조는 User와 Opponent가 action을 선택했을때 score를 보여주고 있다. (주관적인 점수이다.) Minmax Search 알고리즘에서는 Opponent는 항상 이상적인 선택을 한다고 가정하고 있다.

따라서 User가 발차기를 하면 반격을 선택할것이고 (반격:5 가 가만히 있기:10 보다 Opponent한테 유리), User가 뒤로 물러서기를 선택하면 따라오기를 선택할것이다.

따라서 User는 Min값이 가장 Max가 될 수 있는 뒤로 물러서기를 선택해야 최선의 결과를 볼 수 있다.

$\alpha$-$\beta$ pruning

User가 가지는 최소값을 $\alpha$, Opponent 가지는 최대값을 $\beta$ 라고 할때 위에서 Tree 탐색 속도를 빠르게 할 수 있다. 위 그래프를 다시 살펴보면 왼쪽 노드부터 탐색을 진행한다고 할때, 최초에는 $\alpha$ = $-\infty$, $\beta$ = $\infty$로 초기화 하고 시작한다.

graph TB

A(User):::User
B(Opponent):::Opponent
C(Opponent):::Opponentb
D(Opponent):::Opponent

A -->|O| C
A -->|O| B
A -->|점프| D

E[Score: 5]:::selected_next
F[Score: 10]
G[Score: 8]:::selected
H[Score: 9]
I[Score: 12]
J[Score: 4]

B -->|O| E
B -->|X| F
C -->|O| G
C -->|O| H
D -->|숙이기| I
D -->|공중 공격| J

classDef User fill:#6fe468,stroke:#199812,stroke-width:2px;
classDef Opponent fill:#f96,stroke:#ff5b00,stroke-width:2px;
classDef selected fill:#e5c0ff,stroke:#a346a4,stroke-width:2px;
classDef selected_next fill:#fff7a7,stroke:#bfb52e,stroke-width:2px;

위 그래프를 보면서 개념을 살펴보면, 맨 좌측 노드에서 score가 8이 나왔고, 두번째 노드에서 score가 5가 나온 순간, 좌측 노드에서 8 보다 작은 수인 5가 나왔기 때문에 두번째 노드에서는 다른 선택지를 고려하더라도 최소 5를 가지게 되므로 더이상 탐색할 필요가 없다. ($\beta$:5 <$\alpha$:8)

이런식으로 탐색 수를 줄이는 방식을 $\alpha$-$\beta$ pruning이라고 한다.
(대략적인 설명일 뿐이고 자세한 설명은 cs188-09-Games: Trees, Minimax, Pruning)을 살펴보면 좋을것 같다.

Expectimax Search

Expectimax는 Minmax와 다르게 Opponent가 실수할 수도 있는 환경을 가정한다. 따라서 Opponent가 선택가능한 action들의 score 평균을 이용해서 판단하게 된다.

graph TB

A(User):::User
B(Opponent):::Opponent
C(Opponent):::Opponent
D(Opponent):::Opponent

A -->|뒤로 물러서기| C
A -->|발차기| B
A -->|점프| D

E[Score: 5]
F[Score: 10]
G[Score: 8]
H[Score: 9]
I[Score: 12]
J[Score: 4]

K([average: 8.5]):::selected_next
L([average: 7.5]):::selected_next
M([average: 8]):::selected_next

B -->|반격| E
B -->|가만히 있기| F
E --> L
F --> L
C -->|따라오기| G
C -->|점프| H
G --> K
H --> K
D -->|숙이기| I
D -->|공중 공격| J
I --> M
J --> M

classDef User fill:#6fe468,stroke:#199812,stroke-width:2px;
classDef Opponent fill:#f96,stroke:#ff5b00,stroke-width:2px;
classDef selected_next fill:#fff7a7,stroke:#bfb52e,stroke-width:2px;

위 그래프를 보면 각 최종 선택지의 score 평균을 계산하는 것을 볼 수 있다. 여기서 User는 최선의 기회를 예상하고 첫번째 뒤로 물러서기 Action을 취하게 된다.

Minmax보다 기대 기반으로 동작해서 더 좋은 결과를 기대할 수 있지만, 모든 노드를 다 살펴봐야 하기 때문에 $\alpha$-$\beta$ pruning 같은 기법을 사용할 수 없어서 동작속도가 느리다는 단점이 있다.

DKT 응용

DKT 논문에서는 Expectimax Search를 사용하면 효율이 좋은 방향으로 문제를 추천할 수 있다고 한다.

우선 User가 문제를 푼 기록을 아래와 같이 표로 나타냈다.

$\mathbf{x}_t = { q_t, a_t }$ 를 시간에 따라서 풀어서 입력, 아래와 같은 조건을 가정할때

$q_t$(M개의 문제 유형 태그) $\in$ {0, 1, 2, 3, 4}
$a_t$(정답 여부) $\in$ {0, 1}
위의 조건에 따라서 만들어지는 one-hot vector의 크기는 $x_t \in {0, 1}^{2M}$, 2M = 10길이의 vector.

시간	0	1	2	3	4	5	6	7
$q_t$	0	2	1	4	3	3	2	0
$a_t$	0	0	1	0	1	1	1	1

이때 DKT의 출력: {0:0.33, 1:0.44, 2:0.52, 3:0.27, 4:0.41}

이때 다음 시간(t)에 0~4 까지 문제를 풀었다고 가정하면 각각 모든 문제에대한 확률값이 DKT의 출력으로 나오게 된다.

시간	0	1	2	3	4	5	6	7	8
$q_t$	0	2	1	4	3	3	2	0	select([0~4])
$a_t$	0	0	1	0	1	1	1	1	select([0, 1])

[예시]

0번 문제를 푸는 경우
- 맞을때
  - {0:0.78, 1:0.34, 2:0.33, 3:0.98, 4:0.11} → 평균(Expectaion score): 0.508
  시간 0 1 2 3 4 5 6 7 8
  $q_t$ 0 2 1 4 3 3 2 0 0
  $a_t$ 0 0 1 0 1 1 1 1 1
- 틀릴때
  - {0:0.64, 1:0.37, 2:0.32, 3:0.48, 4:0.31} → 평균(Expectaion score): 0.424
  시간 0 1 2 3 4 5 6 7 8
  $q_t$ 0 2 1 4 3 3 2 0 0
  $a_t$ 0 0 1 0 1 1 1 1 0
1번 문제를 푸는 경우
…

시간	0	1	2	3	4	5	6	7	8
$q_t$	0	2	1	4	3	3	2	0	0
$a_t$	0	0	1	0	1	1	1	1	1

시간	0	1	2	3	4	5	6	7	8
$q_t$	0	2	1	4	3	3	2	0	0
$a_t$	0	0	1	0	1	1	1	1	0

여기서 0번 문제를 맞출 확률은 t=7까지 풀었을때 DKT 출력 값의 0번 확률 x 평균(Expectaion score)이 된다. 이를 그래프로 그려보면,

graph TB
A[t = 7]
B[0번 문제 맞음]
C[0번 문제 틀림]
D[1번 문제 맞음]
E[1번 문제 틀림]
F[....]
A -->|0.33| B
A -->|1 - 0.33| C
A -->|0.44| D
A -->|1 - 0.44| E
A -->|...| F

G[Expectaion score: 0.508]
H[Expectaion score: 0.424]
I[...]

B-->G
C-->H
D-->I

여기서 0번 문제를 풀때 예상되는 Expectation Score는 마르코프 결정 과정 (Markov decision process)과 같으며 0.33 * 0.508 + (1 - 0.33) * 0.424 = 0.45172이 된다.

Game Tree Search 알고리즘

Game Tree Search algorithm

Minmax Search

$\alpha$-$\beta$ pruning

Expectimax Search

DKT 응용

관련된 글

클라우드 환경에서 pytorch DDP 사용하기

간단히 살펴보는 프롬프트 튜닝

GPT는 왜 모르는 글자가 없을까? - BBPE (Byte-level Byte-Pair Encoding)