連載やねうら王miniで遊ぼう！9日目

投稿日時: 2015年12月19日投稿者: やねうらお

今回は、ランダムプレイヤーを作ってみます。

ランダムプレイヤーのプログラム

ランダムプレイヤーというのは、合法手のなかからランダムに一手選んで指すプレイヤーである。先後、両方がランダムプレイヤーであれば、あっという間に1局が終わる。(思考時間がほぼゼロなので…)

理屈はともかく、プログラムを書いてみよう。

void random_player(Position& pos,uint64_t loop_max)
{
  pos.init();
  const int MAX_PLY = 256; // 256手までテスト

  StateInfo state[MAX_PLY]; // StateInfoを最大手数分だけ
  Move moves[MAX_PLY]; // 局面の巻き戻し用に指し手を記憶
  int ply; // 初期局面からの手数

  for (int i = 0; i < loop_max; ++i)
  {
    for (ply = 0; ply < MAX_PLY; ++ply)
    {
      MoveList<LEGAL_ALL> mg(pos); // 全合法手の生成

      // 合法な指し手がなかった == 詰み
      if (mg.size() == 0)
        break;

      // 局面がおかしくなっていないかをテストする
      ASSERT_LV3(is_ok(pos));

      pos.check_info_update();

      // ここで生成された指し手がすべて合法手であるかテストをする
      for (auto m : mg)
      {
        ASSERT_LV3(pos.pseudo_legal(m.move));
        ASSERT_LV2(pos.legal(m.move));
      }

      // 生成された指し手のなかからランダムに選び、その指し手で局面を進める。
      Move m = mg.begin()[rand() % mg.size()].move;

      pos.do_move(m, state[ply]);
      moves[ply] = m;
    }
    // 局面を巻き戻してみる(undo_moveの動作テストを兼ねて)
    while (ply > 0)
      pos.undo_move(moves[--ply]);

    // 1000回に1回ごとに'.'を出力(進んでいることがわかるように)
    if ((i % 1000) == 0)
      cout << ".";
  }
}

// ランダムプレイヤー(指し手をランダムに選ぶプレイヤー)による自己対戦テスト
// これを1000万回ほどまわせば、指し手生成などにバグがあればどこかで引っかかるはず。

void user_test(Position& pos, istringstream& is)
{
  uint64_t loop_max = 100000000; // 1000万回
  is >> loop_max;
  cout << "Random Player test , loop_max = " << loop_max << endl;
  random_player(pos, loop_max);
  cout << "finished." << endl;
}

void random_player(Position& pos,uint64_t loop_max)

{

pos.init();

const int MAX_PLY = 256; // 256手までテスト

StateInfo state[MAX_PLY]; // StateInfoを最大手数分だけ

Move moves[MAX_PLY]; // 局面の巻き戻し用に指し手を記憶

int ply; // 初期局面からの手数

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

{

for (ply = 0; ply < MAX_PLY; ++ply)

{

MoveList mg(pos); // 全合法手の生成

// 合法な指し手がなかった == 詰み

if (mg.size() == 0)

break;

// 局面がおかしくなっていないかをテストする

ASSERT_LV3(is_ok(pos));

pos.check_info_update();

// ここで生成された指し手がすべて合法手であるかテストをする

for (auto m : mg)

{

ASSERT_LV3(pos.pseudo_legal(m.move));

ASSERT_LV2(pos.legal(m.move));

}

// 生成された指し手のなかからランダムに選び、その指し手で局面を進める。

Move m = mg.begin()[rand() % mg.size()].move;

pos.do_move(m, state[ply]);

moves[ply] = m;

}

// 局面を巻き戻してみる(undo_moveの動作テストを兼ねて)

while (ply > 0)

pos.undo_move(moves[--ply]);

// 1000回に1回ごとに'.'を出力(進んでいることがわかるように)

if ((i % 1000) == 0)

cout << ".";

}

// ランダムプレイヤー(指し手をランダムに選ぶプレイヤー)による自己対戦テスト

// これを1000万回ほどまわせば、指し手生成などにバグがあればどこかで引っかかるはず。

void user_test(Position& pos, istringstream& is)

{

uint64_t loop_max = 100000000; // 1000万回

is >> loop_max;

cout << "Random Player test , loop_max = " << loop_max << endl;

random_player(pos, loop_max);

cout << "finished." << endl;

}

いままで説明で出てきたものしか使っていないので、ここまでのことが理解できていれば、わりとすんなり読めるかと思う。

ASSERT_LV3ってなに？

ソースコード中、次の部分には説明を要する。

      // ここで生成された指し手がすべて合法手であるかテストをする
      for (auto m : mg)
      {
        ASSERT_LV3(pos.pseudo_legal(m.move));
        ASSERT_LV2(pos.legal(m.move));
      }

// ここで生成された指し手がすべて合法手であるかテストをする

for (auto m : mg)

{

ASSERT_LV3(pos.pseudo_legal(m.move));

ASSERT_LV2(pos.legal(m.move));

}

指し手の合法性のテストをするのに何故関数が２つ必要なのかについては次回、説明する。

それより、ASSERT_LV2とか3とか、これはなんぞや？

MSVC(Visual C++)だとassert()は、デバッグビルドのときしか有効ではない。リリースビルドのときもassert()を有効にしたい。(ことがある)

また、assertも何段階か設けて、実行に5倍ぐらいの時間がかかってもいいから細かくassertをかけてチェックしたい場合もあれば、軽量なassertで30%程度の速度ダウンで実行されて欲しい場合とがある。

そこで独自のassertを作り、assertのレベルを5段階にした。

LV0 : assertなし。
LV1 : 軽めのassert
…
LV5 : 超強力なassert。すこぶる遅くなる。

※　なぜLV5(レベルファイブ)まであるのかというと、単に語呂が良いからである。「俺の(やねうら王miniの改造で作っている)将棋ソフトのassert、レベルファイブなんだぜ？」などとクリスマス前までに気になる女の子に告白してみてはどうだろうか。

さて、このassertは以下のような実装になっている。

// --- assertion tools

// DEBUGビルドでないとassertが無効化されてしまうので無効化されないASSERT
// 故意にメモリアクセス違反を起こすコード。
#define ASSERT(X) { if (!(X)) *(int*)0 =0; }

// ASSERT LVに応じたassert
// もうちょっと綺麗に書けないものか…。
#if defined(ASSERT_LV3) || defined(ASSERT_LV4) || defined(ASSERT_LV5)
#define ASSERT_LV1(X) ASSERT(X)
#define ASSERT_LV2(X) ASSERT(X)
#define ASSERT_LV3(X) ASSERT(X)
#elif defined(ASSERT_LV2)
#define ASSERT_LV1(X) ASSERT(X)
#define ASSERT_LV2(X) ASSERT(X)
#define ASSERT_LV3(X) ;
#elif defined(ASSERT_LV1)
#define ASSERT_LV1(X) ASSERT(X)
#define ASSERT_LV2(X) ;
#define ASSERT_LV3(X) ;
#elif defined(ASSERT_LV0)
#define ASSERT_LV1(X) ;
#define ASSERT_LV2(X) ;
#define ASSERT_LV3(X) ;
#endif

// --- assertion tools

// DEBUGビルドでないとassertが無効化されてしまうので無効化されないASSERT

// 故意にメモリアクセス違反を起こすコード。

#define ASSERT(X) { if (!(X)) *(int*)0 =0; }

// ASSERT LVに応じたassert

// もうちょっと綺麗に書けないものか…。

#if defined(ASSERT_LV3) || defined(ASSERT_LV4) || defined(ASSERT_LV5)

#define ASSERT_LV1(X) ASSERT(X)

#define ASSERT_LV2(X) ASSERT(X)

#define ASSERT_LV3(X) ASSERT(X)

#elif defined(ASSERT_LV2)

#define ASSERT_LV1(X) ASSERT(X)

#define ASSERT_LV2(X) ASSERT(X)

#define ASSERT_LV3(X) ;

#elif defined(ASSERT_LV1)

#define ASSERT_LV1(X) ASSERT(X)

#define ASSERT_LV2(X) ;

#define ASSERT_LV3(X) ;

#elif defined(ASSERT_LV0)

#define ASSERT_LV1(X) ;

#define ASSERT_LV2(X) ;

#define ASSERT_LV3(X) ;

#endif

もう少し綺麗に書けないものかと思うが…。
「それXXXで、できるよ」などコメントください。

ランダムプレイヤーの何が嬉しいのか？

私がランダムプレイヤーを初めて将棋で見たのはGPS将棋のプレゼン資料(?)であった。GPS将棋が『Modern C++ Design』にしか載ってないようなtemplateテクニックを駆使して書かれていて、「とても読めない」というネットの声を受けて、「ランダムプレイヤーはこう書く」みたいなソースコードを提示されたのだったと思う。(詳しい経緯は知らない。あくまで推測。)

ランダムプレイヤーが何のために必要なのか、私にはそのときはよくわからなかった。単に指し手生成のプログラムのサンプルコードとぐらいにしか思っていなかった。その認識は全然違った。ランダムプレイヤーは、高速に単体テストを行なうための必要なツールだったのだ。

何故単体テストのためにランダムプレイヤーが必要なのか？

普通、将棋プログラムでは将棋所などで自己対戦をたくさんやってそのなかで指し手がおかしければその局面を保存しておき、原因を調べる。

この方法にはいくつか問題がある。

・実際に思考させているのでテストに極めて時間がかかる。
・おかしい局面を見つけてもデバッガでアタッチできるとは限らない。
・assertに引っかかるようにするにはデバッグビルドでなければならないがデバッグビルドだと満足いく速度にならない。
・指し手生成のテストをしたい場合にも探索部を書かないとテストが開始できない。

枚挙にいとまがない。このような理由から、単体テストでおかしな指し手を検出できればそれに越したことはない。

しかし将棋プログラムで単体テストをうまく書くのはとても難しい。レアケースでしか出現しないような指し手に対して本当にうまく指し手生成が出来るのかをテストするには、その局面図自体を用意しなければならない。人間が局面図を考えて、そういうレアケースのテストをしていくのは本当に骨が折れる。1手詰めルーチンのバグなんかについても同様である。

そういうのをどうやれば発見できるのか。

それこそがランダムプレイヤーである。

ランダムプレイヤーさえあれば、探索系のバグ以外はほとんどすべて自動で検出できるのである。(適切なassertが書いてあれば)

だからまず、将棋ソフトをこれから開発しようという人は、ランダムプレイヤーで探索部以外のバグをすべて洗い出すことが完成への近道だと思う。

ランダムプレイヤーによるcross validation

例えば、王手の指し手生成部を書くことを考えよう。

王手の指し手生成はとても難しい。詰将棋ルーチンを作っても棋力が上がるどころか下がりかねないので将棋の思考エンジンのなかでも王手の指し手生成をやっている将棋ソフトは半分もない。Aperyもいまのところやっていない。

・王手の指し手生成は書くのがまず面倒くさい。
・Bitboardを用いて綺麗に書く手法が知られていない。
・王手の指し手生成に抜けがないことを証明することが難しい。
・生成された指し手がすべて王手になっていることを証明することが難しい。
・バグをなくすのが難しい。
・etc…

あと、直接王手の他に間接王手(開き王手)があるということだ。そして、開き王手かつ直接王手になるような指し手もあって、それらの指し手は重複して生成してはならないということだ。

こういう点を考えだすと大変難しく、Bonanzaのソースコードでも王手生成部はお世辞にも美しいとは言いがたい。

Bonanzaのソースコードの分量は次のようになっている。

genchk.c : 王手生成 = 62KB
gencap.c : 捕獲する指し手 = 11KB
gennocap.c : 捕獲しない指し手 = 10KB
…
search.c : 探索部 = 34KB
searchr.c : 探索部(root) = 22KB

王手生成だけでなんと62KBもあるのだ。探索部より大きい。

Bonanzaではtemplateを使ってないので先手用のコードと後手用のコードとが書いてあって倍になっているという事情もあるが、それにしても大きすぎる。

こんなものをバグなしに作れと言われても一発でバグなしに書ききる自信が私にはない。そこで、ランダムプレイヤーの出番である。

ランダムプレイヤーで王手生成のvalidationを行なう

まあ、王手生成部はうんうん唸りながらなんとか綺麗に書けたとしよう。さきほどのコードを応用して、このvalidationを書いてみる。

いま、

王手の指し手 = CHECKS
合法手 = LEGAL

と呼ぶことにしよう。validationは次の2つである。

1) LEGALのなかで王手となるものはすべてCHECKSに含まれているか
2) CHECKSの指し手はすべて王手となるか

この2つのvalidationにより過不足なくCHECKSが生成されていることが証明(?)できるのである。

// ランダムプレイヤーに合法手を生成させて、そのなかの王手になる指し手が
// 王手生成ルーチンで生成した指し手と合致するかを判定して、王手生成ルーチンの正しさを証明する。
void test_genchecks(Position& pos, uint64_t loop_max)
{
  pos.init();
  const int MAX_PLY = 256; // 256手までテスト

  StateInfo state[MAX_PLY]; // StateInfoを最大手数分だけ
  Move moves[MAX_PLY]; // 局面の巻き戻し用に指し手を記憶
  int ply; // 初期局面からの手数

  for (int i = 0; i < loop_max; ++i)
  {
    for (ply = 0; ply < MAX_PLY; ++ply)
    {
      MoveList<LEGAL_ALL> mg(pos); // 全合法手の生成

                               // 合法な指し手がなかった == 詰み
      if (mg.size() == 0)
        break;

      // 局面がおかしくなっていないかをテストする
      ASSERT_LV3(is_ok(pos));

      pos.check_info_update();
      MoveList<CHECKS_ALL> mc(pos);

      // ここで生成された指し手と王手生成ルーチンで生成した指し手とが王手する指し手について一致するかをテストする。
      for (auto m : mg)
      {
        if (pos.gives_check(m))
        {
          for (auto m2 : mc)
            if (m2.move == m)
              goto Exit;

          cout << endl << pos << "not found : move = " << m.move << endl;
          MoveList<CHECKS_ALL> mc2(pos); // ここにブレークポイントを仕掛けてデバッグする。
          ASSERT_LV1(false);
        }
      Exit:;
      }

      // 逆もチェックする。
      for (auto m : mc)
      {
        if (!pos.gives_check(m))
        {
          cout << endl << pos << "not checks : move = " << m.move << endl;
          MoveList<CHECKS_NON_PRO_PLUS> mc2(pos); // ここにブレークポイントを仕掛けてデバッグする。
          ASSERT_LV1(false);
        }
      }

      // 生成された指し手のなかからランダムに選び、その指し手で局面を進める。
      Move m = mg.begin()[rand() % mg.size()].move;

      pos.do_move(m, state[ply]);
      moves[ply] = m;
    }
    // 局面を巻き戻してみる(undo_moveの動作テストを兼ねて)
    while (ply > 0)
      pos.undo_move(moves[--ply]);

    // 100回に1回ごとに'.'を出力(進んでいることがわかるように)
    if ((i % 1000) == 0)
      cout << ".";
  }
}

void user_test(Position& pos, istringstream& is)
{
  uint64_t loop_max = 100000000; // 1000万回
  is >> loop_max;
  cout << "Generate Checks test , loop_max = " << loop_max << endl;
  test_genchecks(pos, loop_max);
  cout << "finished." << endl;
}

// ランダムプレイヤーに合法手を生成させて、そのなかの王手になる指し手が

// 王手生成ルーチンで生成した指し手と合致するかを判定して、王手生成ルーチンの正しさを証明する。

void test_genchecks(Position& pos, uint64_t loop_max)

{

pos.init();

const int MAX_PLY = 256; // 256手までテスト

StateInfo state[MAX_PLY]; // StateInfoを最大手数分だけ

Move moves[MAX_PLY]; // 局面の巻き戻し用に指し手を記憶

int ply; // 初期局面からの手数

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

{

for (ply = 0; ply < MAX_PLY; ++ply)

{

MoveList mg(pos); // 全合法手の生成

// 合法な指し手がなかった == 詰み

if (mg.size() == 0)

break;

// 局面がおかしくなっていないかをテストする

ASSERT_LV3(is_ok(pos));

pos.check_info_update();

MoveList mc(pos);

// ここで生成された指し手と王手生成ルーチンで生成した指し手とが王手する指し手について一致するかをテストする。

for (auto m : mg)

{

if (pos.gives_check(m))

{

for (auto m2 : mc)

if (m2.move == m)

goto Exit;

cout << endl << pos << "not found : move = " << m.move << endl;

MoveList mc2(pos); // ここにブレークポイントを仕掛けてデバッグする。

ASSERT_LV1(false);

}

Exit:;

}

// 逆もチェックする。

for (auto m : mc)

{

if (!pos.gives_check(m))

{

cout << endl << pos << "not checks : move = " << m.move << endl;

MoveList mc2(pos); // ここにブレークポイントを仕掛けてデバッグする。

ASSERT_LV1(false);

}

// 生成された指し手のなかからランダムに選び、その指し手で局面を進める。

Move m = mg.begin()[rand() % mg.size()].move;

pos.do_move(m, state[ply]);

moves[ply] = m;

}

// 局面を巻き戻してみる(undo_moveの動作テストを兼ねて)

while (ply > 0)

pos.undo_move(moves[--ply]);

// 100回に1回ごとに'.'を出力(進んでいることがわかるように)

if ((i % 1000) == 0)

cout << ".";

}

void user_test(Position& pos, istringstream& is)

{

uint64_t loop_max = 100000000; // 1000万回

is >> loop_max;

cout << "Generate Checks test , loop_max = " << loop_max << endl;

test_genchecks(pos, loop_max);

cout << "finished." << endl;

}

さっきのプログラムと似ているが、いくつか解説を要すると思う。

「ここにブレークポイントを仕掛けてデバッグする。」とは？

ソースコード上に
「ここにブレークポイントを仕掛けてデバッグする。」というのが書いてある。

指し手生成　→　正しいかテスト　→　ASSERTに引っかかる

のようにしてASSERTに引っかかった場合、本当はバックトレースしてその直前の指し手生成でどのような流れでその指し手が生成されたのかとか、そのときの変数の値とかを確認したい。

ところが、普通のデバッガーにはそんな機能はないので、ASSERTに引っかかるはずのところで、その直前に再度指し手生成を呼び出すようにして、そこにブレークポイントを仕掛けておくのである。

こうするとおかしな指し手を生成したときと同じ条件で指し手を生成させて、デバッガーで追いかけることが出来る。生活の知恵(?)である。

CHECKS_ALLとは？

さきほどのソースコード上には、CHECKS_ALLというのが書いてある。これは王手になる指し手を、歩の不成も含めて生成するということだ。LEGAL_ALLは、歩の不成も含まれるので、CHECKSの生成のときに歩の不成も含めて生成しないとvalidationを通らない。

ちなみに、やねうら王miniには、指し手生成部で、LEGAL_ALLで歩の不成を生成しないバージョン(LEGAL)もあるし、CHECKS_ALLで歩の不成を生成しないバージョン(CHECKS)もある。

gives_check()とは？

次に、gives_check() これは、指し手mによって王手になるかどうかを判定する関数である。

王手になるかを判定するためには開き王手になるかどうかなども判定しなくてはならないが、開き王手になる駒の情報をgives_check()を呼び出すごとに調べていたのでは大変計算コストがかかる。

そもそも探索部において、その指し手で王手になるかどうかは重要な関心事なのだ。王手になるならその指し手で進めた局面をもっと深くまで調べないといけない。(王手した結果、詰んでしまうと評価関数を呼び出して得た評価値自体がまったく意味のないものになってしまうから)

ということは、少なくともその指し手で王手になるかどうかは探索部ではひとつひとつの指し手について知っている必要があるのだ。

よって、探索部では普通、指し手生成をしたあと、何度もgives_checkが呼び出されるわけであるが、都度、開き王手になる駒の情報などを求めていては大変な無駄である。開き王手の候補となる駒のBitboardなどは一度計算してどこかに保存しておきたい。

それがCheckInfoなのである。

StockfishやAperyでは

CheckInfo ci(pos);

とコンストラクタでPositionクラスの参照を渡して初期化して、gives_check(m,ci);だとかそういう感じで使う。

やねうら王では、これが面倒くさいと感じたのでCheckInfoはStateInfoのなかに格納することにした。その代わり、gives_check()を呼び出す前に、

pos.check_info_update();

一度だけ呼び出して、Stockfish/AperyのCheckInfo ci(pos);に相当することをやっておかないといけないのである。ちょっとダサい作りではあるが、check_info_update()を忘れてgives_check()を呼び出した場合、assertに引っかかるようになっているのでまあいいだろう。

本当はdo_move()が終わった瞬間に勝手に
pos.check_info_update();
に相当する処理が走ってくれればいいのだが、実際の探索ではdo_move()のあと指し手の生成をせずにundo_move()することもあるので、そのときにせっかく計算したものが無駄になってしまう。

実際に必要になるまで少しでも計算を遅延させたいので、このような明示的な初期化が必要となるのだ。

王手の指し手生成について

そんなわけで王手の指し手生成部が書けた。これについては別の記事で詳しく書く。

やっと王手の指し手のみの生成ルーチンが書けた。Bitboardを使った王手生成って綺麗に書くの結構たいへんだ。Bonanzaの1/5ぐらいのソース量でBonanzaの3倍ぐらい速いのが出来たのでランダムプレイヤーを使って500億局面についてcross validationをした。

— やねうら王 (@yaneuraou) December 17, 2015

ここまでのまとめ

探索部以外はランダムプレイヤーで単体テストすべし！

つづく