WEKO3
-
RootNode
アイテム
ゲームHexにおける必勝手順の検証プログラム
https://ipsj.ixsq.nii.ac.jp/records/9368
https://ipsj.ixsq.nii.ac.jp/records/936883ae1bde-85ed-47b2-a142-304d791fea73
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL4912019.pdf (333.6 kB)
|
Copyright (c) 2008 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2008-12-15 | |||||||
| タイトル | ||||||||
| タイトル | ゲームHexにおける必勝手順の検証プログラム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Testing Connectivity for Verifying 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 | ||||||||
| 著者所属(英) | ||||||||
| 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 | ||||||||
| 著者名 |
三島, 健
櫻井, 英俊
吉元, 昭裕
野下浩平
× 三島, 健 櫻井, 英俊 吉元, 昭裕 野下浩平
|
|||||||
| 著者名(英) |
Ken, Mishima
Hidetoshi, Sakurai
Akihiro, Yoshimoto
Kohei, Noshita
× Ken, Mishima Hidetoshi, Sakurai Akihiro, Yoshimoto Kohei, Noshita
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | ゲームHexでは，具体的な必勝手順を求めるために，様々な数学的技法が提案されている．8×8や9×9など大きい盤面に対する必勝手順を導くためには，これらの技法に基づいたシステムで人間とコンピュータの共同作業ができるものを実装する必要がある．本稿では，与えられた局面に対してユニオン連結性を判定するプログラムAとBを提示する．プログラムAは局面表を用いたAND-OR探索に基づくものであり，Hex特有の着手選択アルゴリズムにより強化した．プログラムBは，さらに仮想準連結などを組み込んで改良したものである．これらのプログラムは，実行時間と探索節点について評価する．ベンチマーク問題として，Noshitaによる7×7と8×8の必勝手順に現れる約40種類の難しい問題を選んだ．我々の実験結果によると，これらの局面の正しさは，非常に速く検証できた．このことは，我々のプログラムが実用に使えるということを意味する．着手選択（順序付けと先行排除）は，人間の熟練者と同程度に正確であると評価できる．本稿の実験結果をみると，我々のプログラムは，8×8以上の必勝手順の検証・発見のための対話システムを開発する際に最も基本的な道具として使えることが分かる． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In the game of Hex several mathematical techniques have been proposed for constructing explicit winning strategies. If we try to construct them for relatively large boards of 8×8, 9×9 or more, it is necessary to implement a system which enables human-computer cooperation based on those techniques. This paper presents two programs A and B for testing whether, for a given position, a desired union-connection can be attained. Program A is based on ANDOR searching with a transposition table, which is enhanced by Hex-dependent move-selection algorithms. Program B is further improved by incorporating, among others, virtual semi-connections. We evaluate the efficiency of those programs in terms of the running time as well as the number of searched nodes. For the set of benchmark problems, we have selected about forty hard positions from Noshita's winning strategies for 7×7 and 8×8. Our computing experiment shows that the correctness of those positions has been verified very quickly in that our programs can be used for practical purposes. The quality of the move-selection (ordering and preclusion) can be evaluated to be as accurate as human expert players. Our results show that our programs can be used as the most basic tool for building an interactive system to verify/find winning strategies for 8×8 or more. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN00116647 | |||||||
| 書誌情報 |
情報処理学会論文誌 巻 49, 号 12, p. 4007-4015, 発行日 2008-12-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7764 | |||||||
