置換表はいろいろなことを教えてくれるかもしれない…例えば人生とか
今日おのエントリはGMA0BNが経験した狭い範囲のことがらをGMA0BNが怪しい思考能力でもって無理矢理説明することを試みるものであって*1、間違っているか、あるいはとっくに広く知られていることであって、どっちにせよ現実のコンピューター将棋プログラムを書くための情報としては価値0であることをお断りしておくが、
とにかくネガアルファ法において置換表はこんな感じに呼び出すべきものだ
template<int end_ab> int NegaAlpha(int rdepth, int alpha, int beta) { EnumContext& node = nodes[rdepth]; if (rdepth <= 0) { int v = (end_ab != 0) ? node.GetEvalOnA(alpha, beta) : -node.GetEvalOnA(-beta, -alpha); return v; } // 置換表参照 -- ヒット、fail-low、fail-highでtureを返す。いずれでもなく、可能なら[alpha, beta)を縮小する。 THash stateHash = node.GetHash(); bool hit = pTranspTab->Refer(stateHash, rdepth, /*ref*/ alpha, /*ref*/ beta); // (1) if (hit ) { return alpha; // ヒット、fail-lowやfail-high以外では来ない。(上のコメント参照) } int vmax = -INFINITE; while (node.MoveNext()) { TPMove curMove = node.GetLastMove(); int v = -NegaAlpha<end_ab>(rdepth - 1, -beta, -alpha); if (v > alpha) { alpha = v; if (alpha >= beta) { node.Reset(); pTranspTab->UpdateLower(stateHash, rdepth, alpha); // βカットが起きたので、置換表上のlowerBoundを上方修正 return alpha; } if (v > vmax) { vmax = v; } } } node.Reset(); if (vmax < alpha) { pTranspTab->UpdateUpper(stateHash, rdepth, vmax); // αカットが起きたので、置換表上のupperBoundを下方修正 } else { pTranspTab->Update(stateHash, rdepth, alpha); // 本局面の評価値が確定すた。以降この局面は置換表がヒットする。 } return alpha; }
で、(1)の呼び出しにおいて、alphaとbetaは不変か、αβウィンドウの縮小、すなわちalpha増大かbeta減少のみが起きる。
ただし、まっとうな作りである限り、alpha ≦ betaが常に成立し、alpha ＞ betaには決してならない*2。なぜなら、探索結果としての評価値は、
探索結果としての評価値＝読み筋の末端局面の評価値 ・・・(2)
として一意確定であって、置換表エントリのupperBoundやlowerBoundはこの値に向かって縮小せざるを得ないに決まってるだろＪＫ、
しかしこの考えには注意せねば見逃しかねない微妙な前提が存在し、GMA0BNが直感的に成立して欲しいと願う領域において必ずしも成立しない、というのが本日のお題だる。
仮説1
簡単のため、探索木の末端を当方の手番に限定する。
深さNの探索を行うとして、そこからk手前、すわなち上のコードでいうrdepthがkである中間ノードsを根とする深さkの部分探索の読み筋はNによらない。だから、sのミニマックス値のlowerBoundやupperBoundもNによらず確定であり、反復深化でNを増やすたびに置換表をクリアする必要はない*3。
仮説1の誤り
- N=kなら確かに探索木全体の読み筋とsを根とする部分探索の読み筋はイコールだが、N > kなら一般に両者は関係無い（グラフとしての包含関係が一般に生じない）。
- 探索木全体の読み筋とsを根とする部分探索の読み筋とがグラフとしての包含関係に無い場合、後者の探索の探索結果としての評価値は、前者の探索結果としての評価値とは無関係（独立）である。
＜2.の略証＞
深さNの探索の読み筋に包含されない末端局面tの評価値は、少なくともtを含む部分木がβカットされたとき深さNの探索の結果に全く反映されないことは明らかである。
一方、tを含む部分木がβカットされるか否かは探索木のトラバース順序*4に依存するから、βカットされないこともある。
もし、tを含む部分木がβカットされる/されないによって、tの評価値の、深さNの探索の探索結果への影響の有無が切り替わるとすると、探索結果としての評価値の一意性を述べている式(2)に矛盾する。
よって、深さNの探索の読み筋に包含されない末端局面tの評価値は、深さNの探索の探索結果としての評価値とは独立である。
この主張は、「tの評価値が」無関係だと言っているに過ぎないことに注意。tの評価値の置換表上のlowerBoundやupperBoundは、式(2)があるから、深さNの探索の探索結果としての評価値に従属する。だがその有り様はトラバース順序依存だ。
一方、略証の中にあるように、tを含む部分木がβカットされるか否かはトラバース順序依存でどっちにでも転び得るから、深さNの探索においてtがαβ法のトラバース範囲内に含まれて置換表に登録され、それが後に参照されることもある。で、そのときNは登録時と違っているかもしれない。
例えば登録してから参照されるまでの間に探索の深さNがnからn+2に変われば、両者の探索の結果としてのαβウィンドウはもちろん相違するから<追記>、その結果、αβウィンドウの縮小手順が相違し</追記>、N=nのとき登録された置換表エントリを、N=n+1のとき参照した、では<追記>lowerBoundやupperBoundが式(2)の左辺に向かって縮小していく途中でalpha ＞ betaが生じ得、</追記>矛盾することがある*5。少なくとも反復深化の間、置換表を放置する、はNG。
対処方法
反復深化でNを増やすたびに置換表をクリアする、が最も手堅い。だがもちろん効率が悪い。
もっといい方法があるが来年あたりに何かの機会に書くことがあるかもしれない、
おまけ
置換表への登録やupperBound・lowerBoundの変更は、探索木を既定する前提を固定した上で、
- αカット
- βカット
- 評価値確定時
に行うならそれで全く無問題なのであって、探索木を既定する前提さえ変えないなら、αβ法で得た置換表はそのままMTD(f)での探索においても使える互換性を有するぐらいなものだが、上記1.〜3.以外の実行パスが思考ルーチンにある場合は注意が必要だ。例えば時間が来たら思考中断して再帰呼び出しの任意の階層から一気にfall-throughするような場合とか。
そういう実行パスがあるなら、置換表にはライトプロテクトの仕組みが必要だ。
■追記(2011-11-12 23:18頃)
ごめｗｗｗｗｗこのコードまちがってたわｗｗｗｗｗｗｗ
あるノードxでαカットが起きた（子ノード以下の探索結果としての評価値が、全てalphaを下回っていた）とき、親ノードであるxのl/bを[alpha, alpha]にしてしまっては甚だマズい。
修正すた*6、
電波やテレパシーでご指摘くださったたくさんの皆さんありがとう！
この修正はNB0AMG法*7には多分影響無いと思うが、一旦検証フェーズに戻しまうま、、、
*1:ていうかまあいつもの通りということだが
*2:異なる局面のハッシュ値の衝突（しばしば起きる置換表エントリの衝突ではなくて、ハッシュ値そのもののが同一になること）が生じた場合はそうでもないが、ハッシュ関数を常識的に作ればこれは事実上起きない。
*3:ここでは簡単のため末端の手番を変えない想定なので、Nは+2づつ増やすことに注意。まあ今日の話の本筋には関係ないが。
*4:ていうか要はオーダリング
*5:実際、漏れのプログラムではその矛盾を検出でき、しばしば起きているのを目撃した。
*6:ついでにコメントも直した
*7:「〜の方法」では「〜」の部分がいかにも人名っぽいから以後NB0AMG法にする。
