「評価関数の精度」再考
この連休中において、評価関数を10倍速にすることに成功したから複数コア動員で置換表の助け無しに50万NPSぐらい逝ける気がする目処がたった
それはそうと、今日は、2chの某スレで煽ったり罵ったり怒鳴り合ったりしてるうちに気づいたことなどを書く
こいつは今やってる方法がうまく行かなかったときの保険にしよう
（前説）min-max法が真の最善手を与える
二人零和有限確定完全情報ゲームの任意の局面について、その局面からゲーム終局まで読み切るmin-max探索で得られる最善手こそが、いかなる相手との対局でも最大限負け難いという意味で最良の最善手とみなせる*1。この最善手をここでは真の最善手と呼ぶ。
【精度∞】コンピュータ将棋における評価関数の高速な構成方法【誤差0】
現実の対局プログラムにおいては、対局中にゲーム終局まで読み切るmin-max探索を行うことは計算量的に不可能なので、読む深さを現実的な時間で探索し切れる深さに制限し、かわりに探索の先端ノードにおいて評価関数で計算した評価値を与え、その値に基づいてmin-max探索を行う*2というのが一般に採られる方法である。
ここで、評価関数を調整して真の最善手が選ばれ続ける状態にすることを考えよう。
上記探索方法において、少なくとも読みの深さが定数Nで与えられ、ある局面aから派生し得る全ての局面（自己の指し手でコントロールできる場合は除外し、相手の指し手次第で生じ得る全ての局面）について真の最善手が既知なら、a以降、探索で得る最善手が真の最善手と必ず一致するように評価関数を構成するアルゴリズムを見いだせる（かなり単純である）。
いまノードaの最善手を調整するものとすれば、aの子ノードのうちで、aから真の最善手で到達するノードa'（真の最善手が複数あってもそのうちのただ1個で良い）の評価値が最大となるように、a'から到達可能な探索の先端ノード全ての評価値をかさ上げすればよい。
そんな乱暴なことをすると、一見、かさ上げが巡り巡ってaの他の子ノードの評価値を上げてしまい、結局かさ上げ後のa'評価値以上になって元の木阿弥になる危険性が考えられるが、将棋においてはそうはならないかさ上げ量の下限が必ず存在する。なぜなら、将棋においては周期３手未満のサイクル手順が存在しないから、aの子ノードのうちa'以外の評価値は、探索の末端ノードから根ノードに向かって上がっていく過程で、必ず≪探索の末端ノードからa'に向かうとき通過するパス上にない≫ANDノードを1回以上通過するからである。かかるANDノードにおいては、かさ上げされた評価値と、かさ上げされなかった評価値とのmin{}がとられるから、一定以上のかさ上げを行うと、そのような全てのANDノードにおいて評価値の上昇がブロックされ、aの子ノードのうちa'以外の評価値の変化は完全に阻止される。かさ上げ量は単純にmax{上記ANDノードに入力される子ノード評価値全体のうちかさ上げされなかったもの}としていいし、圧縮したければバイナリサーチで効率的に下限を極められるだろう*3。
これをaの最善手、さらにその先の最善手、さらにその先…について反復する。反復につれ注目する評価値はかさ上げされる一方であり、かつかさ上げされる範囲は直前のかさ上げ範囲の外に出ない（部分木である）から、aからn手先の最善手のための調整が、すでに済んだn-1手以前の最善手の調整結果に影響することはない。
このアルゴリズムは探索木のノード数nに対して多項式時間で終了する。ただし、上述の通り、読みの深さが定数Nであることと、局面aから派生し得る（ただし自己の手番で選択しない局面は除く）全ての局面について真の最善手が既知である必要がある。また結果が算術計算可能な形でないからそのままプログラムに組み込むわけにはいかないが、この難点を回避する良い使い道については次に述べる。
