df-pn探索のコード

ようわからんが、df-pn探索アルゴリズムをC++で書き下してみる。

基本形(?)

多分こんな感じ…？

#include <limits.h>

class Node {
public:
  void ResetChildNode();
  Node& NewChildNode();
  Node& NewNullNode();
  bool HasValue();
  void Dispose();
};

#define INFINITE    INT_MAX

static int depth = 256;           // 探索深度
static int prf_max = INFINITE;    // 証明数上限
static int dis_max = INFINITE;    // 反証数上限
/*= 探索深度は偶数のみ許す。
 */

void dfpn_traverse(Node& nd, /*out*/ int& prf, /*out*/ int& dis)
{
  int subprf, subdis;

  nd.ResetChildNode();
  Node& nxnd = nd.NewChildNode();
  if ((depth & 0x1) == 0) {       // (攻方の手番)
    if (!nxnd.HasValue()) {       // (攻方に合法手無し(受方による自明な詰みが成立))
      prf = INFINITE;
      dis = 0;
    } else if (depth == 0) {      // (所定の探索深度に達したが結論が出ていない)
      prf = 1;
      dis = 1;
    } else {                      // (所定の探索深度に達しておらず結論が出ていない)
      --depth;
      prf = INFINITE;
      dis = 0;
      do {
        dfpn_traverse(nxnd, /*out*/ subprf, /*out*/ subdis);
        if (dis <= INFINITE - subdis)
          dis += subdis;
        else
          dis = INFINITE;         // (オーバーフロー対策)
        if (dis >= dis_max)
          return;                 // 反証数上限カット
        dis_max = dis;
        if (subprf < prf)
          prf = subprf;
        if (prf >= prf_max)
          return;                 // 証明数上限カット
        prf_max = prf;
        nxnd.Dispose();
        nxnd = nd.NewChildNode();
      } while (nxnd.HasValue());
      ++depth;
    }
  } else {                        // (受方の手番)
    if (!nxnd.HasValue()) {       // (受方に合法手無し(攻方による自明な詰みが成立))
      prf = 0;
      dis = INFINITE;
    } else if (depth == 0) {      // (所定の探索深度に達したが結論が出ていない)
      prf = 1;
      dis = 1;
    } else {                      // (所定の探索深度に達しておらず結論が出ていない)
      --depth;
      prf = 0;
      dis = INFINITE;
      do {
        dfpn_traverse(nxnd, /*out*/ subprf, /*out*/ subdis);
        if (prf <= INFINITE - subprf)
          prf += subprf;
        else
          prf = INFINITE;         // (オーバーフロー対策)
        if (prf >= prf_max)
          return;                 // 証明数上限カット
        prf_max = prf;
        if (subdis < dis)
          dis = subdis;
        if (dis >= dis_max)
          return;                 // 反証数上限カット
        dis_max = dis;
        nxnd.Dispose();
        nxnd = nd.NewChildNode();
      } while (nxnd.HasValue());
      ++depth;
    }
  }
  nxnd.Dispose();
}

いや知らんけど。
なお反復深化や局面辞書による効率化やGHI対策などは一切入っていない。
証明数、反証数いずれについても上限に達した時点で即座に探索を打ち切り、子ノードに残りがあった場合もそれらを見ない。仮にαβ探索でα以下やβ以上の出現で同様の打ち切り方をすると完全探索にならないが、詰み証明でdf-pnを使う場合については、

• 証明数については0か0より大か
• 反証数については∞か有限か

のみに興味があり、カットの基準量を二値的にしか扱わないのでこれでも特に問題ないはずだが、、*1。

簡単化の件について

コードが冗漫な気がするがαβ→ネガマックスネガαβみたいに簡単にするいい手が思い浮かばないorz
まあ1000行ぐらいある関数とか日常的に目にするからこの程度は許容範囲内としよう、、

23:30追記

妄言があったので取り消しておいた。詰みを証明する立場からは照明数や反証数について二値的にしか興味を持たなくていいというのは正しいと思うが、それ以外の点が悉くアレだったorz

*1:ていうか通常のαβ探索においてノードの評価値がそのノードのみ見て決められるのに対し、証明数や反証数は子ノードを見ないと決められないから、関数入り口ではハネられない。多分どうあがいても上のコードのような打ち切り形態にならざるを得ない。