16

転置テーブルで強化されたアルファベータ最小最大プルーニングを実装しようとしています。この疑似コードを参照として使用します。

http://people.csail.mit.edu/plaat/mtdf.html#abmem

function AlphaBetaWithMemory(n : node_type; alpha , beta , d : integer) : integer;
    if retrieve(n) == OK then /* Transposition table lookup */
        if n.lowerbound >= beta then return n.lowerbound;
        if n.upperbound <= alpha then return n.upperbound;
        alpha := max(alpha, n.lowerbound);
        beta := min(beta, n.upperbound);
    if d == 0 then g := evaluate(n); /* leaf node */
    else if n == MAXNODE then
        g := -INFINITY; a := alpha; /* save original alpha value */
        c := firstchild(n);
        while (g < beta) and (c != NOCHILD) do
            g := max(g, AlphaBetaWithMemory(c, a, beta, d - 1));
            a := max(a, g);
            c := nextbrother(c);
    else /* n is a MINNODE */
        g := +INFINITY; b := beta; /* save original beta value */
        c := firstchild(n);
        while (g > alpha) and (c != NOCHILD) do
            g := min(g, AlphaBetaWithMemory(c, alpha, b, d - 1));
            b := min(b, g);
            c := nextbrother(c);

    if g <= alpha then 
        n.upperbound := g; 
        store n.upperbound;
    if g >  alpha and g < beta then
        n.lowerbound := g; 
        n.upperbound := g; 
        store n.lowerbound, n.upperbound;
    if g >= beta then 
        n.lowerbound := g; 
        store n.lowerbound;
return g;

このアルゴリズムに対する 3 つの質問:

  1. 保存された各転置テーブル エントリに深さ (= リーフ レベルまでの距離) を格納し、entry.depth>=currentDepth (= エントリがリーフ レベルからほぼ等しい) の場合にのみエントリを使用する必要があると思います。それは上記の疑似コードには示されておらず、そこでは議論されていません。それを正しく理解していることを確認したかったのです。

  2. 各ポジションのベストムーブを保存して、ムーブオーダーに使用し、検索が停止した後にベストムーブを抽出したいと考えています。純粋な最小値と最大値では、どちらの動きが最適かは明らかですが、アルファ ベータ カットオフで反復する場合、どの動きが最適でしょうか? 特定の位置での最良の動きは、ループが終了したときに見つかった最良の動きであると仮定できますか (カットオフの有無にかかわらず)?

  3. このアルゴリズムを反復深化スキームで実行する場合、各深さが増加する前に転置テーブルをクリアする必要がありますか? 前回の反復から保存された位置を使用したいと思いますが、情報がより深い検索に適しているかどうかはわかりません (テーブル エントリの深さを確認するときである必要があります)。

4

1 に答える 1