連載やねうら王miniを強くしよう！1日目

投稿日時: 投稿者:

今回から、やねうら王miniを強くしていく連載が始まります。12回でBonanzaより強くなる。(かも)

今回は、協力詰めsolverを作ってみます。

詰将棋から始めてみよう

指し将棋のAIを作るのは楽しいですが、強くなったかどうかの計測をするのが結構難しく、自己対戦させると時間も馬鹿にならないので、まずは詰将棋AIを作るところから始めたいと思います。詰将棋であれば、正解・不正解がわかりやすく、また詰将棋の問題が解けるまでの時間から探索性能を測れるからです。

詰将棋用のAIであっても、基本的な探索技術は必要となります。また、製作の過程で指し将棋のAIの探索部を作る上で役に立つ知見も色々得られます。

詰将棋の指し手とは

詰将棋は、先手(攻め方)が王手の連続でなくてはなりません。後手(受け方)は王手回避手の連続となります。

厳密に言うとスティールメイトという、後手に指し手がなくなるパターンでの詰みもあるのですが、普通の詰将棋では後手は持ち駒を豊富に持っているので、これはまず起こりません。

つまりは、指し手の種類で言うと、

・先手はCHECKS
・後手はEVASIONS

を生成することになります。

また、先手も後手も最善を尽くすということが前提としてあります。

この最善の定義は非常に難しいですが、ここでは先手は手数が最短になるように、後手は手数が最長になるような指し手を選択するいうことにしておきます。

詰将棋を一般化すると…

普通の詰将棋では、先手と後手の指し手の種類が、CHECKSとEVASIONSに限定されていることがわかりました。これを一般化しようと考えた場合、この条件を緩和してやることが考えられます。例えば、先手は王手でなくても良いだとか。

別の一般化としては、先手・後手が最善を尽くすのではなく、先手は最善、後手は最悪(詰むのに協力)を選択するというのも考えられます。これは協力詰め(ばか詰め)と呼ばれます。

詰将棋の分類

先手が最悪(詰まそうとしない)、後手が最悪(詰むのに協力)を選択すると「最悪詰め」と呼ばれます。先手が最悪、後手が最善を選択すると「悪魔詰め」と呼ばれます。

つまり、後手玉を詰めるとしたときに、次のように分類されます。

先手 後手
最善 最善 ：詰将棋
最善 最悪 ：協力詰
最悪 最悪 ：最悪詰
最悪 最善 ：悪魔詰

協力詰めのほうが詰将棋より(コンピューターには)たぶん簡単

普通の詰将棋だと、詰みを見つけても後手が他の指し手を選んだときにも詰むことを証明しなくてはなりません。後手の取りうるあらゆる指し手に対して先手が詰ませる変化がなくてはなりません。

協力詰めのほうは違います。一つでも詰む変化を発見すればそれが解答(の一つ)です。

ということは、協力詰めのほうが詰将棋より、条件が緩いということがわかります。

探索の用語

探索開始局面から、先手が指し手aを指して、局面Bになって、そこで後手が指し手bを指して、局面Cになって…。

探索開始局面での指し手は複数あるでしょうし、そのあとの局面での指し手も複数あるのが普通です。そう考えると、その組み合わせを紙の上に書こうとしたときに樹形図のようなものが出来あがります。

これをゲーム木と呼びます。

このように、探索のことを考えるときに木に見立てるとわかりやすいので、探索ではグラフ理論の以下の用語を使います。

・node(節点) = 局面(盤面+手駒+手番)のこと。
・edge(枝)    = nodeとnodeとを結ぶ経路(指し手)のこと。
・path(道)     = あるnodeからそのnodeにいたるまでの経路(手順)のこと。
・tree(木)      = あるnodeから到達できるnodeをedgeでつないだもの。
・root(根)      = root node。探索開始局面のこと。
・leaf(葉)       = leaf node。ゲーム木の(木に見立てて)末端の局面のこと。

将棋の探索において、グラフ理論の用語は上記以外はそれほど多く出てこないので、あとは出てきたときに勉強すれば良いでしょう。

縦型探索と横型探索

「縦型探索(深さ優先探索)」と「横型探索(幅優先探索)」についてはggrks。

縦型と横型とどちらがいいかという話になるのですが、ざっくり書くと、横型探索では次に展開する接点をメモリに保持しておかないといけないので、最短経路が求められているようなタイプの問題でなければ縦型探索のほうが好ましいことが多いです。

実際、通例、将棋ソフトでは縦型探索を用います。

いままで将棋ソフトにおいて横型探索を用いていたソフトは、10年以上過去の、ごくごく一部の特殊なソフトだけです。[要出典]

そこで、現代では、縦型探索一択だと思って間違いありません。

協力詰めsolverを書いてみる

協力詰めには先手は王手の連続でなければならないという条件がつけられているのが普通ですが、ここではまずは先手の指し手は王手でなくても良いものとします。

やねうら王miniを使って、プログラムを書いてみます。探索は縦型探索です。プログラムの流れを目で追いかけて、縦型探索のプログラムを理解しましょう。(あるいは「縦型探索」とか「深さ優先探索」とかでggrks。)

再帰の流儀

上のプログラム、再帰を使って書かれていることは一目瞭然で、再帰について知らない人はggrks。

depthが残り探索深さで、日本語で書くと次のようなコードとなっています。

depth == 0というのが、leaf nodeかの判定というわけです。leaf nodeは、そこが終端のnodeですから、何らかの処理をしてreturnせねばなりません。leaf node以外では、nodeを展開せねばなりません。つまり、そのnodeから辿れるnodeを調べるために、再帰的に自分自身の関数を呼び出すことになります。

再帰的なプログラミングでは上のようなコードを書くのが普通なのですが、depth == 0を判定するときに関数呼び出しが1回あるのが気にくわないので、次のように書き換えることがあります。

leaf node以外でも詰みのチェックをして詰んでいればその手順を表示したいのであればさきほどのソースコードのようになるというわけです。

将棋所から詰将棋エンジンとして用いる

さきほどのプログラムをやねうら王miniに組み込んでコンパイルすると、将棋所から詰将棋エンジンとして登録して、詰将棋エンジン代わりに使うことが出来ます。

さっそく将棋所で盤面編集をして以下のばか詰めを解かせようとしたのですが、将棋所もShogiGUIも盤面編集で手駒を無くすことは出来ないようです。

※　Kifu for Windowsで盤面編集をして、ShogiGUIにツールメニュー連携で局面を渡して、ShogiGUIで解かせることは出来ました。https://sites.google.com/site/shogigui/manual/others/kifu-for-windows

090622_b_5

ばか詰（１） (松本博文ブログ)
http://mtmt-blog.com/?p=1783

仕方ないので、コマンドプロンプトから直接USIプロトコルで解かせてみましょう。

さきほどのソースコードのままだと、手順がUSIプロトコルで表示されてわかりにくいので、まず、

sync_cout << “info depth ” << search_depth << ” pv ” << pos.moves_from_start_pretty() << sync_endl; // 開始局面からそこまでの手順

として、日本語で指し手が表示されるようにします。

次に、sfenで直接局面を入力します。sfenについてはggrks。

同じような手順がたくさん出てきます。同じ手順ばかり見ていても面白くないので、指し手を限定させたいです。捕獲する指し手を除外してみましょう。

なるほど。このパターンも飽きました。56龍で詰め上がる指し手を除外してみましょう。

次に、攻め方(先手)の指し手は必ず王手でなければならないという条件をつけてみましょう。協力詰めは、普通この条件がついてますし、さきほどの出題図にも本当はこの条件がついています。

このように色々と制約条件をつけて探索させたいとき、ソースコードを直接いじって条件を付与できることは大変便利です。こうして見ると、詰将棋作家は検討のために簡単なプログラムは書けたほうがいいのでしょうね。

ここまでのまとめ

縦型探索を用いて協力詰めsolverを書くことが出来ました。次回はもっと難解な協力詰めを解かせてみましょう。

次回に続く

「連載やねうら王miniを強くしよう！1日目」への21件のフィードバック

  1. やねうら王mini自体はどれくらい完成しているのですか？
    記事とともにデバッグしてる状態でしょうか。
    この前書いた探索と、ゲーム木検索で256手まで検索して、カーナビ256っていうソフトを妄想したのですが、ゲーム木検索を書く気がしなくて頓挫しています。
    知性とロジックの寒い戦いが見たいような気がするので作りたいのですが、やっていいものかどうか・・・。Orz
    あぁ、これ。ただのネタですよ。ただのネタですよ。
    考えて思ったのですが、自分には知性の創造は無理そうです。
    どうしても冷たいものができてしまう。

    返信 ↓

    • なるほど。Kifu for Windows→ShogiGUIの連携でShogiGUIに局面渡せますね。本文記事に追記しました。ShogiGUIで無事、解答を表示できました。近日中に長手数の協力詰めの解ける思考エンジンを公開しますね。

      返信 ↓

  3. ＞厳密に言うとスティールメイトという、後手に指し手がなくなって指し手がなくなるパターンでの詰みもあるのですが・・・

    圧縮してみました。
    後手に指し手がなくなるパターンでの詰みもあるのですが・・・

    返信 ↓

  4. ＞こうして見ると、詰将棋作家は検討のために簡単なプログラムは書けたほうがいいのでしょうね。

    ・・・次の出版はぜひ「やねうら王miniで学ぶC++基礎講座」をお願いします。

    返信 ↓

      • わかりました。

        それではここはBasicしかしらない読者が一通り「やねうら王mini」を読めるようになる（であろうと思われる）、一番優しく書かれたC++入門本の紹介、、、ということで手を打ちましょう。

        返信 ↓

        • やねうら王miniのソースコード自体まで理解しようと思うと少しハードルが上がるような…。

          @ITのC++の記事、斜め読みするぐらいから始めてみては。

          返信 ↓

          • ページ紹介、ありがとうございます。
            「やねうら王mini」というのは、とてもよい目標になりそうです。

        • samuraiさんはBASICできるのですね。
          自分もBASIC組でして、小学校のころパソコンクラブでBASICを触ったのが最初です。
          高校に入ってポケコンで自由にBASICでミニゲームを作れるようになった後、偽専門当たりでCを初めて最近はC++を触っています。
          C/C++が読めるようになるとほんとすそ野が広がりますのでステップアップをおすすめします。
          アルゴリズムを編むのは楽しいですよ！

          ちなみにCでミニゲーム作るときにネックなのが何かというと、コンソールでのキーコード取得なのですが、VCにはっていう非標準のヘッダがありまして、それの判定に_kbhit()というのを使います。取得がgetch()です。

          とりあえず、BASICのコードを移植して覚えるというのもなかなかハードですが楽しいですよ。ウィンドウを出すのは大変ですが、文字使ったゲームは十分移植できます。

          返信 ↓

  5. あら、消えちゃった。
    ＜conio.h＞っていうヘッダにコンソールのIO関係が入っています。
    非標準なのでどのコンピュータでもとは生きませんがVCのバイナリが動く範囲では有効です。

    返信 ↓

  6. やねうら王をDLしてコンパイルして、exeのあるディレクトリで
    YaneuraOu-Debug-mate.exe test_mate_engine
    と叩いたんですが、局面は認識してくれるものの解いてくれません。

    Position: 6p1l/1+R1G2g2/5pns1/pp1pk3p/2p3P2/P7P/1L1PSP+b2/1SG1K2P1/L5G1L w N2Prbs2n3p 1
    bestmove resign

    Position: lng3+R2/2kgs4/ppp6/1B1pp4/7B1/2P2pLp1/PP1PP3P/1S1K2p2/LN5GL b RG2SP2n3p 1
    bestmove resign

    ===========================
    Total time (ms) : 53
    Nodes searched : 0
    Nodes/second : 0
    Nodes searched(main thread) : 0
    Nodes/second (main thread) : 0

    なんかコマンドの指定方法がまずいんでしょうか。
    USI拡張コマンド.txtにも載っていないもので、申し訳ありませんが教えてください。

    返信 ↓

    • 将棋所からでもそうなりますか？
      まずは、将棋所からその局面を解かせてみて、将棋所のデバッグウインドウ開いて、流れているコマンドを見れば良いような？

      返信 ↓

      • 将棋所で局面を並べたらちゃんと解けました
        1:usinewgame
        >1:position sfen 3sks3/9/4+P4/9/9/+B8/9/9/9 b S2rb4gs4n4l17p 1
        >1:go mate infinite
        <1:info string pn 0 dn 100000000 nodes_searched 133
        <1:info time 10 nodes 133 nps 13300 hashfull 0
        1:quit

        test_cmd.cppの1951行目にsfenの配列があって、1981行目のtest_mate_engine_cmdの中にforでぐるぐる回しているような記述があったので、”test_mate_engine”コマンドを使うとこれらの局面を次々読んでくれるものなのかと勝手に思ってました。

        DEBUG用だと思うので、今後の開発時に使いたいなぁ……と思っていたんですが、TestMateEngineSfen[]の問題群を解かせるのはどのようにやればいいんでしょうか（すいません質問が下手で）。

        返信 ↓

          • そうだったんですね。
            頑張ってみます。ありがとうございました。変な話で申し訳ありません。

コメントを残す

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