Using stochastic AI techniques to achieve unbounded resolution in finite player Goore Games and its applications
The Goore Game (GG) introduced by M. L. Tsetlin in 1973 has the fascinating property that it can be resolved in a completely distributed manner with no intercommunication between the players. The game has recently found applications in many domains, including the field of sensor networks and Quality-of-Service (QoS) routing. In actual implementations of the solution, the players are typically replaced by Learning Automata (LA). The problem with the existing reported approaches is that the accuracy of the solution achieved is intricately related to the number of players participating in the game - which, in turn, determines the resolution. In other words, an arbitrary accuracy can be obtained only if the game has an infinite number of players. In this paper, we show how we can attain an unbounded accuracy for the GG by utilizing no more than three stochastic learning machines, and by recursively pruning the solution space to guarantee that the retained domain contains the solution to the game with a probability as close to unity as desired. The paper also conjectures on how the solution can be applied to some of the application domains.
|Keywords||Goore games, Intelligent game playing, Learning automata, Sensor networks and quality-of-service routing|
|Conference||2007 IEEE Symposium on Computational Intelligence and Games, CIG 2007|
Oommen, J, Granmo, O.-C. (Ole-Christoffer), & Pedersen, A. (Asle). (2007). Using stochastic AI techniques to achieve unbounded resolution in finite player Goore Games and its applications. In Proceedings of the 2007 IEEE Symposium on Computational Intelligence and Games, CIG 2007 (pp. 161–167). doi:10.1109/CIG.2007.368093