Stockfish DD – movegen 指し手生成 | やねうら王公式サイト

今回はStockfishの指し手生成についてです。チェスと将棋では駒の特性が全く違うので、チェスを将棋に変更する場合、この部分は全面的に書き直しが必要となります。

面白いことにチェスではポーン(pawn = 将棋で言う歩)以外は移動に上下の対称性があるので先後の区別がありません。先手も後手も盤上で同じ動きをするので、将棋のように先手用の指し手生成と後手用の指し手生成とを分ける必要がありません。

将棋のほうは先後で駒の移動特性が違う(180度回転させれば同じなんですが…)のと成り駒の移動として金相当になる駒以外に馬と龍という新たな移動特性を持つ駒が生まれるので、将棋のほうが指し手生成は3倍ぐらいソースコードを書くのがしんどい感じがあります。(体感的には)

あとは3手詰めや詰将棋ルーチンを用意するなら指し手生成として王手の指し手のみ生成するコードも用意しないといけません。Stockfishの指し手にはそれは無いのです。(ソースコード上のGenTypeを見ればわかります。指し手生成の実装部には王手のみを生成するコードがあるのですが、純粋な王手だけの指し手を生成するgenerate関数は用意されていません。ゆえに探索部から呼び出されていません。) 従来の将棋ソフトの常識からするとちょっと信じられないですが、まあ、そうなっているということです。

またbitboardを用いて指し手生成をしてありますが、なのはminiのように非bitboard型で持っているなら、Stockfishの指し手生成部のソースコードは何の役にも立たないので一から自分で書く必要があります。

指し手生成の速度は結構利いてくるので、ここをきちんと書けるか否かで探索速度が2,3割変わってきます。まあ2,3割しか変わらないなら上位ソフト以外は関係のない部分とも言えますが、上位ソフトでは絶対に譲れない部分なので極限まで最適化しましょう。

/*
  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 MOVEGEN_H_INCLUDED
#define MOVEGEN_H_INCLUDED

#include "types.h"

// 指し手生成の種別
// これはgenerate関数と組み合わせて使う。
// generate関数で指し手を生成するときに、生成する指し手の種別を指定できる。
enum GenType {
  CAPTURES,			// 駒を捕る手,queenの昇格する手 ※　将棋では銀以外を成る手もここに入れておくか。
  QUIETS,				// 駒を取らない手,成らない手 ※　将棋では銀を成る手もここに入れておくか。
  QUIET_CHECKS, // 駒を取らない王手(QUIETSのなかで王手になる手のみ)。開き王手含む。駒取り、成りは含まない。
  EVASIONS,			// 王手の回避
  NON_EVASIONS, // 王手がかかっていないときのすべての指し手　CAPTURES + QUIETS
  LEGAL // 合法手すべて
  // ※　王手になる指し手のみの生成はないので詰み系の探索をするにはこれでは足りないが…。
  // LEGALは、そこそこ重い。rootやbookなどでしか使わず、通常探索中は呼び出さないようだ。
};

/*
generate<CAPTURES> すべての仮の合法な捕獲する手、queenの昇格する手。
generate<QUIETS> すべての仮の合法な捕獲しない手と成らない手。
generate<QUIET_CHECKS> すべての仮の合法な捕獲せず、成らない手による王手。
generate<EVASIONS> 	手番側が王手がかかっているときに、王手を回避する手を生成する。
generate<NON_EVASION> すべての仮の合法な捕獲する手と捕獲しない手。

備考) 駒を取る手、クイーンに成る手はCAPTURE、それ以外のルーク、ビショップ、ナイトに成る手(under promote)はQUIETSに分類される

a) 王手がかかっていないときの指し手生成
	CAPTURES + QUIETS = NON_EVASION
の関係が成り立つ。

また、QUIETSかつ、王手になる手がQUIET_CHECKS。
  CAPTURESとQUIETSは排反なので、QUIETSに含まれるQUIET_CHECKSは、CAPTURESと排反。
  指し手オーダリングにおいて、指し手を逐次生成するときにCAPTURES→QUIET_CHECKSのように生成するのに使う。

b) 王手がかかっているときの指し手生成
	EVASIONS

※　「仮の」(psudo-)と書いてあるのは、千日手や小駒の利きのある場所への王の移動はチェックしておらず、
	また、pinされている駒を動かして王を素抜かれるような指し手も生成しているからだと思われる。
	「仮の」(psudo-)とついていないのは、generate<LEGAL>のみである。これは本当に合法手しか生成しない。
	(ただし千日手はチェックしていない)

generate<LEGAL> 与えられた局面のすべての合法手を生成する。
→ 素抜きになるような駒は動かさない。王も敵の利きに移動する手は生成しない。その代わり、そこそこ重い。
　通常探索からは呼び出さない。root局面で全合法手を生成する・定跡の指し手が合法手かどうかを
  チェックするなどの目的で使う。(ようだ)
	
*/


class Position;

// 指し手の生成。
// GenType : 生成する指し手の種別
// pos : 局面
// mlist : 生成する指し手用のバッファ(ここが生成された指し手の先頭となる)
// 戻り値 : 生成した指し手の終端(末尾の一つ先を示すポインタ)
// ※　ExtMoveは、指し手 + スコアの合体した64bitの構造体。
// ※　この直後、生成した指し手にスコアをつけてオーダリングするのでこの時点でもう64bitの指し手構造体に指し手生成してしまう。
template<GenType>
ExtMove* generate(const Position& pos, ExtMove* mlist);

/// The MoveList struct is a simple wrapper around generate(), sometimes comes
/// handy to use this class instead of the low level generate() function.
/*
以下のMoveList構造体は、generateまわりのシンプルなwrapperであり、時として
 低レベルなgenerate関数を呼び出すよりこのclassを使ったほうが便利であろう。

注記 : この構造体は指し手生成バッファを自前で持っている。指して生成バッファの確保を明示的に
したくないときに用いると良い。MoveList<LEGAL>と組み合わせて、合法手のみを生成したいときに使われる。
それ以外では、指し手生成バッファは事前に確保してあったものを使うのでこのクラスは用いない。
*/

template<GenType T>
struct MoveList {

  // 局面をコンストラクタの引数に渡して使う。すると指し手が生成され、lastが初期化されるので、
  // このclassのbegin(),end()が正常な値を返すようになる。
  explicit MoveList(const Position& pos) : last(generate<T>(pos, mlist)) {}

  // 内部的に持っている指し手生成バッファの先頭
  const ExtMove* begin() const { return mlist; }

  // 生成された指し手の末尾のひとつ先
  const ExtMove* end() const { return last; }

  // 生成された指し手の数
  size_t size() const { return last - mlist; }

  // 生成された指し手のなかに指し手mがあるかを判定する
  bool contains(Move m) const {
    for (const ExtMove& ms : *this) if (ms.move == m) return true;
    return false;
  }

private:
  // 指し手生成バッファも自前で持っている。
	// MAX_MOVES = 256(1局面でありうる指し手の最大数)
  ExtMove mlist[MAX_MOVES], *last;
};

#endif // #ifndef MOVEGEN_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

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 MOVEGEN_H_INCLUDED

#define MOVEGEN_H_INCLUDED

#include "types.h"

// 指し手生成の種別

// これはgenerate関数と組み合わせて使う。

// generate関数で指し手を生成するときに、生成する指し手の種別を指定できる。

enum GenType {

CAPTURES, // 駒を捕る手,queenの昇格する手 ※　将棋では銀以外を成る手もここに入れておくか。

QUIETS, // 駒を取らない手,成らない手 ※　将棋では銀を成る手もここに入れておくか。

QUIET_CHECKS, // 駒を取らない王手(QUIETSのなかで王手になる手のみ)。開き王手含む。駒取り、成りは含まない。

EVASIONS, // 王手の回避

NON_EVASIONS, // 王手がかかっていないときのすべての指し手　CAPTURES + QUIETS

LEGAL // 合法手すべて

// ※　王手になる指し手のみの生成はないので詰み系の探索をするにはこれでは足りないが…。

// LEGALは、そこそこ重い。rootやbookなどでしか使わず、通常探索中は呼び出さないようだ。

};

generate すべての仮の合法な捕獲する手、queenの昇格する手。

generate すべての仮の合法な捕獲しない手と成らない手。

generate すべての仮の合法な捕獲せず、成らない手による王手。

generate 手番側が王手がかかっているときに、王手を回避する手を生成する。

generate すべての仮の合法な捕獲する手と捕獲しない手。

備考) 駒を取る手、クイーンに成る手はCAPTURE、それ以外のルーク、ビショップ、ナイトに成る手(under promote)はQUIETSに分類される

a) 王手がかかっていないときの指し手生成

CAPTURES + QUIETS = NON_EVASION

の関係が成り立つ。

また、QUIETSかつ、王手になる手がQUIET_CHECKS。

CAPTURESとQUIETSは排反なので、QUIETSに含まれるQUIET_CHECKSは、CAPTURESと排反。

指し手オーダリングにおいて、指し手を逐次生成するときにCAPTURES→QUIET_CHECKSのように生成するのに使う。

b) 王手がかかっているときの指し手生成

EVASIONS

※　「仮の」(psudo-)と書いてあるのは、千日手や小駒の利きのある場所への王の移動はチェックしておらず、

また、pinされている駒を動かして王を素抜かれるような指し手も生成しているからだと思われる。

「仮の」(psudo-)とついていないのは、generateのみである。これは本当に合法手しか生成しない。

(ただし千日手はチェックしていない)

generate 与えられた局面のすべての合法手を生成する。

→ 素抜きになるような駒は動かさない。王も敵の利きに移動する手は生成しない。その代わり、そこそこ重い。

　通常探索からは呼び出さない。root局面で全合法手を生成する・定跡の指し手が合法手かどうかを

チェックするなどの目的で使う。(ようだ)

class Position;

// 指し手の生成。

// GenType : 生成する指し手の種別

// pos : 局面

// mlist : 生成する指し手用のバッファ(ここが生成された指し手の先頭となる)

// 戻り値 : 生成した指し手の終端(末尾の一つ先を示すポインタ)

// ※　ExtMoveは、指し手 + スコアの合体した64bitの構造体。

// ※　この直後、生成した指し手にスコアをつけてオーダリングするのでこの時点でもう64bitの指し手構造体に指し手生成してしまう。

template

ExtMove* generate(const Position& pos, ExtMove* mlist);

/// The MoveList struct is a simple wrapper around generate(), sometimes comes

/// handy to use this class instead of the low level generate() function.

以下のMoveList構造体は、generateまわりのシンプルなwrapperであり、時として

低レベルなgenerate関数を呼び出すよりこのclassを使ったほうが便利であろう。

注記 : この構造体は指し手生成バッファを自前で持っている。指して生成バッファの確保を明示的に

したくないときに用いると良い。MoveListと組み合わせて、合法手のみを生成したいときに使われる。

それ以外では、指し手生成バッファは事前に確保してあったものを使うのでこのクラスは用いない。

template

struct MoveList {

// 局面をコンストラクタの引数に渡して使う。すると指し手が生成され、lastが初期化されるので、

// このclassのbegin(),end()が正常な値を返すようになる。

explicit MoveList(const Position& pos) : last(generate(pos, mlist)) {}

// 内部的に持っている指し手生成バッファの先頭

const ExtMove* begin() const { return mlist; }

// 生成された指し手の末尾のひとつ先

const ExtMove* end() const { return last; }

// 生成された指し手の数

size_t size() const { return last - mlist; }

// 生成された指し手のなかに指し手mがあるかを判定する

bool contains(Move m) const {

for (const ExtMove& ms : *this) if (ms.move == m) return true;

return false;

}

private:

// 指し手生成バッファも自前で持っている。

// MAX_MOVES = 256(1局面でありうる指し手の最大数)

ExtMove mlist[MAX_MOVES], *last;

};

#endif // #ifndef MOVEGEN_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 "movegen.h"
#include "position.h"

/// Simple macro to wrap a very common while loop, no facny, no flexibility,
/// hardcoded names 'mlist' and 'from'.
// 非常に共通のwhileループをwrapするためのシンプルなマクロで、面白くもなく、柔軟性もなく、
// 'mlist'と'from'という変数名をハードコードしてある。

// bitboard bが与えられたときに変数"from"からこのbで示された各地点に移動する指し手をすべて生成するマクロ
#define SERIALIZE(b) while (b) (mlist++)->move = make_move(from, pop_lsb(&b))

/// Version used for pawns, where the 'from' square is given as a delta from the 'to' square
// 移動元のbitboard bが与えられ、その移動変化量d(盤面上のオフセット値)が与えられたときに、
// dの分だけ移動する指し手をすべて生成する。歩による指し手生成に使う。
#define SERIALIZE_PAWNS(b, d) while (b) { Square to = pop_lsb(&b); \
  (mlist++)->move = make_move(to - (d), to); }

namespace {

  // キャスリングの指し手のみ生成する指し手生成
  template<CastlingSide Side, bool Checks, bool Chess960>
  ExtMove* generate_castle(const Position& pos, ExtMove* mlist, Color us) {

    if (pos.castle_impeded(us, Side) || !pos.can_castle(make_castle_right(us, Side)))
      return mlist;

    // After castling, the rook and king final positions are the same in Chess960
    // as they would be in standard chess.
    Square kfrom = pos.king_square(us);
    Square rfrom = pos.castle_rook_square(us, Side);
    Square kto = relative_square(us, Side == KING_SIDE ? SQ_G1 : SQ_C1);
    Bitboard enemies = pos.pieces(~us);

    assert(!pos.checkers());

    const int K = Chess960 ? kto > kfrom ? -1 : 1
      : Side == KING_SIDE ? -1 : 1;

    for (Square s = kto; s != kfrom; s += (Square)K)
    if (pos.attackers_to(s) & enemies)
      return mlist;

    // Because we generate only legal castling moves we need to verify that
    // when moving the castling rook we do not discover some hidden checker.
    // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
    if (Chess960 && (attacks_bb<ROOK>(kto, pos.pieces() ^ rfrom) & pos.pieces(~us, ROOK, QUEEN)))
      return mlist;

    (mlist++)->move = make<CASTLE>(kfrom, rfrom);

    if (Checks && !pos.gives_check((mlist - 1)->move, CheckInfo(pos)))
      --mlist;

    return mlist;
  }

  // 成る指し手のみ生成する指し手生成
  // Deltaは移動する方向
  template<GenType Type, Square Delta>
  inline ExtMove* generate_promotions(ExtMove* mlist, Bitboard pawnsOn7,
    Bitboard target, const CheckInfo* ci) {

    Bitboard b = shift_bb<Delta>(pawnsOn7) & target;

    while (b)
    {
      Square to = pop_lsb(&b);

      if (Type == CAPTURES || Type == EVASIONS || Type == NON_EVASIONS)
        (mlist++)->move = make<PROMOTION>(to - Delta, to, QUEEN);

      if (Type == QUIETS || Type == EVASIONS || Type == NON_EVASIONS)
      {
        (mlist++)->move = make<PROMOTION>(to - Delta, to, ROOK);
        (mlist++)->move = make<PROMOTION>(to - Delta, to, BISHOP);
        (mlist++)->move = make<PROMOTION>(to - Delta, to, KNIGHT);
      }

      // Knight-promotion is the only one that can give a direct check not
      // already included in the queen-promotion.
      if (Type == QUIET_CHECKS && (StepAttacksBB[W_KNIGHT][to] & ci->ksq))
        (mlist++)->move = make<PROMOTION>(to - Delta, to, KNIGHT);
      else
        (void)ci; // Silence a warning under MSVC
    }

    return mlist;
  }


  template<Color Us, GenType Type>
  ExtMove* generate_pawn_moves(const Position& pos, ExtMove* mlist,
    Bitboard target, const CheckInfo* ci) {

    // チェスでは歩(ポーン)は、斜め移動や成りや２マス移動するのでこれだけ特殊化した関数を用意してある。

    // Compute our parametrized parameters at compile time, named according to
    // the point of view of white side.

    // ながとさんのブログより引用 : http://d.hatena.ne.jp/mclh46/20100825/1282750649
    // 先手白を基準に考えたコードを、後手でも流用するために、TRank8BBなら、
    // 白におけるRank8のビットを表すマスクをしろだったらRank8、黒だったらRank1とするようにする。
    // TranslateがTの意味だと思う。TRank7BBがあるのは成りこめるポーンの位置のマスク、
    // TRank3BBがあるのは、２マス移動できるように。

    const Color    Them = (Us == WHITE ? BLACK : WHITE);
    const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
    const Bitboard TRank7BB = (Us == WHITE ? Rank7BB : Rank2BB); // pawnが成れる場所
    const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);
    const Square   Up = (Us == WHITE ? DELTA_N : DELTA_S);
    const Square   Right = (Us == WHITE ? DELTA_NE : DELTA_SW);
    const Square   Left = (Us == WHITE ? DELTA_NW : DELTA_SE);

    Bitboard b1, b2, dc1, dc2, emptySquares;

    Bitboard pawnsOn7 = pos.pieces(Us, PAWN) &  TRank7BB;
    Bitboard pawnsNotOn7 = pos.pieces(Us, PAWN) & ~TRank7BB;

    Bitboard enemies = (Type == EVASIONS ? pos.pieces(Them) & target :
      Type == CAPTURES ? target : pos.pieces(Them));

    // Single and double pawn pushes, no promotions
    if (Type != CAPTURES)
    {
      emptySquares = (Type == QUIETS || Type == QUIET_CHECKS ? target : ~pos.pieces());

      b1 = shift_bb<Up>(pawnsNotOn7)   & emptySquares;
      b2 = shift_bb<Up>(b1 & TRank3BB) & emptySquares;

      if (Type == EVASIONS) // Consider only blocking squares
      {
        b1 &= target;
        b2 &= target;
      }

      if (Type == QUIET_CHECKS)
      {
        b1 &= pos.attacks_from<PAWN>(ci->ksq, Them);
        b2 &= pos.attacks_from<PAWN>(ci->ksq, Them);

        // Add pawn pushes which give discovered check. This is possible only
        // if the pawn is not on the same file as the enemy king, because we
        // don't generate captures. Note that a possible discovery check
        // promotion has been already generated among captures.
        if (pawnsNotOn7 & ci->dcCandidates)
        {
          dc1 = shift_bb<Up>(pawnsNotOn7 & ci->dcCandidates) & emptySquares & ~file_bb(ci->ksq);
          dc2 = shift_bb<Up>(dc1 & TRank3BB) & emptySquares;

          b1 |= dc1;
          b2 |= dc2;
        }
      }

      SERIALIZE_PAWNS(b1, Up);
      SERIALIZE_PAWNS(b2, Up + Up);
    }

    // Promotions and underpromotions
    if (pawnsOn7 && (Type != EVASIONS || (target & TRank8BB)))
    {
      if (Type == CAPTURES)
        emptySquares = ~pos.pieces();

      if (Type == EVASIONS)
        emptySquares &= target;

      mlist = generate_promotions<Type, Right>(mlist, pawnsOn7, enemies, ci);
      mlist = generate_promotions<Type, Left >(mlist, pawnsOn7, enemies, ci);
      mlist = generate_promotions<Type, Up>(mlist, pawnsOn7, emptySquares, ci);
    }

    // Standard and en-passant captures
    if (Type == CAPTURES || Type == EVASIONS || Type == NON_EVASIONS)
    {
      b1 = shift_bb<Right>(pawnsNotOn7) & enemies;
      b2 = shift_bb<Left >(pawnsNotOn7) & enemies;

      SERIALIZE_PAWNS(b1, Right);
      SERIALIZE_PAWNS(b2, Left);

      if (pos.ep_square() != SQ_NONE)
      {
        assert(rank_of(pos.ep_square()) == relative_rank(Us, RANK_6));

        // An en passant capture can be an evasion only if the checking piece
        // is the double pushed pawn and so is in the target. Otherwise this
        // is a discovery check and we are forced to do otherwise.
        if (Type == EVASIONS && !(target & (pos.ep_square() - Up)))
          return mlist;

        b1 = pawnsNotOn7 & pos.attacks_from<PAWN>(pos.ep_square(), Them);

        assert(b1);

        while (b1)
          (mlist++)->move = make<ENPASSANT>(pop_lsb(&b1), pos.ep_square());
      }
    }

    return mlist;
  }


  // 指し手生成
  // Ptは駒。ただし、王と歩の生成はここではやらない。
  // Checks == trueなら、王手になる手のみを生成する
  // target = 移動先
  template<PieceType Pt, bool Checks> FORCE_INLINE
    ExtMove* generate_moves(const Position& pos, ExtMove* mlist, Color us,
    Bitboard target, const CheckInfo* ci) {

      // 王と歩の指し手生成はここではやらない
      assert(Pt != KING && Pt != PAWN);

      // 駒種Ptの手番us側の駒の升が入っている配列の先頭
      const Square* pl = pos.list<Pt>(us);

      // この配列、終端はSQ_NONEが格納されていると仮定できる。
      // 駒種Ptの手番us側のそれぞれについて調べるループ
      for (Square from = *pl; from != SQ_NONE; from = *++pl)
      {
        // 王手をかける手のみを生成する場合
        if (Checks)
        {
          // 大雑把な必要条件によって、かすりもしないことがわかっているなら
          // この駒による指し手生成を除外。(continueする)

          // 角・飛・女王なら
          // その駒の利き(利きが遮断されていることは考慮しない)を移動先の候補として、
          // そのなかから、targetとして指定された升を抽出。
          // さらに、その升に駒種Ptをおいたときに敵玉に王手となる升でなければならない。(これがci->checkSq[pt])
          // これらは必要条件であり、この必要条件を満たさないならば王手にならない。

          // PseudoAttacks[pt][from] = 盤上の駒を考慮しないfromからの利き。(ROOKなら十字方向、盤の端まで)
          // checkSq[pt] = 駒種Ptで王手となる升
          // すくなくともこの２つが交差しないと王手になりようがない。

          if ((Pt == BISHOP || Pt == ROOK || Pt == QUEEN)
            && !(PseudoAttacks[Pt][from] & target & ci->checkSq[Pt]))
            continue;

          // unlikelyは単なるアノテーション用。無視して読んで良い。
          // dcCandidatesは動かすと敵玉に王手となる自駒の候補のbitboard
          // 開き王手は別のところでチェックしているのでここでは生成しない
          if (unlikely(ci->dcCandidates) && (ci->dcCandidates & from))
            continue;
        }

        // Ptの駒種に対してfromから利いている升で、かつ、targetにある升を列挙。
        // こちらは大駒でも合法手のみ生成
        Bitboard b = pos.attacks_from<Pt>(from) & target;

        // 王手をしなければならないなら、その駒によって王手になる場所のみを列挙
        if (Checks)
          b &= ci->checkSq[Pt];

        // これでBitboardが生成できた
        SERIALIZE(b);
      }

      return mlist;
    }

  // 指し手生成
  // target = 移動先の候補。これが指定されているときは、ここに移動させる手しか生成しない。
  // Type = CAPTURES,QUIETS,NON_EVASIONS,QUIET_CHECKSのときはこれが使われる
  template<Color Us, GenType Type> FORCE_INLINE
    ExtMove* generate_all(const Position& pos, ExtMove* mlist, Bitboard target,
    const CheckInfo* ci = nullptr) {

      // 王手になる手のみを生成するのか
      const bool Checks = Type == QUIET_CHECKS;

      mlist = generate_pawn_moves<Us, Type>(pos, mlist, target, ci);
      mlist = generate_moves<KNIGHT, Checks>(pos, mlist, Us, target, ci);
      mlist = generate_moves<BISHOP, Checks>(pos, mlist, Us, target, ci);
      mlist = generate_moves<  ROOK, Checks>(pos, mlist, Us, target, ci);
      mlist = generate_moves< QUEEN, Checks>(pos, mlist, Us, target, ci);

      // 王を移動させて王手になるのは空き王手のケースのみで、
      // これはQUIET_CHECKSのときは呼び出し元で生成している。
      // またEVASIONのときは、ここではなく事前に王の移動による回避手は生成されている
      // (generate<EVASIONS>のなかで)
      if (Type != QUIET_CHECKS && Type != EVASIONS)
      {
        // ここで生成しているのは仮の手であり、玉の移動先に敵の利きがあるかどうかは調べていない。

        // 自玉
        Square from = pos.king_square(Us);

        // 移動先候補としてtarget
        Bitboard b = pos.attacks_from<KING>(from) & target;
        SERIALIZE(b);
      }

      // キャスリングの指し手か..

      if (Type != CAPTURES && Type != EVASIONS && pos.can_castle(Us))
      {
        if (pos.is_chess960())
        {
          mlist = generate_castle< KING_SIDE, Checks, true>(pos, mlist, Us);
          mlist = generate_castle<QUEEN_SIDE, Checks, true>(pos, mlist, Us);
        }
        else
        {
          mlist = generate_castle< KING_SIDE, Checks, false>(pos, mlist, Us);
          mlist = generate_castle<QUEEN_SIDE, Checks, false>(pos, mlist, Us);
        }
      }

      return mlist;
    }


} // namespace


/// generate<CAPTURES> generates all pseudo-legal captures and queen
/// promotions. Returns a pointer to the end of the move list.
///
/// generate<QUIETS> generates all pseudo-legal non-captures and
/// underpromotions. Returns a pointer to the end of the move list.
///
/// generate<NON_EVASIONS> generates all pseudo-legal captures and
/// non-captures. Returns a pointer to the end of the move list.
/*
generate<CAPTURES> すべての仮の合法な捕獲する手、queenの昇格する手。
generate<QUIETS> すべての仮の合法な捕獲しない手と成らない手。
generate<NON_EVASION> すべての仮の合法な捕獲する手と捕獲しない手。

a) 王手がかかっていないときの指し手生成
CAPTURES + QUIETS = NON_EVASION
の関係が成り立つ。

また、QUIETSかつ、王手になる手がQUIET_CHECKS。

b) 王手がかかっているときの指し手生成
EVASIONS

備考) 駒を取る手、クイーンに成る手はCAPTURE、それ以外のルーク、ビショップ、ナイトに
成る手(under promote)はQUIETSに分類される

※　「仮の」(psudo-)と書いてあるのは、千日手や小駒の利きのある場所への王の移動はチェックしておらず、
また、pinされている駒を動かして王を素抜かれるような指し手も生成しているからだと思われる。
「仮の」(psudo-)とついていないのは、generate<LEGAL>のみである。これは本当に合法手しか生成しない。
(ただし千日手はチェックしていない)
*/
template<GenType Type>
ExtMove* generate(const Position& pos, ExtMove* mlist) {

  // CAPTURESとQUIETSとNON_EVASIONSでなければならない
  assert(Type == CAPTURES || Type == QUIETS || Type == NON_EVASIONS);

  // この関数を呼び出すとき、王手がかかっていてはならない。
  assert(!pos.checkers());

  // 現局面の手番
  Color us = pos.side_to_move();

  // 駒の移動先を選択。
  // 1) CAPTURES : 駒を捕獲するならば、相手の駒がある地点が移動先
  //  →　成りも含めるのであればここに含めるべき。
  // 2) QUIETS   : 静止探索用？ 駒がない場所が移動先
  // 3) NON_EVASIONS : 自駒がない場所(捕獲は可能)が移動先
  // ※　将棋の場合、成り/引き成りがあって、CAPTURESにそれらの指し手も追加しないといけなくて
  // なかなか難しいものがあるな…。
  Bitboard target = Type == CAPTURES ? pos.pieces(~us)
    : Type == QUIETS ? ~pos.pieces()
    : Type == NON_EVASIONS ? ~pos.pieces(us) : 0;

  return us == WHITE ? generate_all<WHITE, Type>(pos, mlist, target)
    : generate_all<BLACK, Type>(pos, mlist, target);
}

// Explicit template instantiations
// 明示的なテンプレートの初期化
template ExtMove* generate<CAPTURES>(const Position&, ExtMove*);
template ExtMove* generate<QUIETS>(const Position&, ExtMove*);
template ExtMove* generate<NON_EVASIONS>(const Position&, ExtMove*);


/// generate<QUIET_CHECKS> generates all pseudo-legal non-captures and knight
/// underpromotions that give check. Returns a pointer to the end of the move list.
// すべての仮の合法な捕獲しない手とナイトにならない指し手による王手。(この訳あってる？)
// つまり、捕獲しない手と成らない王手。
// ここで生成する指し手には相手の利きに玉を動かす手や、pinされている駒を動かす手も含まれている。

// ※　この関数では開き王手になる候補の駒の指し手だけを生成し、そのあとgenerate_allで直接王手を生成する。
// 将棋ではこの特殊化はあまりいいコードにならないのでやめたほうがいいかも。

template<>
ExtMove* generate<QUIET_CHECKS>(const Position& pos, ExtMove* mlist) {

  // 王手がかかっている局面でこの関数を呼び出してはならない
  assert(!pos.checkers());

  // 手番側
  Color us = pos.side_to_move();

  // pinされている駒などを調べるためのhelper
  CheckInfo ci(pos);

  // 移動させることで敵玉に対して空き王手になる可能性がある駒
  Bitboard dc = ci.dcCandidates;

  // 開き王手となる候補の駒それぞれに関して
  while (dc)
  {
    // 駒の移動元
    Square from = pop_lsb(&dc);
    // そこにある駒種
    PieceType pt = type_of(pos.piece_on(from));

    // 歩は除外してある。generate_allで一括して生成するためか？
    // ※　将棋だと歩を移動させて開き王手になることはないのだが…。
    if (pt == PAWN)
      continue; // Will be generated togheter with direct checks

    // この駒の移動先(王手になる)のbitboard
    // 利きがあり、駒を捕獲しない場所が移動先の候補
    Bitboard b = pos.attacks_from(Piece(pt), from) & ~pos.pieces();

    // 動かす駒が王ならば、敵玉からQUEENの利き上への移動は開き王手にならない
    // (背後に駒が隠れていることがない)と考えられる。

    // 例) 次ケースだと金を右上に移動させることで角による開き王手になるのだが、
    // 　　この金が自王だと、このようなパターンは生じない。
    // 角□□
    // □金□
    // □□^王

    if (pt == KING)
      b &= ~PseudoAttacks[QUEEN][ci.ksq];

    // これ、開き王手になる候補の駒を無条件ですべての指し手を生成してしまっているが
    // いいのだろうか…。チェスでは比較的、大駒ばかりなのでこの候補となる駒は移動させると
    // 必ず王手になる。
        
    // 将棋の場合、pinされている方向とは違う方向に動かす指し手のみ生成するべきである。
    // 例)
    // else {
    //       // pinされている方向とは違う方向に動かす指し手のみ生成する。
    //        b &= ~LineBB[ci.ksq][from];
    // }

    SERIALIZE(b);
  }

  // それ以外は普通に生成。
  return us == WHITE ? generate_all<WHITE, QUIET_CHECKS>(pos, mlist, ~pos.pieces(), &ci)
    : generate_all<BLACK, QUIET_CHECKS>(pos, mlist, ~pos.pieces(), &ci);
}


/// generate<EVASIONS> generates all pseudo-legal check evasions when the side
/// to move is in check. Returns a pointer to the end of the move list.
/*
手番側が王手がかかっているときに、王手を回避する手を生成する。
*/
template<>
ExtMove* generate<EVASIONS>(const Position& pos, ExtMove* mlist) {

  // この関数を呼び出しているということは、王手がかかっているはずであり、
  // 王手をしている駒があるばすだから、checkers(王手をしている駒)が存在しなければおかしいのでassertを入れてある
  assert(pos.checkers());

  // 王手をしている駒の数のカウンター
  int checkersCnt = 0;

  // 手番側
  Color us = pos.side_to_move();

  // 手番側の玉(自玉)の位置
  Square ksq = pos.king_square(us), from = ksq /* For SERIALIZE */, checksq;

  // 自玉に王手をかけている敵の大駒
  Bitboard sliderAttacks = 0;
  Bitboard b = pos.checkers();

  // このassert、上にあるから重複していて無駄だと思う。
  assert(pos.checkers());

  // Find squares attacked by slider checkers, we will remove them from the king
  // evasions so to skip known illegal moves avoiding useless legality check later.
  // 遠方駒による利きの升を見つけ、のちの無駄な合法性のチェックを回避する
  // 既知の非合法の指し手をスキップするために王の回避手から取り除く。
  // ToDo : so toとavoidingのところ、訳し方がよくわからん。

  do
  {
    // 王手をしている敵の駒のカウントを加算
    ++checkersCnt;

    // 王手をしている敵の駒の位置を取り出す
    checksq = pop_lsb(&b);

    // この駒は敵駒でなくてはならない
    assert(color_of(pos.piece_on(checksq)) == ~us);

    // この駒が大駒であるなら、この駒と王とを結ぶ直線上の升を大駒による攻撃升として追加。
    // (玉をこの大駒の利き上に移動させてはならないので)
    // 例) ^飛 王 
    // となっているとき、王は右には移動できない。敵の飛を捕る移動は出来る。
    if (type_of(pos.piece_on(checksq)) > KNIGHT) // A slider
      // ※　将棋ならば大駒の判定のため、この式は変更する必要がある。
      sliderAttacks |= LineBB[checksq][ksq] ^ checksq;

    // これ、slider以外の場合、その駒の利きをmaskしておいたほうが
    // KINGの移動先が減っていいと思うのだが。

  } while (b);

  // Generate evasions for king, capture and non capture moves
  // 王手回避のための玉の移動先は、自駒のない場所でかつ大駒が利いていないところが候補として挙げられる
  b = pos.attacks_from<KING>(ksq) & ~pos.pieces(us) & ~sliderAttacks;
  // bにfrom(=ksg=自玉の場所)から移動させる手のみを生成する。
  SERIALIZE(b);

  // 両王手であるなら、王の移動のみが回避手となる。ゆえにこれで指し手生成は終了。
  if (checkersCnt > 1)
    return mlist; // Double check, only a king move can save the day

  // 両王手でないことは確定した

  // Generate blocking evasions or captures of the checking piece
  // 王と敵の王手をしている大駒との間の升への移動合および、相手の大駒を捕る手のみが有効であるから、
  // 移動先として、これらの升に限定した指し手生成を行う必要がある。
  Bitboard target = between_bb(checksq, ksq) | checksq;

  return us == WHITE ? generate_all<WHITE, EVASIONS>(pos, mlist, target)
    : generate_all<BLACK, EVASIONS>(pos, mlist, target);
}


/// generate<LEGAL> generates all the legal moves in the given position
// 与えられた局面のすべての合法手を生成する。
// → 素抜きになるような駒は動かさない。王も敵の利きに移動する手は生成しない。その代わり、そこそこ重い。
template<>
ExtMove* generate<LEGAL>(const Position& pos, ExtMove* mlist) {

  ExtMove *end, *cur = mlist;

  // 敵の大駒によってpinされている自駒を列挙
  Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
  // 自駒の位置
  Square ksq = pos.king_square(pos.side_to_move());

  // 王手がかかっているなら、回避手のみを生成。さもなくば通常の指し手のみを生成。
  end = pos.checkers() ? generate<EVASIONS>(pos, mlist)
    : generate<NON_EVASIONS>(pos, mlist);

  // 生成した指し手を1つずつ調べていく。
  while (cur != end)
    // pinされている駒がある状況において駒を動かすと素抜きに遭う可能性がある。
    // また、王の移動でも移動先に相手の利きがある可能性がある。
  if ((pinned || from_sq(cur->move) == ksq || type_of(cur->move) == ENPASSANT)
    && !pos.legal(cur->move, pinned))
    // 末尾の指し手を*curところにコピーすることにより、*curの指し手をremoveしている。
    cur->move = (--end)->move;
  else
    ++cur;

  // ※　将棋の場合、駒打ちは打ち歩詰め以外は合法なはずで、このようなチェックの仕方は馬鹿らしいのではないだろうか。

  return end;
}

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

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 "movegen.h"

#include "position.h"

/// Simple macro to wrap a very common while loop, no facny, no flexibility,

/// hardcoded names 'mlist' and 'from'.

// 非常に共通のwhileループをwrapするためのシンプルなマクロで、面白くもなく、柔軟性もなく、

// 'mlist'と'from'という変数名をハードコードしてある。

// bitboard bが与えられたときに変数"from"からこのbで示された各地点に移動する指し手をすべて生成するマクロ

#define SERIALIZE(b) while (b) (mlist++)->move = make_move(from, pop_lsb(&b))

/// Version used for pawns, where the 'from' square is given as a delta from the 'to' square

// 移動元のbitboard bが与えられ、その移動変化量d(盤面上のオフセット値)が与えられたときに、

// dの分だけ移動する指し手をすべて生成する。歩による指し手生成に使う。

#define SERIALIZE_PAWNS(b, d) while (b) { Square to = pop_lsb(&b); \

(mlist++)->move = make_move(to - (d), to); }

namespace {

// キャスリングの指し手のみ生成する指し手生成

template

ExtMove* generate_castle(const Position& pos, ExtMove* mlist, Color us) {

if (pos.castle_impeded(us, Side) || !pos.can_castle(make_castle_right(us, Side)))

return mlist;

// After castling, the rook and king final positions are the same in Chess960

// as they would be in standard chess.

Square kfrom = pos.king_square(us);

Square rfrom = pos.castle_rook_square(us, Side);

Square kto = relative_square(us, Side == KING_SIDE ? SQ_G1 : SQ_C1);

Bitboard enemies = pos.pieces(~us);

assert(!pos.checkers());

const int K = Chess960 ? kto > kfrom ? -1 : 1

: Side == KING_SIDE ? -1 : 1;

for (Square s = kto; s != kfrom; s += (Square)K)

if (pos.attackers_to(s) & enemies)

return mlist;

// Because we generate only legal castling moves we need to verify that

// when moving the castling rook we do not discover some hidden checker.

// For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.

if (Chess960 && (attacks_bb(kto, pos.pieces() ^ rfrom) & pos.pieces(~us, ROOK, QUEEN)))

return mlist;

(mlist++)->move = make(kfrom, rfrom);

if (Checks && !pos.gives_check((mlist - 1)->move, CheckInfo(pos)))

--mlist;

return mlist;

}

// 成る指し手のみ生成する指し手生成

// Deltaは移動する方向

template

inline ExtMove* generate_promotions(ExtMove* mlist, Bitboard pawnsOn7,

Bitboard target, const CheckInfo* ci) {

Bitboard b = shift_bb(pawnsOn7) & target;

while (b)

{

Square to = pop_lsb(&b);

if (Type == CAPTURES || Type == EVASIONS || Type == NON_EVASIONS)

(mlist++)->move = make(to - Delta, to, QUEEN);

if (Type == QUIETS || Type == EVASIONS || Type == NON_EVASIONS)

{

(mlist++)->move = make(to - Delta, to, ROOK);

(mlist++)->move = make(to - Delta, to, BISHOP);

(mlist++)->move = make(to - Delta, to, KNIGHT);

}

// Knight-promotion is the only one that can give a direct check not

// already included in the queen-promotion.

if (Type == QUIET_CHECKS && (StepAttacksBB[W_KNIGHT][to] & ci->ksq))

(mlist++)->move = make(to - Delta, to, KNIGHT);

else

(void)ci; // Silence a warning under MSVC

}

return mlist;

}

template

ExtMove* generate_pawn_moves(const Position& pos, ExtMove* mlist,

Bitboard target, const CheckInfo* ci) {

// チェスでは歩(ポーン)は、斜め移動や成りや２マス移動するのでこれだけ特殊化した関数を用意してある。

// Compute our parametrized parameters at compile time, named according to

// the point of view of white side.

// ながとさんのブログより引用 : http://d.hatena.ne.jp/mclh46/20100825/1282750649

// 先手白を基準に考えたコードを、後手でも流用するために、TRank8BBなら、

// 白におけるRank8のビットを表すマスクをしろだったらRank8、黒だったらRank1とするようにする。

// TranslateがTの意味だと思う。TRank7BBがあるのは成りこめるポーンの位置のマスク、

// TRank3BBがあるのは、２マス移動できるように。

const Color Them = (Us == WHITE ? BLACK : WHITE);

const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);

const Bitboard TRank7BB = (Us == WHITE ? Rank7BB : Rank2BB); // pawnが成れる場所

const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);

const Square Up = (Us == WHITE ? DELTA_N : DELTA_S);

const Square Right = (Us == WHITE ? DELTA_NE : DELTA_SW);

const Square Left = (Us == WHITE ? DELTA_NW : DELTA_SE);

Bitboard b1, b2, dc1, dc2, emptySquares;

Bitboard pawnsOn7 = pos.pieces(Us, PAWN) & TRank7BB;

Bitboard pawnsNotOn7 = pos.pieces(Us, PAWN) & ~TRank7BB;

Bitboard enemies = (Type == EVASIONS ? pos.pieces(Them) & target :

Type == CAPTURES ? target : pos.pieces(Them));

// Single and double pawn pushes, no promotions

if (Type != CAPTURES)

{

emptySquares = (Type == QUIETS || Type == QUIET_CHECKS ? target : ~pos.pieces());

b1 = shift_bb(pawnsNotOn7) & emptySquares;

b2 = shift_bb(b1 & TRank3BB) & emptySquares;

if (Type == EVASIONS) // Consider only blocking squares

{

b1 &= target;

b2 &= target;

}

if (Type == QUIET_CHECKS)

{

b1 &= pos.attacks_from(ci->ksq, Them);

b2 &= pos.attacks_from(ci->ksq, Them);

// Add pawn pushes which give discovered check. This is possible only

// if the pawn is not on the same file as the enemy king, because we

// don't generate captures. Note that a possible discovery check

// promotion has been already generated among captures.

if (pawnsNotOn7 & ci->dcCandidates)

{

dc1 = shift_bb(pawnsNotOn7 & ci->dcCandidates) & emptySquares & ~file_bb(ci->ksq);

dc2 = shift_bb(dc1 & TRank3BB) & emptySquares;

b1 |= dc1;

b2 |= dc2;

}

SERIALIZE_PAWNS(b1, Up);

SERIALIZE_PAWNS(b2, Up + Up);

}

// Promotions and underpromotions

if (pawnsOn7 && (Type != EVASIONS || (target & TRank8BB)))

{

if (Type == CAPTURES)

emptySquares = ~pos.pieces();

if (Type == EVASIONS)

emptySquares &= target;

mlist = generate_promotions(mlist, pawnsOn7, enemies, ci);

mlist = generate_promotions(mlist, pawnsOn7, emptySquares, ci);

}

// Standard and en-passant captures

if (Type == CAPTURES || Type == EVASIONS || Type == NON_EVASIONS)

{

b1 = shift_bb(pawnsNotOn7) & enemies;

b2 = shift_bb(pawnsNotOn7) & enemies;

SERIALIZE_PAWNS(b1, Right);

SERIALIZE_PAWNS(b2, Left);

if (pos.ep_square() != SQ_NONE)

{

assert(rank_of(pos.ep_square()) == relative_rank(Us, RANK_6));

// An en passant capture can be an evasion only if the checking piece

// is the double pushed pawn and so is in the target. Otherwise this

// is a discovery check and we are forced to do otherwise.

if (Type == EVASIONS && !(target & (pos.ep_square() - Up)))

return mlist;

b1 = pawnsNotOn7 & pos.attacks_from(pos.ep_square(), Them);

assert(b1);

while (b1)

(mlist++)->move = make(pop_lsb(&b1), pos.ep_square());

}

return mlist;

}

// 指し手生成

// Ptは駒。ただし、王と歩の生成はここではやらない。

// Checks == trueなら、王手になる手のみを生成する

// target = 移動先

template FORCE_INLINE

ExtMove* generate_moves(const Position& pos, ExtMove* mlist, Color us,

Bitboard target, const CheckInfo* ci) {

// 王と歩の指し手生成はここではやらない

assert(Pt != KING && Pt != PAWN);

// 駒種Ptの手番us側の駒の升が入っている配列の先頭

const Square* pl = pos.list(us);

// この配列、終端はSQ_NONEが格納されていると仮定できる。

// 駒種Ptの手番us側のそれぞれについて調べるループ

for (Square from = *pl; from != SQ_NONE; from = *++pl)

{

// 王手をかける手のみを生成する場合

if (Checks)

{

// 大雑把な必要条件によって、かすりもしないことがわかっているなら

// この駒による指し手生成を除外。(continueする)

// 角・飛・女王なら

// その駒の利き(利きが遮断されていることは考慮しない)を移動先の候補として、

// そのなかから、targetとして指定された升を抽出。

// さらに、その升に駒種Ptをおいたときに敵玉に王手となる升でなければならない。(これがci->checkSq[pt])

// これらは必要条件であり、この必要条件を満たさないならば王手にならない。

// PseudoAttacks[pt][from] = 盤上の駒を考慮しないfromからの利き。(ROOKなら十字方向、盤の端まで)

// checkSq[pt] = 駒種Ptで王手となる升

// すくなくともこの２つが交差しないと王手になりようがない。

if ((Pt == BISHOP || Pt == ROOK || Pt == QUEEN)

&& !(PseudoAttacks[Pt][from] & target & ci->checkSq[Pt]))

continue;

// unlikelyは単なるアノテーション用。無視して読んで良い。

// dcCandidatesは動かすと敵玉に王手となる自駒の候補のbitboard

// 開き王手は別のところでチェックしているのでここでは生成しない

if (unlikely(ci->dcCandidates) && (ci->dcCandidates & from))

continue;

}

// Ptの駒種に対してfromから利いている升で、かつ、targetにある升を列挙。

// こちらは大駒でも合法手のみ生成

Bitboard b = pos.attacks_from(from) & target;

// 王手をしなければならないなら、その駒によって王手になる場所のみを列挙

if (Checks)

b &= ci->checkSq[Pt];

// これでBitboardが生成できた

SERIALIZE(b);

}

return mlist;

}

// 指し手生成

// target = 移動先の候補。これが指定されているときは、ここに移動させる手しか生成しない。

// Type = CAPTURES,QUIETS,NON_EVASIONS,QUIET_CHECKSのときはこれが使われる

template FORCE_INLINE

ExtMove* generate_all(const Position& pos, ExtMove* mlist, Bitboard target,

const CheckInfo* ci = nullptr) {

// 王手になる手のみを生成するのか

const bool Checks = Type == QUIET_CHECKS;

mlist = generate_pawn_moves(pos, mlist, target, ci);

mlist = generate_moves(pos, mlist, Us, target, ci);

mlist = generate_moves< ROOK, Checks>(pos, mlist, Us, target, ci);

mlist = generate_moves< QUEEN, Checks>(pos, mlist, Us, target, ci);

// 王を移動させて王手になるのは空き王手のケースのみで、

// これはQUIET_CHECKSのときは呼び出し元で生成している。

// またEVASIONのときは、ここではなく事前に王の移動による回避手は生成されている

// (generateのなかで)

if (Type != QUIET_CHECKS && Type != EVASIONS)

{

// ここで生成しているのは仮の手であり、玉の移動先に敵の利きがあるかどうかは調べていない。

// 自玉

Square from = pos.king_square(Us);

// 移動先候補としてtarget

Bitboard b = pos.attacks_from(from) & target;

SERIALIZE(b);

}

// キャスリングの指し手か..

if (Type != CAPTURES && Type != EVASIONS && pos.can_castle(Us))

{

if (pos.is_chess960())

{

mlist = generate_castle< KING_SIDE, Checks, true>(pos, mlist, Us);

mlist = generate_castle(pos, mlist, Us);

}

else

{

mlist = generate_castle< KING_SIDE, Checks, false>(pos, mlist, Us);

mlist = generate_castle(pos, mlist, Us);

}

return mlist;

}

} // namespace

/// generate generates all pseudo-legal captures and queen

/// promotions. Returns a pointer to the end of the move list.

///

/// generate generates all pseudo-legal non-captures and

/// underpromotions. Returns a pointer to the end of the move list.

///

/// generate generates all pseudo-legal captures and

/// non-captures. Returns a pointer to the end of the move list.

generate すべての仮の合法な捕獲する手、queenの昇格する手。

generate すべての仮の合法な捕獲しない手と成らない手。

generate すべての仮の合法な捕獲する手と捕獲しない手。

a) 王手がかかっていないときの指し手生成

CAPTURES + QUIETS = NON_EVASION

の関係が成り立つ。

また、QUIETSかつ、王手になる手がQUIET_CHECKS。

b) 王手がかかっているときの指し手生成

EVASIONS

備考) 駒を取る手、クイーンに成る手はCAPTURE、それ以外のルーク、ビショップ、ナイトに

成る手(under promote)はQUIETSに分類される

※　「仮の」(psudo-)と書いてあるのは、千日手や小駒の利きのある場所への王の移動はチェックしておらず、

また、pinされている駒を動かして王を素抜かれるような指し手も生成しているからだと思われる。

「仮の」(psudo-)とついていないのは、generateのみである。これは本当に合法手しか生成しない。

(ただし千日手はチェックしていない)

template

ExtMove* generate(const Position& pos, ExtMove* mlist) {

// CAPTURESとQUIETSとNON_EVASIONSでなければならない

assert(Type == CAPTURES || Type == QUIETS || Type == NON_EVASIONS);

// この関数を呼び出すとき、王手がかかっていてはならない。

assert(!pos.checkers());

// 現局面の手番

Color us = pos.side_to_move();

// 駒の移動先を選択。

// 1) CAPTURES : 駒を捕獲するならば、相手の駒がある地点が移動先

// →　成りも含めるのであればここに含めるべき。

// 2) QUIETS : 静止探索用？駒がない場所が移動先

// 3) NON_EVASIONS : 自駒がない場所(捕獲は可能)が移動先

// ※　将棋の場合、成り/引き成りがあって、CAPTURESにそれらの指し手も追加しないといけなくて

// なかなか難しいものがあるな…。

Bitboard target = Type == CAPTURES ? pos.pieces(~us)

: Type == QUIETS ? ~pos.pieces()

: Type == NON_EVASIONS ? ~pos.pieces(us) : 0;

return us == WHITE ? generate_all(pos, mlist, target)

: generate_all(pos, mlist, target);

}

// Explicit template instantiations

// 明示的なテンプレートの初期化

template ExtMove* generate(const Position&, ExtMove*);

/// generate generates all pseudo-legal non-captures and knight

/// underpromotions that give check. Returns a pointer to the end of the move list.

// すべての仮の合法な捕獲しない手とナイトにならない指し手による王手。(この訳あってる？)

// つまり、捕獲しない手と成らない王手。

// ここで生成する指し手には相手の利きに玉を動かす手や、pinされている駒を動かす手も含まれている。

// ※　この関数では開き王手になる候補の駒の指し手だけを生成し、そのあとgenerate_allで直接王手を生成する。

// 将棋ではこの特殊化はあまりいいコードにならないのでやめたほうがいいかも。

template<>

ExtMove* generate(const Position& pos, ExtMove* mlist) {

// 王手がかかっている局面でこの関数を呼び出してはならない

assert(!pos.checkers());

// 手番側

Color us = pos.side_to_move();

// pinされている駒などを調べるためのhelper

CheckInfo ci(pos);

// 移動させることで敵玉に対して空き王手になる可能性がある駒

Bitboard dc = ci.dcCandidates;

// 開き王手となる候補の駒それぞれに関して

while (dc)

{

// 駒の移動元

Square from = pop_lsb(&dc);

// そこにある駒種

PieceType pt = type_of(pos.piece_on(from));

// 歩は除外してある。generate_allで一括して生成するためか？

// ※　将棋だと歩を移動させて開き王手になることはないのだが…。

if (pt == PAWN)

continue; // Will be generated togheter with direct checks

// この駒の移動先(王手になる)のbitboard

// 利きがあり、駒を捕獲しない場所が移動先の候補

Bitboard b = pos.attacks_from(Piece(pt), from) & ~pos.pieces();

// 動かす駒が王ならば、敵玉からQUEENの利き上への移動は開き王手にならない

// (背後に駒が隠れていることがない)と考えられる。

// 例) 次ケースだと金を右上に移動させることで角による開き王手になるのだが、

// 　　この金が自王だと、このようなパターンは生じない。

// 角□□

// □金□

// □□^王

if (pt == KING)

b &= ~PseudoAttacks[QUEEN][ci.ksq];

// これ、開き王手になる候補の駒を無条件ですべての指し手を生成してしまっているが

// いいのだろうか…。チェスでは比較的、大駒ばかりなのでこの候補となる駒は移動させると

// 必ず王手になる。

// 将棋の場合、pinされている方向とは違う方向に動かす指し手のみ生成するべきである。

// 例)

// else {

// // pinされている方向とは違う方向に動かす指し手のみ生成する。

// b &= ~LineBB[ci.ksq][from];

// }

SERIALIZE(b);

}

// それ以外は普通に生成。

return us == WHITE ? generate_all(pos, mlist, ~pos.pieces(), &ci)

: generate_all(pos, mlist, ~pos.pieces(), &ci);

}

/// generate generates all pseudo-legal check evasions when the side

/// to move is in check. Returns a pointer to the end of the move list.

手番側が王手がかかっているときに、王手を回避する手を生成する。

template<>

ExtMove* generate(const Position& pos, ExtMove* mlist) {

// この関数を呼び出しているということは、王手がかかっているはずであり、

// 王手をしている駒があるばすだから、checkers(王手をしている駒)が存在しなければおかしいのでassertを入れてある

assert(pos.checkers());

// 王手をしている駒の数のカウンター

int checkersCnt = 0;

// 手番側

Color us = pos.side_to_move();

// 手番側の玉(自玉)の位置

Square ksq = pos.king_square(us), from = ksq /* For SERIALIZE */, checksq;

// 自玉に王手をかけている敵の大駒

Bitboard sliderAttacks = 0;

Bitboard b = pos.checkers();

// このassert、上にあるから重複していて無駄だと思う。

assert(pos.checkers());

// Find squares attacked by slider checkers, we will remove them from the king

// evasions so to skip known illegal moves avoiding useless legality check later.

// 遠方駒による利きの升を見つけ、のちの無駄な合法性のチェックを回避する

// 既知の非合法の指し手をスキップするために王の回避手から取り除く。

// ToDo : so toとavoidingのところ、訳し方がよくわからん。

{

// 王手をしている敵の駒のカウントを加算

++checkersCnt;

// 王手をしている敵の駒の位置を取り出す

checksq = pop_lsb(&b);

// この駒は敵駒でなくてはならない

assert(color_of(pos.piece_on(checksq)) == ~us);

// この駒が大駒であるなら、この駒と王とを結ぶ直線上の升を大駒による攻撃升として追加。

// (玉をこの大駒の利き上に移動させてはならないので)

// 例) ^飛王

// となっているとき、王は右には移動できない。敵の飛を捕る移動は出来る。

if (type_of(pos.piece_on(checksq)) > KNIGHT) // A slider

// ※　将棋ならば大駒の判定のため、この式は変更する必要がある。

sliderAttacks |= LineBB[checksq][ksq] ^ checksq;

// これ、slider以外の場合、その駒の利きをmaskしておいたほうが

// KINGの移動先が減っていいと思うのだが。

} while (b);

// Generate evasions for king, capture and non capture moves

// 王手回避のための玉の移動先は、自駒のない場所でかつ大駒が利いていないところが候補として挙げられる

b = pos.attacks_from(ksq) & ~pos.pieces(us) & ~sliderAttacks;

// bにfrom(=ksg=自玉の場所)から移動させる手のみを生成する。

SERIALIZE(b);

// 両王手であるなら、王の移動のみが回避手となる。ゆえにこれで指し手生成は終了。

if (checkersCnt > 1)

return mlist; // Double check, only a king move can save the day

// 両王手でないことは確定した

// Generate blocking evasions or captures of the checking piece

// 王と敵の王手をしている大駒との間の升への移動合および、相手の大駒を捕る手のみが有効であるから、

// 移動先として、これらの升に限定した指し手生成を行う必要がある。

Bitboard target = between_bb(checksq, ksq) | checksq;

return us == WHITE ? generate_all(pos, mlist, target)

: generate_all(pos, mlist, target);

}

/// generate generates all the legal moves in the given position

// 与えられた局面のすべての合法手を生成する。

// → 素抜きになるような駒は動かさない。王も敵の利きに移動する手は生成しない。その代わり、そこそこ重い。

template<>

ExtMove* generate(const Position& pos, ExtMove* mlist) {

ExtMove *end, *cur = mlist;

// 敵の大駒によってpinされている自駒を列挙

Bitboard pinned = pos.pinned_pieces(pos.side_to_move());

// 自駒の位置

Square ksq = pos.king_square(pos.side_to_move());

// 王手がかかっているなら、回避手のみを生成。さもなくば通常の指し手のみを生成。

end = pos.checkers() ? generate(pos, mlist)

: generate(pos, mlist);

// 生成した指し手を1つずつ調べていく。

while (cur != end)

// pinされている駒がある状況において駒を動かすと素抜きに遭う可能性がある。

// また、王の移動でも移動先に相手の利きがある可能性がある。

if ((pinned || from_sq(cur->move) == ksq || type_of(cur->move) == ENPASSANT)

&& !pos.legal(cur->move, pinned))

// 末尾の指し手を*curところにコピーすることにより、*curの指し手をremoveしている。

cur->move = (--end)->move;

else

++cur;

// ※　将棋の場合、駒打ちは打ち歩詰め以外は合法なはずで、このようなチェックの仕方は馬鹿らしいのではないだろうか。

return end;

}

やねうら王公式サイト

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

Stockfish DD – movegen 指し手生成

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

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

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