게임상에서의 Plan Recognition을 이용한 상태공간 최적화와 강화학습 : State Space Optimization Using Plan Recognition and Reinforcement Learning on Game
- 발행기관 서강대학교 대학원
- 지도교수 오경환
- 발행년도 2007
- 학위수여년월 2007. 8
- 학위명 석사
- 학과 및 전공 컴퓨터학
- 식별자(기타) 000000104430
- 본문언어 한국어
목차
실시간 전략게임은 현실 세계의 의사결정 문제에서 해결해야 하는 문제들을 동일하게 포함하고 있다. 여기서 나타나는 문제들은 실시간 처리능력, 거대한 상태공간과 다중 agent로 인한 높은 복잡도, 불충분한 정보, 실시간 학습 등과 같은 문제이다. 인공지능 분야에서 위와 같은 문제들의 해결을 위한 연구가 지속되어 왔다. 하지만 아직 이러한 문제들로 인해 게임에 적용되는 인공지능은 제한적이고 낮은 성능을 보이고 있다.
최근의 연구에서 실시간 전략게임에 Dynamic Scripting 방법이 제안되었는데 이것은 강화학습을 이용한 rule 기반의 스크립트 생성 방법이다. Dynamic Scripting은 임의의 제한된 상태공간을 가정하고 학습하기 때문에 실시간 환경의 특성을 충분히 반영하지 못하고 있다. 본 논문에서는 해결책으로 상태공간을 최적화하는 방법을 제안한다. 상태공간의 최적화를 위해 Case-Based Plan Recognition(CBPR) 방법을 이용하여 상대편 agent의 행동패턴을 모델링하고 CBPR에서 사용된 추상화된 상태공간을 동일하게 사용하였다. 이렇게 최적화된 상태공간은 Partial Observable Markov Decision Process (POMDP)와 유사한 접근방법을 사용하면서 상태공간을 단순화시켜서 높은 복잡도를 감소시켜주고 이것을 통해 실시간 환경에 적용 가능하게 해준다. 실제 실시간 전략게임인 Wargus에서 이 방법을 적용해 보았다. 그리고 실험으로 실제 대결을 통해 기존의 Dynamic Scripting 보다 우수한 성능을 보임을 입증하였다.
이 방법은 실시간 환경에서 상대편의 전략에 적응하는 방식을 취하기 때문에 사람과의 대결에서도 학습을 통한 우수한 성능을 보일 수 있을 것이다. 사람의 전략에 대한 모델링과 대전을 통한 성능 입증은 차후의 연구과제로 남겨두겠다.
목차
Real Time Strategy (RTS) Game has the same problem which has to be solved in decision making in the real world. These problems are on real-time performance, high complexity caused by the large state space and multi-agent, insufficient information and on-line learning. In Artificial intelligence, many researches have been conducted to solve those problems. AI which has been applied to RTS Game is somewhat limited and has poor performance due to those problems.
Recent research to apply AI to RTS Game has proposed Dynamic Scripting. This method is generating rule-based game script by using reinforcement learning. Dynamic Scripting, however, assuming arbitrary and limited state space, is not able to fully reflect characteristics of real-time environment. This paper suggests a method to optimize state space as a solution. For state space optimization Case-Based Plan Recognition (CBPR) is utilized to model behavior pattern of opponent agent, and abstract state space which was used in CBPR is also utilized as well. Optimized state space in this procedure uses similar approaches as Partial Observable Markov Decision Process (POMDP). And it leads to simplify state space to decrease high complexity and enable RTS game to apply to real-time environment. This method is used in distributed RTS Game, WARGUS in this paper. Following this experiment, it will be verified that this method shows superior performance to existing Dynamic Scripting.
Because this method takes the approaches of adapting to opponent’s tactics, by way of learning it can probably show better performance in human player. Modeling human tactics and verifying performance through playing games with human will be left as a future work,
