For the exact algorithms, the results show that our pruning techniques for backward induction dramatically improve the computation time required by the previous exact algorithms. We perform a thorough experimental evaluation on six substantially different games for both settings. We evaluate the algorithms in two different settings: the offline case, where computational resources are abundant and closely approximating the optimal strategy is a priority, and the online search case, where computational resources are limited and acting quickly is necessary. The algorithms include exact backward induction methods with efficient pruning, as well as Monte Carlo sampling algorithms. In this paper, we describe both novel and existing algorithms that compute strategies for the class of two-player zero-sum simultaneous move games. This formalism has been used to express games in general game playing and can also model many discrete approximations of real-world scenarios. At each stage, a player does not know what action the other player will take, but otherwise knows the full state of the game.
Simultaneous move games model discrete, multistage interactions where at each stage players simultaneously choose their actions.
0 kommentar(er)
