a Japanese computer scientist affiliated with the Graduate School of Arts and Sciences, University of Tokyo. His research interests include game playing algorithms and search, and in particular massively parallel or distributed search algoritms. At the Advances in Computer Games 14 conference in Leiden 2015, he introduced the distributed search algorithm dubbed P-GPP, or pipelined game position parallelization.
Along with Tomoyuki Kaneko and Tetsuro Tanaka , Shu Yokoyama worked on pipelined game position parallelization (P-GPP), applied to Shogi inside GPS Shogi, and to Chess using Stockfish DD. GPP conducts a minimax search by integrating the results obtained locally by workers assigned to leaf nodes of a master tree. The root of a master tree corresponds to the current game position, and the number of nodes of the master tree must be the number of workers available. Neither transposition table nor windows are shared. P-GPP both extends optimistic pondering , and game position parallelization by improving worker management. In P-GPP, positions are assigned to workers automatically by a greedy algorithm on the basis of realization probabilities, acquired from game records and a playing program. The realization probability of a node, defined as the product of the transition probability of each move, is the probability that the corresponding sequence of moves is actually played. By definition, the realization probability of the root is one. After making a move during the course of the game, all workers formerly assigned to siblings of the made move were reassigned to new leaves of the growing new root, deepening and widening the search tree.
Stockfish DD was adopted as a worker program, adding a function of reporting information extending the UCI protocol. Each worker and the master are connected via standard TCP sockets. The master is implemented in C++ with the boost/asio library. For a worker, a utility program Netcat is adopted as a proxy connecting standard streams and a TCP socket. To simulate a distributed environment, they used at most 64 cores in two computers each of which is equipped with two Intel Xeon E5-4650 processors. Stockfish ran as a sequential program using a single thread. Each worker was allowed to use 32MiB for its transposition table . Shu Yokoyama et al confirmed improved playing strength with up to sixty Stockfish workers .
- Shu Yokoyama lecturing on Parameter-Free Tree Style Pipeline in Asynchronous Parallel Game-Tree Search/ at Advances in Computer Games 14, Shu Yokoyama — slides. Video Download, July 03, 2015, capture at 2:55
- Tetsuro Tanaka, Tomoyuki Kaneko (2010). Massively Parallel Execution of Shogi Programs. The Special Interest Group Technical Reports of IPSJ. 2, Vol. GI-24, No.8 (Japanese)
- Kai Himstedt (2012). GridChess: Combining Optimistic Pondering with the Young Brothers Wait Concept. ICGA Journal, Vol. 35, No. 2
- Shu Yokoyama, Tomoyuki Kaneko, Tetsuro Tanaka (2015). Parameter-Free Tree Style Pipeline in Asynchronous Parallel Game-Tree Search. Advances in Computer Games 14, pdf