강화학습 알고리즘 (Two-ply game tree , Alpha-Beta purning, Monte Carlo Tree Search)

오늘은 알파고에서 사용된 것 처럼 게임을 진행하면서 스스로 학습하는 알고리즘인 강화학습 알고리즘에 대한 수업을 듣고 정리해 보았다.

1. Two-ply game tree

Two-ply game tree의 경우 2개의 플레이어가 있다고 생각하고 선택을 한다.

만약 순서대로 한번씩 선택을 하는 경우에는 내가 최선책을 선택하고 나면 다른 플레이어가 해당 시점에서의 최선책을 선택하게 된다.

이에 따라서 내 시점에서 최선의 선택이 아닌 상대가 상대입장에서 최선의 선택을 한 이후에 해당 시점에서의 최선의 선택을 하는것이 Two-ply 게임 트리이다.

여기서 MiniMax-search 를 사용하게 되는데 이는 내 입장 그리고 상대입장을 고려하여 상대방의 최적의 페이스를 고려하고 내 시점에서 최선이 아닌 차선 중 최선을 선택하는 전략이다.

모델 평가

Complete - Yes

Optimal - Yes (상대를 상대함에 있어서)

시간 복잡도 - m이 깊이이고 b가 움직임 수면 B^m 이 시간복잡도이다.

공간 복잡도 - DFS 탐색의 일종이므로 bm 이 공간복잡도 이다.

아래 블로그가 잘 나와 있어서 나는 해당 블로그를 보고 이해를 하였다.

출처 : https://jyeonnyang2.tistory.com/108

A Game Search Problem, A Two-Ply (One Move Deep) Game Tree, The Optimal Strategy in a Game Tree

증진 방법 - Alpha-Beta purning

https://velog.io/@digh0515/AI-5-1.-Alpha-Beta-Pruning-%EC%95%8C%ED%8C%8C%EB%B2%A0%ED%83%80-%ED%94%84%EB%A1%9C%EC%8B%9C%EC%A0%80

[AI] 5-1. Alpha-Beta Pruning (알파베타 프로시저)

 

https://going-to-end.tistory.com/entry/%EC%95%8C%ED%8C%8C-%EB%B2%A0%ED%83%80-%EA%B0%80%EC%A7%80%EC%B9%98%EA%B8%B0-Alpha-beta-pruning

알파-베타 가지치기, Alpha-beta pruning

DFS의 경우 결국 공간 복잡도가 크기 때문에 이러한 한계를 극복하기 위해 나온 알파베타 가지치기라는 개념이 있다고 한다.

알파베타 가지치기의 경우 결국 애초에 고려하지 않는 경우의 수 자체는 계산을 하지 않는 것이라고 한다.

결국 매 선택에 있어서 최적의 값만 선택한다고 하면 고려 자체가 되지 않는 최악의 수 같은 것이 존재하기 마련인데 이런 경우의 수는 계산하기 전에 가지치기를 해서 없애버리는 것이다.

알파베타 가지치기는 결과 값에는 영향을 끼치지 않으며 effectiveness(유효성)은 얼마나 많이 가지치기를 하는가에 달려있다고 한다. 잘라내는 가지의 크기는 밑에 붙어 있는 자식들의 순서에 영향을 받고 이에 따라서 유효성도 달라지게 되는 것이다.

2. Monte Carlo Tree Search

출처 : https://gusals1620.tistory.com/3

몬테카를로 트리 서치 (Monte Carlo Tree Search)에 대한 정확한 정리

수업 시간의 내용이 어려워서 위의 블로그를 보고 이해했다. 블로그 글이 너무 정리가 잘 되어 있으니 자세한 내용은 위의 블로그를 참고하길 바란다.

 

확률 계산 알고리즘인 Monte Carlo는 많이들 아시다시피 정확한 확률 분포를 구하기 어려울 때 무작위 표본 추출을 통해 확률 분포를 도출하는 것으로써 통계열역학으로부터 만들어진 방법론입니다.

그렇다고 한다. 난 문과생이라 그런지 첨 들어봤다.

결국 해당 방식은 랜덤으로 수행을 해서 전체 다 계산해서 판단하기 보다는 충분히 많은 양의 탐색을 해서 대략적으로 이정도면 나쁘지 않은 수다 싶은 시점까지의 계산만 하고 결과 값을 도출하는 것이라고 한다.

각 수마다 승률을 계산하고 계속 업데이트를 하는 식으로 하는 것이다.

여기서 플레이아웃은 임의로 게임을 한번 진행해 본다는 것이다. 플레이 아웃의 수행 시간은 (default Policiy 또는 roll outpolicy)를 사용해서 실행을 하게 되는데 플레이아웃을 매번 확장마다 진행하고 이를 통해서 각 수마다 승률을 계산할 수있다는 것이다.

위 블로그에 자세한 설명이 있는데

출처 : https://gusals1620.tistory.com/3

선택 단계에서 확장 단계 그리고 시뮬레이션 단계 (디폴트 정책 만큼의 시간만 실행) 하고 역전파 단계를 거친다.

역전파 단계에서는 승률이 업데이트 되기 때문에 이전에 전파되었던 기록들을 다시 역으로 역전파를 시켜서 승률을 전부 업데이트 한다.