tic tac toe는 3x3 보드에서 두 명의 플레이어가 번갈아가며 말을 두는 게임이다. 한 플레이어는 X를, 다른 플레이어는 O를 사용하며 가로, 세로, 대각선으로 동일한 기호 3개를 연속 배치하면 승리한다.(이렇기 때문에 삼목이라고 불린다) 모든 칸이 채워졌음에도 승리 조건을 만족하지 못하면 게임은 무승부로 끝난다. Richard S. Sutton and Andrew G. Barto의 Reinforcement Learning: An Introduction Second edition, in progress에 나와있는 설명을 정리해보자.
Sutton & Barto의 강화학습 개념
(출처: Reinforcement Learning: An Introduction Second edition, in progress)
- State s
현재 보드의 상태를 나타낸다. 초기 상태는 ["", "", "", "", "", "", "", "", ""] - Reword r
게임 종료 시 주어지는 값이다.
승리 시 r = 1, 패배 또는 무승부 시 r = 0. - Policy
"To select our moves we examine the states that would result from each of our possible moves (one for each blank space on the board) and look up their current values in the table. Most of the time we move greedily, selecting the move that leads to the state with greatest value, that is, with the highest estimated probability of winning. Occasionally, however, we select randomly from among the other moves instead. These are called exploratory moves because they cause us to experience states that we might otherwise never see."- 에이전트가 특정 상태 s에서 행동 a를 선택하는 규칙이다
- 대부분의 경우, 가장 높은 V(s′)를 가지는 행동을 선택 (greedily, greatest value, Exploitation).
- 나머지 확률로 무작위로 행동을 선택(Randomly, Exploratory move)
- Value Function V(s)
"While we are playing, we change the values of the states in which we find ourselves during the game. We attempt to make them more accurate estimates of the probabilities of winning. To do this, we back up the value of the state after each greedy move to the state before the move, as suggested by the arrows in Figure 1.1. More precisely, the current value of the earlier state is adjusted to be closer to the value of the later state. This can be done by moving the earlier state’s value a fraction of the way toward the value of the later state."- 상태 s에서 시작하여 미래에 받을 보상의 기대값을 나타낸다.
Learning Process
1. 초기화
- 모든 상태 s에 대해 V(s)를 초기값 0.5로 설정한다. (Value Table 선언 후 모든 엔트리를 0.5로 설정)
2. Policy(ε-greedy)
- 확률 ε로 무작위 행동을 선택(Random, Exploration)
- 확률 1 - ε로 가장 높은 V(s')를 가지는 행동을 선택(Greedy, Exploitation)
- ε은 학습이 진행됨에 따라 점진적으로 감소(동적으로 조정).
- 시간이 지날수록 Greedy한 값을 선택하는 비율이 더욱 높아짐.
ex) ε = ε * 0.99
3. 전이
- 현재 상태 s에서 선택한 행동 a를 수행하여 새로운 상태 s'로 전이한다.
- 현재 상태 s = ["X", "", "", "", "O", "", "", "", ""]에서 행동 a = 1을 선택하면, 다음 상태는 s' = ["X", "X", "", "", "O", "", "", "", ""]
4. Value Function 업데이트
Sutton & Barto 방식의 Temporal Difference(TD) 학습을 사용하여 가치 함수를 업데이트
- V(s) ← V(s) + α * (V(s') - V(s))
여기서 α는 학습률
α는 동적으로 조정된다. 여기선 방문 횟수에 따라 동적을 조정된다고 해보자.
ex) α = 1 / (1 + visit_count)
5. Reword Backpropagation
게임이 종료된 상태에서 보상 r을 기반으로 이전 상태들의 가치 함수를 업데이트한다.
- 종료 상태 s'에서 V(s') = r로 설정한다.( 승리 시 1, 패배나 무승부 시 0)
- 이전 상태 s에서 다음 상태 s'의 가치를 이용해 V(s)를 업데이트
- V(s) ← V(s) + α * (V(s') - V(s))
위 과정을 반복