Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Reducing Keepalive Traffic in Software-Defined Mobile Networks with Port Control Protocol Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Comparative Study of Monte-Carlo Tree Search and Alpha-Beta Pruning in Amazons

Authors : Hikari Kato, Szilárd Zsolt Fazekas, Mayumi Takaya, Akihiro Yamamura

Published in: Information and Communication Technology

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

The game of Amazons is a combinatorial game sharing some properties of both chess and Go. We study programs which play Amazons with strategies based on Monte-Carlo Tree Search and a classical search algorithm, Alpha-Beta pruning. We execute several experiments to investigate the effect of increasing the number of searches in a Monte-Carlo Tree Search program. We show that increasing the number of searches is not an efficient method to strengthen the program for Amazons. On the other hand, augmenting the algorithms with a choice of several evaluation functions fulfills has great influence on playing strength.

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 Fitness Function in ABC Algorithm for Uncapacitated Facility Location Problem
next chapter Can We Securely Use CBC Mode in TLS1.0?
Literature
1.
Allis, L.V.: Searching for Solutions in games and Artificial Intelligence. Ph.D. thesis, Maastricht, Rrijksuniversiteit Limburg (1995)
2.
Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-time analysis of the multiarmed bandit problem. Mach. Learning 47(2–3), 235–256 (2002)CrossRefMATH
3.
Avetisyan, H., Lorentz, R.J.: Selective search in an Amazons program. In: Schaeffer, J., Müller, M., Björnsson, Y. (eds.) CG 2002. LNCS, vol. 2883, pp. 123–141. Springer, Heidelberg (2003) CrossRef
4.
Berlekamp, E.R.: Sums of \(N \times 2\) Amazons. Institute of Mathematical Statistics Lecture Notes - Monograph Series, vol. 35 (2000)
5.
Buro, M.: Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs. In: Marsland, T., Frank, I. (eds.) CG 2001. LNCS, vol. 2063, pp. 250–261. Springer, Heidelberg (2002) CrossRef
6.
Coulom, R.: Efficient selectivity and backup operators in Monte-Carlo tree search. In: van den Herik, H.J., Ciancarini, P., Donkers, H.H.L.M.J. (eds.) CG 2006. LNCS, vol. 4630, pp. 72–83. Springer, Heidelberg (2007) CrossRef
7.
Coulom, R.: Computing Elo ratings of move patterns in the game of Go. ICGA J. 30, 198–208 (2007)
8.
Gelly, S., Wang, Y., Munos, R., Teytaud, O.: Modification of UCT with patterns in Monte-Carlo Go. Technical Report PR-6062, INRIA (2006)
9.
Hensgens, P.: A Knowledge-based Approach of the Game of Amazons. Master’s thesis, Maastricht University (2001)
10.
Hoki, K., Muramatsu, M.: Efficiency of three forward-pruning techniques in Shogi: futility pruning, null-move pruning, and late move reduction (LMR). Entertainment Comput. 3, 51–57 (2012)CrossRef
11.
Kaneko, T.: Evaluation functions of computer Shogi programs and supervised learning using game records. J. Jpn. Soc. Artif. Intell. 27, 75–82 (2012)
12.
Kloetzer, J., Iida, H., Bouzy, B.: The Monte-Carlo approach in Amazons. In: Computer Games Workshop, pp. 185–192, Amsterdam, The Netherlands (2007)
13.
Kloetzer, J., Iida, H., Bouzy, B.: A comparative study of solvers in Amazons endgames. In: IEEE 2008 Symposium on Computational Intelligence in Games, Perth, Australia (2008)
14.
Kloetzer, J., Iida, H., Bouzy, B.: Playing Amazons endgames. ICGA J. 32, 140–148 (2009)CrossRef
15.
Kloetzer, J.: Experiments in Monte-Carlo Amazons. IPSJ SIG Technical Report, vol. 2010-GI-24 No. 6, pp. 1–4 (2010)
16.
Kloetzer, J.: Monte-Carlo opening books for Amazons. In: 7th Conference on Computer and Games (2010)
17.
18.
19.
Kocsis, L., Szepesvári, C.: Bandit based Monte Carlo planning. In: 17th European Conference on Machine Learning (ECML 2006), pp. 282–293 (2006)
20.
Kozelek, T.: Methods of MCTS and the game Arimaa. Master’s thesis, Charles University in Prague (2009)
21.
22.
Matsubara, H., Iida, H., Grimbergen, R.: Chess, Shogi, Go, natural developments in game research. ICCA J. 19, 103–112 (1996)
23.
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995) CrossRefMATH
24.
Metadata
Title
Comparative Study of Monte-Carlo Tree Search and Alpha-Beta Pruning in Amazons
Authors
Hikari Kato
Szilárd Zsolt Fazekas
Mayumi Takaya
Akihiro Yamamura
Copyright Year
2015
Book
Information and Communication Technology

Print ISBN: 978-3-319-24314-6

Electronic ISBN: 978-3-319-24315-3

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-24315-3_14

Premium Partner

    Image Credits