Treffer: Evolving strategies with genetic programming

Complexity in the physical world and in knowledge domains entails that human expertise is needed for problem-solving and, with finite computational resources, that automated problem-solving needs heuristic methods from human experts. Both factors contribute to the knowledge acquisition bottleneck. Games of strategy are inherently complex and difficult to solve analytically. When the protagonists are autonomous agents in a simulation, their capabilities for movement approach those that are found in the real-world, and their information picture of this environment is partial and noisy, analytical solutions are not available. Genetic programming (GP) handles complexity in a similar way to nature by evolving solutions. Instead of using a genetic strand, GP's solutions are more conveniently generated in the form of programs, here plans of action representing strategies. Based on its suitability as a generic technique, GP was therefore applied to three models of increasing complexity in pursuit-evasion, guard-intrusion, and a hybrid scenario, to investigate the nature and quality of its solutions to these games, particularly regarding their scalability and robustness. This research aim coincided with an enduser's interest in discovering strategies by automated means for comparison with human-generated strategies. The end-user supplied a real-world simulation that could be used for testing strategies in the third, most complex model. As part of this research, a prototype GP system was constructed for generating strategies and evaluating them on the simulation. Plans in the third model were given a structure in the form of a phase transition network to facilitate the evolution of strategies for accomplishing sub-objectives through plan phases. The prototype system was delivered to the end-user. It was found that highly successful solutions may be deceptively brittle, particularly if they rely on superiority in a capability such as speed. Deliberately reducing a protagonist's relative capabilities to positions of equality and disadvantage encouraged an intelligent differentiation of strategy types, producing some that appear to be generally applicable in their animal-like use of manoeuvres and stealth. It appears that differentiation of strategy types may be predictable from the relative level of capabilities used. An implication is that relative capability used can suggest the best strategy to adopt and, conversely, that selection of an objective to achieve will influence the selection of strategy. If so, then this may be said to be an intelligent approach to matching the use of capabilities and resources to objectives. It is concluded that an approach of restricting capabilities is likely to be beneficial in games of strategy and in numerous other related domains for generating a portfolio of human-competitive strategies for adapting solutions to objectives and circumstances.