{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:18:32Z","timestamp":1760145512895,"version":"build-2065373602"},"reference-count":40,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T00:00:00Z","timestamp":1722470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Amazons is a computerized board game with complex positions that are highly challenging for humans. In this paper, we propose an efficient optimization of the Monte Carlo tree search (MCTS) algorithm for Amazons, fusing the \u2018Move Groups\u2019 strategy and the \u2018Parallel Evaluation\u2019 optimization strategy (MG-PEO). Specifically, we explain the high efficiency of the Move Groups strategy by defining a new criterion: the winning convergence distance. We also highlight the strategy\u2019s potential issue of falling into a local optimum and propose that the Parallel Evaluation mechanism can compensate for this shortcoming. Moreover, We conducted rigorous performance analysis and experiments. Performance analysis results indicate that the MCTS algorithm with the Move Groups strategy can improve the playing ability of the Amazons game by 20\u201330 times compared to the traditional MCTS algorithm. The Parallel Evaluation optimization further enhances the playing ability of the Amazons game by 2\u20133 times. Experimental results show that the MCTS algorithm with the MG-PEO strategy achieves a 23% higher game-winning rate on average compared to the traditional MCTS algorithm. Additionally, the MG-PEO Amazons program proposed in this paper won first prize in the Amazons Competition at the 2023 China Collegiate Computer Games Championship &amp; National Computer Games Tournament.<\/jats:p>","DOI":"10.3390\/a17080334","type":"journal-article","created":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T08:14:46Z","timestamp":1722500086000},"page":"334","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Efficient Optimization of the Monte Carlo Tree Search Algorithm for Amazons"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-0324-9181","authenticated-orcid":false,"given":"Lijun","family":"Zhang","sequence":"first","affiliation":[{"name":"College of Computer Science and Technology, Jilin University, Changchun 130012, China"},{"name":"Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Han","family":"Zou","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Jilin University, Changchun 130012, China"},{"name":"Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yungang","family":"Zhu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Jilin University, Changchun 130012, China"},{"name":"Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,8,1]]},"reference":[{"key":"ref_1","first-page":"164","article-title":"Amazons search algorithm design based on CNN model","volume":"40","author":"Li","year":"2022","journal-title":"Digit. Technol. Appl."},{"key":"ref_2","first-page":"50","article-title":"Research on evaluation function computer game of Amazon","volume":"48","author":"Guo","year":"2012","journal-title":"Comput. Eng. Appl."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Guo, T., Qiu, H., Tong, B., and Wang, Y. (2019, January 3\u20135). Optimization and Comparison of Multiple Game Algorithms in Amazons. Proceedings of the 2019 Chinese Control And Decision Conference (CCDC), Nanchang, China.","DOI":"10.1109\/CCDC.2019.8833089"},{"key":"ref_4","unstructured":"Quan, J., Qiu, H., Wang, Y., Li, F., and Qiu, S. (2016, January 28\u201330). Application of UCT technologies for computer games of Amazon. Proceedings of the 2016 Chinese Control and Decision Conference (CCDC), Yinchuan, China."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Ju, J., Qiu, H., Wang, F., Wang, X., and Wang, Y. (2021, January 28\u201330). Research on Thread Optimization and Opening Library Based on Parallel PVS Algorithm in Amazons. Proceedings of the 2021 33rd Chinese Control and Decision Conference (CCDC), Kunming, China.","DOI":"10.1109\/CCDC52312.2021.9602204"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Li, Z., Ning, C., Cao, J., and Li, Z. (2021, January 28\u201330). Amazons Based on UCT-PVS Hybrid Algorithm. Proceedings of the 2021 33rd Chinese Control and Decision Conference (CCDC), Kunming, China.","DOI":"10.1109\/CCDC52312.2021.9602418"},{"key":"ref_7","unstructured":"Ding, M., Bo, J., Qi, Y., Fu, Y., and Li, S. (2019, January 3\u20135). Design of Amazons Game System Based on Reinforcement Learning. Proceedings of the 2019 Chinese Control And Decision Conference (CCDC), Nanchang, China."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Tong, B., Qiu, H., Guo, T., and Wang, Y. (2019, January 3\u20135). Research and Application of Parallel Computing of PVS Algorithm Based on Amazon Human-Machine Game. Proceedings of the 2019 Chinese Control And Decision Conference (CCDC), Nanchang, China.","DOI":"10.1109\/CCDC.2019.8832907"},{"key":"ref_9","first-page":"224","article-title":"Research on evaluation function in Amazons","volume":"15","author":"Chen","year":"2019","journal-title":"Comput. Knowl. Technol."},{"key":"ref_10","first-page":"78","article-title":"Interface design and implementation of personalized Amazons","volume":"7","author":"Wang","year":"2017","journal-title":"Intell. Comput. Appl."},{"key":"ref_11","unstructured":"Zhang, L. (2010). Research on Amazons Game System Based on Minimax Search Algorithm. [Master\u2019s Thesis, Northeast University]."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1080\/01621459.1949.10483310","article-title":"The Monte Carlo Method","volume":"44","author":"Metropolis","year":"1949","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Coulom, R. (2007, January 1\u20135). Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. Proceedings of the Computers and Games, Turin, Italy.","DOI":"10.1007\/978-3-540-75538-8_7"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1145\/2093548.2093574","article-title":"The grand challenge of computer Go: Monte Carlo tree search and extensions","volume":"55","author":"Gelly","year":"2012","journal-title":"Commun. ACM"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1856","DOI":"10.1016\/j.artint.2011.03.007","article-title":"Monte-Carlo tree search and rapid action value estimation in computer Go","volume":"175","author":"Gelly","year":"2011","journal-title":"Artif. Intell."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1038\/s41586-019-1724-z","article-title":"Grandmaster level in StarCraft II using multi-agent reinforcement learning","volume":"575","author":"Vinyals","year":"2019","journal-title":"Nature"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1038\/nature16961","article-title":"Mastering the game of Go with deep neural networks and tree search","volume":"529","author":"Silver","year":"2016","journal-title":"Nature"},{"key":"ref_18","unstructured":"Berner, C., Brockman, G., Chan, B., Cheung, V., D\u0119biak, P., Dennison, C., Farhi, D., Fischer, Q., Hashme, S., and Hesse, C. (2019). Dota 2 with Large Scale Deep Reinforcement Learning. arXiv."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TCIAIG.2012.2186810","article-title":"A Survey of Monte Carlo Tree Search Methods","volume":"4","author":"Browne","year":"2012","journal-title":"IEEE Trans. Comput. Intell. AI Games"},{"key":"ref_20","unstructured":"Kloetzer, J., Iida, H., and Bouzy, B. (2007, January 15\u201317). The Monte-Carlo Approach in Amazons. Proceedings of the Computer Games Workshop, Amsterdam, The Netherlands."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1080\/14786445008521796","article-title":"Programming a computer for playing chess","volume":"41","author":"Shannon","year":"1950","journal-title":"Lond. Edinb. Dublin Philos. Mag. J. Sci."},{"key":"ref_22","unstructured":"Chaslot, G., Bakkes, S., Szita, I., and Spronck, P. (2008, January 22\u201324). Monte-Carlo Tree Search: A New Framework for Game AI. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, California, CA, USA."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2497","DOI":"10.1007\/s10462-022-10228-y","article-title":"Monte Carlo Tree Search: A review of recent modifications and applications","volume":"56","author":"Godlewski","year":"2023","journal-title":"Artif. Intell. Rev."},{"key":"ref_24","unstructured":"Kloetzer, J. (2011). Monte-Carlo Opening Books for Amazons. Computers and Games: 7th International Conference (CG 2010), Kanazawa, Japan, September 24\u201326 2010, Revised Selected Papers 7, Springer."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1109\/TCIAIG.2014.2309077","article-title":"An Enhanced Solver for the Game of Amazons","volume":"7","author":"Song","year":"2014","journal-title":"IEEE Trans. Comput. Intell. AI Games"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Zhang, G., Chen, X., Chang, R., Zhang, Y., Wang, C., Bai, L., Wang, J., and Xu, C. (2021, January 18\u201322). Mastering the Game of Amazons Fast by Decoupling Network Learning. Proceedings of the 2021 International Joint Conference on Neural Networks (IJCNN), Shenzhen, China.","DOI":"10.1109\/IJCNN52387.2021.9534274"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"96","DOI":"10.3233\/ICG-2011-34212","article-title":"INVADER Prolongs Amazons Title","volume":"34","year":"2011","journal-title":"ICGA J."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"112","DOI":"10.3233\/ICG-2009-32216","article-title":"INVADER Wins Amazons Tournament","volume":"32","author":"Kloetzer","year":"2009","journal-title":"ICGA J."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"228","DOI":"10.3233\/ICG-170027","article-title":"Invader Wins Eighth Amazons Gold Medal","volume":"39","author":"Lorentz","year":"2017","journal-title":"ICGA J."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Guo, Q., Li, S., and Bao, H. (2011, January 23\u201325). The Research of Searching Algorithm in Amazons Game. Proceedings of the 2011 Chinese Control and Decision Conference (CCDC), Mianyang, China.","DOI":"10.1109\/CCDC.2011.5968503"},{"key":"ref_31","unstructured":"Li, X., Hou, L., and Wu, L. (June, January 31). UCT Algorithm in Amazons Human-Computer Games. Proceedings of the 26th Chinese Control and Decision Conference (CCDC), Changsha, China."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Quan, J., Qiu, H., Wang, Y., Li, Y., and Wang, X. (2015, January 23\u201325). Study the Performance of Search Algorithms in Amazons. Proceedings of the 27th Chinese Control and Decision Conference (CCDC), Qingdao, China.","DOI":"10.1109\/CCDC.2015.7161845"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/j.tcs.2005.09.048","article-title":"An Evaluation Function for the Game of Amazons","volume":"349","author":"Lieberum","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Chai, Z., Fang, Z., and Zhu, J. (2019, January 3\u20135). Amazons Evaluation Optimization Strategy Based on PSO Algorithm. Proceedings of the 2019 Chinese Control And Decision Conference (CCDC), Nanchang, China.","DOI":"10.1109\/CCDC.2019.8832447"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Sun, Y., Yuan, D., Gao, M., and Zhu, P. (2022, January 21\u201323). GPU Acceleration of Monte Carlo Tree Search Algorithm for Amazons and Its Evaluation Function. Proceedings of the 2022 International Conference on Artificial Intelligence, Information Processing and Cloud Computing (AIIPCC), Kunming, China.","DOI":"10.1109\/AIIPCC57291.2022.00098"},{"key":"ref_36","first-page":"1","article-title":"Improved Monte-Carlo Search","volume":"1","author":"Kocsis","year":"2006","journal-title":"Univ. Tartu Est. Tech. Rep."},{"key":"ref_37","first-page":"23","article-title":"Game-tree properties and MCTS performance","volume":"11","author":"Finnsson","year":"2011","journal-title":"IJCAI"},{"key":"ref_38","first-page":"164","article-title":"Intel\u00ae threading building blocks","volume":"23","author":"Pheatt","year":"2008","journal-title":"J. Comput. Sci. Coll."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Childs, B.E., Brodeur, J.H., and Kocsis, L. (2008, January 15\u201318). Transpositions and move groups in monte carlo tree search. Proceedings of the 2008 IEEE Symposium on Computational Intelligence and Games, Perth, Australia.","DOI":"10.1109\/CIG.2008.5035667"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Van Eyck, G., and M\u00fcller, M. (2012). Revisiting move groups in monte-carlo tree search. Advances in Computer Games: 13th International Conference, ACG 2011, Tilburg, The Netherlands, November 20\u201322, 2011, Revised Selected Papers 13, Springer.","DOI":"10.1007\/978-3-642-31866-5_2"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/8\/334\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:27:57Z","timestamp":1760110077000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/8\/334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,1]]},"references-count":40,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2024,8]]}},"alternative-id":["a17080334"],"URL":"https:\/\/doi.org\/10.3390\/a17080334","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,8,1]]}}}