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

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

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

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

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

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

ASSERT_LV3ってなに?

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

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

それより、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は以下のような実装になっている。

もう少し綺麗に書けないものかと思うが…。
「それ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が生成されていることが証明(?)できるのである。

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

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

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

指し手生成 → 正しいかテスト → 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()することもあるので、そのときにせっかく計算したものが無駄になってしまう。

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

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

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

ここまでのまとめ

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

つづく


連載やねうら王miniで遊ぼう!9日目” への27件のコメント

  1. >assert()を有効にしたい。(ことがる)-->(ことがある)

    いつもの修正よろしくです。

  2. 時たま変なミニゲームを作ることがあるのですが、その時はランダムプレイヤー作りますけど、将棋ともなると手を抜いても面倒な量になりますね。
    自分だったら、この量書いたら一日つぶれてしまいます。
    乱数にMTRand使わなかったのはなんか理由あるんですか。確かに速度的には遅いですが。
    それと、C++のランダムのセットの中にはrand()と同質の乱数も一応用意はされているらしいです。
    まぁ、タイプ数それなりなんで面倒といえば面倒ですが。
    乱数の余剰取ってるのも昨今では邪悪とされ、ディストリビュータに任せるのが一般的になりつつあるらしいですが、なんか偏らせる意図とかあるんでしょうと解釈しています。

    • > 乱数にMTRand使わなかったのはなんか理由あるんですか。

      メリットがほとんど何もないのにタイプ量が多いのとかマジ勘弁ということで。

      > 乱数の余剰取ってるのも昨今では邪悪とされ、ディストリビュータに任せるのが一般的になりつつあるらしいですが

      この指し手を選択するときに一様分布にするメリットは全くないです。例えば100個の指し手があるとして、32bit整数の擬似乱数を100で剰余をとって、それを乱数にした場合、確かに一様分布にはなりませんが、どれだけ偏るかというと、(0〜4294967295 % 100)となるので 0〜95が96〜99が出る確率より49649673/49649672 ≒ 1.00000002倍多いに過ぎないです。こんなものが問題になることは現実的にありえないです。ゆえにタイプ量の少ないrandを使うのが正解。

      • そういう細部まで理解して使ってらっしゃるなら問題ないのですねぇ。
        失礼しました。
        自分はあんまりこだわらないので、一応便宜上はmtrandを使っていますが、ランダムデバイス作ってmt作って、ディストリビュータ作っての3連ちゃんを毎回書くのはちょっとめんどくさく思っています。
        まぁ、そのうちC++側にもrand()の代用を用意する気はあるらしいのでそれに期待してます。

    • 乱数の検定をやった事があるのですが、xorshift は、メルセンヌ・ツイスタ(以下 MT)に比べると 周期が短い事を除けば良質な乱数でした。 4種8通りの検定をやって問題は見つかりませんでした。MTにくらべコードははるかに短いですし、高速なのでよく使っています。

      周期の短さは、64bit化し32bit 単位で取り出せば、かなり長くなりますし、高速化にもなりますね。

      StockFishの乱数を64bitして32bitづつ取り出した物は、xorshift よりも高速でしたが、検定で2種 NGでした。3sigmaの外の出現確率にやや問題がでる様です。(そのような用途以外はOK。)

      長周期に関しては、MTよりも高速なものを自分で用意しており、これも検定は通りました。いまのPCで100年以上の周期があると考えています。(証明はしていませんが。)

  3. perft depth = 10で0.9%程度(=checks/nodes)です。
    https://twitter.com/yaneuraou/status/678041866726596610?ref_src=twsrc%5Etfw
    この比率はそれなりに安定しているようです。

    次に、500億局面を256手で割ると2億対局弱になります。
    https://twitter.com/yaneuraou/status/677325992629678080?ref_src=twsrc%5Etfw
    ランダムプレイヤーの自己対局はたいていが256手までいって引き分け終了になると想定しています。

    さてそれで2億対局弱に0.9%をかけると176万回程度の王手(check)になるかと思われます。
    そうなると「王手生成部のvalidationはだいたい176万回行った」ということになる・・・と。
    そういう理解でよろしいのでしょうか?

    • 各node(局面)で生成された指し手について調べているので、生成された局面数(平均200手だとして×対局回数)×1nodeで平均して生成される指し手の数(50ぐらい?)×王手の割合(0.9%?)みたいな数になるんですかね。

      • いまひとつ理解しきれません。
        以下もう少し説明をお願いします。

        >ランダムプレイヤーを使って500億局面についてcross validationをした。
        いただいたコメントでの理解は「調査回数は500億局面*0.9%=4.5億回程度」ということで良いのでしょうか?
        それとも「調査回数は500億局面*50*0.9%=225億回程度」ということでしょうか?

        それから、
        「ランダムプレイヤーの自己対局はたいていが256手までいって引き分け終了になると想定しています。」
        という理解は「それで良い」ということでOKでしょうか?

        • 調査回数は、10億局近く回しました。王手になる局面数としては、10億局×1局平均256手×0.9%×平均50手 ≧ 1,000億みたいな感じで、まあ500億は軽く超えてるだろうという概算です。

  4. 最適化で消えるから普通にifで、、、。

    #ifndef ASSERT_LV
    #define ASSERT_LV 0
    #endif

    #define ASSERT_LV_EX(L, X) { if (L <= ASSERT_LV) ASSERT(X); }
    #define ASSERT_LV1(X) ASSERT_LV_EX(1, X)
    #define ASSERT_LV2(X) ASSERT_LV_EX(2, X)
    #define ASSERT_LV3(X) ASSERT_LV_EX(3, X)
    #define ASSERT_LV4(X) ASSERT_LV_EX(4, X)
    #define ASSERT_LV5(X) ASSERT_LV_EX(5, X)

  5. >> 10^20オーダーで終局してしまう可能性もあるのかなと。
    >はい、そうですね。自由にnode(局面)間の状態遷移が出来るわけではないですしね。
    http://yaneuraou.yaneu.com/2015/03/08/%E5%B0%86%E6%A3%8B%E3%81%AF%E6%9C%80%E5%A4%A7%E4%BD%95%E6%89%8B%E3%81%A7%E7%B5%82%E5%B1%80%E3%81%99%E3%82%8B%E3%81%AE%E3%81%A7%E3%81%99%E3%81%8B%EF%BC%9F/

    これは「自己対戦するランダムプレイヤーは必ず止まる」という理解でよろしいのでしょうか?
    ちなみに「自己対戦するランダムプレイヤーは千日手に陥ることはない」・・・という前提です。

      • つまりは(幅優先)横型探索をしていく過程で、千日手が検出されるたびにその枝を切っていく。
        それから、当然チェクメイトになった枝はそこで終了。
        これを続けていくとどのdepthか知りませんが、すべての枝が消え去る、、、訳ですね。
        そして、そのdepthがとむけんさんの主張だと「> 10^20オーダーだ」ということでしょうか。

        ・・・こういう認識になりましたが、違っていたら訂正をお願いします。

    • 「自己対戦するランダムプレイヤーは探索木を上(ルート)から下(リーフ)に走る」と表現できそうです。
      そうしてリーフ(葉っぱ)に書かれている文字が「チェクメイト」か「千日手」のいずれかである、、、という訳です。
      さて、そこで問題になるのが、一番長い走行距離を引き当てたランダムプレイヤーの先にあるのが「チェックメイト」か「千日手」か、一体どちらなのか、、、というものです。
      これは言葉を変えますと、「神が指す一番長い手の、最後の一手は「チェックメイト」なのか「千日手」なのか」、、、ということでもあります。

      千日手、、、の場合は我々には知るよしもありません。
      でも最後の一手が「チェックメイト」であるとすると、「その手」にはある制約がつくことになります。
      つまり、「最後の局面(これはチェックメイトになります)のひとつ前の局面」ではすべてのゆるされる合法手が「チェックメイト」でなくてはいけないのです。
      もし「チェックメイト」にならない合法手が存在すれば、そこは「終端」とはならずに「枝分かれ」が発生してしまいますのでそこでは「最後の一手」とはなりえません。

      さて、そんな局面(あるいは駒の配置)が可能でありましょうか?
      残念ながら、私の思考範囲のなかにはそんな局面は存在しませんでした。
      ・・・それでどなたか、「これがあるよ」と教えていただけると助かるのであります。

      • >・・・それでどなたか、「これがあるよ」と教えていただけると助かるのであります。

        例えば以下の局面は79飛成が唯一の合法手、かつ、相手玉を詰みにする手だと思います。

        後手の持駒:なし
        9 8 7 6 5 4 3 2 1
        +—————————+
        | ・ ・v銀v金 ・v金v銀v桂v香|一
        | ・ ・ ・ ・ ・ ・ ・v角 ・|二
        |v歩 歩 飛v歩v歩v歩v歩v歩 ・|三
        | ・v香 ・ ・ 香 ・ 桂 ・ ・|四
        | ・ ・ ・ 銀 金vと とvと 香|五
        | と ・ ・ 歩v桂 金 銀 桂 ・|六
        | ・ ・ ・ ・ 歩 歩 歩 馬 歩|七
        | 歩 ・ ・ ・ ・ ・ ・ ・v歩|八
        | 玉 ・v龍 ・ ・ ・ ・ ・v玉|九
        +—————————+
        先手の持駒:なし
        後手の持駒:なし

        • 追記:
          上記局面、手番は先手です。あと、▲79飛車不成がと言われればその通りなので、飛車を竜に変えたがいいかもしれません。

          追記2:
          ランダムプレイヤーのコード42行目コメント

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

          は1000回に1回のtypoではないでしょうか。細かい点ではございますが。

        • 自殺王手ですか。
          王手でほかのすべての合法手を封じるとは、、、。
          恐ろしい手があったものです。

          それにしても49飛成さん、みごとでありました。
          そうして、ご教授、ありがとうございます。

          ▲79飛成でも▲79飛車不成でも詰みになりますので、2つの合法手が存在し、かつ2つともチェックメイトであります。
          ですので、「許される全ての合法手がチェックメイトである」という設問の条件を満たしていると思います。
          つまり、この局面が探索木の最も長い枝の先についている葉っぱであってもおかしくはない、、、ということになります。

          こうして「神の最長最後の一手」にある程度の制約が付けられるかと思ったのですが、失敗に終わった様です。

          ちなみに最後の葉っぱ、ステイルメイトでもよい、、、ということに気がついてしまいました。
          そういう訳で、千日手、チェックメイト、ステイルメイトのいずれかの文字が書かれているはずの最後の葉っぱ。
          存在は分かるのですが、永遠にその文字を知ることはできない様であります。

  6. おそらく最新のver3.57をダウンロードして色々と試させてもらっております。
    この記事の test_genchecks を試そうと
    test checks を実行したところ
    // ここで生成された指し手と王手生成ルーチンで生成した指し手とが王手する指し手について一致するかをテストする。
    の中のASSERT_LV1にひたすら引っかかるので調べたところ、
    movegen.cpp の122行目の
    mlist++->move = make_move_promote(from, to) + OurPt(Us,Pt);
    が変な気がしました。正しくは
    mlist++->move = make_move_promote(from, to) + OurProPt(Us,Pt);
    ではないでしょうか?

    あと細かいはなしですがtest_cmd.cpp の899行目の
    cout < verious function “;
    は various ではないでしょうか。

    すでにお気づきでしたらすみません。

    • うおー!王手生成ルーチン、通常探索では使ってないので気づきませんでした…。ありがとうございます。修正しておきました。次回のGitHubの更新時に反映されます。(電王トーナメントの関係で10月に入ってからの更新となります。申し訳ありません。)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です