WEKO3
-
RootNode
アイテム
Hex の必勝手順に対する新証明技法とその応用
https://ipsj.ixsq.nii.ac.jp/records/97635
https://ipsj.ixsq.nii.ac.jp/records/976358037b27c-d4a8-4480-8437-d3dd842f8656
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-GPWS2006019.pdf (261.6 kB)
|
Copyright (c) 2006 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Symposium(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2006-11-10 | |||||||
| タイトル | ||||||||
| タイトル | Hex の必勝手順に対する新証明技法とその応用 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | New Proof Techniques and Their Applications to Winning Strategies in Hex | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||
| 資源タイプ | conference paper | |||||||
| 著者所属 | ||||||||
| 電気通信大学情報工学専攻 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学情報工学専攻 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学情報工学専攻 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, The University of Electro-Communications | ||||||||
| 著者名 |
三島, 健
櫻井, 英俊
野下浩平
× 三島, 健 櫻井, 英俊 野下浩平
|
|||||||
| 著者名(英) |
Mishima, Ken
Sakurai, Hidetoshi
Noshita, Kohei
× Mishima, Ken Sakurai, Hidetoshi Noshita, Kohei
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | ゲームHexは、先手必勝手順の存在が証明されているが、具体的な必勝手順を示すことは長年の研究課題である。本稿では、石の連結性を定義するための新しい概念として、δ連結を提案し、それに基づいて、連結に関与する領域を拡張するための新しい技法δ拡張を導入する。この技法の応用として、従来の技法で記述するには複雑すぎるとされていた8×8盤面の初手63 に対する必勝手順を示す。また、この技法の強力さを示す例として、8×8盤面の初手54 に対する野下の必勝手順(2005)を大幅に簡単化する。同様にして、9×9 盤面に対する必勝手順を示すことができるが、本稿ではその証明木を示す（現在細部のチェック中）。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | 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. We present a new notion named δ-connection which defines a certain type of connections between stones. Based on it, we introduce a new technique named δ-extension for extending the area of empty cells which supports a desired union-connection. We apply our new techniques to show a winning strategy for the 8×8 board with the first move at 63, whose proof has been regarded as intractable by previous techniques. For demonstrating the power of our techniques, we show a winning strategy for 8×8 (first at 54) which is a considerable simplification of Noshita's one (2005). Finally we present a proof-tree of our winning strategy for 9×9 (first at 55), though the details of the proof are now being checked. | |||||||
| 書誌情報 |
ゲームプログラミングワークショップ2006論文集 巻 2006, p. 136-142, 発行日 2006-11-10 |
|||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
