連載やねうら王miniを強くしよう！7日目

今回は、長編(1000手～)の協力詰めが解けるsolverにします。

工夫その1 . 不詰めの証明

よく考えてみると、5手先まで読んだときにそれ以上王手が続かない局面は100手先まで読んだところで詰みません。

そこで、TTEntryに残り探索depthを入れるのと、詰まないことが確定しているならその旨も保存しておくべきです。

具体的には、王手が続かなくなった局面について保存するときにdepthを無限大としてTTEntryに格納しておきます。王手が続かない以上、いくら残り探索深さがあったところで詰みませんので。

この「無限大」を表現するのは、最大探索深さ(MAX_PLY)で良いでしょう。これ以上深くなることは想定していないので…。

次に、あるnodeの子(あるnodeから1手進めた局面)が全部depthが無限大で詰まないことがわかっているなら、そのnodeも詰まないはずです。

そこでそのようにプログラムを修正すればもっと効率的に探索できるはずです。

詰まないことに対する定式化

上の事実は、もう少し別の書き方をすると、あるnodeの子が3つしかないとして(ある局面で指し手が3つあったとして)、それぞれ3手で詰まない、5手で詰まない、無限大で詰まない、ということがわかっている場合、このnodeは、3 + 1 = 4手では詰まない(もっと深さがあれば詰むかも知れない)ということがわかります。

すなわち、あるnodeのTTEntryに書き込むべきdepthの値は、子のnodeが置換表に書いたdepth (これは子のnodeの数だけある)の最小値 + 1 ということがわかります。実際には、no_mate_depthが無限大(MAX_PLY)のときは無限大に1を足すのは少し気持ち悪いので、

no_mate_depth = min(child_no_mate_depth +1, no_mate_depth);

のようにしておくといいと思います。

工夫その2. 置換表に指し手を格納することによる高速化

いま、詰まないことがわかっている局面(no_mate_depth == MAX_PLYである局面)のことを、確定局面と呼ぶことにします。

あるnodeの子nodeが1つを除いて確定局面である場合、この確定局面ではない子nodeだけ調べれば良いです。この局面では1手しか応手がないので、これをone replyと呼ぶことにします。

この子nodeに進むための指し手を置換表に登録しておけば、このnodeの指し手生成を省略できますし、また、確定局面だと判明している子nodeに進んで置換表をprobe()する手間が省けます。

工夫その3. 置換表にClusterを導入する

Clusterについてはすでに説明しました。

工夫その4. 置換表に世代を導入する

すべての子が確定局面であるなら、そのnodeは確定局面です。
このように確定局面は親方向に伝播していきます。

反復深化をしていくときに探索開始局面から最初に辿りつくのは、末端の確定局面ではなく、その親や、その親の親、…、と言った、親nodeです。ということは、確定局面の親を持つなら、その子の情報は置換表上には要らないのです。(別の手順でこの子nodeに到達することもありますが、それはいま考えないことにします。)

ということで、置換表からは、一番親の確定局面だけを残して、その子の情報は捨てたいのです。

従来、こういう目的では置換表用のGC(garbage collection)が実装されてきました。過去の長編詰将棋を解く論文を見ているとGCを実装しているものがよくあります。

現代的な視点では、これらはGCでやるべきではないと思います。
もう少し簡単に実装できるからです。

それが世代という概念です。置換表に世代という16bitの整数カウンターがあるとします。

協力詰めでは反復深化のごとにこのカウンターを1足します。

また、TTEntryにも世代を持たせて、TTEntry::save()のときに、この置換表(TranspositionTable)の世代を書き込んでおきます。probe()に成功したときもTTEntryの世代を置換表の世代にします。(これを世代のrefreshと呼びます。)

こうしておいて、置換表が衝突してCluster内でrehashするときに、世代の近いTTEntryのほうを優先して残すのです。世代が離れているということは前回の反復深化でrefreshされていない、すなわち、使われていなかったことを意味するので、そのnodeの親は確定局面である可能性が高いからです。

このように置換表に世代という概念を導入することで、GCは不要になります。(GCの動作に近い動作になります。)

工夫まとめ

工夫その1.で確定局面が親に伝播(子がすべて確定局面なら親も確定局面)するようになりました。

工夫その2.で、子が1つだけ非確定局面であるnodeでは、他の子(確定局面の子)を辿らないようになりました。

辿らないということはprobeされないということで、工夫その4.により、refreshもされなくて、置換表の世代とTTEntryの世代とがかけ離れていくのでこれらは、工夫その3.のClusterを導入したときに、rehash処理のときに捨て去られる対象となります。

このように、以上の工夫1.～4.は相互に絡み合って効果を発揮するようになっています。

工夫その5.反復深化は2手ずつ

何手で詰むかわからないので1手ずつ深くしていきながら詰むかどうかを調べています。1手ずつ深くしていきながら探索することを反復深化(iterative deeping)と呼びます。この頭文字を取って、id(id_loop)と書いてあります。Stockfishもそんな関数名になっていたと思います。

この反復深化、2手ずつ進めたほうが全体的には高速であるようです。

探索の色んな問題が絡むので2手ずつ進めたほうがいいかどうかは一般的には言えませんが、とりあえず協力詰めでは2手ずつ進めて問題なさげでかつ速くなるというのが結論のようです。

工夫その6.循環局面の検出

協力詰めにおいては連続王手の千日手と劣等局面の判定については難しいところがあるようです。

劣等局面のほうが優れているケース
 協力詰めsolverを並列化するとGHI問題に行き当たる件

上記の話題はまだ調査中で結論が出ていないので、とりあえず保留しておきます。

長編は解けるようになったのですか？

協力詰めsolverを公開します

協力詰めの最長編である『寿限無3』(49909手) が解けました。
序盤で変化の多い一部の長編を除き、すべて解けるようです。

上の協力詰めsolverをダウンロードすると、なかにソースコードが入っています。
(開発中のやねうら王miniのソースコードを流用しています。)

やねうら王miniのソースコードの公開を待ちきれないという人は、上の協力詰めのソースコードをいじってみると良いのではないでしょうか。

協力詰めの論文

協力詰めの論文としては以下の論文ぐらいしかありません。

反復深化探索に基く協力詰将棋の解法
http://mm.cs.uec.ac.jp/doc/ipsj2002.pdf

この論文に気づいたのは私が協力詰めsolverをある程度書き上げてからだったのですが、比較的よく出来た論文だと思います。(上から目線でスマソ)

one replyのアイデアは上記の論文からもらいました。

ただ、上記の論文は現代的な観点で見ると、置換表のGCを実装していたりして実装が複雑だなと思いました。

あと、確定局面に関しては、上の「詰まないことに対する定式化」で書いたような方法で親nodeに伝播させていくほうがシンプルで、かつ枝刈り性能がいいはず。

ここまでのまとめ

長編協力詰めが解ける協力詰めsolverが完成しました。これで終盤の探索についての理解が深まったかと思います。

次回からは新連載、「やねうら王miniを強くしよう2」が始まります。お楽しみに！

今回のソースコード

おまけとして、以下に今回の協力詰めのソースコード(シングルスレッド版)を貼り付けておきます。

あと、置換表の使用率(hashfull)を計算する関数については本連載中には解説していませんでしたが、USIプロトコルでは千分率で返すことになっているのでTTEntryの先頭1000個、サンプリングしてそのTTEntryの世代を調べることで置換表使用率を計算できるという仕組みになっています。(以下のソースコードを参照のこと。)

置換表使用率の出力を実装していないソフトも結構あるとは思いますが、これを実装することにより、置換表にどれくらいのメモリを割り当てるのが適切なのかがわかるようになるので、是非実装されることをお勧めします。

#include "../shogi.h"
#ifdef COOPERATIVE_MATE_SOLVER

#include "../position.h"

// --- 協力詰め探索

namespace CooperativeMate
{
  struct TranspositionTable;

  struct TTEntry {

    // この深さにおいて詰まない
    uint32_t depth() const { return depth32; }

    // この局面で指し手が1つしかないときに指し手生成処理を端折るための指し手
    Move move() const { return (Move)move16; }

    int64_t key() const { return key64; }

    // TTEntryの世代(置換表側で世代カウンターで管理)
    uint16_t generation() const { return gen16; }
    void set_generation(uint16_t g) { gen16 = g; }

    // 置換表のエントリーに対して与えられたデータを保存する。上書き動作
    void save(Key128 key_, uint32_t depth, Move move) { depth32 = depth; key64 = key_.p(1); move16 = (int16_t)move; }

    // 与えられたkey_がこのTTEntryに格納されているかを判定する。
    bool found(Key128 key_) const { return key64 == key_.p(1); }

  private:
    friend struct TranspositionTable;

    uint64_t key64;
    uint32_t depth32;   // この残り探索深さにおいて詰まない
    int16_t move16;     // 1手しかないときの指し手
    int16_t gen16;      // 置換表の世代
    // 8 + 4 + 2 + 2 = 16
  };

  struct TranspositionTable {

    // 置換表のなかから与えられたkeyに対応するentryを探す。
    // 見つかったならfound == trueにしてそのTT_ENTRY*を返す。
    // 見つからなかったらfound == falseで、このとき置換表に書き戻すときに使うと良いTT_ENTRY*を返す。
    TTEntry* probe(const Key128 key, bool& found) const
    {
      TTEntry* const tte = &table[(size_t)key.p(0) % clusterCount].entry[0];
      for (int i = 0; i < ClusterSize; ++i)
      {
        // returnする条件
        // 1. keyが合致しているentryを見つけた。(found==trueにしてそのTT_ENTRYのアドレスを返す)
        // 2. 空のエントリーを見つけた(そこまではkeyが合致していないので、found==falseにして新規TT_ENTRYのアドレスとして返す)

        bool emptyEntry = !tte[i].key(); // 空のエントリーであるか
        if (emptyEntry || tte[i].found(key))
        {
          if (tte[i].generation() != generation16 && !emptyEntry)
            tte[i].set_generation(generation16); // Refresh

          return found = !emptyEntry, &tte[i];
        }
      }

      // 一致するhash keyが格納されているTTEntryが見つからなかったし、空のエントリーも見つからなかったのでどれか一つ犠牲にする。
      TTEntry* replace = tte;
      for (int i = 1; i < ClusterSize; ++i)

        // ・深い探索の結果であるものほど価値があるので残しておきたい。depth × 重み1.0
        // ・generationがいまの探索generationに近いものほど価値があるので残しておきたい。geration×重み 8.0
        // 以上に基いてスコアリングする。
        // 以上の合計が一番小さいTTEntryを使う。

        if ( replace->depth() + (uint16_t)(generation16 - replace->generation()) * 8
             >   tte[i].depth() + (uint16_t)(generation16 - tte[i].generation()) * 8 )
          replace = &tte[i];

      replace->set_generation(generation16);

      return found = false, replace;
    }

    // 置換表のサイズを変更する。mbSize == 確保するメモリサイズ。MB単位。
    void resize(size_t mbSize) {
      free(mem);

      // 2のべき乗にはしない。entryCountは偶数であることだけ保証する。
      // 先手と後手との局面はhash keyの下位1bitで判別しているので、
      // 先手用の局面と後手用の局面とでTTEntryは別のところになって欲しいから。
      clusterCount = (mbSize * 1024 * 1024 / sizeof(Cluster)) & ~UINT64_C(1);

      mem = calloc(clusterCount * sizeof(Cluster) + CacheLineSize - 1, 1);
      if (!mem)
      {
        std::cout << "failed to calloc\n";
        exit(EXIT_FAILURE);
      }
      table = (Cluster*)((uintptr_t(mem) + CacheLineSize - 1) & ~(CacheLineSize - 1));
    }

    // 置換表のエントリーの全クリア
    void clear() { memset(table, 0, clusterCount * sizeof(Cluster)); }

    // 世代カウンターをインクリメントする。
    void new_search() { ++generation16; }

    // 置換表使用率を調べる。世代が同じエントリーの数をサンプリングして調べる。
    int hashfull() const
    {
      // すべてのエントリーにアクセスすると時間が非常にかかるため、先頭から1000エントリーだけ
      // サンプリングして使用されているエントリー数を返す。
      int cnt = 0;
      for (int i = 0; i < 1000 / ClusterSize; ++i)
      {
        const auto tte = &table[i].entry[0];
        for (int j = 0; j < ClusterSize; ++j)
          if ((tte[j].generation() == generation16))
            ++cnt;
      }
      return cnt;
    }

    TranspositionTable() { mem = nullptr; generation16 = 0; resize(16); }
    ~TranspositionTable() { free(mem); }

    // CPUのcache line size(この単位でClusterを配置しないといけない)
    const int CacheLineSize = 64;

    // 1クラスターにおけるTTEntryの数
    static const int ClusterSize = 4;

    struct Cluster {
      TTEntry entry[ClusterSize];
    };

    // 確保されているClusterの先頭
    Cluster* table;
    // callocで確保したもの。64byteでalignしたのが↑のtable
    void* mem;

    size_t clusterCount;
    int16_t generation16;
  };

  // 協力詰めを解く。反復深化のループ。
  void id_loop(Position& root);

  // 協力詰め用のglobalな置換表。
  extern TranspositionTable TT;

} // end of namespace

#endif

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

#include "../shogi.h"

#ifdef COOPERATIVE_MATE_SOLVER

#include "../position.h"

// --- 協力詰め探索

namespace CooperativeMate

{

struct TranspositionTable;

struct TTEntry {

// この深さにおいて詰まない

uint32_t depth() const { return depth32; }

// この局面で指し手が1つしかないときに指し手生成処理を端折るための指し手

Move move() const { return (Move)move16; }

int64_t key() const { return key64; }

// TTEntryの世代(置換表側で世代カウンターで管理)

uint16_t generation() const { return gen16; }

void set_generation(uint16_t g) { gen16 = g; }

// 置換表のエントリーに対して与えられたデータを保存する。上書き動作

void save(Key128 key_, uint32_t depth, Move move) { depth32 = depth; key64 = key_.p(1); move16 = (int16_t)move; }

// 与えられたkey_がこのTTEntryに格納されているかを判定する。

bool found(Key128 key_) const { return key64 == key_.p(1); }

private:

friend struct TranspositionTable;

uint64_t key64;

uint32_t depth32; // この残り探索深さにおいて詰まない

int16_t move16; // 1手しかないときの指し手

int16_t gen16; // 置換表の世代

// 8 + 4 + 2 + 2 = 16

};

struct TranspositionTable {

// 置換表のなかから与えられたkeyに対応するentryを探す。

// 見つかったならfound == trueにしてそのTT_ENTRY*を返す。

// 見つからなかったらfound == falseで、このとき置換表に書き戻すときに使うと良いTT_ENTRY*を返す。

TTEntry* probe(const Key128 key, bool& found) const

{

TTEntry* const tte = &table[(size_t)key.p(0) % clusterCount].entry[0];

for (int i = 0; i < ClusterSize; ++i)

{

// returnする条件

// 1. keyが合致しているentryを見つけた。(found==trueにしてそのTT_ENTRYのアドレスを返す)

// 2. 空のエントリーを見つけた(そこまではkeyが合致していないので、found==falseにして新規TT_ENTRYのアドレスとして返す)

bool emptyEntry = !tte[i].key(); // 空のエントリーであるか

if (emptyEntry || tte[i].found(key))

{

if (tte[i].generation() != generation16 && !emptyEntry)

tte[i].set_generation(generation16); // Refresh

return found = !emptyEntry, &tte[i];

}

// 一致するhash keyが格納されているTTEntryが見つからなかったし、空のエントリーも見つからなかったのでどれか一つ犠牲にする。

TTEntry* replace = tte;

for (int i = 1; i < ClusterSize; ++i)

// ・深い探索の結果であるものほど価値があるので残しておきたい。depth × 重み1.0

// ・generationがいまの探索generationに近いものほど価値があるので残しておきたい。geration×重み 8.0

// 以上に基いてスコアリングする。

// 以上の合計が一番小さいTTEntryを使う。

if ( replace->depth() + (uint16_t)(generation16 - replace->generation()) * 8

> tte[i].depth() + (uint16_t)(generation16 - tte[i].generation()) * 8 )

replace = &tte[i];

replace->set_generation(generation16);

return found = false, replace;

}

// 置換表のサイズを変更する。mbSize == 確保するメモリサイズ。MB単位。

void resize(size_t mbSize) {

free(mem);

// 2のべき乗にはしない。entryCountは偶数であることだけ保証する。

// 先手と後手との局面はhash keyの下位1bitで判別しているので、

// 先手用の局面と後手用の局面とでTTEntryは別のところになって欲しいから。

clusterCount = (mbSize * 1024 * 1024 / sizeof(Cluster)) & ~UINT64_C(1);

mem = calloc(clusterCount * sizeof(Cluster) + CacheLineSize - 1, 1);

if (!mem)

{

std::cout << "failed to calloc\n";

exit(EXIT_FAILURE);

}

table = (Cluster*)((uintptr_t(mem) + CacheLineSize - 1) & ~(CacheLineSize - 1));

}

// 置換表のエントリーの全クリア

void clear() { memset(table, 0, clusterCount * sizeof(Cluster)); }

// 世代カウンターをインクリメントする。

void new_search() { ++generation16; }

// 置換表使用率を調べる。世代が同じエントリーの数をサンプリングして調べる。

int hashfull() const

{

// すべてのエントリーにアクセスすると時間が非常にかかるため、先頭から1000エントリーだけ

// サンプリングして使用されているエントリー数を返す。

int cnt = 0;

for (int i = 0; i < 1000 / ClusterSize; ++i)

{

const auto tte = &table[i].entry[0];

for (int j = 0; j < ClusterSize; ++j)

if ((tte[j].generation() == generation16))

++cnt;

}

return cnt;

}

TranspositionTable() { mem = nullptr; generation16 = 0; resize(16); }

~TranspositionTable() { free(mem); }

// CPUのcache line size(この単位でClusterを配置しないといけない)

const int CacheLineSize = 64;

// 1クラスターにおけるTTEntryの数

static const int ClusterSize = 4;

struct Cluster {

TTEntry entry[ClusterSize];

};

// 確保されているClusterの先頭

Cluster* table;

// callocで確保したもの。64byteでalignしたのが↑のtable

void* mem;

size_t clusterCount;

int16_t generation16;

};

// 協力詰めを解く。反復深化のループ。

void id_loop(Position& root);

// 協力詰め用のglobalな置換表。

extern TranspositionTable TT;

} // end of namespace

#endif

#include "../shogi.h"
#ifdef COOPERATIVE_MATE_SOLVER

#include "all.h"
#include "cooperative_mate_solver.h" 

using namespace std;
using namespace Search;

// --- 協力詰め探索

namespace CooperativeMate
{
  // 協力詰め用のMovePicker
  struct MovePicker
  {
    // ttMove = 置換表の指し手
    MovePicker(const Position& pos_,Move ttMove) : pos(pos_)
    {
      if (ttMove == MOVE_NONE)
      {
        // 協力詰めであれば段階的に指し手を生成する必要はない。
        // 先手ならば王手の指し手(CHECKS)、後手ならば回避手(EVASIONS)を生成。
        endMoves = (pos.side_to_move() == BLACK) ? generateMoves<CHECKS_ALL>(pos, currentMoves)
                                                 : generateMoves<EVASIONS_ALL>(pos, currentMoves);
      } else {
        // 置換表に載っていた指し手が一つしかないのはone replyなのでこれで指し手生成をはしょれる。
        *currentMoves = ttMove;
        endMoves++;
      }
    }

    // 次の指し手をひとつ返す
    // 指し手が尽きればMOVE_NONEが返る。
    Move next_move() {
      if (currentMoves == endMoves)
        return MOVE_NONE;
      return *currentMoves++;
    }

  private:
    const Position& pos;

    ExtMove moves[MAX_MOVES], *currentMoves = moves, *endMoves = moves;

  };

  TranspositionTable TT;

  // 現在の探索深さ
  int search_depth;

  // 詰みが見つかったか
  bool found_mate;

  // 協力詰め
  // depth = 残り探索深さ
  // no_mate_depth = この局面は、この深さの残り探索深さがあっても詰まない(あるいは詰みを発見して出力済み)
  void search(Position& pos, uint32_t depth , int& no_mate_depth)
  {
    // 強制停止
    if (Signals.stop)
    {
      no_mate_depth = MAX_PLY;
      return;
    }

    bool found;
    Key128 key = pos.state()->long_key();
    auto tte = TT.probe(key , found); // 置換表がヒットするか
    if (found && tte->depth() >= depth)
    {
      no_mate_depth = tte->depth();
      return;
      // このnodeに関しては現在の残り探索深さ以上の深さにおいて
      //不詰めが証明されているのでもう帰ってよい。(枝刈り)
    }

    StateInfo st;
    pos.check_info_update(); // legal()とgives_check()とCHECKSの指し手生成に先だって呼び出されている必要がある。

    MovePicker mp(pos, found ? tte->move() : MOVE_NONE);
    Move m;

    int replyCount = 0; // 確定局面以外の応手の数
    Move oneReply = MOVE_NONE;

    no_mate_depth = MAX_PLY; // 有効な指し手が一つもなければこのnodeはいくらdepthがあろうと詰まない。

    while (m = mp.next_move())
    {
      if (!pos.legal(m))
        continue;

      pos.do_move(m, st , pos.gives_check(m));

      // 経路を少し遡って、同じ局面があればこれは連続王手の千日手であり、
      // 残り深さ2手以上少ない状態で詰まないことは前回の反復深化のiterationで証明されているので
      // 枝刈りして良い。
      auto st = pos.state();
      auto key_now = st->long_key();
      for (int i = 0; i < 8; ++i) // とりあえず8*2 = 16手遡る
      {
        if (st->previous != nullptr) st = st->previous; else break;
        if (st->previous != nullptr) st = st->previous; else break;
        if (st->long_key() == key_now) goto UNDO_MOVE;
      }

      if (pos.is_mated())
      {
        // 後手の詰みなら手順を表示する。先手の詰みは必要ない。
        if (pos.side_to_move() == WHITE)
        {
          sync_cout << "checkmate " << pos.moves_from_start() << sync_endl; // 開始局面からそこまでの手順
          found_mate = true;
        }
      } else if (depth > 1) {
        // 残り探索深さがあるなら再帰的に探索する。
        int child_no_mate_depth;
        search(pos, depth - 1, child_no_mate_depth);
        no_mate_depth = min(child_no_mate_depth +1, no_mate_depth);

        if (child_no_mate_depth != MAX_PLY)
        {
          replyCount++;
          oneReply = m;
        }

      } else {
        no_mate_depth = 1; // frontier node。この先、まだ探索すれば詰むかも知れないので..

        replyCount++;
        oneReply = m;
      }
    UNDO_MOVE:;
      pos.undo_move(m);
    }

    // このnodeに関して残り探索深さdepthについては詰みを調べきったので不詰めとして扱い、置換表に記録しておく。
    // また、確定局面以外の子が1つしかなればそれを置換表に書き出しておく。(次回の指し手生成をはしょるため)
    if (replyCount != 1)
      oneReply = MOVE_NONE;

    tte->save(key, no_mate_depth,oneReply);
  }

  // 協力詰め探索の反復深化のループ
  void id_loop(Position& pos)
  {
    found_mate = false;
    pos.set_nodes_searched(0);
    auto start_time = now();

    // 協力詰めの反復深化は2手ずつ深くして良い。(通常のdf-pnの場合、1手ずつのほうが良いかも。)
    for (uint32_t depth = 1; depth < MAX_PLY; depth+=2)
    {
      TT.new_search();
      search_depth = depth;

      int no_mate_depth;
      search(pos,depth, no_mate_depth);

      // 定期的にdepth、nodes、npsを出力する。
      auto end_time = now();
      sync_cout << "info  depth " << depth
        << " nodes " << pos.nodes_searched()
        << " nps " << (pos.nodes_searched() * 1000 / ((int64_t)(end_time - start_time +1)))
        << " hashfull " << TT.hashfull()
        << sync_endl;

      if (Signals.stop)
        break;
      
      if (found_mate)
        break;

      // 最大探索深さに到達する前に王手が続かなくなっていたなら終了
      if (no_mate_depth == MAX_PLY)
      {
        sync_cout << "checkmate nomate" << sync_endl;
        break;
      }
    }
  }

} // end of namespace

#endif

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

#include "../shogi.h"

#ifdef COOPERATIVE_MATE_SOLVER

#include "all.h"

#include "cooperative_mate_solver.h"

using namespace std;

using namespace Search;

// --- 協力詰め探索

namespace CooperativeMate

{

// 協力詰め用のMovePicker

struct MovePicker

{

// ttMove = 置換表の指し手

MovePicker(const Position& pos_,Move ttMove) : pos(pos_)

{

if (ttMove == MOVE_NONE)

{

// 協力詰めであれば段階的に指し手を生成する必要はない。

// 先手ならば王手の指し手(CHECKS)、後手ならば回避手(EVASIONS)を生成。

endMoves = (pos.side_to_move() == BLACK) ? generateMoves(pos, currentMoves)

: generateMoves(pos, currentMoves);

} else {

// 置換表に載っていた指し手が一つしかないのはone replyなのでこれで指し手生成をはしょれる。

*currentMoves = ttMove;

endMoves++;

}

// 次の指し手をひとつ返す

// 指し手が尽きればMOVE_NONEが返る。

Move next_move() {

if (currentMoves == endMoves)

return MOVE_NONE;

return *currentMoves++;

}

private:

const Position& pos;

ExtMove moves[MAX_MOVES], *currentMoves = moves, *endMoves = moves;

};

TranspositionTable TT;

// 現在の探索深さ

int search_depth;

// 詰みが見つかったか

bool found_mate;

// 協力詰め

// depth = 残り探索深さ

// no_mate_depth = この局面は、この深さの残り探索深さがあっても詰まない(あるいは詰みを発見して出力済み)

void search(Position& pos, uint32_t depth , int& no_mate_depth)

{

// 強制停止

if (Signals.stop)

{

no_mate_depth = MAX_PLY;

return;

}

bool found;

Key128 key = pos.state()->long_key();

auto tte = TT.probe(key , found); // 置換表がヒットするか

if (found && tte->depth() >= depth)

{

no_mate_depth = tte->depth();

return;

// このnodeに関しては現在の残り探索深さ以上の深さにおいて

//不詰めが証明されているのでもう帰ってよい。(枝刈り)

}

StateInfo st;

pos.check_info_update(); // legal()とgives_check()とCHECKSの指し手生成に先だって呼び出されている必要がある。

MovePicker mp(pos, found ? tte->move() : MOVE_NONE);

Move m;

int replyCount = 0; // 確定局面以外の応手の数

Move oneReply = MOVE_NONE;

no_mate_depth = MAX_PLY; // 有効な指し手が一つもなければこのnodeはいくらdepthがあろうと詰まない。

while (m = mp.next_move())

{

if (!pos.legal(m))

continue;

pos.do_move(m, st , pos.gives_check(m));

// 経路を少し遡って、同じ局面があればこれは連続王手の千日手であり、

// 残り深さ2手以上少ない状態で詰まないことは前回の反復深化のiterationで証明されているので

// 枝刈りして良い。

auto st = pos.state();

auto key_now = st->long_key();

for (int i = 0; i < 8; ++i) // とりあえず8*2 = 16手遡る

{

if (st->previous != nullptr) st = st->previous; else break;

if (st->long_key() == key_now) goto UNDO_MOVE;

}

if (pos.is_mated())

{

// 後手の詰みなら手順を表示する。先手の詰みは必要ない。

if (pos.side_to_move() == WHITE)

{

sync_cout << "checkmate " << pos.moves_from_start() << sync_endl; // 開始局面からそこまでの手順

found_mate = true;

}

} else if (depth > 1) {

// 残り探索深さがあるなら再帰的に探索する。

int child_no_mate_depth;

search(pos, depth - 1, child_no_mate_depth);

no_mate_depth = min(child_no_mate_depth +1, no_mate_depth);

if (child_no_mate_depth != MAX_PLY)

{

replyCount++;

oneReply = m;

}

} else {

no_mate_depth = 1; // frontier node。この先、まだ探索すれば詰むかも知れないので..

replyCount++;

oneReply = m;

}

UNDO_MOVE:;

pos.undo_move(m);

}

// このnodeに関して残り探索深さdepthについては詰みを調べきったので不詰めとして扱い、置換表に記録しておく。

// また、確定局面以外の子が1つしかなればそれを置換表に書き出しておく。(次回の指し手生成をはしょるため)

if (replyCount != 1)

oneReply = MOVE_NONE;

tte->save(key, no_mate_depth,oneReply);

}

// 協力詰め探索の反復深化のループ

void id_loop(Position& pos)

{

found_mate = false;

pos.set_nodes_searched(0);

auto start_time = now();

// 協力詰めの反復深化は2手ずつ深くして良い。(通常のdf-pnの場合、1手ずつのほうが良いかも。)

for (uint32_t depth = 1; depth < MAX_PLY; depth+=2)

{

TT.new_search();

search_depth = depth;

int no_mate_depth;

search(pos,depth, no_mate_depth);

// 定期的にdepth、nodes、npsを出力する。

auto end_time = now();

sync_cout << "info depth " << depth

<< " nodes " << pos.nodes_searched()

<< " nps " << (pos.nodes_searched() * 1000 / ((int64_t)(end_time - start_time +1)))

<< " hashfull " << TT.hashfull()

<< sync_endl;

if (Signals.stop)

break;

if (found_mate)

break;

// 最大探索深さに到達する前に王手が続かなくなっていたなら終了

if (no_mate_depth == MAX_PLY)

{

sync_cout << "checkmate nomate" << sync_endl;

break;

}

} // end of namespace

#endif