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.
T. Kaneko—A part of this work was supported by JSPS KAKENHI Grant Number 25330432.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
http://www.glaurungchess.com/lmr.html (Last access: February 2015).
- 2.
https://www.cis.uab.edu/hyatt/search.html (Last access: February 2015).
- 3.
http://www.shredderchess.com/chess-info/features/uci-universal-chess-interface.html (Last access: February 2015).
- 4.
http://www.glaurungchess.com/shogi/usi.html (Last access: February 2015).
- 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)\).
- 6.
- 7.
Version 1.4w29 http://www.geenvis.net/polyglot1.4w29.zip.
- 8.
- 9.
The opponent was configured not to use this additional time in pondering.
References
Brockington, M.: Asynchronous Parallel Game-Tree Search. Ph.D. thesis, University of Alberta (1998)
Campbell, M., Hoane Jr., A.J., Hsu, F.H.: Deep blue. Artif. Intell. 134(1–2), 57–83 (2002)
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., 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)
Feldmann, R.: Game Tree Search on Massively Parallel Systems. Ph.D. thesis, University of Paderborn (1993)
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)
Himstedt, K.: An optimistic pondering approach for asynchronous distributed game-tree search. ICGA J. 28(2), 77–90 (2005)
Himstedt, K.: Gridchess: combining optimistic pondering with the young brothers wait concept. ICGA J. 35(2), 67–79 (2012)
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)
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)
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)
Kishimoto, A.: Transposition table driven scheduling for two-player games. M.Sc. thesis, University of Alberta, January 2002
Knuth, D.E., Moore, R.W.: An analysis of alpha-beta pruning. Artif. Intell. 6(4), 293–326 (1975)
Marsland, T.A., Popowich, F.: Parallel game-tree search. IEEE Trans. Pattern Anal. Mach. Intell. 7, 442–452 (1985)
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)
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)
Tsuruoka, Y., Yokoyama, D., Chikayama, T.: Game-tree search algorithm based on realization probability. ICGA J. 25(3), 145–152 (2002)
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)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Yokoyama, S., Kaneko, T., Tanaka, T. (2015). Parameter-Free Tree Style Pipeline in Asynchronous Parallel Game-Tree Search. In: Plaat, A., van den Herik, J., Kosters, W. (eds) Advances in Computer Games. ACG 2015. Lecture Notes in Computer Science(), vol 9525. Springer, Cham. https://doi.org/10.1007/978-3-319-27992-3_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-27992-3_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-27991-6
Online ISBN: 978-3-319-27992-3
eBook Packages: Computer ScienceComputer Science (R0)