Öz
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
Anahtar Kelimeler
2048 game reinforcement learning depth-first search Monte Carlo tree search algorithm analysis
Kaynakça
- 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.
Ö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
2048 oyunu pekiştirmeli öğrenme derin öncelikli arama Monte Carlo ağaç arama algoritma analizi
Kaynakça
- 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.
Ayrıntılar
| Birincil Dil | Türkçe |
|---|---|
| Konular | Bilgisayar Yazılımı |
| Bölüm | Bilgisayar Mühendisliği |
| Yazarlar | |
| Yayımlanma Tarihi | 15 Mart 2023 |
| Gönderilme Tarihi | 13 Eylül 2022 |
| Yayımlandığı Sayı | Yıl 2023 |