Evaluating function and min-max search

チェスではカードゲームなどとは異なり、各プレイヤーは次の手を考える上で完全情報 (perfect information)を持っている。 すると、各盤面に対して、次のいずれかがいえる [von Neumann and Morgenstern, 1944]

1. 白が勝ちの盤面であれば、白は黒がどのような手を打とうとも必ず勝つことができる。
2. 引き分けの盤面であれば、白は黒がどのような手を打とうとも少なくとも引き分けることができるし、黒も白がどのような手を打とうとも少なくとも引き分けることができる。しかし、両者が最善手を打ち続ければゲームは引き分けに終わる。
3. 黒が勝ちの盤面であれば、黒は白がどのような手を打とうとも必ず勝つことができる。

そこで、評価関数（evaluating function / evaluation function） f(P) を白が勝ちのとき f(P) = +1、引き分けのとき f(P) = 0、負けのとき f(P) = -1とすると、各盤面 P から次の盤面 P' の評価関数 f(P') が最大となる手を打ち続ければいい。

もっともこれは存在定理のようなもので、実際にチェスの各盤面が与えられたときに、それが上記の3つのどれに属しているかを判定する手法は知られていない。 masterのゲームが引き分けで終わることが多いことからチェスの初期盤面は引き分けではないかとはいわれている。 しかし、それを確認するためには初期盤面からのすべての手を確認する必要がある（後にαβ探索の発明ですべては必要ないことがわかったが）。 チェスの各盤面に対する有効な1 move（白、黒と順に動かした場合を1 moveという。将棋のように片側だけの手を数えるときは1 plyという）はおよそ10³通りある。 典型的なチェスのゲームは40手程度であることから初期状態から終盤まで読み切るには10¹²⁰程度の盤面を評価する必要がある。 1つの盤面を評価するのに1μsとしても計算を終えるには10⁹⁰年かかることになる（と原著でなってますが10¹⁰⁵年かな？まあ人の寿命が10²なので誰も答えを知りえないという意味では同じ）。

一方で、盤面の種類数で考えると 64! / 32!(8!)²(2!)⁶ = 10⁴³ 程度であるが、これも計算可能な数字ではない。 （チェスとは違い、チェッカーが最近解かれたが、チェッカーは10¹⁵程度の盤面数で、それでも解くのに18年かかっている。）

そこで、完全ではないが評価関数の近似を求めることを考える。 評価関数は白黒それぞれの駒に対するスコアと各駒のレイアウトに応じて計算される。 Shannonは次のような項（いまでいうfeature）を提案している。

1. クイーン、ルーク、ビショップ、ナイト、ポーンそれぞれのスコアを9, 5, 3, 3, 1とする。
2. ポーンの陣形
   1. 後ろにいたり、孤立していたり、重なっているポーンは弱い。
   2. センター e4, d4, c4 にいる。
   3. キングのそばのポーンの弱さ。
   4. ビショップと異なる色のマスにいるポーン。
   5. passしたポーン。
3. 駒の位置
   1. 進んだナイト e5, d5, c5, f5, e6, d6, c6, f6 で特にポーンに守られており、敵のポーンに攻められていない。
   2. ルークの前が開いている (open file / semi-open file)。
   3. 7列目のルーク。
   4. 重なったルーク。
4. コミットメント、攻撃など
   1. 守りに必要な駒。
   2. 攻撃している駒。
   3. pin
5. 晒されているキングは弱い。
6. movability （有効な手の数）

Shannonは、この評価関数は中盤で用いられ、序盤と終盤は異なった原則を用いるべきであるといい。また、これらの項の重みは実験に基づいて決められるべきと今で言うところのmachine learningの必要性を示唆している。

重みを決めるのが難しいので、最初の駒得の部分しか実装してないが、プログラムは次のようになる。

そして、この評価関数を用いてminmax探索を行うことを述べている。 minmax探索については以前にもScalaで書いたので詳しいことは省略するが、C++で書くと次のようになる

チェックメイトの判定のあたり、スコアとして帰ってくる値を使って、もうちょっとスマートにできないかなとは思うのだけど。

minmaxはすべての枝を探索するので、max_depthを1つ上げるごとに30倍程度の時間がかかる。 Shannonの論文では3 moves (max_depth = 6) で、10⁹盤面の評価をしなくてはいけなくて、1つあたり1μsとすると16分程度かかると書かれているが、実際に計算してみると1つの盤面評価に13μs程度かかり、盤面数は3×10⁸で70分かかった。 1 game終わらせるのに徹夜でも2日強は最低かかりそう。

論文ではさらに静止探索 (quiescent search）や前向き枝刈り（forward pruning）のアイデアも書かれている。 それらについては、またの機会に実装することにするが、Shannonの先見の明に驚くばかり。