Abstract
2048 is a cell shift game played on a 4x4 grid. The 2048 game spread among people quickly and had a significant playing time. In addition to its popularity, it attracted the attention of artificial intelligence researchers since many situations can occur despite the small number of actions. The number of situations that can occur on the game board is 1216; considering all the possibilities and the stochastic structure in the game are taken into account, the game's difficulty level is seen. In the literature, studies that include the implementation of the 2048 game can be evaluated mainly under two approaches. These are learning-based methods and search-based methods. In this study, basic algorithms for these two approaches have been determined. Q-Learning was used as a learning-based method when using Deep Priority Search (DFS) and Monte Carlo Tree Search (MCTS) as search-based methods. In addition, algorithms were applied with different techniques, such as pruning and the roulette wheel. Scores and maximum diamonds metrics were taken into account when analyzing algorithms. The most successful algorithm was DFS by score metric, while the MCTS algorithm was the most successful method under the maximum tile
Keywords
2048 game reinforcement learning depth-first search Monte Carlo tree search algorithm analysis
References
- Boris, T., & Goran, S. (2017). Evolving neural network to play game 2048. 24th Telecommunications Forum, TELFOR 2016. Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/TELFOR.2016.7818911
- Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., … Colton, S. (2012, March). A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 4, pp. 1–43. https://doi.org/10.1109/TCIAIG.2012.2186810
- Campbell, M., Hoane, A. J., & Hsu, F.-H. (2002). Deep Blue. In Artificial Intelligence (Vol. 134).
- Cirulli G. (2014). The Creator of the 2048 Game . https://github.com/gabrielecirulli/2048 improving reinforcement learning performance. (n.d.).
- Jacobsen, E. J., Greve, R., & Togelius, J. (2014). Monte mario: Platforming with MCTS. GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference, 293–300. Association for Computing Machinery. https://doi.org/10.1145/2576768.2598392
- Jaśkowski, W. (2018). Mastering 2048 with delayed temporal coherence learning, multistage weight promotion, redundant encoding, and carousel shaping. IEEE Transactions on Games, 10(1), 3–14. https://doi.org/10.1109/TCIAIG.2017.2651887
- Kondo, N., & Matsuzaki, K. (2019). Playing game 2048 with deep convolutional neural networks trained by supervised learning. Journal of Information Processing, 27, 340–347. https://doi.org/10.2197/ipsjjip.27.340
- Levine, S., Kumar, A., Tucker, G., & Fu, J. (2020). Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems. Retrieved from http://arxiv.org/abs/2005.01643
- Lipowski, A., & Lipowska, D. (2011). Roulette-wheel selection via stochastic acceptance. https://doi.org/10.1016/j.physa.2011.12.004
- Matsuzaki, K. (2017). Systematic selection of N-tuple networks with consideration of interinfluence for game 2048. TAAI 2016 - 2016 Conference on Technologies and Applications of Artificial Intelligence, Proceedings, 186–193. Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/TAAI.2016.7880154
- Mehta, R. (2014). 2048 is (PSPACE) Hard, but Sometimes Easy. Retrieved from http://arxiv.org/abs/1408.6315 Newborn, M. (2000). Deep Blue’s contribution to AI. In Annals of Mathematics and Artificial Intelligence (Vol. 28).
- Nie, Y., Hou, W., & An, Y. (n.d.). AI Plays 2048.
- Rodgers, P., & Levine, J. (n.d.). An Investigation into 2048 AI Strategies. Retrieved from http://www.veewo.com/games/
- Sauren K, Jansen N, and Strüber D. (2022). Improving Reinforcement Learning Performance in 2048 Using Expert Knowledge.
- Siau, K., & Wang, W. (2018). Building Trust in Artificial Intelligence, Machine Learning, and Robotics Supply Chain Management View project. Retrieved from www.cutter.com
- Tong, S. (n.d.). Roulette Wheel Selection Game Player. Retrieved from https://digitalcommons.macalester.edu/mathcs_honors/30
- Wang, F. Y., Zhang, J. J., Zheng, X., Wang, X., Yuan, Y., Dai, X., … Yang, L. (2016). Where does AlphaGo go: From church-turing thesis to AlphaGo thesis and beyond. IEEE/CAA Journal of Automatica Sinica, 3(2), 113–120. https://doi.org/10.1109/JAS.2016.7471613
- Weikai, W., & Kiminori, M. (n.d.). Improving DNN-based 2048 Players with Global Embedding. Retrieved from https://github.com/wwk1397/Improving-DNN-
- Yeh, Kun Hao, I. Chen Wu, Chu Hsuan Hsueh, Chia Chuan Chang, Chao Chin Liang, and Han Chiang. (2017). “Multistage Temporal Difference Learning for 2048-like Games.” IEEE Transactions on Computational Intelligence and AI in Games 9(4):369–80. doi: 10.1109/TCIAIG.2016.2593710.
- Yu, Haofeng. (2016). From Deep Blue to DeepMind: What AlphaGo Tells Us.
Abstract
2048, 4x4 ızgara üzerinde oynanan hücre kaydırmalı bir oyundur. 2048 oyunu kısa bir süre içerisinde insanlar arasında yayılarak önemli bir oynanma süresine sahip oldu. Popülerliğinin yanında, aksiyon sayısının az olmasına rağmen oluşabilecek çok fazla durumun bulunması nedeniyle yapay zeka araştırmacılarının dikkatini çekti. Tüm ihtimaller dikkate alındığında oyun tahtası üzerinde oluşabilecek durum sayısının 1216 olması ve oyundaki stokastik yapı dikkate alındığında oyunun zorluk derecesi görülmektedir. Literatürde 2048 oyunu üzerine uygulama içeren çalışmalar iki farklı yaklaşım altında değerlendirilmektedir. Bunlar öğrenme tabanlı yöntemler ve arama tabanlı yöntemlerdir. Bu çalışmada bu iki yöntem için en temel algoritmalar belirlendi. Arama tabanlı yöntemler olarak Derin Öncelikli Arama (Depth First Search - DFS) ve Monte Carlo Ağaç Arama (Monte Carlo Tree Search - MCTS) seçilirken, öğrenme tabanlı yöntem olarak Q-Öğrenme (Q-Learning) kullanıldı. Ayrıca algoritmalar budama ve rulet tekerliği gibi farklı teknikler ile uygulandı. Algoritmaların analizleri yapılırken skor ve maksimum karo metrikleri dikkate alındı. Skor metriği dikkate alındığında en başarılı algoritma DFS olurken, maksimum karo dikkate alındığında en başarılı yöntemin MCTS algoritması olduğu tespit edildi.
Keywords
2048 oyunu pekiştirmeli öğrenme derin öncelikli arama Monte Carlo ağaç arama algoritma analizi
References
- Boris, T., & Goran, S. (2017). Evolving neural network to play game 2048. 24th Telecommunications Forum, TELFOR 2016. Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/TELFOR.2016.7818911
- Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., … Colton, S. (2012, March). A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 4, pp. 1–43. https://doi.org/10.1109/TCIAIG.2012.2186810
- Campbell, M., Hoane, A. J., & Hsu, F.-H. (2002). Deep Blue. In Artificial Intelligence (Vol. 134).
- Cirulli G. (2014). The Creator of the 2048 Game . https://github.com/gabrielecirulli/2048 improving reinforcement learning performance. (n.d.).
- Jacobsen, E. J., Greve, R., & Togelius, J. (2014). Monte mario: Platforming with MCTS. GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference, 293–300. Association for Computing Machinery. https://doi.org/10.1145/2576768.2598392
- Jaśkowski, W. (2018). Mastering 2048 with delayed temporal coherence learning, multistage weight promotion, redundant encoding, and carousel shaping. IEEE Transactions on Games, 10(1), 3–14. https://doi.org/10.1109/TCIAIG.2017.2651887
- Kondo, N., & Matsuzaki, K. (2019). Playing game 2048 with deep convolutional neural networks trained by supervised learning. Journal of Information Processing, 27, 340–347. https://doi.org/10.2197/ipsjjip.27.340
- Levine, S., Kumar, A., Tucker, G., & Fu, J. (2020). Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems. Retrieved from http://arxiv.org/abs/2005.01643
- Lipowski, A., & Lipowska, D. (2011). Roulette-wheel selection via stochastic acceptance. https://doi.org/10.1016/j.physa.2011.12.004
- Matsuzaki, K. (2017). Systematic selection of N-tuple networks with consideration of interinfluence for game 2048. TAAI 2016 - 2016 Conference on Technologies and Applications of Artificial Intelligence, Proceedings, 186–193. Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/TAAI.2016.7880154
- Mehta, R. (2014). 2048 is (PSPACE) Hard, but Sometimes Easy. Retrieved from http://arxiv.org/abs/1408.6315 Newborn, M. (2000). Deep Blue’s contribution to AI. In Annals of Mathematics and Artificial Intelligence (Vol. 28).
- Nie, Y., Hou, W., & An, Y. (n.d.). AI Plays 2048.
- Rodgers, P., & Levine, J. (n.d.). An Investigation into 2048 AI Strategies. Retrieved from http://www.veewo.com/games/
- Sauren K, Jansen N, and Strüber D. (2022). Improving Reinforcement Learning Performance in 2048 Using Expert Knowledge.
- Siau, K., & Wang, W. (2018). Building Trust in Artificial Intelligence, Machine Learning, and Robotics Supply Chain Management View project. Retrieved from www.cutter.com
- Tong, S. (n.d.). Roulette Wheel Selection Game Player. Retrieved from https://digitalcommons.macalester.edu/mathcs_honors/30
- Wang, F. Y., Zhang, J. J., Zheng, X., Wang, X., Yuan, Y., Dai, X., … Yang, L. (2016). Where does AlphaGo go: From church-turing thesis to AlphaGo thesis and beyond. IEEE/CAA Journal of Automatica Sinica, 3(2), 113–120. https://doi.org/10.1109/JAS.2016.7471613
- Weikai, W., & Kiminori, M. (n.d.). Improving DNN-based 2048 Players with Global Embedding. Retrieved from https://github.com/wwk1397/Improving-DNN-
- Yeh, Kun Hao, I. Chen Wu, Chu Hsuan Hsueh, Chia Chuan Chang, Chao Chin Liang, and Han Chiang. (2017). “Multistage Temporal Difference Learning for 2048-like Games.” IEEE Transactions on Computational Intelligence and AI in Games 9(4):369–80. doi: 10.1109/TCIAIG.2016.2593710.
- Yu, Haofeng. (2016). From Deep Blue to DeepMind: What AlphaGo Tells Us.
Details
| Primary Language | Turkish |
|---|---|
| Subjects | Computer Software |
| Journal Section | Computer Engineering |
| Authors | |
| Publication Date | March 15, 2023 |
| Submission Date | September 13, 2022 |
| Published in Issue | Year 2023 |