[NC FellowShip] MCTS

dasoya·2021년 8월 9일
0

보드게임 AI 알고리즘.

기본개념

환경 = 게임
에이전트 = 게임 AI

a_t = 𝝅(s_t)
-> 상태를 받아 다음 행동을 결정하는 함수.

반응형 에이전트

  • 시뮬레이션 X
  • 행동 평가
  • 응답시간 적고, 성능 떨어질 수 있음.
  • 실시간 시뮬레이션에서 활용하기 적절

숙고형 에이전트

  • 시뮬레이션 기반 의사 결정
  • 상태 평가

MiniMax + 알파-베타 가지치기

개선

평가함수 + 탐색 깊이 제한

평가함수 : 가까운 미래 예측. 전문가 지식 필요.

탐색 깊이 제한 : 근사해로 판단. 수평선 효과 발생 가능성 높아짐.

  • 수평선 효과 = 깊이 제한 때문에 미래 예측 결과의 정확도가 떨어짐.

MCTS

무작위 행동을 통한 의사 결정

  1. 선택
  2. 확장
  3. 시뮬레이션
  4. 백업
  • Tree policy -> Default policy -> Back up
  • 𝝅(s_t) 정교화 - > 평가함수 V(s) 의 정교화

탐색과 활용 -> UCB

-> UCB가 입실론-greedy 보다 상수의존도가 낮음.

이외의 개선 방안

  • 부분트리 재활용
  • 보상신호 강화
  • 평가점수(R) 범위 변경
profile
슬기로운 코딩 생활

0개의 댓글