Fingerprinting: Visualization and Automatic Analysis of Prisoner's Dilemma Strategies.

Daniel Ashlock, Eun-Youn Kim
Submitted to IEEE Transactions on Evolutionary Computation

Abstract PDF eprint

Fingerprinting is a technique for generating a representation-independent functional signature for a game playing agent. Fingerprints can be used to compare agents across representations in an automatic fashion. The theory of fingerprints is developed for software agents that play the iterated prisoner's dilemma. Examples of the technique for computing fingerprints are given. The paper summarizes past results and introduces the following new results. Fingerprints of prisoner's dilemma strategies that are represented as finite state machines must be rational functions. An example of a strategy that does not have a finite state representation and which does not have a rational fingerprint function is given: the majority strategy. It is shown that the AllD- and AllC-based fingerprints can be derived from the tit-for-tat fingerprint by a simple substitution. Fingerprints for four new probe strategies are introduced, generalizing previous work in which tit-for-tat is the sole probe strategy. A trial comparison is made of evolved prisoner's dilemma strategies across three representations: finite state machines, feed forward neural nets, and lookup tables. Fingerprinting demonstrates that all three representations sample the strategy space in a radically different manner, even though the neural net's and lookup table's parameters are alternate encodings of the same strategy space. This space of strategies is also a subset of those encoded by the finite state representation. Shortcomings of the fingerprint technique are outlined, with illustrative examples, and possible paths to overcome these shortcomings are given.