Analysis of game playing agents with fingerprints.

摘要

Evolutionary computation (EC) can create a vast number of strategies for playing simple games in a short time. Analysis of these strategies is typically more time-consuming than their production. As a result, analysis of strategies produced by an EC system is often lacking or restricted to the extraction of superficial summary statistics. This thesis presents a technique for extracting a functional signature from evolved agents that play games. This signature can be used as a visualization of agent behavior in games with two moves and also provides a numerical target for clustering and other forms of automatic analysis. The fingerprint can be used to induce a similarity measure on the space of game strategies. This thesis develops fingerprints in the context of the iterated prisoner's dilemma; we note that they can be computed for any two player simultaneous game with a finite set of moves. When using a clustering algorithm, the results are strongly influenced by the choice of the measure used to find the distance between or to compare the similarity of the data being clustered. The Euclidean metric, for example, rates a convex polytope as the most compact type of object and builds clusters that are contained in compact polytopes. Presented here is a general method, called multi-clustering, that compensates for the intrinsic shape of a metric or similarity measure. The method is tested on synthetic data sets that are natural for the Euclidean metric and on data sets designed to defeat k-means clustering with the Euclidean metric. Multi-clustering successfully discovers the designed cluster structure of all the synthetic data sets used with a minimum of parameter tuning. We then use multi-clustering and filtration on fingerprint data. Cellular representation is the practice of evolving a set of instructions for constructing a desired structure. This thesis presents a cellular encoding for finite state machines and specializes it to play the iterated prisoner's dilemma. The impact on the character and behavior of finite state agents of using the cellular representation is investigated. For the cellular representation resented a statistically significant drop in the level of cooperation is found. Other differences in the character of the automaton generated with a direct and cellular representation are reported.