思うだけで学ばない日記 2.0

思うだけで学ばない日記から移転しました☆！よろしくお願いします。

いまさら聞けない将棋の置換表の作り方(1)

lifehack AI 置換表

% マクロ定義 \newcommand{\alphaxx}[1]{{\mathrm{alpha}^{({#1})}}} \newcommand{\betaxx}[1]{{\mathrm{beta}^{({#1})}}} \newcommand{\deltaxx}[1]{{\mathrm{delta}^{({#1})}}} \newcommand{\Vmax}{{V_{max}}} \newcommand{\wndxx}[1]{{\lbrack\ \alphaxx{#1}, \betaxx{#1}\ )}} \newcommand{\statexx}[2]{{#1^{(#2)}}} \newcommand{\pxx}[1]{{\statexx{p,#1}}} 探索窓の性質は前回のエントリで完全に理解したので本題に入り鯛、

準備： 千日手 / 連続王手の千日手の処理を追加

alpha_beta()に千日手および連続王手の千日手の処理を入れる。
探索窓の性質は前回のエントリで完全に理解したので\deltaxx{k}は無くして普通に書く。

int alpha_beta( int depth, int alpha, int beta )            // (A)
{
    // 千日手または連続王手の千日手を判定
    if (is_sennichite()) {                                  // (C1)
        // (現局面の盤面が4回出現)
        if (is_opp_in_perpetual_check()) {                  // (C2)
            // (現局面の盤面が連続王手で4回出現)
            return -∞;                                      // (C2')
        } else {
            return 0;                                       // (C1')
        }
    }

    if ( depth == 0 ) return evaluate();

    generate_all_moves();

    while ( move = next_move() )                            // (a)
    {
        make_move( move );

        value = -alpha_beta( depth-1, -beta, -alpha );      // (B)

        unmake_move( move );

        if ( beta <= value ) return beta;                   // (b)
        if ( alpha < value ) alpha = value;                 // (c)
    }

    return alpha;
}

ここで、-∞は、前回のエントリと同じく

-∞は合法手を有するどんな子が返す評価値よりも小さいことが保証される十分小さい値。

である。

前回のエントリで探索範囲の葉のタイプ3種類の中に

2. ゲームのルールにより評価値が確定する局面
→評価値 \Vmax = (\text{ルールで決まる値})

というものが存在することを述べたが、まさに(C1)、(C2)、(C2')、(C1')がそれに対応するコードである*1。見ての通りで、(C2')と(C1')において、評価値 \Vmax = (\text{ルールで決まる値})を返している。

で、(C1)の関数は↓これ

シンボル / 機能 is_sennichite / 現局面が千日手か否か判定
シグネチャ bool is_sennichite()
引数 （無し）
説明 ゲーム開始局面から現局面sに至るまでに
sと同じ盤面がsも含めて4回現れていたらtrueを返す。
さもなくばfalseを返す。

(C2)のは↓これ

シンボル / 機能 is_opp_in_perpetual_check / 現局面が連続王手の千日手か否か判定
シグネチャ bool is_opp_in_perpetual_check()
引数 （無し）
説明 ゲーム開始局面から現局面sに至るまでに
sと同じ盤面がsも含めて4回現れており、
その過程に含まれる相手手番局面の全てで
当方から王手がかかっていればtrueを返す。
さもなくばfalseを返す。

これらの実現方法の説明はとりま割愛する。

課題

千日手（と連蔵王手の千日手）がルールに無ければ評価値（とPV）が盤面の関数として定まるが、
千日手（と連蔵王手の千日手）がルールに追加されることにより評価値（とPV）が盤面の関数として定まらなくなる。

例1: 千日手（と連蔵王手の千日手）がルールに無い場合：
以下の1～4のケースについて、評価値（とPV）は全て同じ。

  1. S0→S1
    とゲームが進行後に探索を行いS1→A→B→C→D というPVを得る
  2. S0→S1→A→B→C→D→S0→S1
    とゲームが進行後に探索を行いS1→A→B→C→D というPVを得る
  3. S0→S1→A→B→C→D→S0→S1→A→B→C→D→S0→S1
    とゲームが進行後に探索を行いS1→A→B→C→D というPVを得る
  4. S0→S1→A→B→C→D→S0→S1→A→B→C→D→S0→S1→A→B→C→D→S0→S1
    とゲームが進行後に探索を行いS1→A→B→C→D というPVを得る

例2: 千日手（と連蔵王手の千日手）がルールに有る場合：
以下の探索結果のうち1～3は例1と同じ評価値（とPV）だが、4が相違する。

  1. S0→S1
    とゲームが進行した局面で探索を行いS1→A→B→C→D というPVを得る
  2. S0→S1→A→B→C→D→S0→S1
    とゲームが進行した局面で探索を行いS1→A→B→C→D というPVを得る
  3. S0→S1→A→B→C→D→S0→S1→A→B→C→D→S0→S1
    とゲームが進行した局面で探索を行いS1→A→B→C→D というPVを得る
  4. S0→S1→A→B→C→D→S0→S1→A→B→C→D→S0→S1→A→B→C→D→S0→S1
    とゲームが進行した局面で探索を行いS1で千日手（か連続王手の千日手）が成立（PVは「S1」となる。））

大文字は局面ではなく局面の盤面を表していると解釈されたい。またサンプルを最短にしたい思いから、先後双方ﾒﾁｬｸﾁｬやる気の無い指し回しになっているのはご容赦願いたい。例1では盤面S1の関数としてPVと評価値が定まるのに対し、例2では1～4のうち4のみ評価値は-\infty（連続王手の千日手成立）か、0（千日手のみ成立）となり、一般に1～3の評価値（PV先端の盤面Dの局面の評価値をS1視点にしたもの）と相違する。このように、千日手か連蔵王手の千日手のルールの追加により、評価値（およびPV）が盤面ではなく局面の履歴に依存するようになる。一方通常の置換表は盤面の関数としてしか情報を記憶できない。何とか汁、
というのが解決すべき課題である。

問題の端的な側面

評価値（とPV）が局面の履歴に依存するようになったトリガーは、明らかに千日手（と連続王手の千日手）のルール追加である。実際、千日手（と連続王手の千日手）の有ると無いでは以下の違いがある。

  • 例1の世界（千日手（と連続王手の千日手）無し）:
    ある局面sの探索結果はsと盤面が同じ全ての局面について再現する。
  • 例2の世界（千日手（と連続王手の千日手）有り）:
    評価値もPVも、ゲーム開始から探索の根までの履歴次第で様々に変化し、探索結果の再現性が乏しい。（再現させるにはゲーム開始から探索の根までの履歴を揃えねばならない。）

もっとも単純な方策

誤解があるといけないので最初に明らかにしておくが、千日手（と連蔵王手の千日手）がルールにあっても、置換表を使わなければ何の問題も無い。(C1)、(C2)、(C2')、(C1')追加後のalpha_beta()は、千日手（と連蔵王手の千日手）を含むルールに適合した形で前回エントリの「まえおき」に記したふるまいを示し、見つけてくる評価値（とPV）は同じルールの下でMin-max法で探索した結果と等価である。しかし置換表を使わなければ、同じ盤面について前回探索した結果を使いまわすこと（メモ化）ができず同じ探索を繰り返すこととなり、探索の効率に支障があるから、置換表をどうしても使いたい、というのが当blogの主旨であり、GMA0BNの存立基盤である。

おそらく次に単純な方策

これは以下に述べる2つのステージからなる。

ステージ1: 置換表に問題になる値を積まないようにする

評価値に「履歴非依存」フラグを設ける。
例2の3の探索のように、千日手（か連続王手の千日手）によって決まった評価値では0にする。
そうではなくて、合法手0か、静的評価関数により決まった評価値では決まった直後、1でスタートする。
で、alpha_beta()のif文(b)および(c)において、以下の規則でフラグを伝搬させる。

  1. if ( beta <= value ) return beta; // (b)
    betaかvalueのどちらかの履歴非依存フラグが0かつ「<=」成立なら、returnするbetaの履歴非依存フラグを0にする。
  2. if ( alpha < value ) alpha = value; // (c)
    alphaかvalueのどちらかの履歴非依存フラグが0なら、「<」の成立とは無関係に alphaの履歴非依存フラグを0にする。

2番目はif文の条件が成立しようがしまいが、履歴非依存フラグ0（履歴依存）である値との比較結果を履歴非依存フラグ0とする（履歴依存とみなす）ということを意味する。
なんでそこまでせねばならないかというと、履歴依存の探索結果は再現性が乏しいからである。今現在xより大きいと判定されても、次回もそうとは限らない。履歴依存性は関係演算で接触感染するとみなさざるおえない。
で、置換表にはもちろん評価値の履歴非依存フラグが1の場合のみ、探索結果を積む。

ちなみにフラグの0/1を、履歴非依存が1、履歴依存が0としているのは履歴非依存フラグ以外は同じ2つの評価値が得られたとき、履歴非依存の方を大きいものとみなしてif文(c)で優先したいという思いからであるが、上記の通り履歴非依存性は大小関係とは無関係に伝染するので単に気分である。

ステージ2: 置換表の値を悲観的に解釈する

ステージ1の処置で置換表の値は100%信頼できるようになるかというとそうでもない。
前回盤面Sの局面s1を探索し、置換表に履歴非依存の結果を積み、その後同じ盤面Sの局面s2にいきあたったとする。
しかしここで再び探索結果に再現性が無いという問題が再び頭をもたげてくる。
s2の兄弟やその子孫における千日手（や連続王手の千日手）の発生状況が、
s1の兄弟やその子孫における千日手（や連続王手の千日手）の発生状況（履歴依存無し）と同じ保証が無い。
s1の評価値は当方視点で+10CP（相手視点では-10CP）だったが、s2では相手が千日手を選択可能で+0CPにされるかもしれない。
このような状況で置換表でもってs2を+10CPとみなすと、探索結果はファンタジーとなる。
なぜなら、

  • 評価値+10CP以上を狙えるという保証は失われており、
  • にもかかわらず置換表により探索窓が狭められ、評価値+10CP未満となる手を探索しなくなる

からである。

一方、その反対のケースとして、s1では-100CPだったがs2では当方が千日手を選択して+0CPにできる、と言うケースもあり得る。
この場合は問題にならない。置換表が探索窓を狭めても-100CP以上の手の探索は阻害されず、千日手を選択して+0CPにする手があるならそれを見つけられる。

以上をまとめると、置換表を参照する段において、置換表に詰まれている0を超える評価値（の下限）は0とみなす（探索窓を狭めるのは評価値が負の領域のみとし、窓の下限を0より大きくしない）、
という処理が必要である。

連続王手の千日手については、当方が連続王手の千日手を行う以外選択肢が無いという状況に陥ることはほとんどありえない（s1探索時に詰まされなかったことから、s2では評価値-\inftyより上をほぼ確率1で狙える）という確率論でもって事実上無視できる。
嘘だと思うなら当方手番で王手するしか選択肢が無い局面を考案してみると宜しい。
無いわけではないが、以下の条件を満たさねばならない極めてハードルの高い話である。

  1. 王手をかける以外の動きができる置駒が0（∵王手をかける以外の動きができる置駒があれば、それを王手をかけないように動かせば王手をかけずに済む。）
  2. 持駒が0（∵あれば王手とは無関係なマスにdropする手で王手をかけずに済む）

連続王手の千日手は、仕掛ける側の自助努力でほとんど100%回避できるのである。

この方策の評価

やったらﾜｶﾙが、ステージ1の措置により置換表利用率は2^23 Byteの置換表で通常の対戦を行って3～4%行くか行かないかみたいなあまり見慣れない低い値しか示さなくなる。
とりあえず探索結果はファンタジーにならないが（後で述べる探索処理のテストにパスする）、効率が悪すぎる。

次回予告

近代的なコンピュータ将棋プログラムはもちろん上記のようなｱﾌｫな方策はとっていない（脳内調べ
置換表の効率を落とすことなく探索結果の非決定性を計算量の問題で探索を適当な深さまでで打ち切るしかないというどんな方策でも避けられない要因1点に押し込め、履歴依存性の影響を無くす遥かに洗練された方法が存在する。

*1:今追加した、

ｶﾝﾀﾝに証明できるわけないじゃんムリムリ！（※ ムリじゃなかった！？）

lifehack 置換表 AI

% マクロ定義 \newcommand{\alphaxx}[1]{{\mathrm{alpha}^{({#1})}}} \newcommand{\betaxx}[1]{{\mathrm{beta}^{({#1})}}} \newcommand{\deltaxx}[1]{{\mathrm{delta}^{({#1})}}} \newcommand{\Vmax}{{V_{max}}} \newcommand{\wndxx}[1]{{\lbrack\ \alphaxx{#1}, \betaxx{#1}\ )}} \newcommand{\statexx}[2]{{#1^{(#2)}}} \newcommand{\pxx}[1]{{\statexx{p,#1}}}

まえおき: 証明目標の修正

前回のエントリではalpha_beta()の探索結果がMin-max法による探索結果と同じになる探索窓の条件を求めようとしたがそれは知りたいこととﾋﾞﾐｮｰに違ってたorz、
知るべきことは、局面pにおいて、min-max値\Vmax（p視点）をもたらすPVが未知であるという状況で、\Vmaxとの大小関係が不明確な探索窓を設定してp以下をalpha_beta()で探索したとき、必ず以下のどれかになる探索窓の条件、である。

  1. \Vmaxが探索窓に含まれていればmin-max値\Vmaxと、それをもたらすPVを出力する。
  2. \Vmaxが探索窓の下限以下ならば、探索窓の下限以下の値を出力する。
  3. \Vmaxが探索窓の上限以上ならば、探索窓の上限以上の値を出力する。

2と3のときは、alpha_beta()のpに関する探索結果はMin-max法と相違する。ただし、\Vmaxと探索窓の大小関係の符号だけは正しく出力する。

これが顧客が本当に必要だった探索窓である。

結論

alpha_beta()による探索は、何も考えなくとも上記「まえおき」の挙動となる（ｷﾘ

ここでalpha_beta()というのは↓これ（再掲）。

#define F(depth, alpha, beta, delta)    \
        (-alpha_beta( (depth) - 1, -(beta), -((alpha) + (delta)) ))     /* Macro 1 */

int alpha_beta( int depth, int alpha, int beta )            // (A)
{
    if ( depth == 0 ) return evaluate();

    generate_all_moves();

    int delta = 0;
    while ( move = next_move() )                            // (a)
    {
        make_move( move );

        value = F(depth, alpha, beta, delta);               // (B')

        unmake_move( move );

        if ( beta <= value ) return beta;                   // (b)
        if ( alpha + delta < value ) delta = value - alpha; // (c')
    }

    return alpha + delta;
}

alpha_beta()は普通のαβ法の探索ルーチンに対し以下の変更を行っているのは前に説明した通り。

  1. ループ内でalphaを直接増やしたりする代わりにalphaを定数、増加分をdeltaとして分離
  2. 引数の[alpha, beta) と、再帰呼び出し時の[-beta, -alpha) が一つの関数alpha_beta内に混在して荒われるのを抑止

この変更は証明用の記号を捻出する目的で行った形式的なもので、αβ法の手順の変更ではないから、下記の証明結果はalpha_beta()を基の姿に戻しても通用する。

同じ調子でMin-max法の探索ルーチンを書くと次のようになる：

int nega_max( int depth )                                   // (A)
{
    if ( depth == 0 ) return evaluate();

    generate_all_moves();

    int alpha = -∞;
    int delta = 0;
    while ( move = next_move() )                            // (a)
    {
        make_move( move );

        value = nega_max(depth - 1);                        // (B')

        unmake_move( move );

        if ( alpha + delta < value ) delta = value - alpha; // (c')
    }

    return alpha + delta;
}

ここで-∞は合法手を有するどんな子が返す評価値よりも小さいことが保証される十分小さい値。
この関数nega_max()も下記の証明で参照する。

証明

局面pをMin-max法で探索したときのPVの評価値を\Vmax（p視点）、
局面pをalpha_beta()を用いて探索窓\wndxx{k}で探索したときのreturn値（SCORE）をxとする。

  1. x \leq \alphaxx{k}なら、下記補題[3]より、\Vmax \leq \alphaxx{k}である。
  2. x \geq \betaxx{k}なら、下記補題[4]より、\Vmax \geq \betaxx{k}である。
  3. \alphaxx{k} < x < \betaxx{k}なら、下記補題[5]より、 x=\Vmaxである。

以上により、alpha_beta()による探索は、上記「まえおき」の挙動となる。

補助証明

補題[1]

子が存在する（make_move()が実行される）局面pについて、局面pの子sがpのPVであることと、pをnega_max()で探索したとき以下が成立することは同値である。

  1. p視点での評価値が(-(sの評価値))を超える子がpに存在しない
    （すわなち\max\{-\infty+\deltaxx{k}\} =\Vmax）
  2. p視点での評価値が(-(sの評価値))と同じになる子がsより先に見つかっていない
    （すわなちsの探索に着手する時点で-\infty+\deltaxx{k} < \Vmax）

ここで、ｋはpのrからの深さ、\Vmaxはpの評価値。
（証明）
nega_max()でif文(c')が実行される条件をコードを見たらﾜｶﾙ
ていうかこの補題はMin-max法とPVの定義と言っても過言ではない。

補題[2]

子が存在する局面には必ずPVが存在する。
（証明）
有限ゲームなのでどの局面の子の数も有限なのでnega_max()で探索したとき必ず\max\{-\infty+\deltaxx{k}\} =\Vmaxが定まる。

補題[3]

局面sをalpha_beta()で探索窓\wndxx{k}で探索したとき返されるSCOREが\alphaxx{k}以下ならば、局面sをnega_max()で探索したときの評価値（s視点）は\alphaxx{k}以下である。
（証明）
alpha_beta()を用いて局面sを探索窓\wndxx{k}で探索した結果が\alphaxx{k}以下になることは、以下の成立と同値である。

  • (1) sの全ての子について、SCOREが-\alphaxx{k}以上である。
  • (2) sの全ての子について、そのそれぞれの子（sの孫）の中にSCOREが\alphaxx{k}以下のものが1つ以上存在する。

このことから、nega_max()を用いて局面sを探索して得られるPVについて、以下のことが言える。

  • (1') PVの先端がsの子の代である（そこが探索範囲の葉である）場合は、その葉の評価値は-\alphaxx{k}以上である。
  • (2') PVの先端がsの孫の代である（そこが探索範囲の葉である）場合は、その葉の評価値は\alphaxx{k}以下である。

なぜなら、葉においてalpha_beta()が返すSCOREとnega_max()が返す評価値が直接対応付くからである。
内部ノードではそうはいかないが、葉ならそれができうる。
細かく見ると以下の通り。

葉は次の3つのタイプのどれかである。

  1. 合法手無しの局面
    →評価値 \Vmax = -\infty
  2. ゲームのルールにより評価値が確定する局面
    →評価値 \Vmax = (\text{ルールで決まる値})
  3. 静的評価を行う局面
    →評価値 \Vmax = (\text{静的評価関数（上記コードのevaluate()）が返した値})

葉が2か3のタイプの場合は、nega_max()、alpha_beta()いずれも同じ値をreturnするから評価値=SCOREが成立する。従って、場合(1')、(2')の結論がただちに言える。
すわなち

  • 場合(1')において、-\alphaxx{k}に対する葉の評価値の大小と、同じ値に対する葉のSCOREの大小は一致する。
  • 場合(2')において、\alphaxx{k}に対する葉の評価値の大小と、同じ値に対する葉のSCOREの大小は一致する。

葉が1のタイプの場合は、nega_max()が-\infty、alpha_beta()が探索窓の下限を返すため両者はイコールにはならないものの、

  • 場合(1')において、-\alphaxx{k}に対し、葉の評価値-\inftyは小さく、同じ値に対しSCORE -\betaxx{k}もまた小さい。
  • 場合(2')において、\alphaxx{k}に対し、葉の評価値-\inftyは小さく、同じ値に対しSCORE \alphaxx{k}は以下である。

なので比較対象値に対する「以下」「以下」はSCOREと評価値の両者で揃うため、やはり場合(1')、(2')の結論が言える。

したがって、場合(1’)か(2’)に該当する葉でPVが終わった場合は、その葉のSCOREの大小判定でもってMin-max法による評価値の大小判定に代えることができる。

以上で、

（補助命題）局面sをalpha_beta()で探索窓\wndxx{k}で探索したとき返されるSCORE xが\alphaxx{k}以下、かつPVの先端がsの子か孫の場合、PVの評価値（s視点）は\alphaxx{k}以下である

が証明された。

一方、sからsの孫までの探索窓は一般式で書けば下表である。

階層 探索窓下限α 探索窓上界β
s \alphaxx{k} \betaxx{k}
子 \alphaxx{k+1} = -\betaxx{k} \betaxx{k+1} = -\alphaxx{k}-\deltaxx{k}
孫 \alphaxx{k+2} \\= -\betaxx{k+1} \\= \alphaxx{k}+\deltaxx{k} \betaxx{k+2} \\= -\alphaxx{k+1}-\deltaxx{k+1} \\= \betaxx{k}-\deltaxx{k+1}

sのSCOREが\alphaxx{k}以下という前提から、\deltaxx{k} = 0と言える。従い、この前提の下では探索窓の推移は次式となる。

階層 探索窓下限α 探索窓上界β
s \alphaxx{k} \betaxx{k}
子 \alphaxx{k+1} = -\betaxx{k} \betaxx{k+1} = -\alphaxx{k}
孫 \alphaxx{k+2} \\= -\betaxx{k+1} \\= \alphaxx{k} \betaxx{k+2} \\= -\alphaxx{k+1}-\deltaxx{k+1} \\= \betaxx{k}-\deltaxx{k+1}

このようにsの孫の探索窓の下限はsと同じく\alphaxx{k}となる。このためsの孫に対しても上記補助命題を適用でき、さらにその孫にも以降繰り返し適用できるので、PVの先端がsの子以降のどこになってもPVの評価値（s視点）は\alphaxx{k}以下と言える。

補題[4]

局面sをalpha_beta()で探索窓\wndxx{k}で探索したとき返されるSCORE xが\betaxx{k}以上ならば、局面sをnega_max()で探索したときの評価値（s視点）は\betaxx{k}以上である。
（証明）
補題[3]と同様にして最初からやっても証明できうるが、せっかくなので補題[3]を活用する。
仮定より、SCOREとして-xを返したpの子sが存在し、その探索窓の下限は\alphaxx{k+1}=-\betaxx{k}である。すわなち
\begin{equation} \left\{ \begin{aligned} x &\geq \betaxx{k}\\ \alphaxx{k+1} &= -\betaxx{k} \end{aligned} \right. \end{equation} ということなので、 -x \leq \alphaxx{k+1}が成立する。従って、下記補題[4]よりpの子視点の評価値-\Vmaxは \alphaxx{k+1}=-\betaxx{k}以下である。よって、\Vmax \geq \betaxx{k}である。（PVの先端がpの孫以降ではなくpの子である場合は補題[3]に拠らず直接最後の結論を導く。）

補題[5]

局面sをalpha_beta()で探索窓\wndxx{k}で探索したとき返されるSCORE xが\alphaxx{k} < x < \betaxx{k}を満たすならば、xは局面sをnega_max()で探索したときの評価値（s視点）に等しい。
（証明）
これは補題[3]や[4]とは大小関係が反転しておりそれらを利用できないため、補題[3]と同様にしつつも最初から組み立てる方向で証明する。
alpha_beta()を用いて局面sを探索窓\wndxx{k}で探索した結果SCORE xが\alphaxx{k} < x < \betaxx{k}を満たすことは、以下の成立と同値である。

  • (1) x = max{ -(sの子のSCORE) }
    （∵ x < \betaxx{k}であるためβカットが起きず、if文(c')の最後の実行により左記最大値が選択され、returnされる。）
  • (2) max{ -(sの子のSCORE) }をもたらす局面qの全ての子（sの孫）において、-x = max{ -(qの子のSCORE) }
    （∵ \betaxx{k+1}=-\alphaxx{k}-\deltaxx{k} \geq -\VmaxだがPV発見前のため\geqの等号は成立しておらず、-x < \betaxx{k+1}であるためβカットが起きず、if文(c')の最後の実行により左記最大値が選択され、returnされる。）

このことから、nega_max()を用いて局面sを探索して得られるPVについて、以下のことが言える。

  • (1') PVの先端がsの子の代である（そこが探索範囲の葉である）場合は、その葉の評価値はmax{ -(sの子のSCORE) }である。
  • (2') PVの先端がsの孫の代である（そこが探索範囲の葉である）場合は、その葉の評価値はmax{ -(qの子のSCORE) }である。

補題[3]の中で記した3タイプの葉のうち、2か3のタイプでは葉のSCORE=葉の評価値なので場合(1')、(3')の結論はただちに言える。
1のタイプについては、PVの葉が1のタイプということはPVの評価値（s視点）は-\inftyか\inftyとなることからそれを包含する探索窓が有り得ず、当補題ではなく補題[3]か[4]による解決となる。（よって以下の議論では葉のタイプは2か3に限定する。そうしても一般性を失わない。）

以上で、

（補助命題）局面sをalpha_beta()で探索窓\wndxx{k}で探索したとき返されるSCORE xが xが\alphaxx{k} < x < \betaxx{k}を満たし、かつPVの先端がsの子か孫の場合、PVの評価値（s視点）はxに等しい

が証明された。

一方、sからsの孫までの探索窓は一般式で書けば下表である。

階層 探索窓下限α 探索窓上界β
s \alphaxx{k} \betaxx{k}
子 \alphaxx{k+1} = -\betaxx{k} \betaxx{k+1} = -\alphaxx{k}-\deltaxx{k}
孫 \alphaxx{k+2} \\= -\betaxx{k+1} \\= \alphaxx{k}+\deltaxx{k} \betaxx{k+2} \\= -\alphaxx{k+1}-\deltaxx{k+1} \\= \betaxx{k}-\deltaxx{k+1}

場合(1)、(2)の結論（x、-xがそれぞれの親視点で最大値）が言えることから、\alphaxx{k}+\deltaxx{k} \leq xかつ \alphaxx{k+1}+\deltaxx{k+1} \leq -xである。さらに、PV自体の探索窓については左記等号は非成立である。（∵直前の子まではPV発見前であるため、その評価値（親視点）はPVの評価値（親視点）より小さい。）
従って、PVの探索窓は下記となる。

階層 探索窓下限α 探索窓上界β
s \alphaxx{k} \betaxx{k}
子 \alphaxx{k+1} = -\betaxx{k} \betaxx{k+1} > -x
孫 \alphaxx{k+2} \\= -\betaxx{k+1} \\< x \betaxx{k+2} \\= -\alphaxx{k+1}-\deltaxx{k+1} \\> x

このようにsの孫の探索窓は \alphaxx{k+2} < x < \betaxx{k+2}を満たし、sの探索窓と同じくxを包含している。このためsの孫に対しても上記補助命題を適用でき、さらにその孫にも以降繰り返し適用できるので、PVの先端がsの子以降のどこになってもPVの評価値（s視点）はxに等しいと言える。

むすび

αβ法とMin-max法の等価性かくにん！よかった

最初は葉から任意の局面pまで貫通するPVというものを最初に想起してその評価値について何事かを言わんとしたがそうするとPV上に子が葉のみの内部ノードと子が内部ノードのみの内部ノードのみならず子に葉が混在する内部ノードと言うケースまで有り得るため葉からpに向かってストレートに一本道に数学的帰納法できそうも無くどうするべきのか悩んだ末にalpha_beta()の挙動とPV（こちらはnega_max()すわなちMin-max法の産物）をpの側から対応付けてPVの先端＝葉でSCOREと評価値の関係を入れるという方策を思いついて突破すた、

本物の方々がどうやっているのかわ知りま栓、

いじょ

いまさら聞けない探索窓の性質

lifehack 置換表 AI

% マクロ定義 \newcommand{\alphaxx}[1]{{\mathrm{alpha}^{({#1})}}} \newcommand{\betaxx}[1]{{\mathrm{beta}^{({#1})}}} \newcommand{\deltaxx}[1]{{\mathrm{delta}^{({#1})}}} \newcommand{\Vmax}{V_{max}}

FAQ

一つ前のエントリについて電波でいろいろ質問をいただいたのでまずそれについて回答死体、

Q1. 無限小に対する加算について:

これは少なくとも \alphaxx{k}=-\infty, \betaxx{k}=+\inftyとすることで探索せずに実現できるから、そう不当な要請ではない。

と書いたあるが、 \alphaxx{k}=-\inftyに \deltaxx{k}をいくら足しても -\inftyのままで探索窓が狭まらないのでは？
A1. ここでの \inftyは無限ではなく（もちろん \infty という文字を用いている以上どうやっても有限の文字数で表す術の無いｶﾞﾁの無限でもなく）十分大きい有限の数を表す記号と解釈されたい。

Q2. 「rの正当な評価値」と V_{max}=max{(sの親ノードpの子の評価値)} は、どっちもMin-max法で探索したときの評価値（min-max値）なのでは？
A2. どっちもmin-max値だというのはそれやそうやがどの局面のmin-max値かが違う、というつもりで書いていたが、いくつか記述に不備があったので訂正死体、
まず {V_{max}}について：

△: {V_{max}} = max{\text{(sの親ノードpの子の評価値)}}
〇: {V_{max}} = \text{(sの親ノードpのmin-max値)}

で、「rの正当な評価値」の方のは「rの」min-max値に他ならない。
この後示すが、両者はrの読み筋上にpがある場合は一致し*1、そうでなければ直接的な関係を持たないという関係にある。

alpha_beta()による探索がMin-max法と同じになる条件

Min-max法は「相手が当方の利得を最大限削ってくる前提で当方の利得を最大にする子を選ぶ」という操作ので、探索において最大の評価値をもたらす子のトラバースに着手できる必要がある。
逆に最大の評価値をもたらす子のトラバースを完遂すれば、そのp視点の評価値が {V_{max}}である。
pの探索をalpha_beta( \alphaxx{k}, \betaxx{k})で始めたとすると、p視点の評価値 {V_{max}}を返すことになる子のトラバースが着手されるためには、再帰呼び出しk段目であるところの当のalpha_beta()の中で、 \alphaxx{k}+\deltaxx{k}はきっちり {V_{max}}まで更新される必要があり、その手前でβカットされてはならない。したがって、以下の成立が必要である。
\begin{equation} \begin{aligned} {V_{max}} \leq \betaxx{k} \end{aligned} \end{equation} \tag{1} \label{eqn01}
一方、p視点の評価値 {V_{max}}を返すことになる子は探索深さk+1の呼び出しalpha_beta( \alphaxx{k+1}, \betaxx{k+1}) = alpha_beta( -\betaxx{k}, -\alphaxx{k}-\deltaxx{k})で探索を始められ、このalpha_beta()の中で、 \alphaxx{k+1}+\deltaxx{k+1}はきっちり -{V_{max}}まで更新される必要があり、その手前でβカットされてはならない。したがって、以下の成立が必要である。
\begin{equation} \begin{aligned} -{V_{max}} &\leq \betaxx{k+1}\\ \therefore {V_{max}} &\geq \alphaxx{k}+\deltaxx{k}\\ \therefore {V_{max}} &\geq \alphaxx{k} (\because \text{Always} \ \deltaxx{k} \geq 0 ) \end{aligned} \end{equation} \tag{2} \label{eqn02}
式 \eqref{eqn01}と式 \eqref{eqn02}をまとめると、結局必要条件は次式となる。
\begin{equation} \begin{aligned} \alphaxx{k} \leq {V_{max}} \leq \betaxx{k} \end{aligned} \end{equation} \tag{3} \label{eqn03}
逆に式 \eqref{eqn03}が満たされれば、 \Vmaxは葉までの探索の再帰呼び出しの中で常に探索窓の中にあり続ける。なぜなら、探索深さk+1の呼び出しの探索窓は
\begin{equation} \begin{aligned} &\lbrack \ \alphaxx{k+1}, \betaxx{k+1} \ ) \\ = &\lbrack \ -\betaxx{k}, -\alphaxx{k} - \deltaxx{k} \ ) \end{aligned} \end{equation} \tag{4} \label{eqn04}
であるわけやが、式 \eqref{eqn03}が満たされると仮定すると、式 \eqref{eqn04}のalphaの関係よりただちに
\begin{equation} \begin{aligned} \alphaxx{k+1} &\leq -\Vmax \end{aligned} \end{equation} \tag{5} \label{eqn05}
が言え、betaの方は適当な非負の数dを導入して
\begin{equation} \begin{aligned} \Vmax = \alphaxx{k} + d \end{aligned} \end{equation} \tag{6} \label{eqn06}
と置いたならば、これと式 \eqref{eqn04}のbetaの関係から \alphaxx{k}を消去して
\begin{equation} \begin{aligned} -\Vmax = \betaxx{k+1} - (d-\deltaxx{k}) \end{aligned} \end{equation} \tag{7} \label{eqn07}
を得、 -\Vmaxがpの子の中でp視点の最大の評価値であることから (d-\deltaxx{k})は非負が保証されるので、結局
\begin{equation} \begin{aligned} &\alphaxx{k} \leq \Vmax \leq \betaxx{k} \\ \longrightarrow \ & \alphaxx{k+1} \leq -\Vmax \leq \betaxx{k+1} \end{aligned} \end{equation} \tag{8} \label{eqn08}
なんじゃわふーん、これでpから探索範囲の葉（のうちのp視点での評価値 \Vmaxを発生した葉）に至るまでの探索窓が全ての再帰呼び出し深さについて \Vmax（pと手番違い局面では -\Vmax）を包含することの数学的帰納法による証明になっているはず……
あとはその行きついた葉の静的評価した値がp視点で必ず \Vmaxとなることを証明したら「pにおいてmin-max値 \Vmaxが探索窓に含まれている」という最初の仮定に背理が含まれなかったことが言えて証明が完成する……
のやがこれがやたらムズい。とりま背理要素は見当たらなさげなので証明できたことにしよう（駄目

Principal Variation（PV）

で、式 \eqref{eqn08}の再帰呼び出し段数k+1における探索窓は、細かく書くと
\begin{equation} \begin{aligned} \alphaxx{k+1} &\leq -\Vmax \\ &= \betaxx{k+1} - (d-\deltaxx{k}) \leq \betaxx{k+1} \end{aligned} \end{equation} \tag{9} \label{eqn09}
を満たすなので探索窓の幅は単調減少することも言える。
このように、pにおいて評価値\Vmaxをもたらす子、孫、ひ孫の連鎖はどの再帰呼び出し段数においても探索窓の中に \Vmax（手番側の先後がpと異なる局面では -\Vmax）が収まっていることとなる。
で、少なくともpの子の探索において、pの視点の評価値\Vmaxとなる子を最初を最初に見つけたら、以降の子の中の再帰呼び出し深さk+1の探索（pから見て孫の探索）でpの視点の評価値が\Vmax以下となる子はβカットされるから（ \because \text{以降のpの子の探索において} \ \betaxx{k+1} = -\alphaxx{k} - \deltaxx{k} \ = -\Vmax ）、この連鎖は1本道となる。これが読み筋またはPrincipal Variation（PV）というやつ、

ただしpのPVがrのPVとなる保証は無い。pのPVの\Vmaxが、rにとっての\Vmax（先のエントリで「rの正当な評価値」と言っていたやつ）と（手番側の先後がrとpとで異なることによる符号の違いを除き）一致する場合に限り、rとpは1本の同一PV上となる。そうでない場合は、上記のような感じでpのPVはrとpの間のどこかでβカットされ、rまで続かない。

驚くべき説明を見つけたが余白が足りないので以下略、

*1:rとpの手番側の先後が不一致の場合に異符号とはなるがそれ以外は一致する。

エッホエッホ、チャトランガ系ゲームの置換表にはβ値は積むなって伝えなきゃ、エッホエッホ

lifehack 置換表 AI

このことを理解するには正しい探索観を涵養することが肝要である。まずそれ用の記法を導入する。
次の図はAlpha-beta法に基づき探索を行うプログラムの疑似コードである[1]（疑似コード内のコメントは筆者）：

int alpha_beta( int depth, int alpha, int beta )            // (A)
{
    if ( depth == 0 ) return evaluate();

    generate_all_moves();

    while ( move = next_move() )                            // (a)
    {
        make_move( move );

        value = -alpha_beta( depth-1, -beta, -alpha );      // (B)

        unmake_move( move );

        if ( beta <= value ) return beta;                   // (b)
        if ( alpha < value ) alpha = value;                 // (c)
    }

    return alpha;
}

人類の大多数が親の顔よりよく見るコードなので個々の要素の説明は省略するが、とりま次の2点が了解されるであろう。

  • (A)においてalpha_beta()の引数として与えられたbeta（alphaより大とする）がalphaに近い値であるほど、(b)の条件分岐でreturnする確率が高まる。
  • (B)において返される値valueが大きいほど、(c)でalphaがbetaに近づく確率が高まり、alphaがbetaに近づくことにより（上と同じく）(b)の条件分岐でreturnする確率が高まる。

閉区間[alpha, beta]は探索窓と呼ばれ、これを速やかに狭めることがループを早く抜けて探索を早く終わらせることに直結するという、Alpha-beta法における最重要概念である*1。
この観点で上記コードを見ると、探索窓がいささか紛らわしい書き表し方になっているのがﾜｶﾙ
関数alpha_betaの宣言部(A)における仮引数リスト「alpha, beta」と再帰呼び出し(B)における「-beta, -alpha」のそれぞれが探索窓を意味し、つまりはalpha_beta()の定義内に2種類の探索窓が現れている。しかも変数alphaの値は(a)のループを回るにつれ(c)で増加する可能性があり、一般にalpha_beta()呼び出し時の値から変化する。
このため、「alpha_beta()の再帰呼び出しk段目の探索窓」と言ったときそれがどの閉区間を指すのか曖昧である。この問題を解消すべく、以下の議論においては、2種類の探索窓のうち後者を関数マクロF()に押し込み、さらに変数deltaを導入することでループ(a)内でのalpha自体の更新を無くした次の疑似コードを使用汁、：

#define F(depth, alpha, beta, delta)    \
        (-alpha_beta( (depth) - 1, -(beta), -((alpha) + (delta)) ))     /* Macro 1 */

int alpha_beta( int depth, int alpha, int beta )            // (A)
{
    if ( depth == 0 ) return evaluate();

    generate_all_moves();

    int delta = 0
    while ( move = next_move() )                            // (a)
    {
        make_move( move );

        value = F(depth, alpha, beta, delta);               // (B')

        unmake_move( move );

        if ( beta <= value ) return beta;                   // (b)
        if ( alpha + delta < value ) delta = value - alpha; // (c')
    }

    return alpha + delta;
}

こうした上で、改めて「alpha_beta()の再帰呼び出しk段目の探索窓」を[alpha, beta]と定義する*2。さらに、再帰呼び出しの段数kという文脈を、alphaとbetaの右肩に括弧付きでkの値を書いて明示することにしよう。すると文脈k+1と文脈kの間の関係として次式が成り立つ：
% マクロ定義 \newcommand{\alphaxx}[1]{{\mathrm{alpha}^{({#1})}}} \newcommand{\betaxx}[1]{{\mathrm{beta}^{({#1})}}} \newcommand{\deltaxx}[1]{{\mathrm{delta}^{({#1})}}} \begin{equation} % 式(1) \left\{ \begin{aligned} \alphaxx{k+1} & = -\betaxx{k} \\ \betaxx{k+1} & = -( \alphaxx{k} + \deltaxx{k} ) \end{aligned} \right. \end{equation} \tag{1} \label{eqn01}

んまー「特定プログラミング言語で描かれた風の疑似コード」という定義の不明確なものをベースに理論構築を図るのはいささか問題かもしれないが、人類の大多数が親の顔よりよく見るコードなのでクオリアが裏切ることはないﾊｽﾞ……

一般項

後述するように式\eqref{eqn01}で問題点を説明できるためあくまで参考情報だが、とりあえず式\eqref{eqn01}より、探索窓の下端\alphaxx{k}と上端\betaxx{k}の一般項は次式となる：
(kが偶数 2n (n=1, 2, 3, \dots)のとき)
\begin{equation} \left\{ \begin{aligned} \alphaxx{2n} & = -\betaxx{1} + \sum_{k=1}^{n-1} \deltaxx{2k} \\ \betaxx{2n} &= -\alphaxx{1} - \sum_{k=1}^{n} \deltaxx{2k-1} \end{aligned} \right. \end{equation} \tag{2a} \label{eqn02-even}
(kが奇数 2n+1 (n=1, 2, 3, \dots)のとき)
\begin{equation} \left\{ \begin{aligned} \alphaxx{2n+1} & = \alphaxx{1} + \sum_{k=1}^{n} \deltaxx{2k-1} \\ \betaxx{2n+1} &= \betaxx{1} - \sum_{k=1}^{n} \deltaxx{2k} \end{aligned} \right. \end{equation} \tag{2b} \label{eqn02-odd}

何が問題か

ゲーム木のあるノードr以下を適当な深さまで探索する状況を考える。同じ探索範囲をMin-max法で葉まで探索したとき得られる評価値がrの正当な評価値である。Alpha-beta法の探索窓はrの正当な評価値を包含せねばならない。（正確には、上記疑似コードはNega-alpha法なので、alpha_beta()の呼び出し深さkが奇数なら(rの正当な評価値)、kが偶数なら -(rの正当な評価値) を包含せねばならない。）さもないと評価値が探索範囲をMin-max法で葉まで探索したとき得られるものと相違し*3、探索結果がファンタジーと化してしまう。

いま探索窓 [ \alphaxx{k}, \betaxx{k}]がrの正当な評価値を包含するものとする：
\begin{equation} \left\{ \begin{aligned} \alphaxx{k} & \le \text{(rの正当な評価値)} \\ \betaxx{k} & \ge \text{(rの正当な評価値)} \end{aligned} \right. \end{equation} \tag{3} \label{eqn03}
（これは少なくとも \alphaxx{k} = -\infty, \betaxx{k} = \infty とすることで探索せずに実現できるから、そう不当な要請ではない。）

すると、式\eqref{eqn01}と式\eqref{eqn03}より、次式が言える。
\begin{equation} \left\{ \begin{aligned} \alphaxx{k+1} & \le -\text{(rの正当な評価値)} \\ \betaxx{k+1} & \ge -\text{(rの正当な評価値)} + \deltaxx{k} \end{aligned} \right. \end{equation} \tag{4} \label{eqn04}

\deltaxx{k} は変更後のalpha_beta()のループ(B)に入る直前に0を代入され、(c')で上方修正のみされ得るから非負である。その上限は、alpha_beta()の呼び出し深さ k+1 で今から探索しようとするノードsの親ノードp（呼び出し深さ k で探索中）の子の評価値の最大値V_{max}から \alphaxx{k}を引いた値である：
\begin{equation} \deltaxx{k} \le V_{max} - \alphaxx{k} \end{equation} \tag{5} \label{eqn05}
\begin{equation} V_{max} = \max{\{\text{(sの親ノードpの子の評価値)}\}} \end{equation} \tag{6} \label{eqn06}
「sの親ノードpの子」という言い方が分かりにくければ、「sとsの兄弟ノードを合わせたもの」と言い換えても良い。 V_{max}はそれらの評価値を親ノードp視点の符号で見たときの最大値を意味する。

で、 \betaxx{k+1}を「 -\text{(rの正当な評価値)} + V_{max} - \alphaxx{k}」より小さくすると、alpha_beta()の呼び出し深さ k でのオーダリング（疑似コードの(a)で生成される指し手moveの生成順）依存で、探索結果がファンタジーとなる危険領域に突入する危険性が生じる。

一方、チャトランガ系のゲームでは一般に同じ盤面に至るゲームの進行手順が複数あり、盤面を指定しただけではその親局面が定まらない。

ここまで書いたらﾜｶﾙと思うが、つまりは盤面を指定しただけでは親局面の子の集合が定まらず、当然式 \eqref{eqn06}で定義される V_{max}もまた一意に定まらず、 \betaxx{k+1}の下界を与える「 -\text{(rの正当な評価値)} + V_{max} - \alphaxx{k}」も定まらないのである。

従い、盤面だけから生成したハッシュをキーとする関数としてβ値を与えることはできない。（やったら探索結果がファンタジーとなる危険性が生じる。）

尾張に向かって

以上で当エントリのタイトルを回収したが、さらに具体的なゲームとして将棋を想定した場合、置換表で正しい探索結果を得るためにはさらに厳しい条件をクリアせねばならないというしょっぱい話がこの後続く……

もしチェスと同じ調子で置換表を作った場合、そいつはあんまり宜しくない、というようなことをこの後書く。

参考文献

[1] 保木邦仁. コンピュータ将棋における全幅探索とfutility purningの応用. 情報処理. 2006, 47, 8, p.884-889

*1:探索窓を半開区間[alpha, beta)と考えたい人も居るかもしれないが、Nega-alpha法を考える限り閉区間と考えた方が式(3)から式(4)への移行を不等号を自然な形で行えて話の通りが良い。

*2:変更後のコードにおいて、再帰呼び出しk段目を実行中のalphaは定数なのでこれは一意の閉区間を指す。

*3:alpha_beta()のとある呼び出し深さkでの探索における(b)において、rの正当な評価値を見出す前に、早すぎるβカットが生じることによる。

いまさら聞けないはてなブログでの連立方程式の書き方

lifehack

式をまとめる括弧無し かつ 式ごとに番号を付けるﾊﾟﾃｨｰﾝ

ソース：

[tex:
\begin{align}
    E &= mc^2 \tag{2} \\
    F &= ma \notag \\
    F &= ma' \tag{3} \\
\end{align}
]

結果：

\begin{align} E &= mc^2 \tag{2} \\ F &= ma \notag \\ F &= ma' \tag{3} \end{align}

Geminiに聞いた、

式をまとめる括弧有り、かつ式毎に番号を付けるﾊﾟﾃｨｰﾝ

ソース：

[tex:
\left\{
\begin{eqnarray}
    E &= mc^2 \tag{2} \\
    F &= ma \notag \\
    F &= ma' \tag{3}
\end{eqnarray}
\right.
]

結果:

\left\{ \begin{eqnarray} E &= mc^2 \tag{2} \\ F &= ma \notag \\ F &= ma' \tag{3} \end{eqnarray} \right.

eqnarrayはamsmath パッケージで非推奨とされており、このような場合subequationsを使うものらしいが、はてなブログのMathJax（？）環境ではsubequationsがエラーとなり、使えないらしいから仕方が無い。
括弧が左に寄ってしまう不格好さはGME0BNのテクノロジーでは如何ともし難い……

式をまとめる括弧有り、かつ全体に番号を1個付けるﾊﾟﾃｨｰﾝ

これならば近代的な書き方ができうる。
ソース:

[tex:
\begin{equation}
\left\{
    \begin{aligned}
    E &= mc^2 \\
    F &= ma \\
    F &= ma'
    \end{aligned}
\right.
\end{equation} \tag{1}
]

結果：

\begin{equation} \left\{ \begin{aligned} E &= mc^2 \\ F &= ma \\ F &= ma' \end{aligned} \right. \end{equation} \tag{1}

つなみにeqnarrayを使っても同様の仕上がりとなる。
ソース:

[tex:
\left\{
    \begin{eqnarray}
    E &= mc^2 \\
    F &= ma \\
    F &= ma'
    \end{eqnarray}
\right. \tag{1-with-eqnarray}
]

結果：

\left\{ \begin{eqnarray} E &= mc^2 \\ F &= ma \\ F &= ma' \end{eqnarray} \right. \tag{1-with-eqnarray}

式をまとめる括弧有り、かつ式番号無しのﾊﾟﾃｨｰﾝ

式番号が不要ならequation使用時は明示的に \notag を書かねばならない。\tag{} を省略しただけだと勝手に連番が降られる。
また、式番号有りのときデフォルトで \displaystyle だったものがそうでなくなるので、\displaystayle を維持したい場合は明示的にそう書く必要がある、
ということらしいのだが、はてなブログでは \displaystyleを書いてもどことなく効果が薄い。（数式番号有り時と同じようなセンタリングにならない。）
とりま一応明示的に書いてはおく……
ソース:

[tex: { \displaystayle 
\begin{equation}
\left\{
    \begin{aligned}
    E &= mc^2 \\
    F &= ma \\
    F &= ma'
    \end{aligned}
\right.
\end{equation} \notag
}]

結果：

{ \displaystyle \begin{equation} \left\{ \begin{aligned} E &= mc^2 \\ F &= ma \\ F &= ma' \end{aligned} \right. \end{equation} \notag }

ちなみにeqnarray使用時は単に\tag{} を省略するだけで良い。
\displaystayle を明示的に書かねばならないはずだがはてなブログでは効果が薄いのはequation使用時と同じ。
ソース:

[tex: { \displaystyle
\left\{
    \begin{eqnarray}
    E &= mc^2 \\
    F &= ma \\
    F &= ma'
    \end{eqnarray}
\right.
}]

結果：

{ \displaystyle \left\{ \begin{eqnarray} E &= mc^2 \\ F &= ma \\ F &= ma' \end{eqnarray} \right. }

いじょ

置換表2024 最終章（早いな；；；

lifehack AI 置換表

昨日のエントリの

(r個のシンボルに基づくXORベースの64 bitハッシュの衝突確率) = 1 - ( 1 - 1/(2^64) )^( Σ[n=1..floor[r/2]]{ C(r, n) } )

と、

これはXORするシンボルの数を増やしていることになるので、ハッシュの衝突確率はその分増大（劣化）する

というのは撤回死体、orz

まず式の方は、正解から言うと64 bit整数のHS(s(k)) r-1個のXORをランダムな情報源とみなすという単純な仮定の下では、

(r個のシンボルに基づくXORベースの64 bitハッシュの衝突確率) = 1/(2^64)

という単純な結論にしかならない。

昨日の間違った式は、r項のXORを2項に分割するそれぞれの仕方
（Σ[n=1..floor[r/2]]{ C(r, n) }通り）について、XOR結果がPに一致するか否かが独立であるとみなしてゐる。（ ( 1 - 1/(2^64) )の冪乗であるあたりがそれ。）

しかし実際は、

A(1) (+) ( A(2) (+) A(3) (+) ... (+) A(r) )

がPと一致したらどう上記以外の2項のXORに分解しても結果はPに一致するし、Pと一致しなかったらどう2項のXORに分解しても結果はPに一致しない、という具合で、最初の2項への分割（任意）の結果に対して残りの分割の結果が完全に従属するから全く独立では無いから間違ってゐる、、、

「ハッシュの衝突確率はその分増大（劣化）する」のくだりについては、なんかXORするHS(s(k))が増えれば増えるほどPとの衝突確率が増えるとかどう考えてもおかしいやんか；；；

というわけで真実は64 bit整数のHS(s(k)) r-1個のXORをランダムな情報源とみなすという単純な仮定の下では

(r個のシンボルに基づくXORベースの64 bitハッシュの衝突確率) = 1/(2^64)

ぐらいのことしか言えない、

置換表2024

AI lifehack 置換表

今日わXORベースのハッシュの衝突確率についてチョットイイ話をする、

定義

ここでハッシュとは、n種類中のr個のシンボルで表せる何かであるところのX（簡単のためrが一定として、最大C(n, r)種類の何かのﾌﾞﾂ。ここでC(n, r)はコンビネーション)を、0～C(n, r)-1よりかなり小さい値域の整数に対応付けたものを指す。

さらに、ハッシュはハッシュでもXORベースのハッシュとは、以下の手段で作ったハッシュH(X)を（ここでは）指す。

ハッシュシード HS(s(k))
n種類のシンボルs(k) (k=1..n)それぞれに互いに異なるランダムなm bitの整数を割り当てたもの。
ハッシュH(X)
r個のシンボルs(k(i)) (i=1..r) で構成されるXに対し、次式で計算した値：

H(X) = HS(s(k(1))) (+) HS(s(k(2))) (+) HS(s(k(3))) (+) ... (+) HS(s(k(r))) --- (1)

ここで、演算子「(+)」はXORを意味する*1。

この主たる用途は置換表である。以下、HS(s(k))を64 bit整数（値域0～2^(64-1)）とする。

置換表1: 素数で割るタイプ

HS(s(k))の値域を64 bit整数とすれば式(1)よりH(X)も64 bit整数となり、置換表をサイズ（要素数）M（ただしM < 2^64）の配列として、

H(X) % M

で即置換表の配列のindexが得られてそこにXの情報を格納できうる。
ただしMは素数である方が良い。これの説明のは整数に関する除法の定理で
ｶﾝﾀﾝ……

整数に関する除法の定理
すべての整数aと正の整数bに対して,
a = bq + r (0≦r < b)
を満たす整数(q, r)がただ1組存在する、

ここではaがH(X)、bが置換表のサイズM、rがindex kにあたる：

H(X) = Mq + k (0≦k < M)

置換表としてせっかく用意した要素数Mの配列を有効活用するには、最大C(n, r)種類のうちからランダムに選んだXのハッシュH(X)に対して、index kが0..M-1の範囲で均等に出現していただきたい。

ところが、H(X)とMが共通の約数c (c>1)を持つとすると、適当な整数H'(X)、m'、k'を用いて

H'(x)c = (m'c)q + k'c (0≦k'c < m'c)

と書きうる*2 。

辺々cで割ると

a' = (m')q + k' (0≦k' < m')

となって k'≡a' (mod m') に他ならず、kは、せっかく用意した配列のサイズMに対し、m'=M/c個のバリエーションしかとり得ないことがﾜｶﾙ。

ランダムに選んだXのH(X)の分布もランダムだと仮定すると、H(X)がcの倍数になる確率は1/c。故に、indexのバリエーションの期待値は

(1/c)(M/c) + (1-1/c)M --- (2)

となり、Mより目減りする。仮にH(X)とMの共通の約数がc一個とかではなくていっぱいあったりすると、例えばc, d, eを素因数として、全てのH(X)を見渡したときにc、d、e、...の最大w個見いだせる、とかだったりすると、indexのバリエーションの期待値は

( (1/c)^2 + (1/d)^2 + (1/e)^2 + ... ) M + ( 1-(1/c) )( 1-(1/d) )( 1-(1/e) )M

という具合で禿げしくMより目減りする、、、

いや正確にはこうか……：

( Σ[ i=1..C(w, i) ]{ (p(i))^2 } ) M + ( π[ i=1..C(w, i) ]{ 1-p(i) } ) M --- (3)

ここでp(i)は、H(X)とMの共通の約数であるところの素因数（全てのH(X)を見渡したとき最大w個見いだせる）からi個取り出したものの積のみがH(X)とMの共通の素因数である確率。
ここで、H(X)とMがc^mを約数として持つ場合は、m個のcはそれぞれ区別する*3。

一方、ここまでc>1という仮定でやっているが、仮にc=1（またはc=M）とすると、indexのバリエーションの期待値は、式(2)からﾜｶﾙようにMに一致する。すわなち、MはいかなるH(X)に対しても素であること（MとH(X)の共通の約数cがいかなるH(X)に対しても1（とM自身）のみであること）が正義、というわけで、そうするにはMを素数にするしかない。

置換表2: 割り算を使わないタイプ

置換表1は2進数の単なるシフトで済まない真正の割り算を伴うので、高速にハッシュを生成したい向きには不評である。発想を転換してMを2の累乗にすると掛け算による解決ができうる:

k = ( (H(X) / M) * (適当な素数) + H(X) ) % M

ここでMは2の累乗であるから、仮にm bitとして、H(X)/Mはm bit右シフト、最後の % Mは(2^m)-1との論理積で済む。
幸いC/C++では符号無し整数の演算は、結果の値がその整数型の整数表現で表現できない場合にラップアラウンドするだけで例外も何も生じないことが保証されている。おあつらえ向きの素数は(2^32)-1である：

k = ( (H(X) >> m) * (u64)0xffffffff) + H(X) ) & ( (2^m)-1)

なんか64 bit整数の掛け算は遅そうくね？と不安視する向きは、次の式でも良い：

k = ( (u32)( (H(X) >> 32) ) * (u32)0xffffffff) + (u32)( H(X) ) ) & ( (2^m)-1)

普通m < 32なので、後者の式ではせっかく用意したHS(s(k))のうち第m bit～第31 bitの0/1がindexに反映されないのがもったいない気がするが、とりまH(X)がランダムに分布するなら上の式でindex kも0..M-1の範囲をランダムに分布する（と思う（ﾏﾃ；

置換表エントリの衝突

最大C(n, r)種類のXに対し、Xの情報を格納するための配列をM要素しか用意しないのであるから、同じindex kを示すXがC(n, r)/M個ぐらい存在するのは当然である。すわなち、(C(n, r)/M)/(C(n, r)) = 1/M ぐらいの確率で異なるXについてindexが同じ値kとなり、同じ配列要素が割り当てられる。これをここでは置換表エントリの衝突と呼ぶ。この衝突自体はC(n, r) >> Mである以上避けられないが、良く知られた対策を行いさえすれば、間違った（目的とするXとは異なるﾌﾞﾂの）情報を引き出してしまう危険性は無くせる*4ので詳細略。

ハッシュの衝突

本題に近づいてｷﾀ、

ハッシュの衝突というのは、異なるXに対し同じハッシュ値H(X)となることを指す。

置換表というものはクリアしながら使わねばならないという都市伝説が広く膾炙されているが*5、いくつかの条件を満たせば一切クリアせずに使い続けて問題を生じない。その条件の一つが

ハッシュの衝突が無い（とみなせること）

である。

置換表の情報は有用なのでかなうことなら一生クリアせずに使い続けたいが、ハッシュの衝突という現実があるからそうもいかない。
いつ置換表をクリアすべきか、ハッシュの衝突確率に基づき基準を出す。

XORハッシュの衝突確率

ｶﾝﾀﾝのためまず2項のXORについて考える。A(+)BがPに一致する条件は何か？
これはPとAの差異があるビットと、Bの値1のビットが完全一致することだる：

例：A(+)BがPに一致する例：
A=1000101101101
B=1111101010110
P=0111000111011

AとPの違いのあるビットを1、違いの無いビットを0で表したものがBに他ならない。

んまービット毎のXORなのだから当然っていやー当然……
こうなる確率は、Aがランダムな64 bit整数と仮定して良ければ1/(2^64)。

次に式(1)のように多項のXORを考ゆる、いちいちHS(s(k))と書くのはﾒﾄﾞいので、A(1)、A(2)、A(3)、...、A(r)のXORというように書くとすると、

A(1) (+) A(2) (+) A(3) (+) ... (+) A(r)

が偶然Pに一致する確率を問う話となる、

これわ

A(1) (+) ( A(2) (+) A(3) (+) ... (+) A(r) )

と考えたら2項のXOR A (+) BがPに一致する話に帰着する。

で、この伝による2項のXORへの帰着の仕方がΣ[n=1..floor[r/2]]{ C(r, n) }通りあり、衝突しないのはその全ての2項のXORで衝突が起きない場合に限られるから、衝突確率は次式となる：

(r個のシンボルに基づくXORベースの64 bitハッシュの衝突確率) = 1 - ( 1 - 1/(2^64) )^( Σ[n=1..floor[r/2]]{ C(r, n) } )

■ [追記] 撤回すた！9/10のエントリ参照。

細菌のハッシュの著名な応用分野では1つの結果を出すのに√10億 = 31623個（適当）ぐらいハッシュH(X)を使うので、

(1-(r個のシンボルに基づくXORベースの64 bitハッシュの衝突確率))^31623^n ≦ (適当な基準(0.95とか))

を満たす最大のnの値を求め、n手思考する度に置換表をクリアすれば宜しい

補足

ここまでH(X)がランダムに分布すると仮定してきたが、XORベースのハッシュの場合本当に成立しているのだろうか、

式(1)をみたらこれは全64 bitの各bitについて、r個の{ 0, 1 }のパリティーを計算しているのに他ならない。

HS(s(k)) 1個についてみたら、HS(s(k))以外のr-1個のXOR結果に対しHS(s(k))をXORすることにより、全64 bitのうち複数bitが同時に変化するので、各bitのパリティー計算結果は独立ではないのだが、rが大きくなるにつれあるHS(s(k))によってもたらされたbit間の非独立性（相関）が別のHS(s(k'))多数によって打ち消され、独立とみなし得る（ような気がする（ﾏﾃ；
あるビットが1になる確率はランダムな{ 0, 1 } r個のパリティーなので1/2。なので、独立とみなし得るなら、H(X)がある値に一致する確率は(1/2)^64となり、64 bitの整数のどれもがこの等確率で選ばれる。すわなちXORベースのハッシュにおいても。C(n, r)種類の中からXを選ぶときの分布がランダムならH(X)はランダムに分布するとみなし得る、

備考

ここまでXORするシンボルの数をr個固定として議論すた、
置駒の移動の処理はそれで良いのだが（駒の移動の履歴をハッシュに反映させるわけにはいかないため、差分計算においては、変更する前のシンボルをXORで打ち消した後、新しいシンボルをXORする。この結果r個が保たれる）、持駒については履歴を消す必要が無いため、持駒P 1～n枚のハッシュに対し、持駒P n+1枚に相当するハッシュをXORするだけでPの枚数n→n+1の差分計算完了とする実装が有り得る。これはXORするシンボルの数を増やしていることになるので、ハッシュの衝突確率はその分増大（劣化）する、
■ [追記] 撤回すた！9/10のエントリ参照。

おわりに

本来なら線形分離2023という記事をクリスマス頃に書くはずだったのだが
単に記事を書き忘れているだけであることをここに宣言す、

*1:当エントリでは演算子「^」は冪乗の意味で使う。

*2:cはaとbの最大公約数ではなくて単なる約数なのでkもcの倍数であることはユークリッドの互除法のやつのような証明は不要で言える(と思う)。

*3:区別したくなければ取り出し方の式が単純なコンビネーションで済まず、対応する確率の定義とともに工夫せねばならない。

*4:正確には、良く知られた対策により、誤った情報を引き出してしまう確率がハッシュの衝突確率に帰着する。

*5:脳内調べ