Efficiency of parallel minimax algorithm for game tree search
Plаmеnkа Borovskа, Milena Kirilova Lazarova · 2007
The paper investigates the efficiency of parallel minimax algorithms for search in a game tree. The game used as a case study is a tic-tac-toe. The suggested parallel computational model exploits tree partitioning at width for each level of the game tree and is based on combination of the parallel algorithmic paradigms "manager-workers" and "asynchronous iterations". Performance comparison has been made for hybrid (multilevel,) flat and multithreaded parallel programming models. Speedup and efficiency as well as scalability in respect to the size of the multicomputer and its impact on the performance of the parallel system have been estimated on the basis of experimental results. The communication/computation ratio (CCR) of the parallel hybrid and flat implementations of the minimax algorithm has been estimated.