General video game playing escapes the no free lunch theorem
Daniel Ashlock, Diego Pérez-Liébana, Amanda Saunders · 2017
Popular topics in current research within the games community are general game playing and general video game playing. Both of these efforts seek to find relatively general purpose AI to play games. Within the optimization community we are approaching the 20th anniversary of the no free lunch theorem. In this paper we suggest reasons why a games version of a no free lunch result is probably not problematic. This is accomplished by noting that none of the "general" efforts are - or should be - actually general. Technology is proposed to exploit the lack of generality to permit more effective game playing AIs to be designed. A program for classifying games is outlined that consists of gathering performance data on many games for many algorithms and then using the resulting matrix of performance data to create a tree structured classification of the games. This classification is proposed as the basis for assigning games to appropriate algorithms within a more general framework. A novel algorithm that yields more stable tree-based classification is also proposed.