Stockfish DD – movepick 指し手オーダリング

今回はmove pickerと言って、指し手を段階的に生成して、生成した指し手のなかから1つ一番よさげな指し手を取り出す部分(いわゆる指し手オーダリング)について見ていきます。

killerが2本あったり、なるべくソートが要らないように工夫してあったり、なかなか興味深いです。

killerが2本ある理由は、1本だけだと局所解みたいなのが出てきて現在のkillerと入れ替わったときにそのあとの枝刈り性能がしばらく落ちるからで、逆に3本以上はあまり意味なくて…みたいな理由です。

その他、

gain。指し手単体による評価値の増加を調べたテーブル。
history。beta cutを起こした指し手に加点してそれ以外を減点したテーブル。
counter move。反駁手(?)。ある指し手に対してbeta cutを起こしたことのある相手の指し手をペアにしたもの。

という考え方は、他のこの手のゲーム木探索でも使えるアイデアで、かなり参考になるかと思います。

/*
Stockfish, a UCI chess playing engine derived from Glaurung 2.1
Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad

Stockfish is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

Stockfish is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef MOVEPICK_H_INCLUDED
#define MOVEPICK_H_INCLUDED

#include <algorithm> // For std::max
#include <cstring>   // For std::memset

#include "movegen.h"
#include "position.h"
#include "search.h"
#include "types.h"


/// The Stats struct stores moves statistics. According to the template parameter
/// the class can store History, Gains and Countermoves. History records how often
/// different moves have been successful or unsuccessful during the current search
/// and is used for reduction and move ordering decisions. Gains records the move's
/// best evaluation gain from one ply to the next and is used for pruning decisions.
/// Countermoves store the move that refute a previous one. Entries are stored
/// according only to moving piece and destination square, hence two moves with
/// different origin but same destination and piece will be considered identical.

// ※　history heuristicsのために用いる統計情報

// Stats構造体は指し手の統計情報を格納する。template parameterに基づき、
// このclassは、HistoryとGainsとCountermovesを格納できる。
// Historyは、現在の探索において、どの程度、個々の指し手が成功したか/失敗したかであり
// これはreduction(残り探索深さを縮めること)とmove ordering(指し手の優先順位付け)の決定に使われる。
// Gainsはある探索深さから次の探索深さに推移するときの、指し手に関する最も大きな評価値の利得であり、
// 枝刈りの決定に使われる。
// Countermovesは、一つ前の指し手を論駁する(やり込める)指し手である。
// エントリーは、単に動かす駒と移動先の升だけが格納されている。
// これにより、移動元は異なるが、移動先および動かす駒が同じ２つの指し手は、同一視される。

template<bool Gain, typename T>
struct Stats {

  static const Value Max = Value(2000);

  // 駒種を与えるとそれに対応する行き先の配列 &T[SQUARE_NB]を返すoperator
  const T* operator[](Piece p) const { return table[p]; }

  // このクラスが保持しているテーブルを0クリアする
  void clear() { std::memset(table, 0, sizeof(table)); }

  // T = std::pair<Move,Move>だとして
  // Countermoveの登録用。
  // 駒種pに対するtoへの移動指し手に対応する応手がm、みたいな感じで登録して使う。
  void update(Piece p, Square to, Move m) {

    // この関数、Tとしてstd::pair<Move,Move>を渡したときのことなのか。
    // mが1番目ならば何もしない。
    if (m == table[p][to].first)
      return;

    table[p][to].second = table[p][to].first;
    table[p][to].first = m;
  }

  // GainsStats,HistoryStats用
  // 駒種pをtoに移動させる指し手に対する統計情報を追加する。
  // HistoryStatsならばtable[p][to] + vの絶対値がMax(=2000)を超えないなら、table[p][to]にvを加算。
  // GainsStatsならtable[p][to]は、max(v,table[p][to]-1)
  // ToDo : →　使い道がよくわからん。
  void update(Piece p, Square to, Value v) {

    // template parameterで渡されたGainによって処理を切り替える。

    // GainsStats用
    if (Gain)
      table[p][to] = std::max(v, table[p][to] - 1);

    // HistoryStats用
    // 絶対値がMaxを超えないならtable[p][to]にvを加算してしまう。
    else if (abs(table[p][to] + v) < Max)
      table[p][to] += v;
  }

private:
  // 移動させる駒とその駒の移動先
  T table[PIECE_NB][SQUARE_NB];
};

// 指し手による駒の位置によるスコア変動を記録したもの。Quietな指し手(王手と駒取り・成り以外の手)で
// 駒を移動させたときに入るスコアの統計値的なもの。
// ※　将棋だと成りはこれに記録したほうがいいような気は少しするが…。
typedef Stats< true, Value> GainsStats;

// history。beta cutoffした指し手に加点して、それ以外のQuietな手には減点したもの。
// 指し手オーダリングに用いる
typedef Stats<false, Value> HistoryStats;

// カウンターの指し手。ある指し手に対して、beta cutoffを引き起こした次の指し手とのペア。
typedef Stats<false, std::pair<Move, Move> > CountermovesStats;


/// MovePicker class is used to pick one pseudo legal move at a time from the
/// current position. The most important method is next_move(), which returns a
/// new pseudo legal move each time it is called, until there are no moves left,
/// when MOVE_NONE is returned. In order to improve the efficiency of the alpha
/// beta algorithm, MovePicker attempts to return the moves which are most likely
/// to get a cut-off first.

// MovePickerクラスは、現局面から1度にひとつの「仮の合法」な指し手を選ぶのに使われる。
// ※　「仮の合法(pseudo legal)な指し手」とは、自殺手が含まれているという意味。
// もっとも重要な関数はnext_move()であり、この関数が呼ばれるたびに指し手がなくなるまで
// 「仮の合法」な指し手を返す。指し手がなくなったときMOVE_NONEが返る。
// αβアルゴリズムの効率を改善するために、MovePickerは最初にcut-offできそうな指し手を
// 返そうと試みる。

class MovePicker {

  MovePicker& operator=(const MovePicker&); // Silence a warning under MSVC

public:

  // コンストラクター3種
  // Position →　現在の局面
  // Move →　置換表の指し手。ttMove
  // Depth → 残り探索深さ
  // HistoryStats → 統計情報 history heuristicのために使う。
  // 最後のパラメーターで3つのコンストラクターがある。

  // 1) 静止探索で使うコンストラクター
  //  Square →　直前の指し手の移動先の升(Recaptureするときに使う)
  // a) 王手されているなら回避手生成へ。
  // さもなくば、
  // b) 残り探索深さがDEPTH_QS_NO_CHECKS(==2 == ONE_PLY)より大きいならば静止探索0(駒取り,王手)へ。
  // c) 残り探索深さがDEPTH_QS_RECAPTURES(==-10 == -5 * ONE_PLY)より大きいなら静止探索1(駒取りのみ)へ。
  // d) DEPTH_QS_RECAPTURES(==-10 == -5 * ONE_PLY)以下なら、Recapture(取り返しのみ生成)へ。
  MovePicker(const Position&, Move, Depth, const HistoryStats&, Square);

  // 2) ProbCut用コンストラクター
  //   PieceType → 直前で捕獲された駒
  //   これはProbCutに使う。
  //   例えば、PieceTypeとして歩を渡した場合、歩を取る手は返さないことになる。
  MovePicker(const Position&, Move, const HistoryStats&, PieceType);

  // 3) 通常のコンストラクター
  //    Move* → Counter Moveの配列の先頭 , Search::Stack*ss → splitしたとき用
  // ※　ここで渡したssに対して、next_move<true>()したときに、
  // ss->splitPoint->movePicker->next_move<false>()のようにして共有しているMovePicker objectから指し手が生成される。
  //  王手がかかっているときは回避手のみ。
  //  そうでないときは仮の合法の指し手すべてがオーダリングされて返る。
  MovePicker(const Position&, Move, Depth, const HistoryStats&, Move*, Search::Stack*);

  // この局面で次に試すべき1手を返す。指し手がもうなければMOVE_NONE。
  // 指し手には自殺手も含まれているので注意。
  // SpNode = split nodeであるときだけtrue。
  // ※　その場合、このクラスではlockしていないので、呼び出し側でlockにより保護しておくこと。
  template<bool SpNode> Move next_move();

private:
  template<GenType> void score();

  // 次の指し手生成フェーズになったときに呼び出され、指し手を生成し、スコアリングして、必要ならばソートして戻る。
  void generate_next();

  // 現在の局面(コンストラクターで渡されている)
  const Position& pos;

  // history情報(コンストラクターで渡されている)
  // 指し手のオーダリングのためにスコアをつけるのに使う。
  const HistoryStats& history;

  // SpNodeのときは、ここから指し手を取り出して使う。
  // コンストラクタで渡されたSearch::Stack*
  Search::Stack* ss;

  // カウンターの指し手
  // ※　countermoves[0]とcountermoves[1]としてアクセス可能だと仮定。
  // 指し手がないときはMOVE_NONEと仮定。取得中にSMP競合により書き換わることはあると仮定。
  Move* countermoves;

  // 残り探索深さ(コンストラクタで渡された値)
  Depth depth;

  // コンストラクターで渡された置換表の指し手。
  // 仮の合法性はこのクラスのコンストラクターでチェック済みであり、この指し手で進めてもアクセス違反になることはない。
  Move ttMove;

  // ここではKiller2個 + カウンターの指し手用2個で4個のバッファ。
  ExtMove killers[4];

  // 取り返す手のみを生成するときにターゲットとなる升
  // これは、コンストラクターで与えられる。
  Square recaptureSquare;

  // captureThreshold : PROBCUT用のMovePickにおいて、このスコア以下の指し手は返さない。
  //  この値は、コンストラクターで渡されたPieceTypeに対して、
  // captureThreshold = PieceValue[MG][pt]
  // のようにして求めてある。つまり、ptとして歩を渡した場合、歩を取る手は返さないことになる。
  
  // stage : 指し手生成のフェーズ。これについてはmovepick.cppのほうの先頭にある定義を見よ。

  int captureThreshold, stage;

  // cur : 現在返した指し手を指すポインタ。指し手生成バッファ上やkillers配列上を指していたりする。
  // endBadCaptures : 悪いスコアの捕獲する指し手。これは指し手生成バッファの末尾から用いる。
  // end : curがendに到達したらその一連の指し手は終了して次の指し手を返すフェーズに移行するという作りになっている。
  //  curは++していくとは限らず、フェーズによっては--していくこともある。
  // endQuiets : 「捕獲する指し手・killerの指し手以外」(＝普通の指し手)の生成フェーズにおいて、
  // 　その生成された指し手の末尾をポイントするのに使う。

  ExtMove *cur, *end, *endQuiets, *endBadCaptures;

  // 指し手生成バッファ。このノードにおいて生成された指し手の集合。
  // ※　これ、stack上に確保されていくことになるが、将棋の場合、指し手が多いので
  // あまりされたらスタックがオーバーしたりしてな…。
  ExtMove moves[MAX_MOVES];
};

#endif // #ifndef MOVEPICK_H_INCLUDED

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

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

Stockfish, a UCI chess playing engine derived from Glaurung 2.1

Stockfish is free software: you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation, either version 3 of the License, or

(at your option) any later version.

Stockfish is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with this program. If not, see .

#ifndef MOVEPICK_H_INCLUDED

#define MOVEPICK_H_INCLUDED

#include // For std::max

#include // For std::memset

#include "movegen.h"

#include "position.h"

#include "search.h"

#include "types.h"

/// The Stats struct stores moves statistics. According to the template parameter

/// the class can store History, Gains and Countermoves. History records how often

/// different moves have been successful or unsuccessful during the current search

/// and is used for reduction and move ordering decisions. Gains records the move's

/// best evaluation gain from one ply to the next and is used for pruning decisions.

/// Countermoves store the move that refute a previous one. Entries are stored

/// according only to moving piece and destination square, hence two moves with

/// different origin but same destination and piece will be considered identical.

// ※　history heuristicsのために用いる統計情報

// Stats構造体は指し手の統計情報を格納する。template parameterに基づき、

// このclassは、HistoryとGainsとCountermovesを格納できる。

// Historyは、現在の探索において、どの程度、個々の指し手が成功したか/失敗したかであり

// これはreduction(残り探索深さを縮めること)とmove ordering(指し手の優先順位付け)の決定に使われる。

// Gainsはある探索深さから次の探索深さに推移するときの、指し手に関する最も大きな評価値の利得であり、

// 枝刈りの決定に使われる。

// Countermovesは、一つ前の指し手を論駁する(やり込める)指し手である。

// エントリーは、単に動かす駒と移動先の升だけが格納されている。

// これにより、移動元は異なるが、移動先および動かす駒が同じ２つの指し手は、同一視される。

template

struct Stats {

static const Value Max = Value(2000);

// 駒種を与えるとそれに対応する行き先の配列 &T[SQUARE_NB]を返すoperator

const T* operator[](Piece p) const { return table[p]; }

// このクラスが保持しているテーブルを0クリアする

void clear() { std::memset(table, 0, sizeof(table)); }

// T = std::pairだとして

// Countermoveの登録用。

// 駒種pに対するtoへの移動指し手に対応する応手がm、みたいな感じで登録して使う。

void update(Piece p, Square to, Move m) {

// この関数、Tとしてstd::pairを渡したときのことなのか。

// mが1番目ならば何もしない。

if (m == table[p][to].first)

return;

table[p][to].second = table[p][to].first;

table[p][to].first = m;

}

// GainsStats,HistoryStats用

// 駒種pをtoに移動させる指し手に対する統計情報を追加する。

// HistoryStatsならばtable[p][to] + vの絶対値がMax(=2000)を超えないなら、table[p][to]にvを加算。

// GainsStatsならtable[p][to]は、max(v,table[p][to]-1)

// ToDo : →　使い道がよくわからん。

void update(Piece p, Square to, Value v) {

// template parameterで渡されたGainによって処理を切り替える。

// GainsStats用

if (Gain)

table[p][to] = std::max(v, table[p][to] - 1);

// HistoryStats用

// 絶対値がMaxを超えないならtable[p][to]にvを加算してしまう。

else if (abs(table[p][to] + v) < Max)

table[p][to] += v;

}

private:

// 移動させる駒とその駒の移動先

T table[PIECE_NB][SQUARE_NB];

};

// 指し手による駒の位置によるスコア変動を記録したもの。Quietな指し手(王手と駒取り・成り以外の手)で

// 駒を移動させたときに入るスコアの統計値的なもの。

// ※　将棋だと成りはこれに記録したほうがいいような気は少しするが…。

typedef Stats< true, Value> GainsStats;

// history。beta cutoffした指し手に加点して、それ以外のQuietな手には減点したもの。

// 指し手オーダリングに用いる

typedef Stats HistoryStats;

// カウンターの指し手。ある指し手に対して、beta cutoffを引き起こした次の指し手とのペア。

typedef Stats > CountermovesStats;

/// MovePicker class is used to pick one pseudo legal move at a time from the

/// current position. The most important method is next_move(), which returns a

/// new pseudo legal move each time it is called, until there are no moves left,

/// when MOVE_NONE is returned. In order to improve the efficiency of the alpha

/// beta algorithm, MovePicker attempts to return the moves which are most likely

/// to get a cut-off first.

// MovePickerクラスは、現局面から1度にひとつの「仮の合法」な指し手を選ぶのに使われる。

// ※　「仮の合法(pseudo legal)な指し手」とは、自殺手が含まれているという意味。

// もっとも重要な関数はnext_move()であり、この関数が呼ばれるたびに指し手がなくなるまで

// 「仮の合法」な指し手を返す。指し手がなくなったときMOVE_NONEが返る。

// αβアルゴリズムの効率を改善するために、MovePickerは最初にcut-offできそうな指し手を

// 返そうと試みる。

class MovePicker {

MovePicker& operator=(const MovePicker&); // Silence a warning under MSVC

public:

// コンストラクター3種

// Position →　現在の局面

// Move →　置換表の指し手。ttMove

// Depth → 残り探索深さ

// HistoryStats → 統計情報 history heuristicのために使う。

// 最後のパラメーターで3つのコンストラクターがある。

// 1) 静止探索で使うコンストラクター

// Square →　直前の指し手の移動先の升(Recaptureするときに使う)

// a) 王手されているなら回避手生成へ。

// さもなくば、

// b) 残り探索深さがDEPTH_QS_NO_CHECKS(==2 == ONE_PLY)より大きいならば静止探索0(駒取り,王手)へ。

// c) 残り探索深さがDEPTH_QS_RECAPTURES(==-10 == -5 * ONE_PLY)より大きいなら静止探索1(駒取りのみ)へ。

// d) DEPTH_QS_RECAPTURES(==-10 == -5 * ONE_PLY)以下なら、Recapture(取り返しのみ生成)へ。

MovePicker(const Position&, Move, Depth, const HistoryStats&, Square);

// 2) ProbCut用コンストラクター

// PieceType → 直前で捕獲された駒

// これはProbCutに使う。

// 例えば、PieceTypeとして歩を渡した場合、歩を取る手は返さないことになる。

MovePicker(const Position&, Move, const HistoryStats&, PieceType);

// 3) 通常のコンストラクター

// Move* → Counter Moveの配列の先頭 , Search::Stack*ss → splitしたとき用

// ※　ここで渡したssに対して、next_move()したときに、

// ss->splitPoint->movePicker->next_move()のようにして共有しているMovePicker objectから指し手が生成される。

// 王手がかかっているときは回避手のみ。

// そうでないときは仮の合法の指し手すべてがオーダリングされて返る。

MovePicker(const Position&, Move, Depth, const HistoryStats&, Move*, Search::Stack*);

// この局面で次に試すべき1手を返す。指し手がもうなければMOVE_NONE。

// 指し手には自殺手も含まれているので注意。

// SpNode = split nodeであるときだけtrue。

// ※　その場合、このクラスではlockしていないので、呼び出し側でlockにより保護しておくこと。

template Move next_move();

private:

template void score();

// 次の指し手生成フェーズになったときに呼び出され、指し手を生成し、スコアリングして、必要ならばソートして戻る。

void generate_next();

// 現在の局面(コンストラクターで渡されている)

const Position& pos;

// history情報(コンストラクターで渡されている)

// 指し手のオーダリングのためにスコアをつけるのに使う。

const HistoryStats& history;

// SpNodeのときは、ここから指し手を取り出して使う。

// コンストラクタで渡されたSearch::Stack*

Search::Stack* ss;

// カウンターの指し手

// ※　countermoves[0]とcountermoves[1]としてアクセス可能だと仮定。

// 指し手がないときはMOVE_NONEと仮定。取得中にSMP競合により書き換わることはあると仮定。

Move* countermoves;

// 残り探索深さ(コンストラクタで渡された値)

Depth depth;

// コンストラクターで渡された置換表の指し手。

// 仮の合法性はこのクラスのコンストラクターでチェック済みであり、この指し手で進めてもアクセス違反になることはない。

Move ttMove;

// ここではKiller2個 + カウンターの指し手用2個で4個のバッファ。

ExtMove killers[4];

// 取り返す手のみを生成するときにターゲットとなる升

// これは、コンストラクターで与えられる。

Square recaptureSquare;

// captureThreshold : PROBCUT用のMovePickにおいて、このスコア以下の指し手は返さない。

// この値は、コンストラクターで渡されたPieceTypeに対して、

// captureThreshold = PieceValue[MG][pt]

// のようにして求めてある。つまり、ptとして歩を渡した場合、歩を取る手は返さないことになる。

// stage : 指し手生成のフェーズ。これについてはmovepick.cppのほうの先頭にある定義を見よ。

int captureThreshold, stage;

// cur : 現在返した指し手を指すポインタ。指し手生成バッファ上やkillers配列上を指していたりする。

// endBadCaptures : 悪いスコアの捕獲する指し手。これは指し手生成バッファの末尾から用いる。

// end : curがendに到達したらその一連の指し手は終了して次の指し手を返すフェーズに移行するという作りになっている。

// curは++していくとは限らず、フェーズによっては--していくこともある。

// endQuiets : 「捕獲する指し手・killerの指し手以外」(＝普通の指し手)の生成フェーズにおいて、

// 　その生成された指し手の末尾をポイントするのに使う。

ExtMove *cur, *end, *endQuiets, *endBadCaptures;

// 指し手生成バッファ。このノードにおいて生成された指し手の集合。

// ※　これ、stack上に確保されていくことになるが、将棋の場合、指し手が多いので

// あまりされたらスタックがオーバーしたりしてな…。

ExtMove moves[MAX_MOVES];

};

#endif // #ifndef MOVEPICK_H_INCLUDED

/*
Stockfish, a UCI chess playing engine derived from Glaurung 2.1
Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad

Stockfish is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.


Stockfish is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <cassert>

#include "movepick.h"
#include "thread.h"

namespace {

  // 指し手生成の段階
  enum Stages {
    // -- 通常(王手がかかっていない局面)

    MAIN_SEARCH,  // 通常の指し手生成はここからスタート。置換表の指し手がなければ即座に次のフェーズへ。
    CAPTURES_S1,  // 捕獲する指し手。SEE >= 0のもののみ。スコア(SEEのスコアではなくhistoryのスコア)の大きい値のものから順番に
    KILLERS_S1,   // Killerの指し手2つ + カウンターの指し手最大2つ。
    QUIETS_1_S1,  // それ以外の指し手。historyのスコアが0以上のもの。insertion_sort()済み。
    QUIETS_2_S1,  // それ以外の指し手。historyのスコアが0未満のもの。残りdepthが3手以上あるときのみinsertion_sort()
    BAD_CAPTURES_S1,  // 捕獲する指し手で、SEE < 0のものをhistoryのスコアのいい順に。(CAPTURES_S1で調べなかったもの)

    // -- 王手回避(王手がかかっている局面)

    EVASION,      // 王手回避手は、ここからスタート。置換表の指し手がなければ即座に次のフェーズへ。
    EVASIONS_S2,  // 王手回避手の生成、オーダリングして1手ずつ。

    // -- 静止探索1(駒を取る手＋王手)

    QSEARCH_0,    // 静止探索1は、ここからスタート。置換表の指し手がなければ即座に次のフェーズへ。
    CAPTURES_S3,  // 捕獲する指し手のみ生成。historyのスコア順に返す。
    QUIET_CHECKS_S3,// 駒を取らない王手になる指し手のみ生成。

    // -- 静止探索2(駒を取る手のみ)

    QSEARCH_1,    // 静止探索2は、ここからスタート。置換表の指し手がなければ即座に次のフェーズへ。
    CAPTURES_S4,  // 捕獲する指し手のみ生成。histroyのスコア順に返す。

    // -- PROBCUT用

    PROBCUT,      // ProbCutは、ここからスタート。置換表の指し手がなければ即座に次のフェーズへ。
    CAPTURES_S5,  // 捕獲する指し手のみ生成。captureThreshold以下の指し手は返さない。

    // -- RECAPTURE用

    RECAPTURE,
    CAPTURES_S6,
    STOP
  };

  // Our insertion sort, guaranteed to be stable, as is needed
  // insertion sort、安定性が保証されていて、実際これが必要とされる。
  // ※　ここで言う安定性とはソートのときに同じ値だと並び替わらないということ。
  //   αβ探索では二番目以降の指し手のスコアとして一番目と同じスコアがつくので
  //   ソートのときにその順番が入れ替わってもらっては困るから。

  // ExtMoveは、Move(指し手)とスコアが、64bitに収められている構造体
  void insertion_sort(ExtMove* begin, ExtMove* end)
  {
    ExtMove tmp, *p, *q;

    for (p = begin + 1; p < end; ++p)
    {
      tmp = *p;
      for (q = p; q != begin && *(q - 1) < tmp; --q)
        *q = *(q - 1);
      *q = tmp;
    }
  }

  // Unary predicate used by std::partition to split positive scores from remaining
  // ones so to sort separately the two sets, and with the second sort delayed.
  // 個別にソートするために、残りのExtMoveから正のスコアのものだけを
  // わけるためにstd::partitionによって使われる単一の述語である。
  // その後者(0以下のスコアのExtMove)のソートは遅延される。
  // ※　必要になるまでソートされない。必要にならなければソートされない。

  inline bool has_positive_score(const ExtMove& ms) { return ms.score > 0; }

  // Picks and moves to the front the best move in the range [begin, end),
  // it is faster than sorting all the moves in advance when moves are few, as
  // normally are the possible captures.

  // [begin,end) の範囲にあるベストな指し手を指し手の先頭に移動させ、それを選びとる。
  // ※　ソートせずに1つだけ取り出すの意味。
  // ※　beginを含み、endは含まないの意味。begin,endは下の関数の引数を見てわかるようにExtMove*であり、
  // iteratorだと思えばわかりやすい。
  // これは指し手がほとんどないときに、前もってすべての指し手をソートするより早い。
  // 通例、捕獲する指し手においてそうでありうる。
  // ※　as以下は主語と述語が倒置されている。

  inline ExtMove* pick_best(ExtMove* begin, ExtMove* end)
  {
    // 最大値をとるものを探してそれを先頭要素と交換し、その先頭要素のポインターを返す
    std::swap(*begin, *std::max_element(begin, end));
    return begin;
  }
}


/// Constructors of the MovePicker class. As arguments we pass information
/// to help it to return the presumably good moves first, to decide which
/// moves to return (in the quiescence search, for instance, we only want to
/// search captures, promotions and some checks) and about how important good
/// move ordering is at the current node.

// MovePickerクラスのコンストラクター群。 我々がよい指し手を最初に返せる手助けを
// するための情報を引数に渡し、どんな性質の指し手を返すか(静止探索中、例えば、
// 我々は捕獲する手とか、成る手や王手のみを探索したいだとか)を決定し、よい指し手の
// オーダリングがこの現在のノードにおいてどれくらい重要であるかを返す。

MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h,
  Move* cm, Search::Stack* s) : pos(p), history(h), depth(d) {

  // 残り探索深さが0以上でなければならない。
  assert(d > DEPTH_ZERO);

  // movesは指し手生成バッファ
  // curは現在返している指し手。とりあえずまず初期化のため、先頭を指すようにしておく。
  cur = end = moves;

  // 悪いスコアの捕獲する指し手。これは、指し手生成バッファの後方から使っていくものとする。
  endBadCaptures = moves + MAX_MOVES - 1;

  // カウンターの指し手
  countermoves = cm;

  // 共有オブジェクト
  // Search::Stack*
  ss = s;

  // 現局面で王手がかかっているなら、指し手生成の段階として回避手(EVASION)のみ。
  // 王手がかかっていないなら通常の指し手生成(MAIN_SEARCH)からスタート。
  if (p.checkers())
    stage = EVASION;
  else
    stage = MAIN_SEARCH;

  // 置換表の指し手があって、かつ、その手が仮の合法(※　自殺手である可能性はあるが、
  // この指し手で進めてもアクセス違反にはならないの意味)
  // であるなら、この指し手をttMoveとして、最初に試す。
  ttMove = (ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE);

  // endは生成された指し手の末尾であるので置換表の指し手があったのならば
  // この分として、生成した指し手の終端を指すポインタ(end)を1つ進める。
  // cur!=endのあいだ、新たな指し手の生成はされないので、これにより1つの指し手ぶんだけ稼げる。
  end += (ttMove != MOVE_NONE);
}

MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h,
  Square sq) : pos(p), history(h), cur(moves), end(moves) {

  // Recapture用のコンストラクター

  assert(d <= DEPTH_ZERO);

  // 王手がされているなら回避フェーズへ
  if (p.checkers())
    stage = EVASION;

  // 残り探索深さがDEPTH_QS_NO_CHECKS(==-2 == -1 * ONE_PLY)より大きいならば静止探索0(駒取り,王手)へ。
  else if (d > DEPTH_QS_NO_CHECKS)
    stage = QSEARCH_0;

  // 残り探索深さがDEPTH_QS_RECAPTURES(==-10 == -5 * ONE_PLY)より大きいなら静止探索1(駒取りのみ)へ。
  else if (d > DEPTH_QS_RECAPTURES)
  {
    stage = QSEARCH_1;

    // Skip TT move if is not a capture or a promotion, this avoids qsearch
    // tree explosion due to a possible perpetual check or similar rare cases
    // when TT table is full.

    // もし、捕獲する手でもなく成る手でもないならば置換表の指し手は無視する。
    // これは、ありうる千日手チェックや置換表あふれによる類似の競合状況
    // のために静止探索木爆発が起きるのを回避するためである。

    // ※　残り探索深さがマイナス5以下だからそろそろ切り上げないとね。

    if (ttm && !pos.capture_or_promotion(ttm))
      ttm = MOVE_NONE;
  }
  else
  {
    // DEPTH_QS_RECAPTURES(==-10 == -5 * ONE_PLY)以下なら、Recapture(取り返しのみ生成)へ。

    stage = RECAPTURE;

    // 取り返す升
    recaptureSquare = sq;
    ttm = MOVE_NONE;
  }

  ttMove = (ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE);
  end += (ttMove != MOVE_NONE);
}

MovePicker::MovePicker(const Position& p, Move ttm, const HistoryStats& h, PieceType pt)
: pos(p), history(h), cur(moves), end(moves) {

  assert(!pos.checkers());

  stage = PROBCUT;

  // In ProbCut we generate only captures better than parent's captured piece
  // ProbCutにおいて親(局面で)のキャプチャーされた駒よりいい駒の捕獲のみを生成したい。

  captureThreshold = PieceValue[MG][pt];

  ttMove = (ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE);

  if (ttMove && (!pos.capture(ttMove) || pos.see(ttMove) <= captureThreshold))
    ttMove = MOVE_NONE;

  end += (ttMove != MOVE_NONE);
}


/// score() assign a numerical move ordering score to each move in a move list.
/// The moves with highest scores will be picked first.

// score()は、指し手リストのなかのそれぞれの指し手に対して数値化した指し手オーダリングスコアを割り当てる。
// 一番高いスコアの指し手は最初ら選び取られる。

// 駒を取る指し手に対してオーダリングするためにスコアをつける関数。
template<>
void MovePicker::score<CAPTURES>() {
  // Winning and equal captures in the main search are ordered by MVV/LVA.
  // Suprisingly, this appears to perform slightly better than SEE based
  // move ordering. The reason is probably that in a position with a winning
  // capture, capturing a more valuable (but sufficiently defended) piece
  // first usually doesn't hurt. The opponent will have to recapture, and
  // the hanging piece will still be hanging (except in the unusual cases
  // where it is possible to recapture with the hanging piece). Exchanging
  // big pieces before capturing a hanging piece probably helps to reduce
  // the subtree size.
  // In main search we want to push captures with negative SEE values to
  // badCaptures[] array, but instead of doing it now we delay till when
  // the move has been picked up in pick_move_from_list(), this way we save
  // some SEE calls in case we get a cutoff (idea from Pablo Vazquez).

  // 通常探索中の(捕獲対象の駒が捕獲に使う駒より)勝った/等しい駒の捕獲は
  // MVV/LVAによりオーダリングされる。驚くべきことに、これはSEEベースの
  // 指し手オーダリングより少しパフォーマンスが良いと思われる。
  // この理由は、多分、勝った捕獲がある局面や、価値のある駒の捕獲
  // (しかし十分に防御されている)駒を先に取れる局面はたいてい無傷でいられるからであろう。
  // 
  // ※　ToDo : 訳がよくわからん。いい駒を安い駒で取れる以上、形勢に差があるってこと？
  //
  // (駒を取られた)相手側は取り返す必要があるが、浮き駒は依然として浮いている。
  // (浮き駒で取り返せる状況は除くが、それはレアケースである)
  // 浮き駒を捕獲する前に大駒を交換することはsub treeのサイズを縮小させるのに役立つ。
  // メイン探索のなかで我々はbadCaptures[]に入っている負のSEE値をつけた捕獲を推したいが、
  // しかし、この代わりに、我々はその指し手がpick_move_from_list()のなかで取り上げられるまで
  //　遅延するようにしている。この方法は、cutoffされる場合に、同じSEEが呼び出されるのを節約する。
  //  (このアイデアはPablo Vazquezのものである)
  // 
  // ※　hanging piece : cf . http://www.logicalchess.com/hcc/scholastics/tutorials/hanging.html
  // 　タダ取りされる駒のこと。浮き駒。

  Move m;

  for (ExtMove* it = moves; it != end; ++it)
  {
    m = it->move;
    // 捕獲する駒の点数 - 捕獲する駒の種別(安い駒ほど低い)
    // ※　MVV/LVAによるオーダリング。
    // 同じ駒を取るなら、安い駒で取ったほうが取り返された時の損失が避けられるという考え。
    it->score = PieceValue[MG][pos.piece_on(to_sq(m))]
      - type_of(pos.moved_piece(m));

    // 成りを含むのであれば、その価値を上乗せ
    if (type_of(m) == PROMOTION)
      it->score += PieceValue[MG][promotion_type(m)] - PieceValue[MG][PAWN];

    // アンパサンなら、歩の価値を上乗せ。
    else if (type_of(m) == ENPASSANT)
      it->score += PieceValue[MG][PAWN];
  }
}

// historyによりスコアリング
template<>
void MovePicker::score<QUIETS>() {

  Move m;

  // 指し手生成バッファの先頭から、今回生成された指し手の末尾まで。
  for (ExtMove* it = moves; it != end; ++it)
  {
    m = it->move;

    // historyはコンストラクタで渡されているものとする。
    // history[動かす駒][移動先]
    // にてスコアリング
    it->score = history[pos.moved_piece(m)][to_sq(m)];
  }
}

// 王手回避手のためのオーダリング
template<>
void MovePicker::score<EVASIONS>() {
  // Try good captures ordered by MVV/LVA, then non-captures if destination square
  // is not under attack, ordered by history value, then bad-captures and quiet
  // moves with a negative SEE. This last group is ordered by the SEE score.

  // MVV/LVAによりオーダリングされた良い捕獲する手を試し、そのあと行き先に利きがない場合に、
  // 捕獲しない手をhistoryの値でオーダリングして試し、それからbad-captureと捕獲しない指し手
  // を負のSEEで試す。最後のグループはSEEのスコアでオーダリングされる。

  // ※　玉が逃げたあと駒が取られてSEEが著しくマイナスになることがあるのでそれを避ける意味か。

  Move m;
  int seeScore;

  for (ExtMove* it = moves; it != end; ++it)
  {
    // 指し手それぞれについて、SEEの符号を見てそれがマイナスであれば、
    // スコア値として、マイナスのグループへ放り込む。
    // これ、自殺手なら、指し手をMOVE_NONEにしてもいいぐらいだと思うのだが…。

    m = it->move;
    if ((seeScore = pos.see_sign(m)) < 0)
      it->score = seeScore - HistoryStats::Max; // At the bottom

    // 捕獲する指し手であれば、プラスのグループに放り込む
    // 行き先にある駒の価値 - 動かした駒を引いた値をスコアとする。
    // (どうせ取るなら、小駒で取ったほうが取り返されたときの損失が少ないというMVV/LVAに基づく考えかた)

    else if (pos.capture(m))
      it->score = PieceValue[MG][pos.piece_on(to_sq(m))]
      - type_of(pos.moved_piece(m)) + HistoryStats::Max;

    // さもなくば、historyの値そのまま。
    else
      it->score = history[pos.moved_piece(m)][to_sq(m)];

    // 以上、SEEの符号とcaptureかどうかによってスコア順に3グループに分類される。

    // これを呼び出したgenerate_next()ではソートしていないが
    // next_move()で1手取り出すごとに最大値のものを取り出しているので
    // 結果として最大のものから順番に取り出される。
  }
}


/// generate_next() generates, scores and sorts the next bunch of moves, when
/// there are no more moves to try for the current phase.

// generate_next()は、現在のフェーズに対する指し手が存在しないとき、
// 次の一連の指し手を生成し、(指し手に)スコアをつけ、それらをソートする。

// ※　next_move()から指し手がなくなったときに呼び出される。

void MovePicker::generate_next() {

  cur = moves;

  switch (++stage) {

  case CAPTURES_S1: case CAPTURES_S3: case CAPTURES_S4: case CAPTURES_S5: case CAPTURES_S6:
    // 駒を取る指し手のみ生成。
    end = generate<CAPTURES>(pos, moves);
    // 捕獲する手のオーダリングのためにスコアをつける関数。
    score<CAPTURES>();
    // ソート自体はここでは行わず、next_move()で一手ずつ取り出すときに最大のものを取り出すことによって実現する。
    return;

  case KILLERS_S1:

    // curは指し手生成バッファだけではなく、killerの配列に対してもポイントして使う。
    cur = killers;
    // 2手分。
    end = cur + 2;

    // この探索深さのkillerの1手目、2手目からコピー。
    // (これコピーしている最中にkillerが書き換わって、killers[0]==killers[1]にならないのか？)
    killers[0].move = ss->killers[0];
    killers[1].move = ss->killers[1];
    killers[2].move = killers[3].move = MOVE_NONE;
    // 3,4手目はMOVE_NONE

    // Be sure countermoves are different from killers
    // カウンターの指し手はkillerとは違うと考えよ。

    // カウンターの指し手2つそれぞれについて、killer[0],[1]と異なるならば
    // それをkiller[2],[3]に追加する。
    for (int i = 0; i < 2; ++i)
    if (countermoves[i] != cur->move && countermoves[i] != (cur + 1)->move)
      (end++)->move = countermoves[i];

    // 追加したあと、SMP競合(並列化している他のスレッドによる書き換え)により
    // countermove[1]がMOVE_NONEでかつcountermove[0]と[1]が一致したならば
    // killer[3]を消しておく。
    // ※　このコードおかしくないか？killer[2]とkiller[3]を比較すべきではないのか？
    // さらに言えば、killer[3]をMOVE_NONEにするならついでにend--しておくべきではないか？
    if (countermoves[1] && countermoves[1] == countermoves[0]) // Due to SMP races
      killers[3].move = MOVE_NONE;

    return;

  case QUIETS_1_S1:
    // historyのスコアがプラスの分

    // endQuietsは生成した指し手の終端。
    // 指し手生成バッファの先頭から行う。
    endQuiets = end = generate<QUIETS>(pos, moves);

    // スコアリング
    // 対象 = 指し手生成バッファの先頭から、end(生成された指し手の末尾)まで。
    score<QUIETS>();

    // プラスの分だけ分けて…
    // endは、プラスの指し手の終端(このあとまだendQuietsまで指し手は続く)
    end = std::partition(cur, end, has_positive_score);

    // プラスの部分だけをinsertion_sort()
    // ※　将棋だと駒打ちがあるので指し手の数があまりにも大きいので、
    // プラスの手であっても残り探索深さがある程度ないときや、指し手の数が多いときは
    // insertion_sort()もやめたほうがいいのではなかろうか。

    insertion_sort(cur, end);
    return;

  case QUIETS_2_S1:
    // historyのスコアがマイナスの分

    // 指し手はQUIETS_1_S1で生成済み。
    cur = end;
    end = endQuiets;

    // 3手以上残り探索深さがあるなら、ソートしてしまう。
    if (depth >= 3 * ONE_PLY)
      insertion_sort(cur, end);
    return;

  case BAD_CAPTURES_S1:
    // Just pick them in reverse order to get MVV/LVA ordering
    // MVV/LVAオーダリングで取得するには逆順でbad captureの指し手を取り出していくだけで良い。

    // 指し手生成バッファの末尾にSEE < 0 だった指し手が詰められており、
    // また、historyのスコアのいい順番に末尾から詰めて行ったので、この順番で取り出していけば
    // MVV/LVA ordering相当になる。

    // cur = 指し手生成バッファの終端
    // end = 指し手生成バッファの終端からbad captureを詰めていった最新の場所(endBadCaptures)
    // にして、cur--しながら、cur==endになったところまで指し手生成をすれば良い。

    cur = moves + MAX_MOVES - 1;
    end = endBadCaptures;
    return;

  case EVASIONS_S2:
    // 王手回避手をすべて生成
    end = generate<EVASIONS>(pos, moves);

    // 1手でも回避手があるのであればスコアリング(回避手がない場合すらある)
    if (end > moves + 1)
      score<EVASIONS>();
    return;

  case QUIET_CHECKS_S3:
    // 駒を取らない王手のみ生成。
    end = generate<QUIET_CHECKS>(pos, moves);
    return;

    // stateをインクリメントした結果、次のフェーズに突っ込んだら、これは停止扱い。
  case EVASION: case QSEARCH_0: case QSEARCH_1: case PROBCUT: case RECAPTURE:
    stage = STOP;
    // breakを書いていないのはわざと。↓に抜ける。

  case STOP:
    // next_move()のwhileのループのなかからnext_phase()が次に呼び出されるのを回避。
    end = cur + 1; // Avoid another next_phase() call
    return;

  default:
    assert(false);
  }
}


/// next_move() is the most important method of the MovePicker class. It returns
/// a new pseudo legal move every time is called, until there are no more moves
/// left. It picks the move with the biggest score from a list of generated moves
/// taking care not returning the ttMove if has already been searched previously.

// next_move()は、MovePickerクラスのなかでもっとも重要な関数である。これは、
// 返すべき指し手がなくなるまで、呼び出されるたびに新たな仮の合法な指し手を返す。
// 生成された指し手のリストのなかから、もしすでにttMove(置換表の指し手)が探索されて
// いたならば、それを返さないように注意しながら、一番大きなスコアの指し手を選びとる。

// falseになっているのは非split node用だから。
template<>
Move MovePicker::next_move<false>() {

  // 返すべき指し手
  Move move;

  while (true)
  {
    // 返すべき指し手が生成した指し手の終端に達したならgenerate_next()を呼び出して
    // 次の一連の指し手を生成する。
    while (cur == end)
      generate_next();

    switch (stage) {


      // 置換表の指し手を返すフェーズ
    case MAIN_SEARCH: case EVASION: case QSEARCH_0: case QSEARCH_1: case PROBCUT:
      // 指し手生成バッファに存在していたとみなして、ttMoveを返してしまう。
      // endはcur+1なので、次にこの関数が呼び出されたときは、cur == endになっており、
      // generate_next()が呼び出され、generate_next()のなかでstage++されて、次のステージになるという仕組み。
      ++cur;
      return ttMove;

      // 捕獲する指し手を返すフェーズ
    case CAPTURES_S1:
      // 生成された指し手のなかからベストなスコアのものを返す。
      // 数が少ないはずなので、ソートする必要はなく、単に最大のスコアの指し手を探してそれを返す。
      // pick_best()のなかでその最大のスコアの指し手が*curとswap()してあるので、cur++して次の指し手をポイントするようにしておく。
      move = pick_best(cur++, end)->move;
      // 置換表の指し手ならば無視して、次の指し手へ。
      if (move != ttMove)
      {
        // SEEの符号を見て、正ならばそれを返す。
        if (pos.see_sign(move) >= 0)
          return move;

        // Losing capture, move it to the tail of the array
        // 駒損する捕獲であるので、これを配列の末尾に移動させる。

        // ※　endBadCapturesは、指し手生成バッファの末尾であり、末尾から先頭方向に向かって使っていく。
        // ※　SEEの符号が負だからと言って、通常の指し手よりそこまで悪いとは考えにくいのだが…。
        //   このせいで、駒捨てを連発するような詰将棋的な手順は完全に除外されてしまうな…。
        //   将棋ではあまりいいオーダリングとは言えないのではなかろうか。
        (endBadCaptures--)->move = move;
      }
      break;

    case KILLERS_S1:
      // killer move
      move = (cur++)->move;
      // killerはMOVE_NONEでありえるのでそれは除外
      if (move != MOVE_NONE
        // killerは仮の合法ですらない可能性があるのでそれも除外
        &&  pos.pseudo_legal(move)
        // 置換表の指し手ならそれも除外
        // ※　置換表の指し手のチェックのほうが軽いので先にしてはどうか。
        // まあ、置換表の指し手とkillerが一致する確率より、「仮の合法」でない確率のほうが圧倒的に高いからということなのか？
        && move != ttMove
        // この局面において、この指し手が捕獲する指し手ではないことが条件。
        // (捕獲する指し手ならばCAPTURES_S1でチェック済みだから)
        && !pos.capture(move))
        return move;
      break;

    case QUIETS_1_S1: case QUIETS_2_S1:
      // 捕獲、killer、カウンター指し手以外の指し手。
      // QUIETS_1_S1はhistoryのスコアがプラスの指し手、
      // QUIETS_2_S1は、historyのスコアがマイナスの指し手である。
      // ※　将棋では、QUIETS_1_S1のあとにBAD_CAPTURES_S1をもってくるぐらいのほうがいいのかもな？

      move = (cur++)->move;
      // 置換表の指し手ではなく、かつ、killerとは一致しないことが条件。
      // ※　これ、たいていは抜けるのだから、(move ^ ttMove) | (move ^ killers[0].move) | ... == 0
      // みたいに書くほうがよくないか？
      if (move != ttMove
        && move != killers[0].move
        && move != killers[1].move
        && move != killers[2].move
        && move != killers[3].move)
        return move;
      break;

    case BAD_CAPTURES_S1:
      // 悪い捕獲する手
      // CAPTURES_S1においてSEE < 0だった手を、historyのスコアのいい順に。
      return (cur--)->move;

    case EVASIONS_S2: case CAPTURES_S3: case CAPTURES_S4:
      // 生成された数が少ないはずなのでソートせずに最大のものを毎回探して取り出す処理にしてある。
      move = pick_best(cur++, end)->move;
      if (move != ttMove)
        return move;
      break;

    case CAPTURES_S5:
      // 捕獲する指し手でかつ、captureThreshold以上のものだけを生成。
      // ProbCutで用いる。
      // 歩を取る手などしょーもない駒取りを延々と静止探索内で読むわけにはいかないから。
      move = pick_best(cur++, end)->move;
      if (move != ttMove && pos.see(move) > captureThreshold)
        return move;
      break;

    case CAPTURES_S6:
      move = pick_best(cur++, end)->move;
      if (to_sq(move) == recaptureSquare)
        return move;
      break;

    case QUIET_CHECKS_S3:
      // 駒を取らない王手。スコアリングされていないので、置換表の指し手と違うことだけを確認して指し手を返す。
      move = (cur++)->move;
      if (move != ttMove)
        return move;
      break;

    case STOP:
      return MOVE_NONE;

    default:
      assert(false);
    }
  }
}


/// Version of next_move() to use at split point nodes where the move is grabbed
/// from the split point's shared MovePicker object. This function is not thread
/// safe so must be lock protected by the caller.

// splitしたノードにおいて使うバージョンのnext_move()である。指し手をsplit pointで
// 共有しているMovePicker objectからもらう。この関数はスレッドセーフではないので
// 呼び出し側でlockにより保護されるべきである。

template<>
Move MovePicker::next_move<true>() { return ss->splitPoint->movePicker->next_move<false>(); }

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

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

Stockfish, a UCI chess playing engine derived from Glaurung 2.1

Stockfish is free software: you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation, either version 3 of the License, or

(at your option) any later version.

Stockfish is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with this program. If not, see .

#include

#include "movepick.h"

#include "thread.h"

namespace {

// 指し手生成の段階

enum Stages {

// -- 通常(王手がかかっていない局面)

MAIN_SEARCH, // 通常の指し手生成はここからスタート。置換表の指し手がなければ即座に次のフェーズへ。

CAPTURES_S1, // 捕獲する指し手。SEE >= 0のもののみ。スコア(SEEのスコアではなくhistoryのスコア)の大きい値のものから順番に

KILLERS_S1, // Killerの指し手2つ + カウンターの指し手最大2つ。

QUIETS_1_S1, // それ以外の指し手。historyのスコアが0以上のもの。insertion_sort()済み。

QUIETS_2_S1, // それ以外の指し手。historyのスコアが0未満のもの。残りdepthが3手以上あるときのみinsertion_sort()

BAD_CAPTURES_S1, // 捕獲する指し手で、SEE < 0のものをhistoryのスコアのいい順に。(CAPTURES_S1で調べなかったもの)

// -- 王手回避(王手がかかっている局面)

EVASION, // 王手回避手は、ここからスタート。置換表の指し手がなければ即座に次のフェーズへ。

EVASIONS_S2, // 王手回避手の生成、オーダリングして1手ずつ。

// -- 静止探索1(駒を取る手＋王手)

QSEARCH_0, // 静止探索1は、ここからスタート。置換表の指し手がなければ即座に次のフェーズへ。

CAPTURES_S3, // 捕獲する指し手のみ生成。historyのスコア順に返す。

QUIET_CHECKS_S3,// 駒を取らない王手になる指し手のみ生成。

// -- 静止探索2(駒を取る手のみ)

QSEARCH_1, // 静止探索2は、ここからスタート。置換表の指し手がなければ即座に次のフェーズへ。

CAPTURES_S4, // 捕獲する指し手のみ生成。histroyのスコア順に返す。

// -- PROBCUT用

PROBCUT, // ProbCutは、ここからスタート。置換表の指し手がなければ即座に次のフェーズへ。

CAPTURES_S5, // 捕獲する指し手のみ生成。captureThreshold以下の指し手は返さない。

// -- RECAPTURE用

RECAPTURE,

CAPTURES_S6,

STOP

};

// Our insertion sort, guaranteed to be stable, as is needed

// insertion sort、安定性が保証されていて、実際これが必要とされる。

// ※　ここで言う安定性とはソートのときに同じ値だと並び替わらないということ。

// αβ探索では二番目以降の指し手のスコアとして一番目と同じスコアがつくので

// ソートのときにその順番が入れ替わってもらっては困るから。

// ExtMoveは、Move(指し手)とスコアが、64bitに収められている構造体

void insertion_sort(ExtMove* begin, ExtMove* end)

{

ExtMove tmp, *p, *q;

for (p = begin + 1; p < end; ++p)

{

tmp = *p;

for (q = p; q != begin && *(q - 1) < tmp; --q)

*q = *(q - 1);

*q = tmp;

}

// Unary predicate used by std::partition to split positive scores from remaining

// ones so to sort separately the two sets, and with the second sort delayed.

// 個別にソートするために、残りのExtMoveから正のスコアのものだけを

// わけるためにstd::partitionによって使われる単一の述語である。

// その後者(0以下のスコアのExtMove)のソートは遅延される。

// ※　必要になるまでソートされない。必要にならなければソートされない。

inline bool has_positive_score(const ExtMove& ms) { return ms.score > 0; }

// Picks and moves to the front the best move in the range [begin, end),

// it is faster than sorting all the moves in advance when moves are few, as

// normally are the possible captures.

// [begin,end) の範囲にあるベストな指し手を指し手の先頭に移動させ、それを選びとる。

// ※　ソートせずに1つだけ取り出すの意味。

// ※　beginを含み、endは含まないの意味。begin,endは下の関数の引数を見てわかるようにExtMove*であり、

// iteratorだと思えばわかりやすい。

// これは指し手がほとんどないときに、前もってすべての指し手をソートするより早い。

// 通例、捕獲する指し手においてそうでありうる。

// ※　as以下は主語と述語が倒置されている。

inline ExtMove* pick_best(ExtMove* begin, ExtMove* end)

{

// 最大値をとるものを探してそれを先頭要素と交換し、その先頭要素のポインターを返す

std::swap(*begin, *std::max_element(begin, end));

return begin;

}

/// Constructors of the MovePicker class. As arguments we pass information

/// to help it to return the presumably good moves first, to decide which

/// moves to return (in the quiescence search, for instance, we only want to

/// search captures, promotions and some checks) and about how important good

/// move ordering is at the current node.

// MovePickerクラスのコンストラクター群。我々がよい指し手を最初に返せる手助けを

// するための情報を引数に渡し、どんな性質の指し手を返すか(静止探索中、例えば、

// 我々は捕獲する手とか、成る手や王手のみを探索したいだとか)を決定し、よい指し手の

// オーダリングがこの現在のノードにおいてどれくらい重要であるかを返す。

MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h,

Move* cm, Search::Stack* s) : pos(p), history(h), depth(d) {

// 残り探索深さが0以上でなければならない。

assert(d > DEPTH_ZERO);

// movesは指し手生成バッファ

// curは現在返している指し手。とりあえずまず初期化のため、先頭を指すようにしておく。

cur = end = moves;

// 悪いスコアの捕獲する指し手。これは、指し手生成バッファの後方から使っていくものとする。

endBadCaptures = moves + MAX_MOVES - 1;

// カウンターの指し手

countermoves = cm;

// 共有オブジェクト

// Search::Stack*

ss = s;

// 現局面で王手がかかっているなら、指し手生成の段階として回避手(EVASION)のみ。

// 王手がかかっていないなら通常の指し手生成(MAIN_SEARCH)からスタート。

if (p.checkers())

stage = EVASION;

else

stage = MAIN_SEARCH;

// 置換表の指し手があって、かつ、その手が仮の合法(※　自殺手である可能性はあるが、

// この指し手で進めてもアクセス違反にはならないの意味)

// であるなら、この指し手をttMoveとして、最初に試す。

ttMove = (ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE);

// endは生成された指し手の末尾であるので置換表の指し手があったのならば

// この分として、生成した指し手の終端を指すポインタ(end)を1つ進める。

// cur!=endのあいだ、新たな指し手の生成はされないので、これにより1つの指し手ぶんだけ稼げる。

end += (ttMove != MOVE_NONE);

}

MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const HistoryStats& h,

Square sq) : pos(p), history(h), cur(moves), end(moves) {

// Recapture用のコンストラクター

assert(d <= DEPTH_ZERO);

// 王手がされているなら回避フェーズへ

if (p.checkers())

stage = EVASION;

// 残り探索深さがDEPTH_QS_NO_CHECKS(==-2 == -1 * ONE_PLY)より大きいならば静止探索0(駒取り,王手)へ。

else if (d > DEPTH_QS_NO_CHECKS)

stage = QSEARCH_0;

// 残り探索深さがDEPTH_QS_RECAPTURES(==-10 == -5 * ONE_PLY)より大きいなら静止探索1(駒取りのみ)へ。

else if (d > DEPTH_QS_RECAPTURES)

{

stage = QSEARCH_1;

// Skip TT move if is not a capture or a promotion, this avoids qsearch

// tree explosion due to a possible perpetual check or similar rare cases

// when TT table is full.

// もし、捕獲する手でもなく成る手でもないならば置換表の指し手は無視する。

// これは、ありうる千日手チェックや置換表あふれによる類似の競合状況

// のために静止探索木爆発が起きるのを回避するためである。

// ※　残り探索深さがマイナス5以下だからそろそろ切り上げないとね。

if (ttm && !pos.capture_or_promotion(ttm))

ttm = MOVE_NONE;

}

else

{

// DEPTH_QS_RECAPTURES(==-10 == -5 * ONE_PLY)以下なら、Recapture(取り返しのみ生成)へ。

stage = RECAPTURE;

// 取り返す升

recaptureSquare = sq;

ttm = MOVE_NONE;

}

ttMove = (ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE);

end += (ttMove != MOVE_NONE);

}

MovePicker::MovePicker(const Position& p, Move ttm, const HistoryStats& h, PieceType pt)

: pos(p), history(h), cur(moves), end(moves) {

assert(!pos.checkers());

stage = PROBCUT;

// In ProbCut we generate only captures better than parent's captured piece

// ProbCutにおいて親(局面で)のキャプチャーされた駒よりいい駒の捕獲のみを生成したい。

captureThreshold = PieceValue[MG][pt];

ttMove = (ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE);

if (ttMove && (!pos.capture(ttMove) || pos.see(ttMove) <= captureThreshold))

ttMove = MOVE_NONE;

end += (ttMove != MOVE_NONE);

}

/// score() assign a numerical move ordering score to each move in a move list.

/// The moves with highest scores will be picked first.

// score()は、指し手リストのなかのそれぞれの指し手に対して数値化した指し手オーダリングスコアを割り当てる。

// 一番高いスコアの指し手は最初ら選び取られる。

// 駒を取る指し手に対してオーダリングするためにスコアをつける関数。

template<>

void MovePicker::score() {

// Winning and equal captures in the main search are ordered by MVV/LVA.

// Suprisingly, this appears to perform slightly better than SEE based

// move ordering. The reason is probably that in a position with a winning

// capture, capturing a more valuable (but sufficiently defended) piece

// first usually doesn't hurt. The opponent will have to recapture, and

// the hanging piece will still be hanging (except in the unusual cases

// where it is possible to recapture with the hanging piece). Exchanging

// big pieces before capturing a hanging piece probably helps to reduce

// the subtree size.

// In main search we want to push captures with negative SEE values to

// badCaptures[] array, but instead of doing it now we delay till when

// the move has been picked up in pick_move_from_list(), this way we save

// some SEE calls in case we get a cutoff (idea from Pablo Vazquez).

// 通常探索中の(捕獲対象の駒が捕獲に使う駒より)勝った/等しい駒の捕獲は

// MVV/LVAによりオーダリングされる。驚くべきことに、これはSEEベースの

// 指し手オーダリングより少しパフォーマンスが良いと思われる。

// この理由は、多分、勝った捕獲がある局面や、価値のある駒の捕獲

// (しかし十分に防御されている)駒を先に取れる局面はたいてい無傷でいられるからであろう。

// ※　ToDo : 訳がよくわからん。いい駒を安い駒で取れる以上、形勢に差があるってこと？

// (駒を取られた)相手側は取り返す必要があるが、浮き駒は依然として浮いている。

// (浮き駒で取り返せる状況は除くが、それはレアケースである)

// 浮き駒を捕獲する前に大駒を交換することはsub treeのサイズを縮小させるのに役立つ。

// メイン探索のなかで我々はbadCaptures[]に入っている負のSEE値をつけた捕獲を推したいが、

// しかし、この代わりに、我々はその指し手がpick_move_from_list()のなかで取り上げられるまで

//　遅延するようにしている。この方法は、cutoffされる場合に、同じSEEが呼び出されるのを節約する。

// (このアイデアはPablo Vazquezのものである)

// ※　hanging piece : cf . http://www.logicalchess.com/hcc/scholastics/tutorials/hanging.html

// 　タダ取りされる駒のこと。浮き駒。

Move m;

for (ExtMove* it = moves; it != end; ++it)

{

m = it->move;

// 捕獲する駒の点数 - 捕獲する駒の種別(安い駒ほど低い)

// ※　MVV/LVAによるオーダリング。

// 同じ駒を取るなら、安い駒で取ったほうが取り返された時の損失が避けられるという考え。

it->score = PieceValue[MG][pos.piece_on(to_sq(m))]

- type_of(pos.moved_piece(m));

// 成りを含むのであれば、その価値を上乗せ

if (type_of(m) == PROMOTION)

it->score += PieceValue[MG][promotion_type(m)] - PieceValue[MG][PAWN];

// アンパサンなら、歩の価値を上乗せ。

else if (type_of(m) == ENPASSANT)

it->score += PieceValue[MG][PAWN];

}

// historyによりスコアリング

template<>

void MovePicker::score() {

Move m;

// 指し手生成バッファの先頭から、今回生成された指し手の末尾まで。

for (ExtMove* it = moves; it != end; ++it)

{

m = it->move;

// historyはコンストラクタで渡されているものとする。

// history[動かす駒][移動先]

// にてスコアリング

it->score = history[pos.moved_piece(m)][to_sq(m)];

}

// 王手回避手のためのオーダリング

template<>

void MovePicker::score() {

// Try good captures ordered by MVV/LVA, then non-captures if destination square

// is not under attack, ordered by history value, then bad-captures and quiet

// moves with a negative SEE. This last group is ordered by the SEE score.

// MVV/LVAによりオーダリングされた良い捕獲する手を試し、そのあと行き先に利きがない場合に、

// 捕獲しない手をhistoryの値でオーダリングして試し、それからbad-captureと捕獲しない指し手

// を負のSEEで試す。最後のグループはSEEのスコアでオーダリングされる。

// ※　玉が逃げたあと駒が取られてSEEが著しくマイナスになることがあるのでそれを避ける意味か。

Move m;

int seeScore;

for (ExtMove* it = moves; it != end; ++it)

{

// 指し手それぞれについて、SEEの符号を見てそれがマイナスであれば、

// スコア値として、マイナスのグループへ放り込む。

// これ、自殺手なら、指し手をMOVE_NONEにしてもいいぐらいだと思うのだが…。

m = it->move;

if ((seeScore = pos.see_sign(m)) < 0)

it->score = seeScore - HistoryStats::Max; // At the bottom

// 捕獲する指し手であれば、プラスのグループに放り込む

// 行き先にある駒の価値 - 動かした駒を引いた値をスコアとする。

// (どうせ取るなら、小駒で取ったほうが取り返されたときの損失が少ないというMVV/LVAに基づく考えかた)

else if (pos.capture(m))

it->score = PieceValue[MG][pos.piece_on(to_sq(m))]

- type_of(pos.moved_piece(m)) + HistoryStats::Max;

// さもなくば、historyの値そのまま。

else

it->score = history[pos.moved_piece(m)][to_sq(m)];

// 以上、SEEの符号とcaptureかどうかによってスコア順に3グループに分類される。

// これを呼び出したgenerate_next()ではソートしていないが

// next_move()で1手取り出すごとに最大値のものを取り出しているので

// 結果として最大のものから順番に取り出される。

}

/// generate_next() generates, scores and sorts the next bunch of moves, when

/// there are no more moves to try for the current phase.

// generate_next()は、現在のフェーズに対する指し手が存在しないとき、

// 次の一連の指し手を生成し、(指し手に)スコアをつけ、それらをソートする。

// ※　next_move()から指し手がなくなったときに呼び出される。

void MovePicker::generate_next() {

cur = moves;

switch (++stage) {

case CAPTURES_S1: case CAPTURES_S3: case CAPTURES_S4: case CAPTURES_S5: case CAPTURES_S6:

// 駒を取る指し手のみ生成。

end = generate(pos, moves);

// 捕獲する手のオーダリングのためにスコアをつける関数。

score();

// ソート自体はここでは行わず、next_move()で一手ずつ取り出すときに最大のものを取り出すことによって実現する。

return;

case KILLERS_S1:

// curは指し手生成バッファだけではなく、killerの配列に対してもポイントして使う。

cur = killers;

// 2手分。

end = cur + 2;

// この探索深さのkillerの1手目、2手目からコピー。

// (これコピーしている最中にkillerが書き換わって、killers[0]==killers[1]にならないのか？)

killers[0].move = ss->killers[0];

killers[1].move = ss->killers[1];

killers[2].move = killers[3].move = MOVE_NONE;

// 3,4手目はMOVE_NONE

// Be sure countermoves are different from killers

// カウンターの指し手はkillerとは違うと考えよ。

// カウンターの指し手2つそれぞれについて、killer[0],[1]と異なるならば

// それをkiller[2],[3]に追加する。

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

if (countermoves[i] != cur->move && countermoves[i] != (cur + 1)->move)

(end++)->move = countermoves[i];

// 追加したあと、SMP競合(並列化している他のスレッドによる書き換え)により

// countermove[1]がMOVE_NONEでかつcountermove[0]と[1]が一致したならば

// killer[3]を消しておく。

// ※　このコードおかしくないか？killer[2]とkiller[3]を比較すべきではないのか？

// さらに言えば、killer[3]をMOVE_NONEにするならついでにend--しておくべきではないか？

if (countermoves[1] && countermoves[1] == countermoves[0]) // Due to SMP races

killers[3].move = MOVE_NONE;

return;

case QUIETS_1_S1:

// historyのスコアがプラスの分

// endQuietsは生成した指し手の終端。

// 指し手生成バッファの先頭から行う。

endQuiets = end = generate(pos, moves);

// スコアリング

// 対象 = 指し手生成バッファの先頭から、end(生成された指し手の末尾)まで。

score();

// プラスの分だけ分けて…

// endは、プラスの指し手の終端(このあとまだendQuietsまで指し手は続く)

end = std::partition(cur, end, has_positive_score);

// プラスの部分だけをinsertion_sort()

// ※　将棋だと駒打ちがあるので指し手の数があまりにも大きいので、

// プラスの手であっても残り探索深さがある程度ないときや、指し手の数が多いときは

// insertion_sort()もやめたほうがいいのではなかろうか。

insertion_sort(cur, end);

return;

case QUIETS_2_S1:

// historyのスコアがマイナスの分

// 指し手はQUIETS_1_S1で生成済み。

cur = end;

end = endQuiets;

// 3手以上残り探索深さがあるなら、ソートしてしまう。

if (depth >= 3 * ONE_PLY)

insertion_sort(cur, end);

return;

case BAD_CAPTURES_S1:

// Just pick them in reverse order to get MVV/LVA ordering

// MVV/LVAオーダリングで取得するには逆順でbad captureの指し手を取り出していくだけで良い。

// 指し手生成バッファの末尾にSEE < 0 だった指し手が詰められており、

// また、historyのスコアのいい順番に末尾から詰めて行ったので、この順番で取り出していけば

// MVV/LVA ordering相当になる。

// cur = 指し手生成バッファの終端

// end = 指し手生成バッファの終端からbad captureを詰めていった最新の場所(endBadCaptures)

// にして、cur--しながら、cur==endになったところまで指し手生成をすれば良い。

cur = moves + MAX_MOVES - 1;

end = endBadCaptures;

return;

case EVASIONS_S2:

// 王手回避手をすべて生成

end = generate(pos, moves);

// 1手でも回避手があるのであればスコアリング(回避手がない場合すらある)

if (end > moves + 1)

score();

return;

case QUIET_CHECKS_S3:

// 駒を取らない王手のみ生成。

end = generate(pos, moves);

return;

// stateをインクリメントした結果、次のフェーズに突っ込んだら、これは停止扱い。

case EVASION: case QSEARCH_0: case QSEARCH_1: case PROBCUT: case RECAPTURE:

stage = STOP;

// breakを書いていないのはわざと。↓に抜ける。

case STOP:

// next_move()のwhileのループのなかからnext_phase()が次に呼び出されるのを回避。

end = cur + 1; // Avoid another next_phase() call

return;

default:

assert(false);

}

/// next_move() is the most important method of the MovePicker class. It returns

/// a new pseudo legal move every time is called, until there are no more moves

/// left. It picks the move with the biggest score from a list of generated moves

/// taking care not returning the ttMove if has already been searched previously.

// next_move()は、MovePickerクラスのなかでもっとも重要な関数である。これは、

// 返すべき指し手がなくなるまで、呼び出されるたびに新たな仮の合法な指し手を返す。

// 生成された指し手のリストのなかから、もしすでにttMove(置換表の指し手)が探索されて

// いたならば、それを返さないように注意しながら、一番大きなスコアの指し手を選びとる。

// falseになっているのは非split node用だから。

template<>

Move MovePicker::next_move() {

// 返すべき指し手

Move move;

while (true)

{

// 返すべき指し手が生成した指し手の終端に達したならgenerate_next()を呼び出して

// 次の一連の指し手を生成する。

while (cur == end)

generate_next();

switch (stage) {

// 置換表の指し手を返すフェーズ

case MAIN_SEARCH: case EVASION: case QSEARCH_0: case QSEARCH_1: case PROBCUT:

// 指し手生成バッファに存在していたとみなして、ttMoveを返してしまう。

// endはcur+1なので、次にこの関数が呼び出されたときは、cur == endになっており、

// generate_next()が呼び出され、generate_next()のなかでstage++されて、次のステージになるという仕組み。

++cur;

return ttMove;

// 捕獲する指し手を返すフェーズ

case CAPTURES_S1:

// 生成された指し手のなかからベストなスコアのものを返す。

// 数が少ないはずなので、ソートする必要はなく、単に最大のスコアの指し手を探してそれを返す。

// pick_best()のなかでその最大のスコアの指し手が*curとswap()してあるので、cur++して次の指し手をポイントするようにしておく。

move = pick_best(cur++, end)->move;

// 置換表の指し手ならば無視して、次の指し手へ。

if (move != ttMove)

{

// SEEの符号を見て、正ならばそれを返す。

if (pos.see_sign(move) >= 0)

return move;

// Losing capture, move it to the tail of the array

// 駒損する捕獲であるので、これを配列の末尾に移動させる。

// ※　endBadCapturesは、指し手生成バッファの末尾であり、末尾から先頭方向に向かって使っていく。

// ※　SEEの符号が負だからと言って、通常の指し手よりそこまで悪いとは考えにくいのだが…。

// このせいで、駒捨てを連発するような詰将棋的な手順は完全に除外されてしまうな…。

// 将棋ではあまりいいオーダリングとは言えないのではなかろうか。

(endBadCaptures--)->move = move;

}

break;

case KILLERS_S1:

// killer move

move = (cur++)->move;

// killerはMOVE_NONEでありえるのでそれは除外

if (move != MOVE_NONE

// killerは仮の合法ですらない可能性があるのでそれも除外

&& pos.pseudo_legal(move)

// 置換表の指し手ならそれも除外

// ※　置換表の指し手のチェックのほうが軽いので先にしてはどうか。

// まあ、置換表の指し手とkillerが一致する確率より、「仮の合法」でない確率のほうが圧倒的に高いからということなのか？

&& move != ttMove

// この局面において、この指し手が捕獲する指し手ではないことが条件。

// (捕獲する指し手ならばCAPTURES_S1でチェック済みだから)

&& !pos.capture(move))

return move;

break;

case QUIETS_1_S1: case QUIETS_2_S1:

// 捕獲、killer、カウンター指し手以外の指し手。

// QUIETS_1_S1はhistoryのスコアがプラスの指し手、

// QUIETS_2_S1は、historyのスコアがマイナスの指し手である。

// ※　将棋では、QUIETS_1_S1のあとにBAD_CAPTURES_S1をもってくるぐらいのほうがいいのかもな？

move = (cur++)->move;

// 置換表の指し手ではなく、かつ、killerとは一致しないことが条件。

// ※　これ、たいていは抜けるのだから、(move ^ ttMove) | (move ^ killers[0].move) | ... == 0

// みたいに書くほうがよくないか？

if (move != ttMove

&& move != killers[0].move

&& move != killers[1].move

&& move != killers[2].move

&& move != killers[3].move)

return move;

break;

case BAD_CAPTURES_S1:

// 悪い捕獲する手

// CAPTURES_S1においてSEE < 0だった手を、historyのスコアのいい順に。

return (cur--)->move;

case EVASIONS_S2: case CAPTURES_S3: case CAPTURES_S4:

// 生成された数が少ないはずなのでソートせずに最大のものを毎回探して取り出す処理にしてある。

move = pick_best(cur++, end)->move;

if (move != ttMove)

return move;

break;

case CAPTURES_S5:

// 捕獲する指し手でかつ、captureThreshold以上のものだけを生成。

// ProbCutで用いる。

// 歩を取る手などしょーもない駒取りを延々と静止探索内で読むわけにはいかないから。

move = pick_best(cur++, end)->move;

if (move != ttMove && pos.see(move) > captureThreshold)

return move;

break;

case CAPTURES_S6:

move = pick_best(cur++, end)->move;

if (to_sq(move) == recaptureSquare)

return move;

break;

case QUIET_CHECKS_S3:

// 駒を取らない王手。スコアリングされていないので、置換表の指し手と違うことだけを確認して指し手を返す。

move = (cur++)->move;

if (move != ttMove)

return move;

break;

case STOP:

return MOVE_NONE;

default:

assert(false);

}

/// Version of next_move() to use at split point nodes where the move is grabbed

/// from the split point's shared MovePicker object. This function is not thread

/// safe so must be lock protected by the caller.

// splitしたノードにおいて使うバージョンのnext_move()である。指し手をsplit pointで

// 共有しているMovePicker objectからもらう。この関数はスレッドセーフではないので

// 呼び出し側でlockにより保護されるべきである。

template<>

Move MovePicker::next_move() { return ss->splitPoint->movePicker->next_move(); }

やねうら王公式サイト

コンピューター将棋やねうら王公式サイト

Stockfish DD – movepick 指し手オーダリング

コメントを残すコメントをキャンセル

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル