보드게임 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) 범위 변경