ネットワーク指標を用いたコンピュータHex戦略の開発

• Item type: Journal(1)
• 公開日: 2014-11-15
• タイトル: ネットワーク指標を用いたコンピュータHex戦略の開発
• タイトル / 言語: en
• タイトル: Development of Computer Hex Strategy Using Network Characteristics
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：ゲームプログラミング] Hex，ゲーム，ネットワーク，媒介中心性，最短経路長，局面評価関数
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 北海道大学情報科学研究科
• 著者所属: 北海道大学情報科学研究科
• 著者所属: 北海道大学情報科学研究科
• 著者所属: 北海道大学情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate Schoool of Information Science and Technology Hokkaido University
• 著者所属(英): en
• 著者所属(英): Graduate Schoool of Information Science and Technology Hokkaido University
• 著者所属(英): en
• 著者所属(英): Graduate Schoool of Information Science and Technology Hokkaido University
• 著者所属(英): en
• 著者所属(英): Graduate Schoool of Information Science and Technology Hokkaido University
• 著者名: 高田, 圭; 本庄, 将也; 飯塚, 博幸; 山本, 雅人
• 著者名(英): Kei, Takada; Masaya, Honjo; Hiroyuki, Iizuka; Masahito, Yamamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Hexは2人零和有限確定完全情報ゲームに分類されるボードゲームであり，先手必勝や引き分けがないことなどが知られている．交互に石を打つことでゲームは進行し，先に自色の対辺を自分の色の石で接続すれば勝利となる．コンピュータHexの国際大会が開かれており，コンピュータHexの研究がさかんに行われている．Hexの局面をネットワークで表現できることが知られており，局面ネットワークを電気回路として評価する方法が有名であるが，局面ネットワークをネットワーク特徴量を用いた評価も可能である．本研究では，局面を電気回路ととらえて評価するのではなく，ネットワークとしてとらえることで，複数の視点からの局面評価を目指す．Hex戦略と局面ネットワークの関係性を明らかにするために，熟練者同士の対戦の棋譜を使用した．棋譜を調査することで，有利なプレイヤの局面ネットワークには，平均最短経路長，平均媒介中心性と盤の両端間の経路長に特徴が現れることが分かった．そこで，平均媒介中心性と盤の両端間の最短経路を考慮した局面評価関数を提案し，その有効性を検証した．その結果，Hexの局面をネットワークとしてとらえることが，強いコンピュータHexの開発につながることを示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The game of Hex is the board game with simple rules and is classified as a two-player, zero-sum, logical perfect information game. The game proceeds by players putting their pieces in turn on empty cells of the board. A player wins if player connects the two opposing sides of the board of their own color their pieces. The study of computer Hex is popular enough that there is an international tournament of computer Hex. The electrical circuit model is a well-known method to evaluate boards in conventional studies. The present study investigates an evaluation method using network characteristics obtained from the board, in order to capture board states from different perspectives. To clarify the relation between the network characteristics and Hex strategies, game records by human experts were used. As a result, we found that the averages of shortest path lengths and betweenness centrality show a relationship in the winner's records. Therefore, we propose a novel evaluation function using these two network characteristics and evaluate its effectiveness. Our results shows that it is possible to develop a strong computer hex program using these network characteristics.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 55, 号 11, p. 2421-2430, 発行日 2014-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764