Study of learning algorithms in games
Rahul Bhasker · DR-NTU (Nanyang Technological University) · 2009
In many computer games various bots operate against the player. Unlike algorithms for static targets which already exist, these bots require algorithms to search for moving targets and these algorithms are inherently more computation and resource intensive. In some computer games, search algorithms utilize as much as 70% of CPU time and hence design requirements of these algorithms necessitate good computation and execution efficiency. The typical moving target search algorithm repeatedly applies the A* algorithm to the moving target to find a partial solution and execute the move. However, as the size of the problem space increases, the size of the heuristic table required grows exponentially. In previous work, the Abstraction MTS significantly reduced the memory requirements and showed improved performance over other existing MTS algorithms by clustering the problem space into “abstract groups”. However, the existing Abstraction MTS has no learning component and hence the performance is constant even if the same problem space is used repeatedly. This project explores the re-introduction of learning into the Abstraction MTS, without reducing the performance of the basic Abstraction MTS algorithm.