不完全情報ゲームにおける並列処理

• Item type: SIG Technical Reports(1)
• 公開日: 2003-08-04
• タイトル: 不完全情報ゲームにおける並列処理
• タイトル / 言語: en
• タイトル: Parallel processing of incomplete information game
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工科大学
• 著者所属: 東京工科大学
• 著者所属(英): en
• 著者所属(英): Tokyo University of Technology
• 著者所属(英): en
• 著者所属(英): Tokyo University of Technology
• 著者名: 小田和友仁; 上原, 貴夫
• 著者名(英): Tomohito, Otawa; Takao, Uehara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 不完全情報ゲームであるブリッジでは，相手の手札を推測し想定したまざまな場合（ワールド）においてゲーム木探索をおこなうために時間がかかる．そこで，各ワールドを1台のコンピュータに割りつけ，複数のコンピュータで並列に処理する方法を提案する．ひとつのワールドでは完全情報ゲームとしてのゲーム木探索ができ，そのワールドは1台のコンピュータ内にあるので，αβ法やトランスポジションテーブルといった高速化の手法が有効に適用できる．しかし，探索の深度を一定としたαβ法を適用すると，カットオフの適用率によりワールドごとの処理時間にばらつきが生じ，遅いコンピュータを待つ時間が増加する．本研究では反復深化法を適用し，一定時間で探索を打ち切ることによりこの問題を解決した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11362144
• 書誌情報: 情報処理学会研究報告ゲーム情報学（GI）; 巻 2003, 号 79(2003-GI-010), p. 23-30, 発行日 2003-08-04
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会