nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

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

verfasst von : Saatvik Saradhi Inampudi

Erschienen in: Advanced Computing

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Adaptive Coronavirus Mask Protection Algorithm Enabled Deep Learning for Brain Tumor Detection and Classification

Nächstes Kapitel 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

Titel: Enhancing Hex Strategy: AI Based Two-Distance Pruning Approach with Pattern-Enhanced Alpha-Beta Search
verfasst von: Saatvik Saradhi Inampudi
Verlag: Springer Nature Switzerland
Buch: Advanced Computing
Print ISBN: 978-3-031-56699-8

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner