Ssong

반갑습니다 :)

[RL] David Silver RL Lecture 10: Classic Games

Date:     Updated:

카테고리:

태그:

1. State of the Art

  • 규칙은 간단, 개념은 복잡
  • 수 천년간 연구를 해옴
  • IQ Test로서의 의미
  • AI의 초파리 같은 개념 (가장 기본이 되는 실험체)
  • 현실 세계를 포함하는 소우주
  • 재미가 있다.

AI in Games: State of the Art

Image

RL in Games: State of the Art

Image

2. Game Theory

2.1 Optimality in games

i번째 플레이어에게 최적의 정책 \(π^i\)는 무엇일까?

만약 다른 플레이어들의 정책이 \(π^{-i}\)로 고정되었다면

Best response \(π^i_*(π^{-i})\) : 그들의 정책에 대해 optimal한 정책이다.

Nash equilibrium : 모든 플레이어에 대해 유효한 정책 \(π^i\) = \(π^i_*(π^{-i})\)

  • 모든 플레이어가 Best response를 하는 상황 (Nash equilibrium에서 벗어날 필요가 없는, 벗어나는 선택을 하는 순간 손해를 보는)
  • 예를 들어, 상대도 나도 가위바위보를 하는데 33%확률로 랜덤하게 내는경우. 서로의 policy를 바꿀 동기가없다. Nash equilibrium 상태

2.2 Single-Agent and Self-Play Reinforcement Learning

Best response는 single agent RL 문제의 정답이다.

  • 상대가 고정되어있으므로 다른 플레이어는 environment의 한 부분으로 생각할 수 있다.
  • 게임을 MDP로 표현할 수 있다.
  • Best response = MDP의 optimal policy

Nash equilibrium은 self play-RL의 부동점이다.

Experience는 각 agent가 게임을 진행하면서 발생된다. 각 agent는 다른 플레이어에 대한 best response를 학습한다. 한플레이어의 정책은 다른 플레이어의 env를 결정한다. 모든 플레이어는 상대방에 적응을 한다.

Nash equilibrium을 이루는 정책은 unique (딱 한가지)일까??

⇒ No, 어떠한 조건을 만족하면 unique해진다.

조건 1. two-player game : 흑-백 처럼 번갈아가면서하는 게임 (alternative game)

조건 2. zero-sum game : 상호간에 공격을 하는 게임 (reward의 합 0)

조건 3. perfect information : 바둑이나 체스는 상대의 state를 정확히 알 수있음 (포커는 상대의 패를 모르니 imperfect)

  • perfect information or Markov Game은 fully observed
    • Chess, Checkers, Othello, Backgammon, Go
  • imperfect information은 partially observed
    • Scrabble, poker

이 3가지 조건을 만족하면 Nash equilibrium은 unique해진다. (딱 하나의 Nash equilibrium이 존재)

이번 강의에서는 Nash equilibrium을 찾는 방법론을 배운다.

  • Game tree search
  • Self-play reinforcement learning

3. Minimax Search

  • value function 은 Policy를 통해 얻어지는 보상의 총합.

Image

  • minimax value function은 (백 기준)흑이 얻는 보상을 최소화하는 동안, 백이 얻는 보상을 최대화.

Image

  • minimax policy : joint poilicy π가 minimax value를 얻는 policy. (두 플레이어가 best response를 하는 policy)
  • unique한 minimax value function이 존재하고, 그 minimax policy는 Nash equilibrium을 이룬다.

3.1 Minimax Search Example

Image

  • 제일 하단 노드부터 계산을 시작한다.
  • b1의 경우 a1, a2중 큰 것을 골라야한다. (백 입장)
  • a1의 경우 b1, b2중 작은 것을 골라야한다. (흑 입장)
  • 다시 root 노드의 경우 백입장에서 큰 값을 골라야 하므로 -2를 고른다.

tree는 exponential 하게 커지기 때문에 게임의 끝까지 search하는 것은 실용적이지 못하다.

대신 value function approximator를 사용해 tree 끝까지 가는 것이 아니라 중간부터는 value function을 넣어둔다. (evaluation function, heuristic function)

Minimax search는 fixed width까지 하고 leaf node의 minimax value를 계산하기 위해 value function을 사용한다.

3.2 Binary-Linear Value Function

  • Binary feature vector x(s) : 있으면 1, 없으면 0
  • Weight vector w : 각 말의 value
  • Position은 살아있는 features의 weight합으로 계산할 수 있다. (여러 계산 방식 중 한 예)

Image

3.3 Examples

Deep Blue

  • Knowledge
    • Binary-linear value function을 사용했고 8000개의 chess features를 계산, Weight는 전문가들이 직접 계산했다.
  • Search
    • alpha-beta search에서 좋은 성능을 냈고,1초에 200m의 수를 계산해 앞선 16~40수까지를 계산했다
  • Results
    • human champion인 Garry Kasparov를 4-2로 이겼다 (1997)
    • 인터넷 역사상 가장 많이 시청한 경기

Chinook

  • Knowledge
    • Binary-linear value function을 사용했고, 21개의 knowledge-based features가 있었다.
  • Search
    • alpha-beta search에서 좋은 성능을 냈다
    • Retrograde analysis
      • 승리 포지션에서 거꾸로 Search, 모든 승리 포지션은 table에 저장됨. last n checkers 부터는 완벽하게 플레이했다. (n = 11개 정도)
  • Results
    • Defeated Marion Tinsley in world championship (1994)
    • Chinook solved Checkers (2007)

4. Self-Play Reinforcement Learning

4.1 Self-Play Temporal-Difference Learning

Image

  1. intermidate reward, gamma가 없다. (게임이 끝나야 reward가 1 또는 -1이기 때문)
  2. value가 minimax value로 바뀜 (2명이 하는 게임)

model-free에서는 어떤 action을 해야 그 state로 가는지 알 수 없었다. 하지만 게임에선 rule이 그 방법을 알려주기 때문에 V의 계산만으로도 policy improve를 할 수 있다.

Image

\(Q(s,a) = R(s,a) + rV(s')\)인데, R이 없고, gamma도 필요 없으니까 다음 state에서의 value function은 S에서 a를 했을때 value랑 같다.

내가 현재 이동할 수 있는 State중에 value가 가장 높은 것을 선택하면 된다. (바둑 : 내가 원하는 state에 그냥 돌을 놓으면 됨, 체스도 마찬가지)

Image

이렇게 둘을 improve할 수 있다.

4.2 Self-Play TD in Othello: Logistello

Image

돌들의 position의 조합으로 150만개의 features를 만들고. 그것을 Binary-linear value function으로 만듬.

Hand crafted feature랑은 다른게 전문가들이 각 feature에 weight를 직접 부여했다면 logistello는 여러 상황이 있냐 없냐만 만든것이다.

  • generalised policy iteration을 사용했다.
    • Generate batch of self-play games from current policy
    • MC를 활용해 정책 평가 (regress to outcomes)
    • Greedy policy improvement를 통해 새로운 플레이어 생성

4.3 TD-gammon

Image

random weights로 초기화를 하고 self-play로 학습

Image

greedy policy improvement(no exploration)했는데도 항상 수렴했다.

⇒ 주사위를 굴려서 진행되는 게임인데 이 주사위가 stochasitc해서 explore역할을 했다.

(environment안에 inherent stochasticity가 있다고 표현)

  • 다른 게임에서도 통하지는 않는다.

New TD-gammon : Neural Network에서 hidden units를 늘릴수록 성능이 좋았다.

5. Combining Reinforcement Learning and Minimax Search

5.1 Simple TD

TD : 다음 successor value로 업데이트 하는 것

Image

Value function approximator v(s,w)가 쓰였다.

Image

다음 state의 value로 업데이트

Learning과 Searching 두 단계로 나눠서 진행

  1. TD learning으로 학습
  2. 학습된 value function으로 minimax search 진행

Image

othello, backgammon에서는 superhuman의 성능을 보였지만
chess, checkers에서는 좋지 않은 성능을 보였다.(search 없이 checkmate를 찾는게 어려움)

idea : Search를 learning과 같이 해서 value function을 더 낫게 할 수 없을까?

TD Root

Image

TD Update를 할 때, TD target에서의 next state value를 next state의 minimax value로 바꿔서 계산을 한다.

즉 State \(S_t\)가 minimax value 방향으로 update가 가능하다. (Learning에 Searching이 결합한 경우)

TD leaf

Image

현재 state에서의 search 결과를 다음 state에서의 search 결과로 바꿔준다.

one-step 더 가서 계산한것이 더 정확할거니까

TreeStrap

why mix real step and imaginary step? lets just do everything in imagination

Image

Simulated-Based Search

Image

imperfect game을 할 때 UCT search를 사용한다.

Smooth UCT Search

Image

6. Conclusions

Image

  • 각 게임마다 어떤 features를 사용을 했고, 어떤 방식을 활용했는지 정리를 했다.

맨 위로 이동하기

RL Lecture 카테고리 내 다른 글 보러가기

댓글남기기

최근 글 10 개 :)