どうぶつしょうぎ読み切り?

当ブログでもお知らせしたコンピュータ将棋協会5月例会にて話題になり、コメント欄でも多くの結果が公表されたどうぶつしょうぎ。現在の結論は、後手(そらチーム?)の勝ちらしい、とのことです。

当ブログの5月例会の記事のコメント欄の内容をおさらいすると、当協会5月例会の時点ですでにGPS将棋田中さんうさぴょんの池さんによって解析が進められており、千日手らしい、との結論が出されていました。その後バグが発見されたことで千日手の結論が撤回され、後手勝ちに変わりました。田中先生はコンピュータの後退解析(retrograde analysis)により78手で後手勝ちの結論。 鈴木将棋の鈴木さんもコンピュータのdf-pn(depth-first proof-number search)による探索で後手勝ちと結論づけました。

後退解析とは、ゲームが終わった局面、すなわちライオンが詰んだ、もしくは相手の一段目に入った状態の局面を作り、その1手前、2手前…の局面を調べていく方法です。この場合、1手前の局面は手番を持っている側の勝ち、2手前の局面はその元になった局面になる手を指してしまうと負けることがわかっているので結論は他の手次第…と順次解析を広げてゆき、初期局面に到達するまで繰り返します。これは主にチェスの解析で多く用いられてきた方法で、チェッカーを完全解析したプロジェクトにもこの方法が組み合わされていました。また、詰将棋を作る方法としても、詰みの局面から手数を伸ばしていく方法(いわゆる逆算法)はおなじみですね。

df-pnは、証明数(proof-number)と反証数(disproof-number)を使って読むべき局面を特定して効率よく探索を進める方法です。この方法では、コンピュータは相手の選択肢ができるだけ少なくなるように指し手を選んでいきます。いわゆる「ほぼ一本道」の指し方で最後の局面まで到達すれば高速ですし、また一本道で読んだ先に複雑な局面が待っていて他の手を読むことになったとしても、一本道に費やす時間がそれほど長くないため、効率よく時間を使えます。

持駒ルールゆえに終局面が無数にある将棋では、後退解析が使われることは通常ありません。どうぶつしょうぎも持駒ルールなのですが、こちらはそれでも局面数が充分少ないので後退解析が使えるようです。一方のdf-pnは、詰将棋や詰碁を解く場合に驚異的な威力を発揮しますが、中盤以前の局面ではほとんど使われません(KFEndが用いているABC探索は非常に近い方法ですが)。どうぶつしょうぎでは、通常の詰将棋並に指し手の数が少ないので有効になっているようです。

近いうちに、発表されたお2人からより詳しい分析結果が公表されると思われます。現時点では、多くの人々の目に触れるための正規の研究発表には至っていないので、5月例会の記事のコメント欄にもあるようにピアレビュー中と考えるのが妥当でしょう。すなわち、よく知られた数学の難問であるフェルマーの最終定理や3次元ポワンカレ予想の証明が公表された当初のように、他の研究者によって証明に誤りがないかどうかをチェックされる段階にあたります。

今回の研究の結果を一言で表現すると、「意外に難しい(難しかった)」ということになるのではないでしょうか。田中先生によれば、どうぶつしょうぎの総局面数は約2億局面だそうですが、今のコンピュータ将棋は1秒間に100万局面くらいは読むので、3分程度で網羅できそうにも思えますが、そんな生易しいものではないようです。どうぶつしょうぎは、アルゴリズムのベンチマーク素材としても好適かもしれません。ピアレビューその他の今後の評価で特に期待されるのは、後退解析やdf-pnの他に有力な解析方法が出てきて切磋琢磨が行われることです。特に、プログラミングには自信があるが9×9の将棋は大変そうだ、ということで様子見している方、どうぶつしょうぎなら如何?

最後に、せっかく新しく生まれたゲームにこんなに早く結論を出してしまっていいの? という問いに、当ブログの見解をお答えしておきます。チェッカーのときと同様、これはどうぶつしょうぎを指す人の楽しみを奪うことはないと考えます。どうぶつしょうぎの解析結果は、さながら無限に続く円周率の数字のように膨大なものになるでしょう。その手順を覚えるよりも、自らの考えでどうぶつしょうぎを指す人の方がずっと多いのではないでしょうか。

このエントリーをはてなブックマークに追加
はてなブックマーク - どうぶつしょうぎ読み切り?
Share on Facebook
Post to Google Buzz
Bookmark this on Yahoo Bookmark
Bookmark this on Livedoor Clip
Share on FriendFeed

コメント:2個

  1. 山田 剛より、 2009/6/18(木):

    この記事には、トラックバックのほか、以下の反響をいただいています。
    http://b.hatena.ne.jp/entry/http://www.computer-shogi.org/blog/animal-shogi_solution/
    http://slashdot.jp/science/article.pl?sid=09/06/18/007259

    予想以上の反響で驚いています。どうぶつしょうぎの知名度はすごいですね。

    スラッシュドットへは、当ブログ主が自分でたれこむべきだったかも。

  2. 長さんより、 2009/6/23(火):

    どうぶつしょうぎに強くなりたいのなら誰もが、現代の日本将棋に余りに固執する事をやめ、大将棋の嗔猪、大局将棋の臥龍、大将棋の猫刃、平安大将棋の猛虎に使い慣れ、それらの駒の性能を普段から充分に、イメージできるようにしておく事が大切です。さすれば自ずと、この将棋のコツ、必勝法あるいは有利な手番が、これらの駒に比べて性能の相当に大きな玉将(ライオン)を2段目に進め、相手から見て玉前、自分から見て3段目を早期制圧する事である点が、簡単に理解できるはずです。

コメントをどうぞ

トラックバックのリンク

コンピュータ将棋協会blog is Digg proof thanks to caching by WP Super Cache!