最強ランクの将棋ソフト「Bonanza」、ソースコードを公開 78
ストーリー by kashibat-svt
さらなる高みへ登り詰めるのか 部門より
さらなる高みへ登り詰めるのか 部門より
otk 曰く、
CNET/Venture Viewの記事より。“最強ランク”の1つに数えられるコンピュータ将棋プログラム「Bonanza（ボナンザ）」（開発者＝保木邦仁氏）のソースコードが公開されている。ここには思考ルーチンのコードも含まれており、将棋ソフト開発者の間では「ソースを再利用すべきか」「Bonanzaクローンが蔓延するのではないか」といった声があがっているという。
Bonanzaは2006年の「第16回世界コンピュータ将棋選手権」において初出場で優勝するなど、個人が開発するソフトでありながら“最強ランク”の1つに数えられる将棋ソフト（2008年の第18回大会では第3位）。従来はバイナリのみの配布だったが、1月29日公開のv4.0.3よりソースコードも含め配布されるようになったようだ。
（追記：2009/02/22 12:02）公式サイトからのダウンロードはかなり重いので、入手したい場合は窓の杜からのダウンロードを推奨します（#1518125のコメント、ありがとうございます）（by otk）
次回大会ライブラリとして認められたようです (スコア:5, 参考になる)
コンピュータ将棋協会のサイトを巡っていたら、
既に、次回大会で使用可能なライブラリとして認められていたようです。
第19回(2009年)コンピュータ将棋選手権使用可能ライブラリ
開発者名 : 保木邦仁
ライブラリ名 : Bonanza Version 4.0.3
ライブラリ一覧 [computer-shogi.org]
アルゴリズムがキモ (スコア:4, すばらしい洞察)
この種のソフトは，マシンパワーもさることながら，
「よりよい手を探すアルゴリズム」
がキモだと思うのです．碁や将棋は，たとえばチェスよりも遥かに広い確率空間をもつので，
要するに総当たり戦が使えないのです（よね？）．
より良いアルゴリズムを作るのは，その素質のある人に限られる，と私は考えています．
企業がプロジェクトチームで作ろうが，名棋士を呼ぼうが，一人のアルゴリズムの天才にはかないません．
したがって，ソースを公開したことで模倣者が出てきたとしても，再利用するしか能がない模倣者は，
次のよりよいアルゴリズムにはかなわないのではないでしょうか．
そうじゃないだろう！
Re:アルゴリズムがキモ (スコア:2, 参考になる)
> 要するに総当たり戦が使えないのです（よね？）．
従来の強い将棋ソフトはアルゴリズム重視でしたが、Bonanzaは総当たり探索が大きな特徴ですよ。ある意味先行する他のソフトはCPUが遅かったころから開発されていたのに対して、後続の強みが発揮されている点だと思っています。
Bonanza:思考ルーチン/Wikipedia [wikipedia.org]
全幅検索
Bonanza以前のコンピュータ将棋ソフトでは、その局面で可能なすべての指し手を評価する（全幅検索）のではなく、駒を取るなどの自然な指し手を重視して検索していた。これはすべての指し手を評価すると選択肢が膨大になり、現実的ではないと考えられていたからである。Bonanzaはその常識を覆し、全幅検索を実現することでこれまでのソフトが見落としていた（あるいは軽視していた）指し手に高い評価を与えることが可能となった。
Re:アルゴリズムがキモ (スコア:1)
失礼しました，まさにその通り．．．
真に恐れるべきなのは，名棋士の頭ですね．
そうじゃないだろう！
Re:Bonanzaの作者は他の将棋ソフトの作者とは違って本人はさほど将棋が強くないんじゃなかった？ (スコア:4, 興味深い)
さほどどころか、無茶苦茶に弱いですよ。少なくとも最初の開発時点では、「ルールを知ってるだけ」レベルです。
#あの当時の将棋が出来る知人中一番弱かったんじゃないかなあ……
Bonanza自体も、保木が本職側のアルゴリズムを応用して片手間に作ってみたら意外に強かったというだけで、特に将棋を熟知して作り込んだわけでもありませんし。
（当時の他の方々とはアプローチの方向が違い、そのため他のプログラムに対し実力以上に強かったという面もあります。勿論それだけではなくそれなりの実力もあるアルゴリズムではありますが）
とりあえず本人は、「Bonanzaばっかり取り上げられて、本職（量子化学計算）の側がちっとも評価されん」とぼやいておりました。
そして究極の域へ・・・ (スコア:4, おもしろおかしい)
長い年月をかけ、幾多のアレゲな者たちの知恵を受け継ぎ、
いつの日か究極の進化を遂げた Bonanza は悟る。
対局開始時の盤面こそが最強である、と！
後手の場合：
対戦相手の初手のあと「おまえはもう負けている」と呟き、凄まじい勢いで手を打ちつづけ、勝つ。
先手の場合：
一手も打てず時間切れ「参りました orz」
# 究極って「窮極」とも書くんだね。
Re:そして究極の域へ・・・ (スコア:3, 興味深い)
将棋自体は2人零和有限確定完全情報ゲームというジャンルのゲームなので、完全に解析されれば最善手は一つに絞られ、「先行(後攻)が"必ず"勝つor負けるor引き分ける 」が決定できます。
(3x3マルバツゲームでお互い最善手を指せば必ず引き分けになるのと同じ)
今では情報があまりにも膨大なので、終局の時くらいしかその計算ができないだけで、将棋ソフトの行き着く先は第1手目から勝ち負けが判明している詰め将棋と同じようになるのかと。
Re:そして究極の域へ・・・ (スコア:3, 興味深い)
「究極的には勝敗の行方が初めから決定している」というのと「最善手が一つに絞られる」というのは若干意味合いが異なりますよね。現実に見かけるような局面であっても、例えば「詰み筋（つまりその時点での最善手）が複数あってどれを選んでも勝ちは決まり」という状況は多いですから。
あと、将棋自体はルールを厳密に定めれば2人零和有限確定完全情報ゲームということになると思いますが、詰将棋の世界ですらこんなもの [biglobe.ne.jp]がある（詳しい解説はこちら [cool.ne.jp]）上に、実際の対局では持将棋のルール（勝敗の判定基準は決まっているが、どの段階で勝敗判定を行うかが明文化されていない）などもあって、世の中で実際に指されている将棋が真に2人零和有限確定完全情報ゲームとなる日はまだ先のように思えます。
＃この場合、「確定」という条件が落ちているという解釈であってますでしょうか＞詳しい方
Re:そして究極の域へ・・・ (スコア:1)
詰将棋の方は実に面白いですね。根本は「詳しい解説」の方によると、
> 1. 「自分が負けとなる禁じられた局面を作る手」 =「禁手」かどうか?
これは、「禁手」とはっきり書かなかったルールブックもまずいですが、屁理屈に近い感があり、
この＝は成立していると考えて良いと思います。
> 2. 「打歩詰め」の定義が循環論法になっている(「打歩詰めの定義」には「禁手」が必要、「禁手」の定義には「打歩詰め」が必要)
こちらは、本質的なルールの欠陥と言えると思います。
ただし、実際将棋を指すプログラムを作るとすれば(千日手判定が入っているプログラムであれば)、本例の玉方が「56歩」と打つ手は、
「打歩詰め」であると判定する(すなわち、詰将棋の作意は成立している)とするのがすっきりしているでしょうね。
(「56歩は打歩詰め」ではない、と判定するには千日手による反則を例外扱いする必要があります。)
解説の人も最後に書いていますが、「打歩詰め」の「循環論法」は歩を打つことで詰みを回避できるような変則ルール上の詰将棋でも、
歩の枚数だけの参照を繰替えせば、循環は解決できますし、普通の指将棋ならもっと解決は簡単なので解決して欲しいですね。
Best regards, でぃーすけ
Re:そして究極の域へ・・・ (スコア:3, 参考になる)
実際に、現在のA級順位戦に相当するリーグ戦のある対局で、下手すると無限に手が続きかねない局面（勿論、指しているのは生身の人間なので無限には続けられないわけですが、理論的には）が登場したことがきっかけで、現在のルールに変更されたとのことです。
その辺りの詳細はこちら [cool.ne.jp]。
＃もしそこで両者ともに意地を張り続けて、一日制の対局で二日目突入、なんてことになったら
＃「将棋界の一番長い日」の意味が変わっていたかもしれませんね
現在の「同一局面４回」ルールでも、仰る通り理論的な最長手数は相当なものになると思います（計算はしていません）が、それでも対局手数がちゃんと有限で収まる保証があるというのは、理論的にも実際の運営の上でも重要なことだと思います。
Bonanzaクローンが蔓延？ (スコア:3, 興味深い)
世界コンピュータ将棋選手権は「参加プログラムは、思考部を自作し、
かつそれにオリジナリティがあるものに限る」というルールを掲げていてるので、
Bonanzaを若干チューニングしたものがぞろぞろ出てきた時に、
困っちゃうんだろうね
将棋ソフトの発展のために作られたルールだけど、
有名な強豪ソフトのソース公開で、
この発展の方法論に見直しを迫られることになるかも
蔓延しちゃまずいの？ (スコア:2, すばらしい洞察)
蔓延したとして、どういったことが問題になるのでしょうか？
Bonanzaのサイトにアクセスが集中しているのか、ダウンロードがまったく進まない状態なのでライセンスを確認できていませんが、ライセンス違反があったとしたらそれはもちろん問題です。
ただ、それ以外に、Bonanzaおよびそのクローンが広まることで起きる問題って何がありますか？
将棋のソフトを販売している人や会社は困るかも知れませんが、Bonanzaの強さや無料という魅力に負けたのならそれはしかたないことだろうし。
Re:蔓延しちゃまずいの？ (スコア:2, 興味深い)
大丈夫、Bonanzaに素人が少し改変を加えるくらいだと必ずと行って良いほど元より弱くなるでしょう。
改変しなきゃ(特に序盤〜中盤で角を切ったりすると)ばればれだし。
2、3日前に2chで見た限りだとパラメータ少しでも弄るとすぐ弱くなるみたいですよ。
Best regards, でぃーすけ
Re:蔓延しちゃまずいの？ (スコア:2)
という事は、今後抜本的なアルゴリズムの改良が必要ってことで、ソース公開に踏み切ったんですかねぇ
どんなのが出てくるか、ちょっと楽しみですね
脳味噌腐乱中…
Re:蔓延しちゃまずいの？ (スコア:1)
結局Bonanza派生版だらけになってもおかしくないと思いますよ.
Re:蔓延しちゃまずいの？ (スコア:1)
あらゆる将棋アルゴリズムでできた「空間」のなかで、Bonanzaは強さのローカルマクシマム(つまりどの方向にパラメータを動かしても強さが下がるだけ)に陥ってしまった、と感じてらっしゃるのかもしれませんね、作者さんは。パラメータをいじる以外のアルゴリズムの小さな変更でも弱くなるのかもしれません。
「探索するアルゴリズム」を探索することのできる人間というのはなんとも興味深い存在です。アルゴリズムを探索する「アルゴリズム」は普通の意味でのアルゴリズムではないわけですから(数値パラメータ空間の探索だけなら普通のがアルゴリズムでしょうが)。
Re:蔓延しちゃまずいの？ (スコア:2, 興味深い)
単なる想像ですが、角を取った瞬間の評価値が高いでしょうから、例えば最良優先探索なんかを採用している場合に優先的に読んでしまうのかもしれませんね。
(「必ず相手も指した段階で評価する」とかすれば防げるのかな？)
Bonanzaの場合、他ソフトや人がやらないようなところで交換ではなく切ってしまうのは他のソフトより「角」の価値が大分低く評価されているからだ、
という話を聞いたことがあります。
Best regards, でぃーすけ
Re:蔓延しちゃまずいの？ (スコア:1)
短期的には亜種が増えそうな気もしますが、すぐに落ち着くかと。
ソース公開に至った経緯 (スコア:2, 興味深い)
Re:ソース公開に至った経緯 (スコア:4, すばらしい洞察)
てか、スラド(の中)の人がインタビュー申し込むってのは？
ときどきやってるオプソ作者インタビューの番外編みたいな感じで。
無敵のレベル6になるには (スコア:2, おもしろおかしい)
Re:無敵のレベル6になるには (スコア:1)
なるほど、
重要なのはコードではなく、
その背後にある学習結果としての膨大なデータにあるといいたいわけですね！！！
#もとネタ知ってるけど。
マクロの基本は検索置換(by y.mikome)
Re:無敵のレベル6になるには (スコア:1)
よくしらないけど、棋譜データベースを作るのは
力仕事にしても時間もかかるし、結構大変なんじゃないかな
将棋ソフトを作ろうと思う人は、アルゴリズム部分に興味が
あるのだろうし、ボナンザの序盤データベースが流用できれば
開発は楽になるだろうね
とボナンザはボナンザは推測します。
とりあえず保存 (スコア:1, 参考になる)
参考になるソースか見てみよう。と思ってダウンロードしてみました。
(まだ解凍もしてませんが)
ダウンロード中に、ページをみていたのですが
＞なお，v4.0 から 200MByte 程度メモリを使用するようになりました．ご注意ください．
・・・うちの想定してる環境じゃ、そんなにメモリが取れませんよ。
Re:とりあえず保存 (スコア:3, すばらしい洞察)
携帯ゲーム機に移植しようとしてるな・・・
Re:とりあえず保存 (スコア:3, 参考になる)
すでにあるみたいですよ＞携帯ゲーム版
http://www.success-corp.co.jp/software/psp/bonanza/ [success-corp.co.jp]
某所の評価によれば、”最強”にすると思考時間がとても長いそうですが。まぁ無理もないか。
Re:とりあえず保存 (スコア:2, 興味深い)
COM対局モードでは、初心者、初級、中級、上級、最強とCPUレベルを選択できます。
定跡を知っていれば、初級レベルまでは、9割以上の勝率で楽勝。中級、上級では
さすがに手ごわくなってきて、勝率は下がってきます。
最強モードも試しましたが、10数手頃から早くも、CPUは7分間の長考モード突入！
こっちは、定跡で1分以内で指してるのに、空気読めよ、って感じ。(笑)
で、忍耐負けで最後まで、指せたことありません。
Re:とりあえず保存 (スコア:2)
PC88の大戦略ほどではあるまい。
Re:とりあえず保存 (スコア:1)
演算パワーとしてはモンスターマシンのPS3に移植するなんてプロジェクトも生まれそうですね
Re:とりあえず保存 (スコア:1)
演算コア部分だけサーバ側で処理して、GUI部分だけ端末向けに作れば、移植が楽だな。
サーバー運用費が掛かるけどね。
Re:とりあえず保存 (スコア:1)
改造してより省メモリのソフトを作るって手もあるよ。
お手軽利用？ (スコア:1, 興味深い)
子プロセスとして生成(起動)したbonanza プロセスと通信するライブラリが含まれていますね。
Bonanzaには手を加えず、上物だけ開発してBonanzaエンジンを利用出来るみたい
といっても、インタフェースを変えるくらいしか思い付きませんが
本格的にいじるなら、並列化とか分散とかその辺は面白そう
Bonanza自体は材料になっちゃいますけど
Re:お手軽利用？ (スコア:1)
bonanza が決めた手に乱数を加えて指す手を決める「きまぐれモード」とか作って、対局者をどのくらいかく乱できるかとか試すと、楽しいかも。
並列化して、将棋界の Deep Blue を目指すのも悪くないかもね。
Re:お手軽利用？ (スコア:4, おもしろおかしい)
対抗して人類側も並列化すればいいかも。
つまりＡ級棋士＋タイトル保持者で集まって相談しながら次の手を決めるという……。
Re:お手軽利用？ (スコア:5, おもしろおかしい)
（最終局、タニーと地道が勝つこと前提）
と思ったけど、やっぱり話が合わないかも。
序盤：モテ変態流炸裂
中盤：木村顔面受け
終盤：藤井ファンタジスタ！
Re:お手軽利用？ (スコア:4, おもしろおかしい)
B:いや、こっちの方が。
C:俺の手の方が絶対に良いって。
A:こうなったら、誰の手を打つか勝負して決めよう。
B:何で勝負する?
C:この3人が集まったんだから将棋に決まってるだろjk
こうして、次の一手を決める将棋トーナメントが始まった。
Re:お手軽利用？ (スコア:2)
ペア将棋なんか見ていて思ったんだけど、３対３で戦うなら
誰もが思い浮かぶだろう羽生名人・森内九段・佐藤棋王の組み合わせとか
レーティング上位 [nifty.com]で羽生名人・久保八段・木村八段の組み合わせより
所司一門で「定跡伝道師」所司七段：序盤の定跡部分・渡辺竜王：中盤の大局観・「スーパーあつし君」宮田五段：最終盤の詰み
の組み合わせの方が強そうだな。
コンピュータなら序盤：定跡ファイルで（とにかく新しいやつ）、中盤：ボナ、終盤：柿木かな。
Re:お手軽利用？ (スコア:1)
合計 3,717 段ですね。
# お約束とわかっていつつも。
Re:お手軽利用？ (スコア:1, おもしろおかしい)
どこかのエロゲが搭載するんですね。
Re:お手軽利用？ (スコア:2)
切り捨てではなくてチェスクロックの方の持ち時間１分。
＃駒は桝目の真ん中に
Re:お手軽利用？ (スコア:1, 参考になる)
そこで駒を取ったり成ったりしたときにミニイベントですよ。
一部脱いだりオプション付けたり。
# 無数の組み合わせで新たな属性が見つかるかもしれません。絵師は死ぬ。
コンピュータの場合・・・ (スコア:1, 興味深い)
「制限時間」の代わりに「制限処理量」を設定すべきなのではないかと思ったり。
時間だと、それこそハードウェアの進歩次第で、力押しで全ての手を解析とか出来そうなわけで。
＃将棋の腕もプログラムの腕もほぼ皆無なので、スコア0スタートの為にAC
＃＃+1の設定であれば逆に-1になるような「カルマボーナスを逆向きに使う」とかあればいいのに。
Re:コンピュータの場合・・・ (スコア:1)
「制限エネルギー消費量」を設定する。
＃残りエネルギーがありません。これから１手１KJです。
Linuxへの移植は (スコア:1)
これまでは皆Wineで遊んでたみたいですが。
Re:Linuxへの移植は (スコア:3, 参考になる)
BonanzaのソースはLinux用のMakefileまで付いている
親切設計になっています。
/.ed (スコア:1)
Re:/.ed (スコア:1)
まだ本家からは全然落とせないんですが窓の杜のBonanza [impress.co.jp]から落とせました。
LIVE-GON(リベゴン)
参考文献 (スコア:1, 参考になる)
直接の参考文献では無いけれど、一応参考までに [amazon.co.jp]
＃いつの間にか増えてる。
Re:参考文献 (スコア:2)
ご本人の著書は、渡辺明竜王との共著「ボナンザVS勝負脳 [kadokawa.co.jp]」です。学習アルゴリズムの特徴が簡潔に説明されています。
後に「ボナンザ学習法」と呼ばれるようになった学習アルゴリズムの詳細については、情報処理学会誌に掲載された論文 [bookpark.ne.jp]や、ゲーム・プログラミングワークショップ 2006 [uec.ac.jp]の予稿集などをどうぞ。
「コンピュータ将棋の進歩」シリーズ最新刊は3年以上前に刊行されてるんですけど…。ボナンザ学習法の詳細が述べられた一般向け書籍はまだ発行されていないと思います。
学習側のソースがキモ (スコア:1)
ボナンザは、今まで手で調整していた特徴パラメタの重みを、プロ棋士の棋譜から機械学習で自動調整できるようにしたところに特徴があるわけですよね。
だから、(すでにパラメタ設定された)遊べるようになってる将棋ソフトそのものよりも、パラメタ調整用のときに使った棋譜学習プログラムの方が肝心だと思うのですが、そちらは公開されたのでしょうか。