Representing Uncertainty in RTS Games - Björn Jónsson 1978- (2011)
Heildartexti lokaskýrslu. Prentuð útgáfa er varðveitt á bókasafni HR. Real-time strategy (RTS) games are partially observable environments, requiring players to reason under uncertainty. The main source of uncertainty in RTS games is that players do not initially know the game map, including what units the opponent has created. This information gradually improves, in part by exploring, as the game progresses. To compensate for this uncertainty, human players use their experience and domain knowledge to estimate the combination of units that opponents control, and make decisions based on these estimates. For RTS game AI to mimic this behavior of human players, a suitable knowledge representation is required. The order in which units can be created in RTS games is conditioned by a game specific technology tree where units represented by parent nodes in the tree need to be created before units represented by child nodes can be created. We propose the use of a Bayesian Network (BN) to represent the beliefs that RTS game AI players have about the expansion of the technology tree of their opponents. We implement a BN for the RTS game StarCraft and give several examples of its use. In particular, we evaluate our design by improving strategy prediction under uncertainty from previously reported work [37]. Using our BN, we are able to increase the precision of strategy prediction up to 56%. These results show that the proposed BN can be used to infer creation time values for unobserved units in RTS games and that BNs are a promising approach for RTS game AI to represent and reason with uncertainty in RTS games. Háskólinn í Reykjavík