やねうら王miniプロジェクトの副産物として協力詰めsolverが出来たのでバイナリとソースコードを公開します。
ダウンロード
やねうら王 協力詰めsolver ver.0.65 (2016/01/04 更新)
やねうら王 協力詰めsolver ver.0.81[並列化版] (2016/01/11 更新)
※ 並列化に対応したVer0.70公開しました。(2016/01/06) 長編が解けないバグが残っているようなので修正中です。→0.81公開。まだ何かバグがあるかも。
※ Dropboxのダウンロードエラーになるときは、(私のアカウントの)転送帯域を使いきったからで、そのときはしばらく時間をあけてからまた試してみてください。
※ ソースコードからビルドしたい人はVisual C++2015で空のプロジェクトを作成して、srcフォルダのファイル(miscフォルダも含めて)をプロジェクトに追加すればビルドできると思います。あとstack overflowにならないようにリンカーの設定のところでスタックサイズを500MBぐらい確保しておくと良いです。
使い方
将棋所かShogiGUIに詰め将棋用の思考エンジンとして登録。将棋所やShogiGUIでは先手の駒を駒箱に入れられないようですが、Kifu for Windowsで編集してツールメニュー連携(ShogiGUI)させるとか、kifファイルで局面図を書き出して読み込ませる(or 編集→局面のコピーで、クリップボード経由のコピペ)などすれば良いと思います。
・置換表は大きければ大きいほど良いです。思考エンジン設定のCM_Hashの値を[MB]単位で指定します。
・Ver.0.65のほうはスレッド数は設定しても反映されません。1スレッド探索です。(並列化してませんので)
経緯
探索をより深く理解するために、まず長編詰将棋が解けるsolverを作る、その足がかりとしてまず長編協力詰めsolverを作るという流れで「長編協力詰め」というジャンルにたどり着いた私ですが、長編協力詰めには詰みあがるまでに49,909手もかかる作品があるようです。
協力詰（ばか詰） １００１手～ (詰将棋おもちゃ箱 － 加藤徹 全作品)
http://www.ne.jp/asahi/tetsu/toybox/kato/fbaka4.htm
上のリンク先に掲載されている作品はどれも芸術的です。歩を1つ稼ぐために410手かけるだとか、こんな手順を思いつくというのはどう考えても狂気の沙汰です。
加藤徹さんというのはどこの天才かと思って調べたら、どうやら、「詰将棋おもちゃ箱」の管理人のTETSUさんでした。かねてより「何やら、(コンピューター将棋の話題も含め)地味に将棋関連の記事を毎日こまめにまとめてはるな～」と感心していたのですが、世の中にはとんでもない化物がいたものです。
TETSUさんに敬意を表して、上に掲載されている全作品を短時間で解図できる協力詰めsolverを公開したかったのですが、それは結構難しそうです。とりあえず、今回のsolver(ver.0.62)でも寿限無(19447手)は1時間ほどで解図できたので、いったん公開しておきます。
ソースコードもつけておくので興味のある方は、この世にあるすべての協力詰めが解図できるように挑戦してはいかがでしょうか。このsolverの仕組み自体は、やねうら王miniの連載のほうで解説します。
2016/1/3 4:20 追記
No.172『寿限無2』(38889手)解けました。(15時間ほどかけて..) いくつかバグがあったので修正しました。[Ver0.64]
メモ
CPU Core i7 4771にて。(1スレッド。置換表にメモリ 26GB割り当て)
- No.73(5321手) 解けました。(16時間 Ver.0.76 Core i7 5820K HT12スレッドにて)
- No.73a(5329手) 解けました。(19時間 Ver.0.64)
- No.85b(19447手)『寿限無』 解けました。(1時間 Ver.0.61 → Ver.0.70 Core i7 5820K HT12スレッドにて 100秒！)
- No.107a(9029手) → 5日かけて1000手ぐらいまでしか読めませんでした..
- No.107b(4197手) → 5日かけて2200手ぐらいまでしか読めませんでした..
- No.161a(4143手) 解けました。(3時間半 Ver0.65)
- No.162a(7181手) → 10日かけて5500手ほど読んだところで雷による停電で停止..
No.172(38889手)『寿限無2』 解けました。(15時間 Ver.0.61) - No.211(10853手) 解けました。(3時間 Ver.0.73)
- No.211a(12693手) 解けました。早詰め発見しました。12687手。(12時間 Ver.0.64 → 5時間半 Ver.0.65)
- 『寿限無3』(49909手) 解けました。(8時間 Ver.0.64)
更新履歴
2016/01/09 version 0.77リリース。長編が解けなくなっていたバグを修正しました。MAX_PLYまで行って不詰めのときにそれを表示するようにしました。
2016/01/07 version 0.73リリース。長編で解けなくなっていた作品があったのを修正しました。まだ何か並列化に伴うバグがあるかも。
2016/01/06 version 0.70リリース。並列化対応。『寿限無』が100秒で解けました。HT12スレッドで3～10倍ぐらい解図が速い模様。
2016/01/04 version 0.65リリース。循環局面の枝刈り追加。反復深化2手ずつに変更。前のバージョンの半分ぐらいの時間で解けるようになりました。
2016/01/03 version 0.64リリース。one replyの処理、バグってたので修正。
2016/01/02 version 0.62リリース
元旦に掲載されたブログにも驚きましたが、２日目からフルスロットルで働くやねさんにも驚きであります。
・・・どうぞこのままの勢いがこの一年間、継続できますように、、、。
あと1週間ほどで電池切れになります。(たぶん)
ありがたや～。しかし、VSプロジェクトが入ってないですね。
おいおい、妙技を堪能したいと思います。
ところで、これで将棋ソフトとしては何割位できてるとお考えでしょうか？？
将棋ソフトとしては..探索部を200行ほど書けばBonanza6(の強さ)にはなるのでは…。
なるほど。
ほとんど完成してて肝が抜けてる感じなんですね。
想像していたより小さいですね。
もっと、ブラックマジック満載でコードも10万行くらいあって、妙技満載で。とか妄想してましたが。
この規模でかけるもんなんだなーと、感心しきりです。
ファイル名がcooperate_mateになっていますが、チェスプロブレムでは協力詰はhelp mateと言います。
https://en.wikipedia.org/wiki/Helpmate
ファイル名を直すべきとか直して欲しいとかではなく、英語ではそう呼ばれている事をお知らせしたかっただけです。
あと置換表に、初期局面からその局面に到達する最短手数を覚えさせておくのは、有効かと思います。
100手で到達可能な局面に102手で到達する手順は意味がありません。
協力詰ではいかに手数を縮めるかが肝になっている作品が多いですし、循環局面のチェックも兼ねることが出来ます。
この手法は自分で検証しようと思ってましたが、もたもたしているうちにv0.65にバージョンアップしていました。
やねさんが実装したほうが、更新速度も処理速度も上なので、提案しておきます。
おお、help mateって言うんですね！ありがとうございます。まあ、いまさらなのでソースコードはこのままにしときます。
> あと置換表に、初期局面からその局面に到達する最短手数を覚えさせておくのは、有効かと思います。
試してみましたが、20%ほど遅くなりました。
循環局面はVer.0.65の方法で判定したほうが速い＆「100手到達できる局面に102手で到達」した場合、(反復深化の同じiterationにおいては)残り探索深さが100手で到達したときより2以上少ないはずで、これは前回の反復深化のiterationにおいて詰まないことは置換表に書き込まれていますからprobe()した直後に枝刈りされています。ゆえに、rootからの手数を置換表に格納するコスト等に見合わないのでしょう…。
コストはそれほどでもないと思っていましたが、見合わないのですね。
検証して下さりありがとうございました。
自分で検証していれば、やねさんにお手間を掛けさせることも無かったのに、すみません。
> 自分で検証していれば、やねさんにお手間を掛けさせることも無かったのに、すみません。
どんまいです！私も興味あったもので…。
ありがとうございます！ビルドして kato085b.ki2 を実行させてみました。
i7 860 2.8GHz
0.65 64 SSE4.2
CM_HASH:4000
探索局面数:2464088076
NPS:1447165
28分22秒
おお、ビルドしなおせば、AVX2なしでも動きましたか。
楽しみにしていました、ありがとうございます！
さっそく”matsuri” + “s”で指し手生成を実行してみたのですが、5M回/sで、驚きました。自分で適当に書いたものだと2M回/sがやっとでした。（協力詰めにはあまり興味がありません……）
また、ソースの行数は約7000行ほどあるようですがやねうら王miniでは2000行くらいになるのでしょうか？
> ソースの行数は約7000行ほどあるようですが
・空行、コメント行を除く
・/misc/ フォルダの中身は削除
・王手の指し手生成は削除
3000行弱になるかな…(たぶん)
ここから指し将棋用の探索部も増えるわけですし2000行台って結構鬼門ですよね。しかもstockfishの探索部は1000行ほどあった気が。。。
期待して待ってます！
探索部なんてものは2、300行ほど書けばBonanza6の強さにはなるでしょう…。(たぶん)
Bonanza6超え最少コード数コンテストへの出場はやねうら王nanoでお願いします。
＞No.85b(19447手)『寿限無』 解けました。(1時間 Ver.0.61 → Ver.0.70 Core i7 5820K HT12スレッドにて 100秒！)
おそろしや！
36倍速！！
ver.0.78[並列化版] (2016/01/10 更新) は、Downloadできましたが、ver.0.65 (2016/01/04 更新)では、以下のエラーがでました。
Error (404)
We can’t find the page you’re looking for. Check out our Help Center and forums for help, or head back to home.
リンクが切れているのでしょうか？
そっちはDropboxのpublicフォルダで、Dropboxの転送量が一定を超えると3日間、公開リンクが停止するペナルティを受けるのです…。先日、Yahooニュースでひまうら王が紹介されて(紹介されたこと自体はありがたいことですが)、その煽りを受けまして…。
>3日間、公開リンクが停止
速度制限のような物と思っていました。
”３日間、公開リンクが停止” とはかなり厳しいですね。
中国株のサーキットブレーカーでさえ、１日なのに。。。
ver.0.78 movegen.cpp line 72~
// 成れるなら成りも生成する駒
case SILVER:
if (enemy_field(Us) & from) {
// 敵陣からなら成れることは確定している
MAKE_MOVE_TARGET(target);
} else {
ここ、MAKE_MOVE_TAGET_PRO(target);じゃないですか？
(‘ω’) うわあああああああああ
指し手生成にまだこんなバグが残っていようとは…。敵陣からの移動成りが抜けてたんですね！ご指摘、ありがとうございます！！
ということは..perft10の結果に影響しそう。先手のほう、76歩、22角成、31馬、XX銀打(敵陣への銀打ち)、XX銀成で銀成が出てくるので…。
perft9 も怪しい？
先手、76歩、22角成、31馬、33銀打、2(4)4銀成で敵陣から引く銀成が２つ。
確かにまずそうです..(´・ω・`)
やはりバグだった様で、見つけられて良かったです。
素人で将棋ソフトを完成させるような実力は全く無いですが、ソースを読んで勉強させてもらってます。
ソースを読む気が続いてるのもバグを見つけられたのもコメントがたくさん入ってるおかげです。
ありがとうございます。ソースコード、見てくれる人がたくさんいればいるほど心強いです。
香車成らずもバグってたから parft 7 から怪しげですねぇ。
96歩 94歩 95歩 同歩 同香 ｘｘｘ 93(2,1)香（成、不成）
うおー！？そんなバグも！？修正しますた(｀･ω･´)ゞ > Ver.0.81
ひまわりの山本です。
やねうら王miniのソースコード読ませて頂いております。
意図されているのかもしれませんが、現在公開されているものはquitコマンドを受けた際にプロセスを終了しないと思います。
将棋所を終了する際に一緒に消えるので動作には問題ないのですが、気になったのでご報告いたします。
また、コメントの誤りなのですが、shogi.hの筋と段に関するprettyのコメントが間違えています。
（筋が八で段が８になっている）
とても読みやすくて勉強になりますので、今後も期待してます！
公開してくださってありがとうございます。
修正しておきました！(｀･ω･´)ゞ
quitのほうはあとで実装しようと思ってたので合わせて修正しておきました。