+ +
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つの空セル のいずれか）への着手に対し，他方のセルへの応手の評価値を上げることを意味する．
これらの評価項目の値を線形結合し，評価値によって着手の順序を決める．線形結 合の係数は計算実験により定める．
4.2.1 ゲームの一般的な必勝手順
一般的な二人プレイヤのゲームにおける（先手）必勝手順を示す証明木は，次のよ うな木のことである．
証明木の節点は局面を表す．先手局面を示す節点から出る枝は先手の着手を表す．後 手局面を示す節点から出る枝は後手の着手を表す．根は先手が初手を打った直後の後 手局面を表す．節点（局面）の子節点は，枝に対応した着手をすることによって得ら れる局面を表す．それぞれの節点が満たす条件を以下で示す．
• 先手（後手）局面を示す節点は，ただ一つの正しい着手を枝とする．
• 後手（先手）局面を示す節点は，盤面上の全ての空セルに対する着手を枝とする．
• 葉は，先手（後手）の勝利局面である．
Hexにおける先手（後手）の勝利局面とは，盤面の上辺と下辺（左辺と右辺）が黒 石（白石）で直接連結している局面を表す．
4.2.2 Hexにおける必勝手順
ゲームHexでは，上述の条件で証明木を記述した場合，特に盤面が大きくなると，節 点数が膨大になってしまう．証明木を簡略に記述するための様々な技法が過去の研究 において提案されている．Hexの必勝手順を求めた多くの論文では，必勝手順を簡潔 に記述するため，次のような工夫を行っている．
（1） 先行排除による後手着手の限定
（2） 盤面分割の方法に基づく着手のパターン化
（1）の先行排除による後手の着手の限定について，2.4節で説明しているが，ここで 改めて述べる．本来，後手局面における後手（白）の着手候補は空セルの数だけ存在 する．先行排除により悪い着手を排除することで，着手候補を絞ることができる．後 手局面を示す節点では，（先行排除を示す）解析盤面を付与することにより，証明木に おける枝刈りを行っている．
解析盤面とは以下のような盤面である．その後手局面（節点）から先手が余分に黒 を着手し，先手の勝利を示した盤面である．解析盤面では，（2）で述べているように，
（仮想連結やユニオン連結などの）盤面分割の技法を用いて，先手勝ちを示している．
盤面分割の方法を用いて，領域（空セルの集合）における石間の連結を保障すること で，その領域内における着手を省略する．これにより，両辺が直接連結していなくて も，先手の勝利を示すことができる．その際，領域外の空セルへの後手の着手が，先 行排除により着手候補から排除される．
K. Noshitaが示した7×7の盤面の必勝手順の木（図35）を例にして説明する．根
は，先手が黒を44のセルに着手した初期局面（後手局面）を表す．この局面では48個 の空セルのがあるため，着手候補も48手存在する．根で先行排除を行うと，48手中41 手が排除できる．着手候補からこの41個の着手候補は取り除かれ，図35で示すよう に，根には7個の子節点が残る．すなわち後手の着手候補が7手残る．
根には，図36と図37で示す解析図（先行排除）が付与されている．図36は，根の 局面に対し先手が54のセルに一手余分に着手することで，先手勝ちとなる局面を示す．
2つのST-lemmaにより，黒石と上辺，黒石と下辺が，それぞれ連結している．よって，
上辺と下辺が連結している．同様に，図36では，先手が34のセルに一手余分に着手 することで，2つのST-lemmaが成り立つ．よって，先手勝ちの局面である．図36と 図37の領域の積集合を取ると，図38のように，（対称性を考慮して）7個の着手候補が 残る．このように，その他の内部節点の後手局面でも先行排除により，後手の着手候 補を限定している．
葉の盤面では，実際には上辺と下辺が連結することが必ずしも明示的に書かれていな い10 ．しかしユニオン連結が成立する複数の領域に対する（通常は簡単な）論理計算に より，先手の勝利を示している．たとえば，根から白27黒55と着手した局面（図39）で は，S-lemmaとT-lemmaより，44−55∧55−bが成り立つ．よって，44−bが成り立つ．
また，U-lemma[16, 17]より，t−44∨t−bが成り立つ．よって，44−b∧(t−44∨t−b) が成り立つ．以上より，t−b が成り立つ．
44
27(a) 36(b) 47(c) 36
46(d)
55 26
37(e) 35(f) 45(g)
45
37(p) 27(q) 36(r) 43(s) 53(t) 52(u) 61(v) 51(w)
56 53 33 62
41(r) 42(s) 51(t) 52 61(p) 52(q)
33
43(u) 53
27(v) 25 35
53 53 33 33
55 36
33 52 52
図 35: K. Noshitaが参考文献[17]で示した7×7の必勝手順
10K. Noshitaの8×8の必勝手順[17, 18, 19]の葉では，（内部節点のおける解析と同様に）複数の解析 図（先行排除の図）を付与し，全ての着手候補を排除することで先手勝ちを示している．参考文献[17]
によると，7×7の必勝手順（図35）は，より詳しい解析を行うことにより，総節点数5個の証明木で 記述できる．
* * * *
* * *
* * *
- - -- -
-- - -
-1 1
2
2
3
3
4
4
5
5
6
6
7
7
図 36: 根局面の先行排除1[17]
* * * *
* * *
* * *
- - -- -
-- - -
-1 1
2
2
3
3
4
4
5
5
6
6
7
7
図 37: 根局面の先行排除2[17]
f g b d
a e c
1 1
2
2
3
3
4
4
5
5
6
6
7
7
図 38: 根局面の解析結果（Figure 10[17]）
- - - - -
-- - - -
-- - -
-- - +
- - + *
- - * * *
- * * * *
1 1
2
2
3
3
4
4
5
5
6
6
7
7
図 39: Figure 11[17]
4.2.3 必勝手順の検証方法
本論文のプログラムを用いた必勝手順の検証方法は次のとおりである．内部節点の 後手局面では，先行排除により後手の着手を限定している．そこで，先行排除の正し さを検証する．排除された着手の集合によって定まる（一般には）複数の盤面それぞ れにおいて，後手から着手をはじめて先手勝ちを示す．
葉の節点は後手局面である．この局面では，盤面分割などを用いて先手必勝である ことを示している．そこで，まずプログラムを用い，部分盤面内で目標の連結が成立 することを確認する．次に部分盤面同士の連結を人手で統合して，その葉が先手必勝 であることを示す．