Skip to main content
Top

2015 | OriginalPaper | Chapter

Parameter-Free Tree Style Pipeline in Asynchronous Parallel Game-Tree Search

Authors : Shu Yokoyama, Tomoyuki Kaneko, Tetsuro Tanaka

Published in: Advances in Computer Games

Publisher: Springer International Publishing

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

search-config
loading …

Abstract

Asynchronous parallel game-tree search methods are effective in improving the playing strength by using many computers connected through relatively slow networks. In game-position parallelization, the master program manages a game-tree and distributes positions in the tree to workers. Then, each worker asynchronously searches the best move and the corresponding evaluation for its assigned position. We present a new method for constructing an appropriate master tree that provides more important moves with more workers on their sub-trees to improve the playing strength. Our contribution introduces two advantages: (1) being parameter free in that users do not need to tune parameters through trial and error, and (2) efficiency suitable even for short-time matches, such as one second per move. We implemented our method in chess with a top-level chess program Stockfish and evaluated the playing strength through self-plays. We confirm that the playing strength improves with up to sixty workers.

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!

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!

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!

Footnotes
5
By the definition of the greedy algorithm, we have \(p_{v^*} \ge p_v\) for any \(v \in T' \setminus T\). In the special case that \(p_{v^*} = p_v\) for all \(v \in T' \setminus T\), utility \(U(T')\) equals U(T) by the definition of \(v^*\), and this contradicts the assumption that \(U(T') > U(T)\).
 
9
The opponent was configured not to use this additional time in pondering.
 
Literature
1.
go back to reference Brockington, M.: Asynchronous Parallel Game-Tree Search. Ph.D. thesis, University of Alberta (1998) Brockington, M.: Asynchronous Parallel Game-Tree Search. Ph.D. thesis, University of Alberta (1998)
2.
go back to reference Campbell, M., Hoane Jr., A.J., Hsu, F.H.: Deep blue. Artif. Intell. 134(1–2), 57–83 (2002)CrossRefMATH Campbell, M., Hoane Jr., A.J., Hsu, F.H.: Deep blue. Artif. Intell. 134(1–2), 57–83 (2002)CrossRefMATH
3.
go back to reference Donninger, C., Kure, A., Lorenz, U.: Parallel brutus: the first distributed, FPGA accelerated chess program. In: Proceedings of the 18th International Symposium on Parallel and Distributed Processing, 2004, p. 44, April 2004 Donninger, C., Kure, A., Lorenz, U.: Parallel brutus: the first distributed, FPGA accelerated chess program. In: Proceedings of the 18th International Symposium on Parallel and Distributed Processing, 2004, p. 44, April 2004
4.
go back to reference Donninger, C., Lorenz, U.: The chess monster hydra. In: Becker, J., Platzner, M., Vernalde, S. (eds.) FPL 2004. LNCS, vol. 3203, pp. 927–932. Springer, Heidelberg (2004) CrossRef Donninger, C., Lorenz, U.: The chess monster hydra. In: Becker, J., Platzner, M., Vernalde, S. (eds.) FPL 2004. LNCS, vol. 3203, pp. 927–932. Springer, Heidelberg (2004) CrossRef
5.
go back to reference Feldmann, R.: Game Tree Search on Massively Parallel Systems. Ph.D. thesis, University of Paderborn (1993) Feldmann, R.: Game Tree Search on Massively Parallel Systems. Ph.D. thesis, University of Paderborn (1993)
6.
go back to reference Heinz, E.A.: New self-play results in computer chess. In: Marsland, T., Frank, I. (eds.) CG 2001. LNCS, vol. 2063, pp. 262–276. Springer, Heidelberg (2002) CrossRef Heinz, E.A.: New self-play results in computer chess. In: Marsland, T., Frank, I. (eds.) CG 2001. LNCS, vol. 2063, pp. 262–276. Springer, Heidelberg (2002) CrossRef
7.
go back to reference Himstedt, K.: An optimistic pondering approach for asynchronous distributed game-tree search. ICGA J. 28(2), 77–90 (2005) Himstedt, K.: An optimistic pondering approach for asynchronous distributed game-tree search. ICGA J. 28(2), 77–90 (2005)
8.
go back to reference Himstedt, K.: Gridchess: combining optimistic pondering with the young brothers wait concept. ICGA J. 35(2), 67–79 (2012)MathSciNetCrossRef Himstedt, K.: Gridchess: combining optimistic pondering with the young brothers wait concept. ICGA J. 35(2), 67–79 (2012)MathSciNetCrossRef
9.
go back to reference Himstedt, K., Lorenz, U., Möller, D.P.F.: A twofold distributed game-tree search approach using interconnected clusters. In: Luque, E., Margalef, T., Benítez, D. (eds.) Euro-Par 2008. LNCS, vol. 5168, pp. 587–598. Springer, Heidelberg (2008) CrossRef Himstedt, K., Lorenz, U., Möller, D.P.F.: A twofold distributed game-tree search approach using interconnected clusters. In: Luque, E., Margalef, T., Benítez, D. (eds.) Euro-Par 2008. LNCS, vol. 5168, pp. 587–598. Springer, Heidelberg (2008) CrossRef
10.
go back to reference Hoki, K., Kaneko, T., Yokoyama, D., Obata, T., Yamashita, H., Tsuruoka, Y., Ito, T.: Distributed-shogi-system Akara 2010 and its demonstration. Int. J. Comput. Inf. Sci. 14(2), 55–63 (2013) Hoki, K., Kaneko, T., Yokoyama, D., Obata, T., Yamashita, H., Tsuruoka, Y., Ito, T.: Distributed-shogi-system Akara 2010 and its demonstration. Int. J. Comput. Inf. Sci. 14(2), 55–63 (2013)
11.
go back to reference Kaneko, T., Tanaka, T.: Distributed game tree search and improvements – match between hiroyuki miura and GPSShogi. IPSJ Mag. 54(9), 914–922 (2013). (In Japanese) Kaneko, T., Tanaka, T.: Distributed game tree search and improvements – match between hiroyuki miura and GPSShogi. IPSJ Mag. 54(9), 914–922 (2013). (In Japanese)
12.
go back to reference Kishimoto, A.: Transposition table driven scheduling for two-player games. M.Sc. thesis, University of Alberta, January 2002 Kishimoto, A.: Transposition table driven scheduling for two-player games. M.Sc. thesis, University of Alberta, January 2002
14.
go back to reference Marsland, T.A., Popowich, F.: Parallel game-tree search. IEEE Trans. Pattern Anal. Mach. Intell. 7, 442–452 (1985)CrossRef Marsland, T.A., Popowich, F.: Parallel game-tree search. IEEE Trans. Pattern Anal. Mach. Intell. 7, 442–452 (1985)CrossRef
15.
go back to reference Obata, T., Sugiyama, T., Hoki, K., Ito, T.: Consultation algorithm for computer shogi: move decisions by majority. In: van den Herik, H.J., Iida, H., Plaat, A. (eds.) CG 2010. LNCS, vol. 6515, pp. 156–165. Springer, Heidelberg (2011) CrossRef Obata, T., Sugiyama, T., Hoki, K., Ito, T.: Consultation algorithm for computer shogi: move decisions by majority. In: van den Herik, H.J., Iida, H., Plaat, A. (eds.) CG 2010. LNCS, vol. 6515, pp. 156–165. Springer, Heidelberg (2011) CrossRef
16.
go back to reference Tanaka, T., Kaneko, T.: Massively parallel execution of shogi programs. In: The Special Interest Group Technical Reports of IPSJ. 2, vol. GI-24, pp. 1–8 (2010) (In Japanese) Tanaka, T., Kaneko, T.: Massively parallel execution of shogi programs. In: The Special Interest Group Technical Reports of IPSJ. 2, vol. GI-24, pp. 1–8 (2010) (In Japanese)
17.
go back to reference Tsuruoka, Y., Yokoyama, D., Chikayama, T.: Game-tree search algorithm based on realization probability. ICGA J. 25(3), 145–152 (2002) Tsuruoka, Y., Yokoyama, D., Chikayama, T.: Game-tree search algorithm based on realization probability. ICGA J. 25(3), 145–152 (2002)
18.
go back to reference Ura, A., Yokoyama, D., Chikayama, T.: Two-level task scheduling for parallel game tree search based on necessity. J. Inf. Process. 21(1), 17–25 (2013) Ura, A., Yokoyama, D., Chikayama, T.: Two-level task scheduling for parallel game tree search based on necessity. J. Inf. Process. 21(1), 17–25 (2013)
Metadata
Title
Parameter-Free Tree Style Pipeline in Asynchronous Parallel Game-Tree Search
Authors
Shu Yokoyama
Tomoyuki Kaneko
Tetsuro Tanaka
Copyright Year
2015
DOI
https://doi.org/10.1007/978-3-319-27992-3_19

Premium Partner