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:
Adaptive Playouts in Monte-Carlo Tree Search with Policy-Gradient Reinforcement Learning Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Feature Strength and Parallelization of Sibling Conspiracy Number Search

Authors : Jakub Pawlewicz, Ryan B. Hayward

Published in: Advances in Computer Games

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Recently we introduced Sibling Conspiracy Number Search — an algorithm based not on evaluation of leaf states of the search tree but, for each node, on relative evaluation scores of all children of that node — and implemented an SCNS Hex bot. Here we show the strength of SCNS features: most critical is to initialize leaves via a multi-step process. Also, we show a simple parallel version of SCNS: it scales well for 2 threads but less efficiently for 4 or 8 threads.

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 Reducing the Seesaw Effect with Deep Proof-Number Search
next chapter Parameter-Free Tree Style Pipeline in Asynchronous Parallel Game-Tree Search
Footnotes
1
Hex has a good local heuristic. Shannon built an analogue circuit to play the connection game Bridg-it, with moves scored by voltage drop [7]. Adding links between virtual connected cells [2] improves the heuristic, which is reliable among siblings [9].
 
2
This is the current likely range of the final root minimax value. It is analogous to the aspiration window of \(\alpha \beta \) search.
 
3
Another approach is to dynamically partition the CNS tree and evaluate subproblems in parallel. Lorenz achieved this for the restriction of CNS to 2 conpirators, i.e., effectively bounding proof function numbers at 2 [14].
 
Literature
1.
Allis, L.V.: Searching for Solutions in Games and Artificial Intelligence. PhD thesis, University of Limburg, Maastricht, The Netherlands (1994)
2.
Anshelevich, V.V.: A hierarchical approach to computer Hex. Artif. Intell. 134(1–2), 101–120 (2002)CrossRefMATH
3.
4.
Breuker, D.M.: Memory versus Search in Games. PhD thesis, Maastricht University, Maastricht, The Netherlands (1998)
5.
6.
Coulom, R.: CLOP: confident local optimization for noisy black-box parameter tuning. In: van den Herik, H.J., Plaat, A. (eds.) ACG 2011. LNCS, vol. 7168, pp. 146–157. Springer, Heidelberg (2012) CrossRef
7.
Gardner, M.: The 2nd scientific american book of mathematical puzzles and diversions, Chap. 7, pp. 78–88. Simon and Schuster, New York (1961)
8.
Gelly, S., Silver, D.: Combining online and offline knowledge in UCT. In: 24th ACM ICML, pp. 273–280 (2007)
9.
10.
Huang, S.-C., Arneson, B., Hayward, R.B., Müller, M., Pawlewicz, J.: MoHex 2.0: a pattern-based MCTS Hex player. In: van den Herik, H.J., Iida, H., Plaat, A. (eds.) CG 2013. LNCS, vol. 8427, pp. 60–71. Springer, Heidelberg (2014)
11.
Iida, H., Sakuta, M., Rollason, J.: Computer shogi. Artif. Intell. 134(1–2), 121–144 (2002)CrossRefMATH
12.
Kishimoto, A., Winands, M., Müller, M., Saito, J.-T.: Game-tree searching with proof numbers: the first twenty years. ICGA J. 35(3), 131–156 (2012)CrossRef
13.
Klingbeil, N., Schaeffer, J.: Empirical results with conspiracy numbers. Comput. Intell. 6, 1–11 (1990)CrossRef
14.
Lorenz, U.: Parallel controlled conspiracy number search. In: Monien, B., Feldmann, R.L. (eds.) Euro-Par 2002. LNCS, vol. 2400, pp. 420–430. Springer, Heidelberg (2002) CrossRef
15.
Lorenz, U., Rottmann, V., Feldman, R., Mysliwietz, P.: Controlled conspiracy number search. ICCA J. 18(3), 135–147 (1995)
16.
17.
McAllester, D., Yuret, D.: Alpha-beta conspiracy search. ICGA 25(1), 16–35 (2002)
18.
Nagai, A.: Df-pn Algorithm for Searching AND/OR Trees and Its Applications. Ph.d. thesis, Department of Information Science, University Tokyo, Tokyo, Japan (2002)
19.
Pawlewicz, J., Hayward, R.: Sibling conspiracy number search. manuscript (2015)
20.
Pawlewicz, J., Hayward, R.B.: Scalable parallel DFPN search. In: van den Herik, H.J., Iida, H., Plaat, A. (eds.) CG 2013. LNCS, vol. 8427, pp. 138–150. Springer, Heidelberg (2014)
21.
Pawlewicz, J., Lew, Ł.: Improving depth-first PN-search: 1 + \(\epsilon \) trick. In: van den Herik, H.J., Ciancarini, P., Donkers, H.H.L.M.J. (eds.) CG 2006. LNCS, vol. 4630, pp. 160–171. Springer, Heidelberg (2007) CrossRef
22.
Saito, J.-T., Chaslot, G.M.J.-B., Uiterwijk, J.W.H.M., van den Herik, H.J.: Monte-Carlo proof-number search for computer Go. In: van den Herik, H.J., Ciancarini, P., Donkers, H.H.L.M.J. (eds.) CG 2006. LNCS, vol. 4630, pp. 50–61. Springer, Heidelberg (2007) CrossRef
23.
24.
van der Meulen, M.: Parallel conspiracy-number search. Master’s thesis, Vrije Universiteit Amsterdam, The Netherlands (1988)
25.
Winands, M.: Informed Search in Complex Games. PhD thesis, Universiteit Maastricht, Maastricht, The Netherlands (2004)
26.
Winands, M.H.M., Schadd, M.P.D.: Evaluation-function based proof-number search. In: van den Herik, H.J., Iida, H., Plaat, A. (eds.) CG 2010. LNCS, vol. 6515, pp. 23–35. Springer, Heidelberg (2011) CrossRef
Metadata
Title
Feature Strength and Parallelization of Sibling Conspiracy Number Search
Authors
Jakub Pawlewicz
Ryan B. Hayward
Copyright Year
2015
Book
Advances in Computer Games

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

Electronic ISBN: 978-3-319-27992-3

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-27992-3_18

Premium Partner

    Image Credits