Automated strategy generation for games with uncertain rules

The purpose of this investigation is to develop a methodology for the automated generation of game strategies that addresses uncertainty in game rules, large, complex solution spaces, and the need for automation to examine many possible strategy variations. Many real world problems, like business and military war gaming, are characterized by these ill defined game conditions. These problems are not well matched to traditional automated game playing techniques. Manual analysis can examine only a small fraction of the space of solutions. An alternate approach to traditional game playing techniques is taken, which is to search the solution space of strategies of the game. In the approach taken, games involving conflict between opposing players are studied and decomposed into their component parts. A general algorithm for developing strategies for this type of game is generated. The algorithm gives formal definitions for the components of strategies, their arrangement, and the space of conflicts they define. This enables their symbolic manipulation and allows the application of other algorithms to these components for search, either automated or manual, or other operations. War games, which are a specific instance of a game involving conflict between opposing players, are studied. Their component parts are identified and a methodology for applying the general algorithm for strategy generation to war games is then developed. A framework using evolutionary computation (EC) techniques for automated search is constructed around the war game components as part of this methodology. EC techniques are adapted to match the game domain which has unique characteristics. Using a generic war gaming example, the methodology is demonstrated in a series of experiments to generate strategies. A theoretic model of the game is developed to determine expected outcomes for various game conditions. The results of the strategy generation experiments are compared to the expected outcomes. Results matching the expected outcomes demonstrate that the solution space search and strategy generation methodology is robust and finds solutions with expected characteristics in the very large solution space.