Hybrid Training Strategies: Improving Performance of Temporal Difference Learning in Board Games
Source abstract
Abstract
Temporal difference (TD) learning is a well-known approach for training automated players in board games with a limited number of potential states through autonomous play. Because of its directness, TD learning has become widespread, but certain critical difficulties must be solved in order for it to be effective. It is impractical to train an artificial intelligence (AI) agent against a random player since it takes millions of games for the agent to learn to play intelligently. Training the agent against a methodical player, on the other hand, is not an option owing to a lack of exploration. This article describes and examines a variety of hybrid training procedures for a TD-based automated player that combines randomness with specified plays in a predetermined ratio. We provide simulation results for the famous tic-tac-toe and Connect-4 board games, in which one of the studied training strategies significantly surpasses the other options. On average, it takes fewer than 100,000 games of training for an agent taught using this approach to act as a flawless player in tic-tac-toe.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Artificial Intelligence in Games · Reinforcement Learning in Robotics · Evolutionary Algorithms and Applications
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Telematic Systems and Computation, Rey Juan Carlos University, Fuenlabrada, 28942 Madrid, Spain
Funding
Comunidad de Madrid
References (28)
Show source-provided references
1. Reinforcement Learning: A Survey10.1613/jair.301 ↗
2. Sutton, R., and Barto, A. (1998). Reinforcement Learning: An Introduction, MIT Press.10.1109/TNN.1998.712192 ↗
3. Konen, W., and Bartz-Beielstein, T. (2009, January 8–12). Reinforcement learning for games: Failures and successes. Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers, Montreal, QC, Canada.10.1145/1570256.1570375 ↗
4. Some studies in machine learning using the game of checkers10.1147/rd.33.0210 ↗
5. Tesauro, G. (1992, January 1–3). Temporal difference learning of backgammon strategy. Proceedings of the 9th International Workshop on Machine Learning, San Francisco, CA, USA.
6. Tesauro, G. (1992). Practical Issues in Temporal Difference Learning. Reinforcement Learning, Springer.10.1007/978-1-4615-3618-5_3 ↗
7. Self-Play and Using an Expert to Learn to Play Backgammon with Temporal Difference Learning
8. Konen, W. (2015). Reinforcement Learning for Board Games: The Temporal Difference Algorithm, Research Center CIOP (Computational Intelligence, Optimization and Data Mining), TH Koln—Cologne University of Applied Sciences. Technical Report.
9. Gatti, C.J., Embrechts, M.J., and Linton, J.D. (2011, January 9–12). Reinforcement learning and the effects of parameter settings in the game of Chung Toi. Proceedings of the 2011 IEEE International Conference on Systems, Man, and Cybernetics, Anchorage, AK, USA.10.1109/ICSMC.2011.6084216 ↗
10. Gatti, C.J., Linton, J.D., and Embrechts, M.J. (2011, January 27–29). A brief tutorial on reinforcement learning: The game of Chung Toi. Proceedings of the ESANN 2011 Proceedings, European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, Bruges, Belgium.
11. Reinforcement learning of local shape in the game of go
12. Temporal Difference Learning of Position Evaluation in the Game of Go
13. Van der Ree, M., and Wiering, M.A. (2013, January 16–19). Reinforcement learning in the game of othello: Learning against a fixed opponent and learning from self-play. Proceedings of the 2013 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL), Singapore.10.1109/ADPRL.2013.6614996 ↗
14. Russell, S., and Norvig, P. (2009). Artificial Intelligence: A Modern Approach, Prentice Hall Press. [3rd ed.].
15. Learning to Predict by the Methods of Temporal Differences10.1007/BF00115009 ↗
16. Pool, D., and Mackworth, A. (2017). Artificial Intelligence: Foundations of Computational Agents, Cambridge University Press. [2nd ed.].10.1017/9781108164085 ↗
17. Szubert, M., Jaskowski, W., and Krawiec, K. (2009, January 7). Coevolutionary temporal difference learning for Othello. Proceedings of the Proceedings of the 5th International Conference on Computational Intelligence and Games (CIG’09), Piscataway, NJ, USA.10.1109/CIG.2009.5286486 ↗
18. Krawiec, K., and Szubert, M. (2011, January 12–16). Learning n-tuple networks for Othello by coevolutionary gradient search. Proceedings of the GECCO’2011, Dublin, Ireland.10.1145/2001576.2001626 ↗
19. Learning to play Othello with n-tuple systems
20. Thill, M., Bagheri, S., Koch, P., and Konen, W. (2014, January 26–29). Temporal Difference Learning with Eligibility Traces for the Game Connect-4. Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG), Dortmund, Germany.10.1109/CIG.2014.6932870 ↗
21. Steeg, M., Drugan, M., and Wiering, M. (2015, January 8–10). Temporal Difference Learning for the Game Tic-Tac-Toe 3D: Applying Structure to Neural Networks. Proceedings of the 2015 IEEE Symposium Series on Computational Intelligence, Cape Town, South Africa.
22. Smys, S., Bestak, R., and Rocha, Á. (2019). An Efficient Training Strategy for a Temporal Difference Learning Based Tic-Tac-Toe Automatic Player. Inventive Computation Technologies, International Conference on Inventive Computation Technologies ICICIT 2019, Coimbatore, India, 29–30 August 2019, Springer. Lecture Notes in Networks and Systems.
23. Baum, P. (1975). Tic-Tac-Toe. [Master’s Thesis, Computer Science Department, Southern Illinois University].
24. Flexible strategy use in young children’s tic-tac-toe
25. A Note on the Computer Solution of Connect-Four
26. Allis, V.L. (1988). A Knowledge-Based Approach of Connect-Four. [Master’s Thesis, Vrije Universiteit].10.3233/ICG-1988-11410 ↗
27. Solving Connect-4 in Medium Board Sizes10.3233/ICG-2008-31205 ↗
28. Hemanth, D.J., Kumar, V.D.A., and Malathi, S. (2020). Analysis of Minimax Algorithm Using Tic-Tac-Toe. Intelligent Systems and Computer Technology, IOS Press.10.3233/APC37 ↗