Reward allotment in an event-driven hybrid learning classifier system for online soccer games

ABSTRACT

This paper describes our study into the concept of using rewards in a classifier system applied to the acquisition of decision-making algorithms for agents in a soccer game. Our aim is to respond to the changing environment of video gaming that has resulted from the growth of the Internet, and to provide bug-free programs in a short time. We have already proposed a bucket brigade algorithm (a reinforcement learning method for classifiers) and a procedure for choosing what to learn depending on the frequency of events with the aim of facilitating real-time learning while a game is in progress. We have also proposed a hybrid system configuration that combines existing algorithm strategies with a classifier system, and we have reported on the effectiveness of this hybrid system. In this paper, we report on the results of performing reinforcement learning with different reward values assigned to reflect differences in the roles performed by forward, midfielder and defense players, and we describe the results obtained when learning is performed with different combinations of success rewards for various type of play such as dribbling and passing. In 200 matches played against an existing soccer game incorporating an algorithm devised by humans, a better win ratio and better convergence were observed compared with the case where learning was performed with no roles assigned to all of the in-game agents.

REFERENCES

• 1: Barry, A. Limits in Long Path Learning with XCS. In Proceedings of the Fifth Annual Genetic and Evolutionary Computation Conference. Vol. 2, LNCS 2724, Springer-Verlag, Berlin, Heidelberg, 2003, 1832--1843.
• 2: Richard K. Belew , Michael Gherrity, Back Propagation for the Classifier System, Proceedings of the 3rd International Conference on Genetic Algorithms, p.275-281, June 01, 1989
• 3: Larry Bull , Dave Wyatt , Ian C. Parmee, Towards The Use Of XCS In Interactive Evolutionary Design, Proceedings of the Genetic and Evolutionary Computation Conference, p.951, July 09-13, 2002
• 4: Butz, M.V., Goldberg, D.E., and Lanzi, P.L. Gradient-Based Learning Updates Improve XCS Performance in Multistep Problems. In Proceedings of the Sixth Annual Genetic and Evolutionary Computation Conference. Vol. 2, LNCS 3103, Springer-Verlag, Berlin, Heidelberg, 2004, 751--762.
• 5: Dawson, D. Improving Performance in Size-Constrained Extended Classifier Systems. In Proceedings of the Fifth Annual Genetic and Evolutionary Computation Conference. Vol. 2, LNCS 2724, Springer-Verlag, Berlin, Heidelberg, 2003, 1870--1881.
• 6: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 7: Steven M. Gustafson , William H. Hsu, Layered Learning in Genetic Programming for a Cooperative Robot Soccer Problem, Proceedings of the 4th European Conference on Genetic Programming, p.291-301, April 18-20, 2001
• 8: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 9: Holland, J.H. Escaping brittleness: The possibilities of general-purpose learning algorithms applied to parallel rule-based systems. In Michalski, R.S. et al. (eds.): Machine Learning II, Morgan Kaufmann Publishers, CA, 1986, 593--623.
• 10: John H. Holmes , Pier Luca Lanzi , Wolfgang Stolzmann , Stewart W. Wilson, Learning classifier systems: new models, successful applications, Information Processing Letters, v.82 n.1, p.23-30, April 15, 2002 [doi>10.1016/S0020-0190(01)00283-6]
• 11: Huang, C-H. and Sun, C-T. Parameter Adaptation within Co-adaptive Learning Classifier Systems. In Proceedings of the Sixth Annual Genetic and Evolutionary Computation Conference. Vol. 2, LNCS 3103, Springer-Verlag, Berlin, Heidelberg, 2004, 774--784.
• 12: Kitano, H., Asada, M., Kuniyoshi, Y., Noda, I., Osawa, E., and Matsubara, H. RoboCup: A challenge problem for AI. AI Magazine, Vol. 18, 1997, 73--85.
• 13: Kovacs, T. What Should a Classifier System Learn and How Should We Measure It? Journal of Soft Computing, Vol. 6, No. 3-4, 2002, 171--182.
• 14: Luke, S. Genetic Programming Produced Competitive Soccer Softbot Teams for RoboCup 97. In Proceedings of the Third Annual Genetic Programming Conference. Morgan Kaufmann Publishers, San Francisco, CA, 1998, 204--222.
• 15: Anthony Di Pietro , Lyndon While , Luigi Barone, Learning In RoboCup Keepaway Using Evolutionary Algorithms, Proceedings of the Genetic and Evolutionary Computation Conference, p.1065-1072, July 09-13, 2002
• 16: Rick L. Riolo, Bucket brigade performance: I. Long sequences of classifiers, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.184-195, October 1987, Cambridge, Massachusetts, United States
• 17: Rick L. Riolo, Bucket brigade performance: II. Default hierarchies, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.196-201, October 1987, Cambridge, Massachusetts, United States
• 18: Rick L. Riolo, The Emergence of Coupled Sequences of Classifiers, Proceedings of the 3rd International Conference on Genetic Algorithms, p.256-264, June 01, 1989
• 19: RoboCup web page. http://www.robocup.org/
• 20: Sato, Y., and Kanno, R. Event-driven Hybrid Learning Classifier Systems for Online Soccer Games. In Proceedings of the 2005 IEEE Congress on Evolutionary Computation. IEEE Press, Edinburgh, 2005, 2091--2098.
• 21: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 22: Wilson, S.W. Classifier Fitness Based on Accuracy. Evolutionary Computation, Vol. 3, No. 2, 1995, 149--175.
• 23: Wilson, S.W. Generalization in the XCS Classifier System. In Proceedings of the Third Annual Genetic Programming Conference. Morgan Kaufmann Publishers, San Francisco, CA, 1998, 665--674.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.0 GENERAL

General Terms:
Design, Experimentation, Verification

Keywords:
event-driven, learning classifier systems, real-time learning, soccer game, video-game