2048 OYUNU İÇİN FARKLI ALGORİTMALARIN PERFORMANS ANALİZİ

Sabri Aylık; Hüseyin Haklı

doi:10.17780/ksujes.1174413

EN TR

PERFORMANCE ANALYSIS OF VARIOUS ALGORITHMS FOR THE 2048 GAME

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 OYUNU İÇİN FARKLI ALGORİTMALARIN PERFORMANS ANALİZİ

Öz

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.

Anahtar Kelimeler

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

Research Article

Authors

Sabri Aylık ^*
0000-0001-9204-6927
Türkiye

Hüseyin Haklı
0000-0001-5019-071X
Türkiye

Publication Date

March 15, 2023

Submission Date

September 13, 2022

Acceptance Date

November 30, 2022

Published in Issue

Year 2023 Volume: 26 Number: 1

DOI

https://doi.org/10.17780/ksujes.1174413

IZ

https://izlik.org/JA33SY77HL

Cite

RIS / Bibtex

APA

Aylık, S., & Haklı, H. (2023). 2048 OYUNU İÇİN FARKLI ALGORİTMALARIN PERFORMANS ANALİZİ. Kahramanmaraş Sütçü İmam Üniversitesi Mühendislik Bilimleri Dergisi, 26(1), 67-77. https://doi.org/10.17780/ksujes.1174413