不完全情報ゲームにおける並列処理  [in Japanese] Parallel processing of incomplete information game  [in Japanese]

不完全情報ゲームであるブリッジでは,相手の手札を推測し想定したさまざまな場合(ワールド)においてゲーム木探索をおこなうために時間がかかる.そこで,各ワールドを1台のコンピュータに割りつけ,複数のコンピュータで並列に処理する方法を提案する.ひとつのワールドでは完全情報ゲームとしてのゲーム木探索ができ,そのワールドは1台のコンピュータ内にあるので,αβ法やトランスポジションテーブルといった高速化の手法が有効に適用できる.しかし,探索の深度を一定としたαβ法を適用すると,カットオフの適用率によりワールドごとの処理時間にばらつきが生じ,遅いコンピュータを待つ時間が増加する.本研究では反復深化法を適用し,一定時間で探索を打ち切ることによりこの問題を解決した.

The game tree search is a time consuming task in case of Bridge because Bridge is an imperfect information game and searches must be performed in various worlds generated by guessing opponents' hands. We propose a parallel processing method assigning each world to a computer. Since game tree search can be carried out as a perfect information game in a world and the world is in a computer, the speed up technique, such as alpha-beta algorithm and a transposition table, is effectively applied. When the alpha-beta algorithm with a^given depth is applied to search in each world, the processing time of each computer depends on the rate of cutoff, and the waiting time of computers increases. We solve this problem by applying the iterative deepening method within a limited time.