は，前述したように，13個である（後手節点は7個）．
このように，σ連結とσ拡張を従来の証明法と併用することで，従来より簡単な形 で必勝手順を構築できる．
58 47
57 47
47 45
38 46 54 64
64 54 46 56
46 56 64 54
61 72
7152 73
53 73
48 37 7152 73
54 64
46 36 45 35
37 55 56 27 36 73 46+ 26 35 25
54 64 61 72
47 76
56 55 46 27 43 35
72 35
47 74 66+ 37 46 36
45 35 43 33 34 15 24 14
71 73
5261 43 37 66
48 37
56 27 35+ 45
45 35
42+ 35
53 45
71 73
5254 34 35 16 25 15
41 45 24 14
36 34 35 16 25 15 24 14
43 35 36 26 54 33
26 36 54 53
54 53 36 26 44 33
44 64 36 26 37+ 33
37+ 36
53 54 56 46
57 47
38 27
48 46
45 55
47 45
46 56
63
図 29: 8×8（初手63）の証明木（参考文献[27]の証明木を改訂）
55 71 82(i)
62 43(f)62(b) 4948 47(b.a) {38,29} 67(b.a.a, b.b.a, b.b.b.a){38, 29} (b.b, b.c.a) 4849 68 (b.b.b) 58
52 63(a)
51 58 48
62 43 (d.d.b.b)53
576381
54 64 58 47 384863 73 (d.c)
56 46 (b.c) 47 37 (b.c.b)
29 58 48(d.d.b.a)
56 46 47 37
29 67
63(c) 6748
5361 72(e) 58 48 (e.f)
48 47(e.g) {38,29} 67 57 75
{38, 29} 47(e.h, e.i.a) 4849 68 58
56 46(e.i) 2947 37 (e.i.b)
4657 47 (e.a)
56 (e.b)
39 28 (e.c) 38 (e.d)
4959 47 (e.e)
64 54(h) 57 47(j.a) {43, 51,61} 42 (j.a.(a1 ~a3))
42 62 (j.a.b)
58 48(j.b) {43, 51,61} 42 (j.b.(a1~ a3))
42 62 (j.b.b)
42(j.(c1~ c3))
42 62(j.d) 57 47 (j.(c1~ c3).a)
58 48 (j.(c1~ c3).b) 48 (j.d.b)
5758
46 56 (f.b)
57 47 (f.a)
37 47 (f.c) 54 28 (f.c.a)
58 48 (f.d) 54 64 (f.d.a)
54 58 48 (f.e.a)
81 35 (f.e.b) {72,63} 82 73 83 74 84
81 63 53 91 82 92 83 93 84 9472 71 (f.c.a.a.b) (f.c.a.a.b.b)(f.c.a.a.a) (f.c.a.a.b.a) (f.c.a.a.b.b.a)
43(k) 46 56 (k.b)
57 47 (k.a)
37 47 54 28 64 (k.c.a.a) 6353 63 {71, 62} 91
{71, 62} 63 53 (k.c.a.a.b, k.c.a.a.c)
54 64 (k.e)
58 48(k.d) 58 48 (k.e.a)
{71,62, 53,63} 35(k.e.b)
54(k.f) 47 49 68 67 57 75(k.f.a.a.a) 65 83(k.f.a.a.a.a)48 {38, 29}
56 46 47 37 38 48 49 68
(b.d) 47
(c.c) (c.b) (c.a) (c.c.a)
(d.a) (d.b) (d.d.a)
(d) 35(d.d.b)(d.d) {38, 29}
54 64 (k.d.a)
81 (k.c) 29 39 58
4748
47 (j.d.a) 64(f.c.a.a)
64 (f.e)
{43, 51, 61}
72 53(j) {34,44,35, 45,26,36, 27} (e.g.a, e.h.a, e.h.b.a)
(e.h.b) (e.g.a.a)
(k.c.a) {34,44,35, 45,26,36, 27}
64 38 4749
(k.f.d) (k.f.d.b) (k.f.d .b.a) (k.f.d .b.a.a) (k.f.d .b.a.a.a)
(k.f.a) (k.f.a.a, k.f.b.a, k.f.b.b.a, k.f.d.b.a.a.a.a)
(k.f.c) (k.f.b.b, k.f.c.a)
(k.f.b, k.f.d.a)
図 30: 9×9（初手55）の証明木（参考文献[27]の証明木を改訂）
4 必勝手順の検証プログラム
本章では，人間とコンピュータの共同作業により，必勝手順を導いていくという方 針に基づき，盤面のユニオン連結性を検証するプログラムを提示する．さらに，これ らを用いて，実際に必勝手順の検証を行い，プログラムの性能評価を行う．
本章で提示するプログラムAとプログラムBは，先行研究の先行排除，仮想連結，
仮想準連結などもふくめて，様々な高速化の工夫を取り入れて実現したものである．本 章では，これらのプログラムを用いて，（計算量的な観点から）難しいとされる盤面の 連結性の検証を行った．ベンチマーク問題として，K. Noshitaの7×7の必勝手順全体 の検証を行った．さらに，8×8の必勝手順において，特に検証が難しいとされる部分 盤面におけるユニオン連結性の正しさを確かめた．7×7と8×8の盤面において，プ ログラムAとプログラムB共に連結性を証明するために充分実用的な早さで検証を終 えている．今後さらに大きな盤面（8×8以上）に対して，人手とコンピュータによる 必勝手順の発見・検証が可能であることを示せたといえる．特に，8×8以上における 必勝手順に対し，実用的な実行時間で検証できることを示したことは，本章の大きな 貢献であるといえる．
本章の構成について述べる．まず，4.1節で，本論文で提示する2つの検証プログラ ム，プログラムAとプログラムBの詳細を説明する．次に，4.2節で，Hexにおける必 勝手順を説明し，その検証方法について述べる．プログラムAとプログラムBの性能 評価実験として，4.3節で，必勝手順の検証を行う．本章の総括を4.4節で行う．
4.1 プログラム A とプログラム B
第4章では，2つのプログラムを使用している．それぞれをプログラムA，プログラ ムBと呼ぶ．
プログラムAとプログラムBは，入力として与えられた部分盤面においてユニオン 連結が成立しているか否かを判定する．ユニオン連結は複数の連結の候補を持つ可能 性があるため，連結目標が複数設定できる．また，連結目標を任意の石や辺に設定す ることができる．
4.1.1 仮想連結パターンの利用
プログラムAとプログラムBでは基本的な仮想連結をあらかじめデータとして登録 しておく．目標の連結の成立を判定する際，石が直接接続しているかどうかだけでは なく，仮想連結を用いての接続の判定を行う．
図31，図32，図33はいずれも色のついた領域を用い，黒石と上辺が連結する仮想 連結である．プログラムAとプログラムBでは，S-lemmaとT-lemmaに加え，これ らの仮想連結（計5種類）の連結パターンを使用している．平行移動，線対称を考慮 すると，7×7では，図31，図32，図33の形の仮想連結は，それぞれ6個，4個，14 個のパターンがある．8×8では，それぞれ8個，8個，18個のパターンがある．後手 も同数である．なお，計算時間との兼ね合いを考慮して，これらより大きいパターン は利用していない．
1 1
2
2
3
3
4
4
5
5
図 31: 仮想連結1[10]
1 1
2
2
3
3
4
4
5
5
6
6
7
7
図 32: 仮想連結2[10]
1 1
2
2
3
3
4
4
図 33: 仮想連結3（ST-lemma[17]）
4.1.2 仮想準連結の利用
プログラムBはプログラムAと比べて，いくつかの能率向上の工夫を組み込んでい るが，特に重要なものは仮想準連結の利用である[1, 2]．石の群Xと，石の群Yがある とする．この時，XとYをつなぐ仮想準連結が2つ以上あり，それらの領域が重複し ない場合，XとYが連結していると判定する（2.1節参照）．
具体例を示す．図34は後手局面である（‘ + ’で示す領域上では2つのS-lemmaが成 り立つ）．この盤面では，領域aと領域bの2つの仮想準連結が成立している．この後，
後手が領域aに着手を行うと，先手は領域bに着手を行う．また，後手が領域bに着 手を行うと，先手は領域aに着手を行う．どちらの場合も先手の勝利となる．よって，
上辺と下辺は連結していると判定できる．2.1節の（i）と（ii）を用いることで，この ことを導ける．
+ +
b
a a + +
a 1
1 2
2
3
3
4
4
5
5
6
6
7
7
図 34: 仮想準連結を用いた連結判定
4.1.3 探索法
探索はAND-OR探索によって行う．ユニオン連結が成立するなら1，不成立なら0
を返す．着手候補を評価関数によって評価し，評価値の高い手から順に着手する．着 手候補は空セルに打つ全ての手に対し，先行排除による着手の限定を行ったものであ る．プログラムAでは，先行排除に仮想連結の連結パターンを使用する．プログラム Bでは，先行排除に仮想連結の連結パターンと仮想準連結を利用する．
4.1.4 評価関数
着手の順序付けを決める評価関数を説明する．着手の評価項目は次の5個である．
1. 着手の座標に対する静的および動的な評価．
2. 目標の連結を達成した着手の記憶による評価（キラーリスト技法の変形である）．
3. 2手連続着手して連結を達成できるか否かの評価．
4. S-lemmaの切断を守る着手の評価．
5. ランダムウォークによる着手の評価（たとえば深度5のランダムウォークを200 回行い連結の達成回数を勘定する）．
2, 3, 5では，連結を達成出来るか否かの判定に仮想連結のパターンを利用している
（プログラムBでは仮想準連結も併用している）．4は，S-lemmaの領域（2つの空セル のいずれか）への着手に対し，他方のセルへの応手の評価値を上げることを意味する．
これらの評価項目の値を線形結合し，評価値によって着手の順序を決める．線形結 合の係数は計算実験により定める．