Stanford CS221: 인공지능 원리와 기법 - 게임 II (TD Learning 및 게임 이론)

• •Minimax는 에이전트의 최대 이익과 상대의 최소 이익을 가정하는 탐색 기법이다
• •수작업으로 설계된 평가 함수는 복잡한 게임의 모든 상황을 대변하기 어렵다
• •TD Learning을 통해 데이터로부터 가치 함수를 직접 학습할 수 있다

Minimax는 모든 가능한 수를 탐색하여 최선의 수를 찾는 알고리즘이지만, 탐색 공간이 넓은 경우 상태의 가치를 판단하는 평가 함수가 필수적이다.

• •SARSA는 On-policy 알고리즘으로 현재 정책에 따른 Q-value를 추정한다
• •TD Learning은 보상(r)과 다음 상태의 가치(V)를 이용해 현재 상태의 가치를 갱신한다
• •Self-play는 에이전트가 자기 자신과 대국하며 최적의 가치 함수를 찾아가는 과정이다

TD Learning은 전체 에피소드가 끝나기 전에도 다음 상태의 예측치를 이용해 현재 상태를 업데이트하는 Bootstrapping 기법을 사용한다.

• •Checkers 프로그램은 Self-play와 Alpha-beta pruning을 결합한 초기 사례이다
• •TD-Gammon은 신경망을 통해 중간 보상 없이도 전문가 수준의 플레이를 학습했다
• •AlphaGo Zero는 순수하게 Self-play만으로 바둑의 새로운 통찰력을 제시했다

MCTS는 무작위 시뮬레이션을 통해 각 수의 승률을 계산하는 탐색 알고리즘으로, 강화학습된 정책망과 결합되어 사용된다.

• •동시성 게임에서는 상대의 수를 보고 대응할 수 없으므로 심리전과 확률이 중요하다
• •Pure strategy는 상대에게 읽히기 쉬우며 최적의 대응에 취약하다
• •Mixed strategy는 행동의 확률 분포를 최적화하여 최소한의 기대 수익을 보장한다

혼합 전략은 상대방이 나의 다음 수를 예측할 수 없게 만들어 전략적 우위를 점하는 방법이다.

• •Minimax Theorem은 혼합 전략 하에서 Max-Min과 Min-Max 값이 같음을 보장한다
• •Nash Equilibrium은 모든 플레이어가 서로의 전략에 대해 최선의 대응을 하고 있는 상태이다
• •비영합 게임에서는 협력이 전체 이익을 높일 수 있음에도 균형점은 배신으로 흐를 수 있다

Nash Equilibrium은 다른 플레이어가 전략을 바꾸지 않는 한, 어떤 플레이어도 자신의 전략을 바꾸어 이득을 볼 수 없는 상태를 의미한다.