본문 바로가기 주메뉴 바로가기
검색 검색영역닫기 검색 검색영역닫기 ENGLISH 메뉴 전체보기 메뉴 전체보기

논문

Fingerprinting: Visualization and analysis of prisoner's Dilemma strategies

https://doi.org/10.1109/TEVC.2008.920675

  • 저자김은연
  • 학술지IEEE Transactions on Evolutionary Computation 12/5
  • 등재유형
  • 게재일자(2008)


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. This 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, feedforward 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.


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. This 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, feedforward 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.

이 페이지에서 제공하는 정보에 대해 만족하십니까?