레플리
글 수 57

몬테카를로 트리 검색 알고리즘

조회 수 3812 추천 수 0 2017.03.27 00:43:51


http://mongxmongx2.tistory.com/17

 

 

 

figure1.jpg

 

보드게임처럼 1:1로 하는 게임은 보통 MInimax 알고리즘을 사용합니다.

나와 상대방이 하는 경우의 수를 트리로 만들고 가장 점수가 높은 쪽으로 선택합니다.

좀 더 자세한 내용은 아래 링크에서 확인하실 수 있습니다.

 

http://aidev.co.kr/index.php?mid=game&page=3&document_srl=221

 

 

 

하지만 바둑과 같이 탐색공간이 넓을 경우 Minimax는 계산시간이 너무 오래 걸립니다.

그래서 확률기반으로 랜덤하게 시뮬레이션하는 MCTS(Monte Carlo Tree Search)가 적합합니다.

 

 

 

MCTS_(English).svg.png

 

MCTS는 크게 위와 같이 4가지 과정을 반복합니다.

 

Selection은 어떤 자식 노드로 이동할지 결정합니다.

Expansion은 노드에서 확장을 할지 멈출지를 결정합니다.

Simulation은 현재 노드에서 게임을 끝까지 플레이하고 결과를 얻습니다.

Backpropagation은 시뮬레이션 결과를 상위노드로 전달해 수정합니다.

 

 

 

알파고에서도 기본적으로 MCTS를 바탕으로 하고

거기에 딥러닝 지도학습과 강화학습을 적용하여 구현하였다고 합니다.

 

 

 

< 인공지능 개발자 모임 >

- 페이스북 그룹에 가입하시면 인공지능에 대한 최신 정보를 쉽게 받으실 수 있습니다.

https://www.facebook.com/groups/AIDevKr/

 

List of Articles
제목 글쓴이 날짜 조회 수sort
A* 알고리즘을 사용한 길찾기 file 깊은바다 2016-03-25 14123
유용한 게임 AI 기법 정리 깊은바다 2017-05-04 8406
FSM을 사용한 인공지능 구현 예제 file [1] 깊은바다 2017-04-13 7754
자바스크립트로 만든 장기 인공지능 [4] 깊은바다 2017-03-17 6088
게임트리를 사용한 제로섬 게임의 인공지능 file 깊은바다 2016-03-19 4309
몬테카를로 트리 검색 알고리즘 file 깊은바다 2017-03-27 3812
FSM를 활용한 FPS게임 [2] 사지방컴 2017-10-02 2835
FSM, 몬스터 인공지능의 구현 file 깊은바다 2016-03-19 2685
실용적 예제로 본 게임 인공지능 소스코드 및 PDF 파일 깊은바다 2017-03-31 2293
삼성SDS의 SAIDA팀이 만든 스타크래프트 인공지능 깊은바다 2018-12-07 1996
인공지능 원리로 구현하는 장기 게임 file 깊은바다 2016-03-19 1893
딥러닝으로 게임 콘텐츠 제작하기 file 깊은바다 2017-05-11 1882
A* 알고리즘 데모 file 깊은바다 2018-08-18 1874
FPS 전투가 가능한 인공지능 [5] 사지방컴 2018-05-13 1831
행동트리로 구현하는 인공지능 깊은바다 2017-02-28 1672