ひよこ将棋関連の実行ファイルは → ここ
2011-11-23
50KBでBonanzaレベルの将棋プログラムが書けるか
| 
突然何を言い出すかと思われるでしょうが、教育的なコンピューター将棋のソースコードとしてBonanza相当(せめてBonanzaのRから200以内)の強さのプログラムが50KB程度で書けないのかというのを私は以前から考えております。
・fv.binは使って構いません。
・C++ templateの使用は不可とします。
・解読困難になるショートコーディングのテクニックは使用不可とします。
・USI対応
・教育用目的なのでコメントはたくさんあったほうがわかりやすいはずなので、コメント行はコードサイズのカウントに入れないこととします。
50KBというと..1000行〜1500行ぐらいでしょうか。ちょっと厳しいでしょうか。
100KBなら書けそうですが。R200以内(Bonanza R2600 - R200 = R2400程度?)に収まるかはよくわかりません。
・置換表も最小限の処理だけ
・指し手のオーダリング、何か簡単に書けて効果があるものを考える
コードサイズの問題もありますが、R2400は少し辛いかも知れません。R2100ぐらいなら楽勝でしょうけども。
ああ、あと並列化はやはり山場なので教育目的であってもこの部分を端折るのはあまり教育的ではない気がします。並列化部分をわかりやすく平易に書いて見せてあげるのも大切なことだと思います。いやしかし並列化をするコードまで書きだすと50KBでは少し収まりそうにないです。100KBであれば楽勝だと思うのですが。
「れさぴょん」ならぬ「れさぽん」(いかにもパチもんっぽいのですが)とか言う名前で作ってみようかと少し思ったりもしています。
いや、私のほうはまずはひよこ将棋の開発にある程度区切りをつけてからですが。
Kakinoki-Zがfloodgateに復帰
| 
長らくオンラインになっていなかったKakinoki-Z(柿木将棋?)がfloodgateでオンラインになっています。私が昨日、「残念ながら現在オンラインなのはSunfishぐらいですが…。」と書いたので、わざわざ参戦してくださったのかも知れません。
早速、週刊ひよこ将棋創刊号と当たりました。
http://wdoor.c.u-tokyo.ac.jp/shogi/view/2011/11/23/wdoor+floodgate-900-0+Kakinoki-Z+shuukan-hiyoko-130_PhenomII_6c6t+20111123213004.csa
後手のひよこ将棋の振り飛車に対して、Kakinoki-Zが先手で雁木で受ける形です。普通なら後手有利でしょうけど、先手に飛車先の歩を切られているのが気になります。
週刊ひよこ将棋側が「こんなもん一捻りしてやる!!」と思ったのか、61金型のまま65歩と仕掛けて桂をただ取りされるような変化に飛び込んでゲームセット。
ひよこ将棋側の大局観の悪さ(61金型が離れ駒なのにKKP評価ではマイナスされていない)が露呈した一局でした。KKPだけでは駒組が出来ないんですね。
そういう意味では金・銀だけでもKPP評価が欲しいなぁと思いました。
あとは飛車先の歩を切られているマイナスも評価できていないのも気になります。
たぶん、飛車先の歩×飛車×玉の位置というKPPによって飛車先の歩にはマイナスのペナルティが加わらないといけないのに、KPP評価をしていないのでこの部分がマイナスされていないから、歩を切ってても切ってなくても評価値に変化がないのでしょうね。
KKPのみって結構無理があります。まあ、それでもKKPでどこまで伸びるかはもう少し挑戦してみたいと思っています。
柿木さん、ありがとうございました。
週刊ひよこ将棋創刊号がR2250に到達
| 
週刊ひよこ将棋創刊号がfloodgateでR2250に到達しました。
上位のソフトにもそこそこ勝っているようです。もう2日ほど放置しておこうと思っています。最終的にはR2200台で落ち着くのではないかと思います。
これ、KKPは差分評価していないので差分評価するように修正すれば3割ぐらいnpsが上がりますし、あとfutility pruningや静止探索時に次の指し手によってどれくらい評価値が変動するかを見積る関数があるのですが、私をその部分を適当にしか書いていないのでその部分もKKP用に修正するともう少し強くなります。
それから、Bonanza6から無理やり抜き出してきているのでKKPのパラメーターの値があまりいい値がついていないので、この部分を自力で棋譜から学習させればさらにR50ぐらいあがると思います。
トータルで言うと(いまfloodgateに参戦させているCore i7 860でも)最終的にはR2400ぐらいに出来る可能性を秘めています。その場合ですとマシンをもっと高性能のものにすればR2500ぐらいになると思います。
R2500と言えば、コンピューター将棋選手権では12位ぐらいの成績が残せそうです。あわよくば、決勝にも進めるかも知れません。
コンピューター将棋選手権には2駒評価(KP≒KKP)のみの将棋ソフトで参加されている参加者の方も多数おられると思いますが、「KKPでもこのくらいまで行ける」というのを示すことは他の開発者の目安になるのではないかと思っています。
そんなわけでもうしばらくKKP型の評価関数で頑張ってみようかと思っています。
mctsの解説について
| 
floodgateのmctsの作者さんが解説記事をアップされました。
なんだか催促したようで申し訳ありません。
モンテカルロ木探索将棋プログラムmcts の解説など(フダンの記録)
http://d.hatena.ne.jp/tawake/20111123/1322022038
モンテカルロ木探索の将棋プログラムをどういう評価軸で評価すればいいのかというのは、まだ統一的な見解が存在しないのだと思いますが、実際に作ってみて「他ソフトとの勝率がいくらになったよー」or「floodgateでRがXXXXだったよー」というような評価のしかた以外としまして、
・秒間のplayout回数(po/s)とそのときの強さ
がわかるといいなぁという。
強さは別の尺度で言うなら、GPS将棋/Bonanzaの何ノード分の探索に相当するのか。
すなわち、「何回のplayoutが、GPS将棋/Bonanzaの1回分の静止探索に相当するのか」という尺度で表現できるのではないかと私は考えています。
つまり「po / GPS quies」みたいな単位でもって、そのplayoutにどれくらいの価値があるのかをアバウトには評価できるのではないかと思っています。(この値が小さいほど有意義なplayout)
あとは第三者が追試できるようにGPS将棋とのソース差分などが公開されているといいなぁという…。
週刊ひよこ将棋がBonanzaに一勝!?
| 
週刊ひよこ将棋創刊号 vs Bonanzaの一戦
http://wdoor.c.u-tokyo.ac.jp/shogi/view/2011/11/23/wdoor+floodgate-900-0+shuukan-hiyoko-130_PhenomII_6c6t+Bonanza+20111123080000.csa
下図の局面でBonanzaが36歩に48金。いきなりやばいです。これは受けきれるのでしょうか…。
以下、37歩成に同金、同飛成。もはや先手陣は風前の灯です。
しかし週刊ひよこ将棋がギリギリ受けきって、いや受けきってないですが、何かの拍子にそのまま入玉してしまいます。
何とも不思議な将棋です。KKP評価だけでも結構頑張るんだなぁと思いました。
しかし週刊ひよこ将棋ですが、Bona6から抜き出してきたKKPの値はやはりどうもおかしく(穴熊のときに金銀が逆形になるのがその典型)、自力で棋譜から学習させればもう少し強くなるのかどうかを確かめてみたい気は少ししています。
また金と銀に関してだけKPP評価をするというのは、アリだと思います。
例えば、3年前の記事ですが、白砂さんが次のように書かれています。
２二銀と３二金なら＋２５、３二金と３三銀なら＋５５、といった具合に、いい形に対してプラス評価を与える。逆に、２二金と３一銀は−２５、２二銀と３三金は−５５、と、マイナス評価にする。
この結果、第7図の局面で△２二同金と指すことはなくなった。
第18回世界コンピュータ将棋選手権出場記(白砂青松の将棋研究室)
http://www.hakusa.net/shogi/computer/wcsc18_2.html
私の言葉に言い換えるなら、これは「金・銀に関してKPP評価を導入する」ということです。
しかしこれをやり出すと、銀の退路があるかどうか(銀と歩に関するKPP評価)だとか、角筋に金がいないか(金と角に関するKPP評価)だとかもやりたくなってきます。
それらの問題をまとめて解決しようとしたのがBonanzaの3駒評価(KPP)だということになりそうですが。
今日のfloodgate
| 
まったりゆうちゃんが参戦してきました。まったりゆうちゃんは、東京農工大の小谷研究室で開発されている将棋ソフトで、コンピューター将棋選手権には2004年から参加している常連中の常連です。
週刊ひよこ将棋と当たったときは「おー、あのまったりゆうちゃんか!!」と少し嬉しくなりました。
週刊ひよこ将棋 創刊号 vs まったりゆうちゃん
http://wdoor.c.u-tokyo.ac.jp/shogi/view/2011/11/22/wdoor+floodgate-900-0+shuukan-hiyoko-130_PhenomII_6c6t+mattari_yuchan_SHUQI+20111122180005.csa
まったりゆうちゃんの棋力はR1700前後かとお見受けしたました。(まだテスト中で本来の棋力ではないのかも知れません) まったりゆうちゃんは、確か昨年にはdfpnも搭載したという話だったと思うので本当はもう少し強いのかも知れません。
あとは、
・Nanoha_test*1
・misaki0*2
・Kakinoki-z(柿木将棋でしょうか？)
・Sunfish*3
など、聞いたことのある名前のソフトがたくさんR2050付近に分布しております。残念ながら現在オンラインなのはSunfishぐらいですが…。
普通に開発していれば、棋譜からの学習をしない限り、このあたりがピークだと思うので、激戦区になっているのでしょう。
これらのソフトに駒得のみの評価関数＋αで立ち向かうのがひよこ将棋で、周囲からの失笑と、開発者からの反感を買いながら(?)も、これからも邁進していく所存です。
私としましては駒得のみにこだわるのは「駒得のみで勝って、屈辱を味あわせてやろう」だとかそういう意図は毛頭なく、なるべくシンプルな条件でどこまで出来るのかその限界を見極め、そしてそれを改良するごとにどれぐらいずつ強くなるのかを確かめようという研究者としての好奇心だけによるものです。
私には悪気とか悪意とかそういうのは一切ありませんが(ないつもりですが)、もしお気を悪くされている開発者の方がおられましたら、この場をお借りしてお詫び申し上げます。
ところで、初代Bonanzaは棋譜からの学習 + Bitboardを用いていて指し手生成などがそこそこ速いので他のソフトよりは頭ひとつ分ぐらい抜き出ていて2006年にコンピューター将棋選手権で優勝したのは記憶に新しいです。おそらくいまのfloodgateに初代Bonanzaを当時のマシンでスペックのもので参加すればR2300と言ったところでしょうか。
そういう意味ではひよこはまだ5年前のBonanzaにも追いついていません。5年前のBonanzaでも結構前を行ってたんだなぁと改めて認識しました。
私のほうはそろそろ棋譜からの学習が出来る環境を整えて、評価関数の学習に着手していきたいところです。来月は私は予定がたくさん入っているのでその合間に評価関数の学習が出来ると都合が良いのですが…。
とりあえず、なのははひよこの反対というか、fv.binを使っているのに弱いというコンセプトになってます(;_;)。
floodgate投入は意味なく寿を何とかしてからの予定ですｗ
df-pnのルーチンをどう改良すればいいのか、かず＠なのはさんのブログは大変参考になります。よろしくお願いします(^^)
うーん、探索とかやはり書き直さないとダメなんだな。＜うさぴょん２
実は、うさぴょん２（探索部はほぼうさぴょん、評価関数は自力で学習したモノ）はKKP＋αで「うさぴょん」に有意に負け越したという過去があり、迷いがありました。（でも、やはり駒組みも色々気に入らなかった。９９と穴熊に潜るとやはり８８金型が大好きだったし。その辺、うさぴょんの手組みの+αの部分に負けてた…というのが現在の認識。）
やはり過去を全部吹っ切って、指し手の生成から構造体から盤の構造から何からいっさいがっさい、全部書き換え、高速化、から、ですね。
＜…実は私は「高速化」が一番嫌いです。
結局、０から再出発、か。
そのためにも、「れさぴょん２」かな。
がんばります。
…来年の選手権にはどう考えても間に合わないんですが。
「れさぴょん２」で、『教育的なコード』と『強さ』がそこそこ両立できたら、ドキュメンテーションもちゃんとした上で、工学社さんに持ち込みとかも考えてみます。（きっと『コンピュータ将棋のアルゴリズム ２ −201x年の最強プログラムを求めて』みたいなタイトルで。一度、どうしてもコンピュータ囲碁本が書き上げられなくて（ちょうどMCTSの波が来ていたところで、その辺で私が最新研究に追いつけていなかった＆従来型のプログラムをうまく書き上げられなかったというのが理由として大きかったのですが…他に囲碁の図版どうしよう、とか細かい問題もありました。）、工学社さんのご期待を裏切ってしまったので、どうなるか分かりませんが。）
まぁ、本の形にまとまらなくても、wikiできっちり書いていけばいいのかな、とかも思いつつ。
でも、ある程度、本にまとまってるのっいうことも結構重要なのかな、とかも思ってます。最初の入門書、という意味で、敷居の低い本を書かないといけないのは超プレッシャーだし、ぶっちゃけていうと実はどう考えても「Ｊａｖａ将棋のアルゴリズム」は私にとっては「赤字」（＜執筆にかかった時間その他のコストと印税が見合わないので。）でしたし。いや、まぁ、コンピュータ将棋のアルゴリズムもある意味十分赤字なんですが、あれは今でも「読みました」って言ってくれる人が選手権に行くといることがあるので、何か心に「救い」があります。
「Java将棋のアルゴリズム」は…商業的にも成功しなかった、けれども、カリカリにチューニングしても「何かうまく早くならない_no」とかで諦めてた部分はあります。（静止探索もアレなのもその辺の事情…。）
今から書くなら、
・並列化は必須
・棋譜からの学習（この実験結果から考えると、KKP程度でも良い気がします）も必須
・出きれば＋αとして、『PP』も一部入れたい。
・ビットボードにするのかは悩む ＜可読性が、なぁ…。
・issei_yさん方式のBitboardはあまりにもテクニカル過ぎて、これは不採用にしたい
・手とかハッシュの構造体もどこまで小さくするのか（Bonanzaは結構限界までチューンされている感じでやはり読みにくい）もバランスが難しい
・一方で、探索手法についてはちゃんとしたものを解説したい
・df-pnもある程度はきっちりしたものを書きたい（でも、「寿」や「赤兎馬」、「ミクロコスモス」を解くとかは正直スコープ外。）
そんな感じ、ですかね。
あぁ、悩みや課題は多い…うーん…。
どう考えても仕事しながら1年とかで終わる量じゃないなぁ…。
いや、でも、ボンクラーズのＡ級さんはそれをやり遂げたんだよな。
ましてや、過去にはＦＰＧＡへの挑戦とかもしていたし。
この辺、開発者（れさぴょん２の場合、私）に熱意があれば出きるのか、それも含め、精神力の問題なのか、時間が足りないのか…よく分からないです（苦笑）。
50KBに収めるため並列化なし。教育目的なのでショートコーディングのテクニックなし。USI対応。評価関数自体はfv.binを使用、可読性が落ちるのでC++ templateなし、Bitboardも無し。
それでも少なくともR2300ぐらいにはなって欲しいなと思うのです。