5 結論
本論文では，ゲームHexにおける必勝手順の構成法に関して，2つの大きな成果を 得た．第一に，盤面の必勝を導くための新証明技法の提案した．それらを必勝手順の 証明に応用することで，従来の方法より簡潔な形で必勝手順を構成することができた．
第二に，人間とコンピュータで必勝手順を導いていくためのものとして，必勝手順に おけるユニオン連結性を検証するプログラムを作成した．本論文のプログラムを用い ると，8×8以上の必勝手順の正しさを充分に高速に検証することができた．
本論文では，重複する領域における盤面分割を扱うものとして，σ連結の概念を定 義し，それに基づくσ拡張の技法を導入した．まず最初に，AND-OR連結を定義し，
領域（空セルの集合）における連結の論理和・論理積を扱えるようにした．σ連結は，
AND-OR連結における領域内の着手手順を表す木の形で定義される．σ拡張は，その
領域の外部の特定のセルに着手することで，より大きい領域におけるAND-OR連結 を得る技法である．σ拡張でAND-OR連結が成り立つことは，σ連結の着手指定に基 づき，簡単な場合分けを行うことで証明できる．実際の応用では，σ拡張ができるよ うに，σ連結に基づき領域内の後手の着手に対して先手の応手を定める．これにより，
AND-OR連結の内部着手を考慮せずに探索が可能になり，繰り返しの記述と場合分け
が不要になる．こうして，簡潔な形で必勝の証明を行うことができるようになった．
本論文の新証明技法の応用として，σ連結とσ拡張を証明木の解析（先行排除）に 導入し，8×8（初手54）の先手必勝手順を簡潔な形で示した．ほとんどの後手の着手 は，深い探索なしで必勝を示すことができた．本論文の必勝手順を示す証明木におい て，着手を示す節点の総数は13個である．そのうち，後手節点は7個で，先手節点は 6個である．必勝手順の構成のために，必要なσ連結は，特に重要なものが4個であ り，バリエーションを含めて6個である．それぞれのσ連結に対し，1個ずつのσ拡張 を使用するため，σ拡張の総数は6個である．この必勝手順の証明を完全な形で書き 下すために必要な図面の枚数は99個である．図面の内訳は以下の通りである．主要な
AND-OR連結，σ連結，σ拡張の正しさを証明するための図面が34個である．残りの
65個は，証明木の（7個の）後手節点に付与された先行排除を示す図面である．その うち，8個は，σ連結とσ拡張を用いた先行排除を示す．このように，本論文の証明技 法を応用することで，従来の方法より簡潔な形で必勝を示すことが可能になった16 ． 本論文では，次に，人間とコンピュータの共同作業によって，大きな盤面における必 勝手順を導いていくために，与えられた盤面のユニオン連結性を判定するプログラム を作成し，評価実験を行った．プログラムAとプログラムBのアルゴリズムは，ハッ シュ表を用いたAND-OR探索に基づくものであり，Hex特有の技法を導入することで 強化を行っている．着手の順序付けは，Hexに依存する多くの評価項目を線形結合し た評価関数を用いている．各々の探索節点では，先行排除の方法に基づき局面の枝刈
16本論文の証明技法を局面に適用すると，8×8（初手63）や9×9（初手55）の先手必勝手順を完全 な形で記述することができる．著者は，（8×8（初手54）の必勝手順も含め）3つの必勝手順の完全な 証明をweb上（http://np.cs.uec.ac.jp/∼mishim-k/hex.html）で公開している．
りを行った．着手の順序付けの評価と先行排除では，仮想連結によるパターン照合を 利用することにより効率化を図っている．プログラムBは，プログラムAに加え，い くつかの能率向上の工夫を取り入れている．その中で特に重要な改良点は，着手の順 序付けと先行排除のために，仮想準連結を導入したことである．
本論文では，プログラムAの性能評価実験として，K. Noshitaの7×7の必勝手順
[16, 17]の検証を行った．この必勝手順中の20個の葉を含む23個の局面に対し，そこ
で現れるユニオン連結の正しさを検証した．実験の結果，ほとんどのユニオン連結は 1秒程度で検証が終了し，時間がかかったものでも十数秒で検証ができた．必勝手順全 体の正しさは，1分以下で検証することができた．
プログラムAとプログラムBの性能比較のために，K. Noshitaの8×8の必勝手順
[17, 18, 19] で現れるユニオン連結のうち，（特に計算量という観点から）難しいと思わ
れるものを入力として与え，検証を行った．プログラムAとプログラムB共に，ほと んどのユニオン連結は数分以内で検証できた．プログラムBの方が，プログラムAに 比べて，概ね短い実行時間で検証を終えた．最も差が出たものでは，約200倍の差が あった．この局面は，プログラムAでは連結の判定に十数時間かかったが，プログラ ムBでは5分程度で連結の判定ができた．
これらの結果より，両プログラム共に計算時間という点について，必勝手順の発見・
検証を行う上で，充分に実用的に使用できると考えられる．特に，8×8以上の盤面に 対し，短い実行時間で局面の連結性を検証できたことは大きな成果である．さらに，着 手生成の良さに関して，着手の順序付けと先行排除共に，人間の熟練者と同じ程度に正 確に行っている．今後8×8以上の大きな盤面に対し，人間とコンピュータの共同作業 により，必勝手順を導いていけることを具体的な実験データをもって示せたといえる．
今後の展望について述べる．本論文では，簡潔に必勝を証明するための証明技法を 提案したが，さらに大きな盤面における必勝手順を構築するためには，より効率的に 必勝手順を導くための証明技法の開発が望まれる．それだけでなく，（第4章で連結性 の判定を行うプログラムを作成し検証を行ったように）提案された新証明技法に基づ く必勝手順の正しさをコンピュータで検証するなどの人間とコンピュータの共同作業 が重要である．たとえば，著者は，高木[26]との共同研究において，本論文のσ連結 とσ拡張に基づく8×8（初手54）の必勝手順をコンピュータで検証した．その結果，
短い実行時間で図28の必勝手順全体の正しさを検証できた．今後，強力な証明技法が 考案され，それらにより必勝が示された局面をコンピュータで検証していくといった 方針により，さらに大きな盤面に対する必勝手順が求められていくことが期待される．
謝 辞
本論文をまとめるにあたり，多くの方々のご指導とご協力を賜わりました．この場 を借りて厚く御礼を申し上げさせていただきます．
最初に，本論文を審査していただき，ご指導を賜りました論文審査委員の岩田茂樹 教授，中山泰一准教授，笠井琢美教授，小林聡教授，そして，野下浩平名誉教授に，深 く感謝を致します．
野下浩平先生には，学部時代から博士後期課程2年次にかけて主任指導教員を引き 受けて下さいました．在学中には，論文の執筆に関する有益なアドバイス，技術的な 指導も含め，研究者としての在り方など，様々な側面に渡ってご指導をしていただき ました．そして，何よりも研究の楽しさを教えていただきました．私が現在に至るま で，ゲームの研究に携わってこれたのも，研究生活を有意義なものに昇華できたのも，
野下先生のおかげです．長年に渡りお世話になっていて，感謝の気持ちを伝えるには 言葉が足りませんが，それでも僭越ながらここで感謝の意を表させていただきます．
岩田茂樹先生には，博士後期課程の主任指導教官，それに論文審査委員の主査を引 き受けていただきました．学位審査に関する書類手続きなどの管理，論文をまとめる にあたって適切な助言，プレゼンテーションの添削作業など，多岐に渡りご指導をし て下さいました．学位論文をまとめることができたのも，岩田先生が根気強くご指導 をして下さったからです．心から感謝を致します．
中山泰一先生に感謝を致します．中山先生には，学部から博士後期課程に至るまで 指導教員を引き受けて下さいました．学位論文を書くにあたってスケジューリング管 理を含め，論文審査に関して非常に有益な助言をいただきました．研究の方針につい て行き詰っている際には，研究者の先輩としての立場から適切なアドバイスをいただ き今後の指針を示していただきました．
笠井琢美先生に感謝を致します．学位論文の作成とプレゼンテーションについて，非 常に有益なアドバイスをいただきました．笠井先生の御助言のおかげで，論文をより 良く仕上げることができました．
小林聡先生に感謝を致します．予備審査時のプレゼンテーションでは，貴重な御助 言を下さいました．以降のプレゼンテーションで参考にさせていただきました．
柳井啓司先生は，計算機管理に不慣れな私達にかわって，快適な計算機環境の維持 に努めて下さいました．研究室が別れて以後も，長らくお世話になりました．深く感 謝を致します．
鈴木貢先生に感謝を致します．日頃の雑談も含めて，しばしば相談に乗っていただ きました．特に，学位を習得するにあたり有益なアドバイスをしていただきました．
野下研究室の皆様に感謝を致します．特に，櫻井英俊君，高木慎也君，山岸友哉君，
吉元昭裕君に感謝致します．櫻井英俊君には，共同研究者として日頃から議論を交わ すだけでなく，実験等における様々な雑事を手伝っていきただきました．また，公私 において様々な相談に乗っていただきました．高木慎也君には，共同研究者として協