Extending Fictitious Play with Pattern Recognition

Abstract

Fictitious play, an algorithm to predict the opponents next move based on the observed history of play, is one of the oldest simple yet very ef- fective algorithms in game theory. Although using pattern recognition as a more sophisticated way to analyze the history of play seems a log- ical step, there is little research available on this subject. In this thesis we will examine two different types of pattern recognition, and formulate several algorithms that incorporate these approaches. These algorithms and the basic fictitious play variants they extend are empirically tested in eight tournaments on some well known formal-form games. The results obtained will show that adding pattern recognition to fictitious play im- proves performance, and demonstrate the general possibilities of applying pattern recognition to agents in game theory.