Hexの必勝手順に対する新証明技法について

• Item type: Journal(1)
• 公開日: 2009-02-15
• タイトル: Hexの必勝手順に対する新証明技法について
• タイトル / 言語: en
• タイトル: New Techniques for Proving Winning Strategies in Hex
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 一般論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: ゲーム
• 著者所属: 電気通信大学大学院電気通信学研究科情報工学専攻
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, The University of Electro-Communications
• 著者名: 三島, 健
• 著者名(英): Ken, Mishima
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ゲームHexは，先手必勝手順の存在が証明されているが，具体的な必勝手順を示すことは長年の研究課題である．盤面の大きさが8×8以上になると，必勝手順を簡潔な形で扱うことは複雑すぎるとされてきた．本稿では，石の連結性を定義するための新しい概念として，σ 連結を提案し，それに基づくσ 拡張の技法を導入する．本稿の目的は，σ 連結とσ 拡張によって，新しい先手勝ちの証明法を確立し，必勝手順の構成に応用することである．本稿では，Noshitaのユニオン連結を一般化する．これにより，連結の論理和だけでなく，論理積を扱えるようにする．この一般化した連結をAND-OR連結と呼ぶ．σ 連結は，着手が指定がされたAND-OR連結であり，AND-OR連結の手順を示す証明木の部分木で定義される．σ 拡張は，σ 連結の着手指定に基づいて，AND-OR連結に関与する領域を拡張する技法である．これらの技法を用いることで，深い探索をしなくても，勝利手順を示すことができる．σ 連結とσ 拡張を必勝手順の構成に応用すると，8×8の必勝手順を簡単に検証可能な形で記述することができる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In the game of Hex, it has been proved existentially that the first player always wins. Constructing a winning strategy has been a long-standing research problem. It has been regarded as complex to deal with a winning strategy for 8×8 or more. We present a new notion named σ-<i>connection</i> which defines a certain type of connections between stones. Based on it, we introduce a new technique named σ-<i>extension</i>. The purpose of this paper is to establish a new method for proving the first player's win and applying it to construct a winning strategy. In this paper, we generalize Noshita's union (OR)-connection for accommodating AND-connections as well. This generalized connection will be called AND-OR connection. A σ-connection is an AND-OR connection along with fixed move-sequences. It is defined to be a subtree of a proof tree which represents a strategy for the AND-OR connection. Based on the fixed movesequences, we can extend the area of empty cells which supports the desired AND-OR connection. This technique will be called σ-extension. These techniques enable us to show a winning way without searching further down in our proof tree. Thanks to our σ-connection as well as σ-extension, it is possible to describe an easy-to-verify winning strategy on the 8×8 board.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 50, 号 2, p. 893-903, 発行日 2009-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764