알파고

Finite Two Person Zero-Sum Sequential Game

finite: 일정 시점에 종료되는
two person: 두 행위자가 참여
zero-sum: 두 행위자의 수익의 합이 0
sequential: 각 행위자가 번갈아가며 행동
예시: 바둑, 체스, 오목 등

미니맥스 전략 minimax strategy

상대가 최선의 행동(max)을 한다는 가정 아래, 이를 최소화(min)시키는 행동을 선택
아래 보수 행렬에서 A의 이익/손실 = B의 손실/이익인 경우
- A에게 최선의 선택은 A2(최악의 경우가 -1로 최소)
- B에게 최선의 선택은 B2(최악의 경우가 0으로 최소)
모든 경우의 수를 따져야 함
바둑과 같이 경우의 수가 많은 게임에는 사용 불가

A의 보수 행렬(payoff matrix)	B1	B2	B3
A1	+3	-2	+2
A2	-1	0	+4
A3	-4	-3	+1

내시 균형 Nash Equilibrium

서로가 상대방의 전략에 최선의 대응을 하고 있는 상태
완전 정보 조건 하에서 미니맥스 전략은 내시 균형
앞의 보수 행렬에서
- A는 행동을 어떻게 바꿔도 손해 -> 바꿀 수 없음
- B가 이익을 늘리기 위해 B1으로 행동을 바꾸면 A가 A1으로 바꿔서 맞대응 -> B는 결과적으로 손해 -> 바꿀 수 없음
죄수의 딜레마: 서로 협조하는 것이 최대의 이익을 가져오지만 서로 배신하는 것이 내시 균형인 경우

몬테카를로 트리 탐색

트리 정책(tree policy)과 기본 정책(default policy, 또는 롤아웃 정책)으로 구분
트리 정책에 따라 다음에 탐색할 노드를 선택(selection)
선택된 노드에서 새로운 자식 노드를 생성하여 트리를 확장(expansion)
선택된 수에서 기본 정책에 따라 게임을 진행(simulation, rollout)
시뮬레이션의 결과가 상위 노드로 역전파(backpropagation)

몬테카를로 트리 탐색 절차

UCT Confidence Bounds applied for Trees

가장 널리 쓰이는 트리 정책으로, 다음의 값이 가장 큰 행동을 선택

Q (s, a) + C \frac{ln N ( s )}{N ( s , a )}

$Q (s, a)$ : 상태-행동 가치(그 수를 두었을 때 이긴 비율, 0~1)
$C$ : 탐색-활용을 제어하는 하이퍼파라미터(보통 $2$ 를 사용)
$N (s)$ : 상태 $s$ 를 탐색한 횟수
$N (s, a)$ : 상태 $s$ 에서 행동 $a$ 를 탐색한 횟수
이긴 비율이 높고 지금까지 탐색을 덜 한 행동을 선택

AlphaGo

AlphaGo Fan: 2015년 유럽 챔피언 판 후이 2단과 대국에 사용
- 지도학습 정책망: 프로 6단~9단 사이의 대국 기보 16만개로부터 3천만 가지 바둑판의 상태를 학습. 다음에 어디에 둘 지를 예측
- MCTS에서 트리의 폭을 제한
- 롤아웃망: 시뮬레이션을 빠르게 하기 위해 단순한 구조를 사용
- self-play(알파고끼리 대국)을 하여 정책망을 강화학습 학습
- 정책망을 바탕으로 가치망을 학습
AlphaGo Lee: 2016년 이세돌 9단과 대국
AlphaGo Zero: 정책망과 가치망을 통합, 롤아웃 제거
AlphaZero: 바둑, 장기, 체스 등에 모두 적용가능한 모델

알파고의 정책망, 롤아웃망, 가치망 구조

알파고의 엘로 평점

알파고 버전별 트리 탐색 규모와 엘로 평점

알파고와 인간 기사들의 엘로 평점 비교

엘로 평점 시스템 Elo rating system

물리학자 아르파드 엘로(Arpad Elo)가 개발한 평점 시스템

R \leftarrow R + K (S - E)

$R$ : 평점
$K$ : 상수
$S$ : 이긴 횟수
$E$ : 이긴 횟수의 기댓값

승리 횟수의 기댓값

E_{A} = \frac{1}{1 + 1 0 ^{- (R_{A} - R_{B}) /400}}

$E_{A}$ : A가 이길 확률
$R_{A}$ : A의 평점
$R_{B}$ : B의 평점
로지스틱 함수와 같음

엘로 평점 시스템의 특징

평점으로부터 승리 확률을 예측할 수 있음
모든 선수의 실력을 한 차원에 배열할 수 있다는 가정(unidimensional)
약한 상대에게 지면 평점이 많이 깎이나, 이겨도 조금 밖에 오르지 않음
평점이 오를 수록 더 올리기는 어려워짐

퀴즈

문제 1 / 7맞음: 0힌트: 0틀림: 0채점중: 0남음: 7

Finite Two Person Zero-Sum Sequential Game의 설명으로 올바른 것을 모두 고르세요.

☐일정 시점에 종료된다.
☐두 행위자가 참여한다.
☐두 행위자의 수익의 합이 0이다.
☐모든 행위자가 동시에 한 번만 행동한다.

퀴즈를 풀려면 대화형 기능을 불러와야 합니다.

Finite Two Person Zero-Sum Sequential Game의 설명으로 올바른 것을 모두 고르세요.

finite, two person, zero-sum, sequential의 의미를 각각 확인하세요.

일정 시점에 종료된다.두 행위자가 참여한다.두 행위자의 수익의 합이 0이다.모든 행위자가 동시에 한 번만 행동한다.

일정 시점에 종료된다., 두 행위자가 참여한다., 두 행위자의 수익의 합이 0이다.

미니맥스 전략의 설명으로 가장 알맞은 것은 무엇입니까?

minimax는 상대의 최선(max)에 대응해 자신의 최악을 줄이는(min) 관점입니다.

상대가 최선의 행동을 한다고 보고 그 결과를 최소화하는 행동을 선택한다.상대의 행동을 무작위라고 보고 항상 첫 번째 행동을 선택한다.보상 행렬을 보지 않고 정책망만으로 행동한다.두 행위자의 수익 합을 항상 양수로 만든다.

상대가 최선의 행동을 한다고 보고 그 결과를 최소화하는 행동을 선택한다.

몬테카를로 트리 탐색의 단계 순서로 알맞은 것은 무엇입니까?

트리 정책으로 노드를 고른 뒤, 새 노드를 만들고, 롤아웃 결과를 위로 올립니다.

선택 -> 확장 -> 시뮬레이션 -> 역전파역전파 -> 선택 -> 확장 -> 시뮬레이션시뮬레이션 -> 역전파 -> 선택 -> 확장확장 -> 역전파 -> 선택 -> 시뮬레이션

선택 -> 확장 -> 시뮬레이션 -> 역전파

UCT에서 $N (s, a)$ 가 의미하는 것은 무엇입니까?

괄호 안에 상태와 행동이 함께 들어간 방문 횟수입니다.

상태 s에서 행동 a를 탐색한 횟수상태 s를 전체적으로 탐색한 횟수상태-행동 가치탐색-활용 하이퍼파라미터

상태 s에서 행동 a를 탐색한 횟수

AlphaGo Fan에 대한 설명으로 슬라이드에 나온 것을 모두 고르세요.

정책망, 롤아웃망, self-play, 가치망이 AlphaGo Fan 설명에 함께 등장합니다.

2015년 유럽 챔피언 판 후이 2단과 대국에 사용되었다.지도학습 정책망은 프로 기사 대국 기보로부터 학습했다.MCTS에서 트리의 폭을 제한했다.정책망과 가치망을 처음부터 하나로 통합하고 롤아웃을 제거했다.

2015년 유럽 챔피언 판 후이 2단과 대국에 사용되었다., 지도학습 정책망은 프로 기사 대국 기보로부터 학습했다., MCTS에서 트리의 폭을 제한했다.

엘로 평점 업데이트 식으로 알맞은 것은 무엇입니까?

실제 승리 횟수와 기대 승리 횟수의 차이에 상수 K를 곱해 반영합니다.

R \leftarrow R + K (S - E)

R \leftarrow K + S + E

E_{A} = R_{A} - R_{B}

Q (s, a) + C N (s, a)

R \leftarrow R + K (S - E)

엘로 평점 시스템의 특징으로 올바른 것을 모두 고르세요.

엘로 평점은 승리 확률 예측, 일차원 실력 가정, 상대 강도에 따른 점수 변화가 핵심입니다.

평점으로부터 승리 확률을 예측할 수 있다.모든 선수의 실력을 한 차원에 배열할 수 있다고 가정한다.약한 상대에게 지면 평점이 많이 깎인다.평점이 오를수록 더 올리기는 쉬워진다.

평점으로부터 승리 확률을 예측할 수 있다., 모든 선수의 실력을 한 차원에 배열할 수 있다고 가정한다., 약한 상대에게 지면 평점이 많이 깎인다.