인공지능 강의 4화 :: 게임트리, α-β 가지치기, 몬테카를로

인공지능 강의 4화를 보며 배운내용

 

 

KEYWORDS

최대최소 탐색: 교대로 수를 두는 2인 게임에서 나의 수와 상대의 응수를 나타내는 게임 트리에서 수를 결정하기 위한 탐색 기법

α-β 가지치기: 최대최소 탐색트리의 불필요한 가지를 잘라내서 탐색의 성능을 높이기 위한 알고리즘

몬테카를로 트리 탐색: 게임과 같은 의사결정 문제의 해결을 위해 무작위 표본화를 바탕으로 구성되는 탐색트리로부터 최적의 선택을 하기 위한 경험적 알고리즘

A* 알고리즘: 다음 확장할 노드를 결정할 때 그 노드까지 도달하는 경로비용과 그 노드로 부터 목표 노드에 도달하기 위한 경로비용 예측치의 합이 최소인 노드를 선택하여 탐색

 

 

최대최소 탐색(minimax search)

나 =>내가 둘 수 있는 가장 유리한 수(Maxmize)

상대 => 내게 가장 불리한 수 선택(Minmize)

 

트리의 규모가 매우 클 경우 모든 경우의 수를 탐색해서 종단상태까지 도달할 수 없다

종단상태: 더 이상 게임을 진행할 수 없는 상태(승 무 패 결정되는 상태)

=> 얼마나 깊이 과정을 반복할 것인지 정하고,

경험적 지식을 반영하여 설계된 평가함수를 통해 그 노드의 가치 추청

 

'얼마나 깊이' 라는 말은 예를들어 3목을 한다면

2수까지 계산해서 최적의 수를 찾는지, 3수, 4수, 5수 까지 생각해서 거슬러 올라가 최적의 수를 찾는지 선택의 문제

깊이가 깊어질수록 프로그램 짜기는 힘들겠구나

 

 

α-β 가지치기

최대최소 탐색트리에서 불필요한 가지를 잘라내서 탐색 성능을 높이기 위한 알고리즘

 

α: 최대화 노드의 최대화 과정에서 가장 큰 값

최소화 후계노드 어떤 것 중 하나의 값이 v 일 때 α >= v 이면,

그 최소화 노드의 나머지 후계노드 전부 가지치기한다.

=> 정리해보면, α에는 큰 값이 들어가야 된다.

1. 그 큰값을 정하기위해 밑의 최소화 후계노드에서 정해진다.
2. 만약 α 값이 7이고, 최소화 후계노드 중 3이 있다.
3. 최소화 후계노드는 최소 값을 선택하는 거라 다른 것들을 안봐도 3이하가 선택된다는 것을 알 수 있다.
4. 3이하가 선택되면 α의 7값보다 작다 그럼 선택이 안된다.
5. 그래서 그 쪽의 나머지 후계노드 전부 가지치기 해버리는건다.

 

β는 위와 반대 과정을 갖는다

β: 최소화 노드의 최소화 과정에서 지금까지 구한 가장 작은 가치

후계노드 가치가 v 일 때, β <= v 라면 그 나머지 후계노드 가지치기

 

 

몬테카를로 트리 탐색(Monte Carlo Tree Search: MCTS)

무작위 표본화 바탕으로 탐색트리 구성

 

선택 전략

주어진 노드의 자식노드 중 하나를 선택하기 위한 전략

탐사와 활용 사이의 균형을 이룰 수 있도록 설계

UCT 알고리즘은 잘 알려진 선택전략 중 하나이다.

 

탐사(exploration): 덜 유망한 것으로 보이지만 향후 우수한 것으로 드러날 수 있는 수들을 선택할 수 있도록 하는 것

활용(exploitation): 지금까지 결과 중 가장 우수한 결과를 이끌어 내는 수를 선택

=> Multi-armed bandit(MAB) 문제 라고도 한다

 

시뮬레이션 전략

게임이 끝날 때까지 스스로 수를 선택하여 게임 진행

수의 선택 방법

• 순수한 무작위
• 적절한 시뮬레이션 전략에 따른 유사 무작위 수

 

최종적인 최적 행동 선택

• 최대 자식: 가장 큰 보상
• 강인한 자식: 가장 많이 방문
• 최대-강인 자식: 가장 많은 방문 + 가장 큰 보상
• 안전한 자식: 신뢰도 하한선 큰 자식

알파고는 몬테카를로 탐색 이용했고, 강인한 자식을 선택했다.

 

 

Monte Carlo, Monaco