SSブログ

Stockfishの指し手生成とBonanzaの指し手生成の違い [将棋]

やねうら王Blogの指し手生成のところを見た時に面白いことをしているなぁって思ったが、今日起きた問題は割りとそれに近いのだろうか

http://yaneuraou.yaneu.com/2015/01/06/stockfish-dd-notation-%E6%8C%87%E3%81%97%E6%89%8B%E6%96%87%E5%AD%97%E5%88%97%E3%81%AB%E5%A4%89%E6%8F%9B/


gpsfishのmove.cpp

合法手を生成して、それと一致する文字列と一致したらOKというようにして、合法手かどうかを担保している

// move_from_uci() takes a position and a string representing a move in
/// simple coordinate notation and returns an equivalent Move if any.
/// Moves are guaranteed to be legal.

Move move_from_uci(const Position& pos, const string& str) {

#ifdef GPSFISH
  return osl::record::usi::strToMove(str,pos.osl_state);
#else
  MoveStack mlist[MAX_MOVES];
  MoveStack* last = generate(pos, mlist);

  for (MoveStack* cur = mlist; cur != last; cur++)
      if (str == move_to_uci(cur->move, pos.is_chess960()))
          return cur->move;

  return MOVE_NONE;
#endif
}



movegen.cpp

非合法手を含む手を生成してから合法手なものだけを返すようになっている

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

#ifdef GPSFISH
  return generate(pos, mlist);
#else
  assert(pos.is_ok());

  MoveStack *last, *cur = mlist;
  Bitboard pinned = pos.pinned_pieces(pos.side_to_move());

  last = generate(pos, mlist);

  // Remove illegal moves from the list
  while (cur != last)
      if (!pos.pl_move_is_legal(cur->move, pinned))
          cur->move = (--last)->move;
      else
          cur++;

  return last;
#endif
}


非合法手の生成は、王手がかかっているかどうかで違う。王手がかかってたら逃げる一手

/// generate computes a complete list of legal
/// or pseudo-legal moves in the current position.
template<>
MoveStack* generate(const Position& pos, MoveStack* mlist) {

  assert(pos.is_ok());

  return pos.in_check() ? generate(pos, mlist)
                        : generate(pos, mlist);
}


gpsfishの場合は、その後はOSLのライブラリで、手を生成している関係で、
Stockfish的な処理はばっさりカットしている

Bonafishの場合だと、ここがBonanza風になると思うが、
よく言われる探索時に不成りは生成していないというのは、次のあたりだろうか

root.c

int
make_root_move_list( tree_t * restrict ptree )
{
    unsigned int * restrict pmove;
	int asort[MAX_LEGAL_MOVES] = { 0 };
    unsigned int move;
    int i, j, k, h, value, num_root_move, iret, value_pre_pv;
    int value_best;

    // 1. 指し手生成
    pmove = ptree->move_last[0];
    ptree->move_last[1] = GenCaptures( root_turn, pmove );
    ptree->move_last[1] = GenNoCaptures( root_turn, ptree->move_last[1] );
    ptree->move_last[1] = GenDrop( root_turn, ptree->move_last[1] );
    num_root_move = (int)( ptree->move_last[1] - pmove );


next.c

   static int CONV
gen_next_quies( tree_t * restrict ptree, int alpha, int turn, int ply,
        int qui_ply )
{
    switch ( ptree->anext_move[ply].next_phase )
    {
        case next_quies_gencap:
            { 
                unsigned int * restrict pmove;
                int * restrict psortv;
                int i, j, n, nqmove, value, min_score, diff;
                unsigned int move;

                ptree->move_last[ply] = GenCaptures( turn, ptree->move_last[ply-1] );


使われていない合法手生成ルーチン自体は以下のようになっている

int CONV gen_legal_moves( tree_t * restrict ptree, unsigned int *p0, int flag )
{
    unsigned int *p1;
    int i, j, n;

    p1 = GenCaptures( root_turn, p0 );
    p1 = GenNoCaptures( root_turn, p1 );
    if ( flag )
    {
        p1 = GenCapNoProEx2( root_turn, p1 );
        p1 = GenNoCapNoProEx2( root_turn, p1 );
    }
    p1 = GenDrop( root_turn, p1 );


flagによって生成したりしなかったりするが、ponderの場合は出力して、
outmoveというコマンドの場合は出力しないようになっている

また、学習時には、全部生成するようになっている

learn1.c

    //すべての合法手生成
    pmove = GenCaptures     ( pdata->root_turn, pdata->amove_legal );
    pmove = GenNoCaptures   ( pdata->root_turn, pmove );
    pmove = GenDrop         ( pdata->root_turn, pmove );
    pmove = GenCapNoProEx2  ( pdata->root_turn, pmove );
    pmove = GenNoCapNoProEx2( pdata->root_turn, pmove );


というのを総合すると

Stockfishは

全部の合法手=偽合法手ー非合法手

Bonanzaは

合法手=全部の合法手ー不成り以外の手

となっていて、StockfishとBonanzaでは指し手生成の思想が違うのでgenerateの中をいれかえるような単純移植だと噛み合わない。
最初からちゃんとした合法手ができてる場合は、Stockfishのように変に判定を入れる必要はないような気がするがどうなんだろうか。

gpsfishが文字列を指し手に変換するだけの漢仕様なのは、クラスタの末端なので、上位がバグってなければ問題無いという信用で成り立っているようだが、将棋倶楽部24なんかだと王手放置が飛んでくるので、非合法手の場合の処理をいけなかったらしい

AperyだとPinされているても動かして開き王手も生成しているようなので、Stockfishポリシーと同じようです。(探索の方見てないので、確証はないですが)

	// 部分特殊化
	// Evasion のときに歩、飛、角と、香の2段目の不成も生成する。
	template  struct GenerateMoves {
		FORCE_INLINE MoveStack* operator () (MoveStack* moveStackList, const Position& pos) {
			MoveStack* curr = moveStackList;
			const Bitboard pinned = pos.pinnedBB();

			moveStackList = pos.inCheck() ?
				GenerateMoves()(moveStackList, pos) : GenerateMoves()(moveStackList, pos);

			// 玉の移動による自殺手と、pinされている駒の移動による自殺手を削除
			while (curr != moveStackList) {
				if (!pos.pseudoLegalMoveIsLegal(curr->move, pinned)) {
					curr->move = (--moveStackList)->move;
				}
				else {
					++curr;
				}
			}

			return moveStackList;
		}


不成りも生成するっていうのが、詰みが関わる場面では速度よりも信頼性ってことでしょうか。
2015年以降はApery参考にしておけば間違いないでしょう。

おまけ

http://emptywords.hatenadiary.jp/entry/2014/04/09/193055

<追記>
http://yaneuraou.yaneu.com/2015/03/22/selene%E3%81%8C%E5%8F%8D%E5%89%87%E8%B2%A0%E3%81%91%E3%81%97%E3%81%9F%E3%82%88%E3%81%86%E3%81%A7%E3%81%99%E3%81%8C/

同じことを考えていたようで安心した
確かに学習時に気がつくはずというのはあるので、学習は別で動かしてたとか、バグを発見できなかった理由はいろいろありそう

まあ、時代はAperyいじってれば間違いない。
Stockfishの最新版(今は6のRC3)は定跡ルーチンが消えているので、アップデートする気が激減した。しかもバグ含みで弱いし。


nice!(0)  コメント(0)  トラックバック(0) 
共通テーマ:パソコン・インターネット

nice! 0

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

トラックバック 0

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。