Top

Published in:

2024 | OriginalPaper | Chapter

Enhancing Hex Strategy: AI Based Two-Distance Pruning Approach with Pattern-Enhanced Alpha-Beta Search

Author : Saatvik Saradhi Inampudi

Published in: Advanced Computing

Publisher: Springer Nature Switzerland

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper introduces an effective algorithm designed for creating AI systems for the Hex board strategy game. The core algorithm, developed, employs the two-distance method for both board evaluation and for sorting of the moves. For empty board positions, the sum of two-distances from both ends is calculated to indicate the position’s weight and is used for sorting. Additionally, the Pattern Search algorithm enhances efficiency by prioritizing moves in crucial regions. The algorithm demonstrated consistent performance across various board sizes, including 7 × 7, 9 × 9, and 11 × 11. When implemented as an Android game, this algorithm maintained excellent performance in the given board sizes.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Adaptive Coronavirus Mask Protection Algorithm Enabled Deep Learning for Brain Tumor Detection and Classification

next chapter IRBM: Incremental Restricted Boltzmann Machines for Concept Drift Detection and Adaption in Evolving Data Streams

All figures in this manuscript are from the “Simple Hex Board game with AI”. Link: https://play.google.com/store/apps/details?id=com.SamgoGames.SimpleHex. The game can be installed and played on android based mobile devices with OS 7.0 and above.

Hayward, R.B., Toft, B.: HEX the full story. CRC Recreational Mathematics Series (2019)

Pierce, J.R.: Symbols, Signals and Noise. Harper and Brothers, pp. 10–13 (1961)

Chao, G., Hayward, R., Müller, M.: Move prediction using deep convolutional neural networks in Hex. IEEE Trans. Games 10(4), 336–343 (2017)

Rijswijck, J.V.: Set colouring games. PhD Thesis, Department of Computing Science, University of Alberta, Canada (2006)

Beck, A., Bleicher, M.N., Crowe, D.W.: Excursions into Mathematics, pp. 317–387. Chapter Games, New York (1969)

Yang, J., Liao, S., Pawlak, M.: New winning and losing positions for 7×7 Hex. In: Schaeffer, J., Müller, M., Björnsson, Y. (eds.) Computers and Games (CG 2002). LNCS, vol. 2883, pp. 230–248. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-40031-8_16

Rijswijck, J.V.: Computer Hex: are bees better than fruitflies? Thesis of Master of Science, p. 37, Department of Computing Science, University of Alberta, Canada (2000)

Young, K., Hayward, R.B.: A reverse Hex solver. In: Plaat, A., Kosters, W., van den Herik, J. (eds.) Computers and Games (CG 2016), LNCS, vol. 10068, pp. 137–148. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-50935-8_13

Fabiano, N., Hayward, R.: New Hex patterns for fill and prune. In: Cazenave, T., van den Herik, J., Saffidine, A., Wu, I.C. (eds.) Advances in Computer Games (ACG 2019). LNCS, vol. 12516, pp. 79–90. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-65883-0_7

10.

Broderick, A., Hayward, R.B., Philip, H.: Monte Carlo tree search in Hex. IEEE Trans. Comput. Intel. AI Games 2(4), 251–258 (2010)CrossRef

11.

Huang, S.C., Arneson, B., Hayward, R.B., Müller, M., Pawlewicz, J.: MOHEX 2.0: a pattern-based MCTS Hex player. In: International Conference on Computers and Games, Computers and Games (CG 2013), pp. 60–71 (2013)

12.

Young, K., Vasan, G., Hayward, R.: NeuroHex: a deep q-learning Hex agent. In: Workshop on Computer Games, International Workshop on General Intelligence in Game Playing Agents (CGW 2016, GIGA 2016), Computer Games (2016)

13.

Anshelevich, V.V.: A hierarchical approach to computer Hex. Artif. Intell. 134(1–2), 101–120 (2002). https://doi.org/10.1016/S0004-3702(01)00154-0CrossRef

14.

Chao, G., Siqi, Y., Hayward, R., Müller, M.: A transferable neural network for Hex. ICGA J. 40(3), 224–233 (2018)

15.

Woodcok, M., Uscategui, F., Corrales, D.: Basic analysis of Hex game. Econógrafos, Escuela de Economía 13417, Universidad Nacional de Colombia, FCE, CID (2015)

16.

Liu, H., Du, X.: Strategy and implementation of Hex. In: Proceedings of the 2020 4th International Conference on Electronic Information Technology and Computer Engineering (EITCE 2020), pp. 800–805 (2020)

17.

Yang, J., Simon, L., Mirek, P.: A new solution for a 7×7 Hex game (2002)

18.

Rasmussen, R.: Algorithmic approaches for playing and solving Shannon games. PhD Dissertation, Faculty of Information Technology, Queensland University of Technology, pp. 24–26, 49–52, 108–111 (2007)

19.

David, S., et al.: A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science 362, 1140–1144 (2018). https://doi.org/10.1126/science.aar6404MathSciNetCrossRef

Title: Enhancing Hex Strategy: AI Based Two-Distance Pruning Approach with Pattern-Enhanced Alpha-Beta Search
Author: Saatvik Saradhi Inampudi
Publisher: Springer Nature Switzerland
Book: Advanced Computing
Print ISBN: 978-3-031-56699-8

Electronic ISBN: 978-3-031-56700-1

Copyright Year: 2024
DOI: https://doi.org/10.1007/978-3-031-56700-1_36

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner