Bonanza
Bonanza(ボナンザ)は、コンピュータ将棋のプログラム。Windows用のフリーウェアとして公開されており、誰でも無償でダウンロードして利用できた。ソースコードも公開されている。
作者は公開当時カナダ在住だった日本人の化学者保木邦仁。作成当時は将棋についてはほとんど知らないことも話題となった。2007年に刊行した著書では、自らの棋力を「11級」と評した。
2005年6月にver.1.0が公開。その棋力の高さは公開直後から渡辺明が自身のブログで「プロが平手で餌食になった」「奨励会有段者クラスがコロコロ負けているらしい」とたびたび話題にし、渡辺自身も「10秒将棋だと10回に1、2回はやられる」と述べた。また、コンピュータらしくない自然な手を指すとの評が確立した。棋力の指標となる将棋倶楽部24でのレイティングは2006年当時で2400以上(アマチュア五段相当=主要アマチュア棋戦の県代表争いレベル)に達した。
メジャーアップデートされたver.2.0は2006年5月に行われた第16回世界コンピュータ将棋選手権大会にBonanzaとして初出場し、歴戦の将棋ソフトが居並ぶ中で初優勝した。高性能なワークステーションで参加する者も多い中、Bonanzaは一般向けのノートパソコン (VAIO SZ-90S)、筐体を冷却するのは小型USB扇風機と、低スペックの環境での優勝であった。この赤い扇風機は、後に市販された初回限定版に同梱されるなどBonanzaの象徴となり、後述する渡辺との対局でも、Bonanzaのシンボルマークとして筐体の上に設置された(風は送っていない)。既に草創期を脱し強豪ソフトが固定化されてきた中、初出場での優勝、ノートパソコンでの優勝、フリーウェアの優勝という三重の「初づくし」は、コンピュータ将棋界に巨大な衝撃を与えた。
2006年11月11日の第11回 ゲーム・プログラミングワークショップ2006にて、アルゴリズムの詳細が発表された。
2009年1月、保木はBonanza Version 4.0.3の思考ルーチンのソースプログラムを公開し、他の開発者の利用を認めた。これにより、Bonanzaの思考ルーチンの詳細が明らかになった。これを利用し、2009年5月の第19回世界コンピュータ将棋選手権には電気通信大学の開発チームが、乱数によって異なる思考を行う複数のBonanzaライブラリの合議制アルゴリズムによって指し手を決定する「文殊」を開発して初出場し、本家Bonanzaに直接対決では敗れたものの、総合成績ではBonanzaの5位を上回る3位となった。
2010年5月の第20回世界コンピュータ将棋選手権では、保木と文殊チームが連合し合議制アルゴリズムを採用した「Bonanza Feliz」(Ver.5.0に相当)を擁して出場し5位となったほか、3チームがBonanza4.0.3ライブラリ採用のソフトで出場し、「ボンクラーズ」が本家を上回る4位、芝浦工業大学の「芝浦将棋」が初出場ながら決勝に進出して7位となった。
2011年5月の第21回世界コンピュータ将棋選手権では、電気通信大学の特任助教に就任した保木が単独名義において、ver.6.0でエントリーし2位となる。この大会では、総計17台132コアのコンピュータによる並列処理を行い、うち1台はこれまで搭載していなかった長手数の詰将棋専用のルーチンを搭載して即詰みに対応した。また、保木以外に3チームがBonanzaライブラリ採用のソフトで参加した。
2012年5月の第22回世界コンピュータ将棋選手権では、保木は前年を上回る総計26台288コアのコンピュータを用意し、前年から取り組んでいる「合議法、クラスター並列探索、詰将棋専用マシンによる疎結合並列化」を推し進めたが、二次予選で9位となり、Bonanzaは初めて大会の決勝に残ることができなかった。この大会では6チームがBonanza6.0のライブラリを採用し、ボンクラーズから名称を変更した「Puella α」が2位に入った。
2013年5月の第23回世界コンピュータ将棋選手権では、保木は31台388コアのクラスタ構成で大会に臨み、前年は通過できなかった二次予選を4位で通過した。8チームの総当りで行われる決勝では6回戦を終えて4勝2敗となり、最終7回戦は5勝1敗の首位で前年の優勝チームであり、直前に行われた「電王戦」で三浦弘行八段を破ったGPS将棋との対局となった。対局は途中でBonanzaに即詰みが発生する必敗の局面となったが、25分の持ち時間を使い切ると即敗退となる制限時間のルールにより、GPS将棋が詰みを逃し持ち時間を使い切ったことでBonanzaが逆転で勝利。7回戦を終了して5勝2敗でBonanza、ponanza、GPS将棋の3チームが並んだが大会の順位決定規定によりBonanzaが2006年の初優勝以来7年ぶり2度目の優勝を果たした。この大会ではBonanza以外に9チームがBonanza6.0のライブラリを採用し、NineDayFeverが大会初出場ながら決勝に進出し、2位ponanzaと4位激指に勝つ健闘を見せて5位となった。
2014年に開催される第3回将棋電王戦の出場ソフトを決める、2013年11月の第1回将棋電王トーナメントでは、ハードウェアが主催者によってゲーミングパソコン1台に限定された中、予選を参加18チーム中3位で通過したが、準々決勝でYSSに、5位決定戦1回戦でAperyに敗れ、7位に終わった。
2014年5月の第24回コンピュータ将棋選手権では、保木は35台400コアのクラスタ構成で出場し、2次予選を6勝3敗の4位で通過し、決勝は3勝4敗の6位となった。この大会でもBonanza以外に9チームがBonanza6.0のライブラリを使用し、NineDayFeverが前年の自己順位と本年のBonanzaの順位を上回る4位となった。
2015年5月の第25回コンピュータ選手権にはBonanzaは出場せず、初出場からの連続出場が途切れた。Bonanza6.0のライブラリを使用して出場したチームは、一部のみの使用、実験で使用したものの本番では使用しなかったソフトも含めると10チームとなり、NineDayFeverが自己最高の成績となる2位となった。
2007年3月21日、大和証券杯ネット将棋・最強戦の創設を記念して、渡辺明竜王との平手一番特別対局が組まれた。結果は渡辺が勝利した。対局は品川プリンスホテルでの公開対局となりBonanzaの先手、持ち時間はそれぞれ2時間とされた。Bonanza側には、駒を動かすアシスタントとして当時奨励会三段の田中悠一がつき、保木は初手と終局以外は、Bonanzaの監視を行った。公の場で、コンピュータ将棋がタイトル保持者と平手で対局するのは初めてのことであったが、渡辺は「私は嫌でしたが、頼まれたので引き受けました、と公表すること」を条件として、これを引き受けた。
この対局に用いられたBonanzaは、当時公開されていたver.2.1と比較しても、探索手数を大幅に増やし、戦法の選択を改善するなどチューニングをほどこしたものであった。またハードウェアもリアルコンピューティングの「RC Server Calm2000」(CPU:Intel Xeon X5355 2.66GHz×8cores、メモリ:8GB)と、市販のPCよりは高性能のものを使用した。これにより将棋倶楽部24でのレーティングは2800相当(アマチュア最強レベル)に達したという。
対局は先手のBonanzaの四間飛車穴熊に対し、渡辺が銀冠穴熊という相穴熊模様になった。開発者の保木はインタビューに対し、「優秀とされる穴熊という作戦を(Bonanzaが)選んでくれて、とりあえず一安心。」と語った。中盤までBonanzaが優位に進め、対局を観戦していた棋士、アシスタントの田中も互角もしくはBonanza優勢との見解を示していた。対局した渡辺は89手目にBonanzaが▲2四歩と指した段階で自身の勝利を確信したが、この時Bonanzaが▲2四歩ではなく▲2七香と指していたら自身の敗北を予測していたという。Bonanzaの指した▲2四歩は渡辺の玉の囲いを一気に攻め込む積極的な手であり、一方▲2七香は飛車取りを防ぎつつ一旦受けに回る手だった。▲2七香を指されると数手先でBonanzaの玉に馬が張り付き、渡辺の攻めが続かず、負けに至ると読んだと渡辺本人が対局後に語っている。保木はその時、席を外していたが廊下でBonanzaが▲2四歩と指したのを聞き「(Bonanzaが)そろそろ悪手を指している頃ではないか」と取材陣に語っていた。ちなみに後のインタビューで米長邦雄はこの手に対し、「終盤の斬り合いは本来ソフトが得意とする分野で、間違えることは非常に珍しい。あの▲2四歩にはBonanzaの負けてたまるかという感情のようなものを感じた。」と語った。
結果は112手で渡辺の勝ちとなったが、対局した渡辺が「奨励会初段~三段」、勝又清和六段が「奨励会三段レベル」とBonanzaの実力を評価するなど、将棋ソフトの実力がプロに迫ってきていることを示す結果にもなった。渡辺はこの対局をブログで振り返り、「人間では発想できない良手を指した中盤での意外な強さ」と「コンピュータが絶対的な強さを持つと思われていた終盤での意外な見落とし」を指摘している。一方、開発者の保木は、「美しい棋譜を残すことができた」、すなわち第一人者相手に頓珍漢ではない自然な将棋を指せたことをもって評価とした。
この対局の模様は2007年4月21日にNHK衛星第2テレビで『運命の一手 渡辺竜王VS.人工知能・ボナンザ』というタイトルで90分間のドキュメントとして放送された。番組では、プロ棋士の村山慈明や当時奨励会三段だった戸辺誠らと共にボナンザ対策を練る真剣な表情の渡辺や、対局中の「いやぁ、強すぎるなこりゃ、ほんとに」の嘆息を捉えている。
次にプロ棋士との公式対局が行われたのは3年後の2010年10月11日であり、激指、GPS将棋、Bonanza、YSSによる合議制で作られた「あから2010」が清水市代女流王将と対戦し、あから2010が勝利した。
Bonanzaの思考ルーチンは、以前のコンピュータ将棋ソフトでは採用されていなかった独自のアイデアが用いられている。
保木は当初コンピュータ将棋ではなく、コンピュータチェスの論文をベースとして思考ルーチンの基本部分を作成した。ベースとなるデータは、インターネットなどで入手できた6万局に及ぶ将棋の棋譜データを元にしている。
Bonanza登場以前のコンピュータ将棋では、その局面で可能なすべての指し手を評価する(全幅探索)のではなく、自然な指し手を重視して探索(選択探索)していた。全幅探索では全ての指し手を評価すると選択肢が膨大になり、現実的ではないと考えられていたからである。しかしBonanzaはその常識を覆し、全幅探索を採用することで、これまでの他のソフトが見落としていた(あるいは開発者が軽視していた)指し手に高い評価を与えることが可能となった。現在では後述のように全幅探索と選択探索のハイブリッドである。
開発当時の保木は将棋に対する造詣は深くなく、チェスと同じようなものであると考えていた。そのためコンピュータチェスで一般的な全幅探索を採用したが、保木によると「選択的探索は選択を行う処理が複雑になるため、全幅探索よりも負荷がかかる」としている。
これは保木の本業である化学反応の制御理論を応用したものである。保木自身の棋力ではコンピュータを強くする設定を行うことができず、既存の機械学習で成果を上げたプログラムがなかったため、制御理論をもとに自作することにしたという。
Bonanzaは元にした6万局の棋譜データから、評価関数のパラメータを自動生成している。他のソフトは開発者がパラメータを定めた評価関数を用いているため、開発者の固定観念や棋力の影響を受けることがあった。ただし、パラメータは自動生成だが、何を評価するかは保木自身が決めている。棋譜からパラメータを自動生成することで、開発者の主観を排除した評価関数は強みでもあるが、同時に弱みでもある。当初、Bonanzaは序盤で大駒を切ることが多かったが、これは大駒の点数が他のソフトに比べて低く設定されているためであり、人間の感覚に反するこの設定は、自動生成に由来するものであった。後述の渡辺との対局でも、この特性を利用した角銀交換を迫られたが、その時には既に極端な大駒切りに関しては対策されていたため、交換はしなかった。
保木は後に、Bonanzaがコンピュータ将棋界に与えた影響について「目的関数の最小化を、状態遷移の拘束条件(化学ではシュレーディンガー方程式、将棋ではミニマックス原理)と適切な正則化条件の下で真面目に行なうという点が、思考ゲームの分野にもたらしたブレイクスルーだったのではないか」と振り返った。
チェスがベースであるため、開発当初は終盤の詰将棋のルーチンが搭載されておらず、詰める状況でも相手の駒をとり続けていた。2007年の世界コンピュータ将棋選手権からは、3手詰めのルーチンが搭載された。他のソフトでは最初から詰将棋専用のルーチンを用意しており、後で組み込んだBonanzaが特殊である。これについて保木は、終盤において王手以外の指し手を考慮することは、力の向上につながるともしている。もっとも、詰将棋非対応のため、詰将棋ルーチンを搭載したコンピュータソフトとの対局においては、長手数の即詰みを見落として頓死することがままあり、2011年の世界選手権では詰将棋専用マシンを一台用意して構成に加えた。また、ボナンザを利用した市販のソフトでは、詰め将棋ルーチンを別途搭載することで補っているものもある。
既存のソフトとは全く異なるアプローチをとったため、世界コンピュータ将棋選手権に初出場した際は、保木はBonanzaが極端に強いか、弱いかのどちらかだと考えており、結果として優勝こそしたものの既存の強豪ソフトとほぼ同じ棋力であったことに愕然としたと記している。これらの特徴はコンピュータ将棋の過去の蓄積を知らなかったために実現したことであって、日本にいて情報が入ってくる環境であれば、個人が1年で完成させることは不可能であったと述べている。
以上のように、既存の常識に反する要素が多かったが、保木の試みはコンピュータ将棋の一大革新として、他の開発者が一斉に追随することになった。特に「評価関数のパラメータの自動生成」に関しては、ソースコード公開後のコンピュータ将棋界で「ボナンザ・メソッド」と呼ばれ、2010年には世界コンピュータ将棋選手権の上位ソフト全てがこの方法を導入するようになった。
以下、第11回 ゲーム・プログラミングワークショップ 2006にて発表されたVer. 2時点でのアルゴリズムに基づく。
各盤面の判断となる評価関数が、強い棋士が実際に指した手と同じになるようなパラメータを探索する。以下の誤差関数Jを最小にするパラメータvを最適化問題として探す。
J(P_0, \ldots, \mathbf{v}) = \sum^{N-1}_{i = 0} \sum^{M}_{m=1}T[\zeta(p_m, \mathbf{v}) - \zeta(p_{m=0},\mathbf{v})] + \lambda M_1(\mathbf{v}) + \omega M_2(\mathbf{v})
右辺2項は過学習を防ぐための正則化項。N は学習データの局面数(対局数×手数)、P_iは局面、M はその局面の合法手の数。T は T(0) 近辺で傾きが最大になる適当な関数(シグモイド関数など)。p_m は一手先の次の局面で、p_{m=0} は実際に強い棋士が指した手の局面。\zeta は局面の評価関数。\lambda, \omega は過学習防止の定数値の正則化係数。M_1 は各駒の価値(駒割り)の総和(一次正則化)。M_2 は駒の位置関係に対するパラメータの2乗(二次正則化)に勾配ベクトルへの寄与度をかけた値の総和。vの各値は16ビット整数値に限定。
Jをvで偏微分をとり、勾配ベクトルに沿って確率的勾配降下法で下っていく。勾配ベクトルを求める際、\zeta(p_m, \mathbf{v}) - \zeta(p_{m=0},\mathbf{v}) の部分は、このまま使わずに、評価関数の考える最善手と強い棋士が実際に指した手が一致した場合は、食い違うところまで手をたどっていき、食い違ったところの評価関数の差を使う。勾配を下る学習率パラメータは学習が進むにつれ徐々に小さくしていく。この探索は1カ月以上計算させ続けている。
評価関数は、以下の項目の総和(線形モデル)。2つ目以降は、駒の位置関係に対するパラメータ。
各駒の価値(駒割り)
王、他の駒2つの位置
王、隣接した味方の駒、他の味方の駒3つの位置
ピンされている駒の種類、方向、王との距離
竜飛香の前・後の歩
ただし、これは、Ver. 4以降、Ver. 6現在は単純化しており、以下の3項目だけになっている。4つ以上の駒の関係も3つの駒の関係から近似的に合成できるとしている。この変更によりパラメータ数は大きく増え、パラメータを保存しているfv.binは177 MBになった。下記の駒の位置738通りにおいて、持ち駒も含まれるが、成金と金の区別はしない。
各駒の価値(駒割り) - 13通り
王1つ、他の駒2つの位置(自分と相手の駒の区別あり) - 81 * (1 〜 738 * 2 までの和) = 88,292,106通り
王2つ、他の駒1つの位置 - 81 * 81 * 738 = 4,842,018通り
Ver. 6のfv.binにおいては、2八玉・4九金の状況において、3八銀 = 357、4八銀 = -852、5八銀 = 442 となっており、美濃囲いや銀美濃を正しく学習している。そして、4八銀という駒の利きの悪い配置を大駒を失う並の悪い配置と見なしている。同じ4九金・4八銀でも、壁囲いの3八玉 = 31 であり、まだましであると評価している。
T(x) の |x| が大きい手、つまり、最善手から大きく離れた手は、計算量を減らすため省略する。盤面の表現はビットボードを使い、高速化する。
将棋に関係ない部分の基本的なモデルは、機械学習の基本的なモデルに基づいており、そこに独自の工夫を加えている。
Ver. 6現在、src/client/param.hに駒割りの値が記載されている。それ以外のパラメータは177 MBのwinbin/fv.binに保存されている。
Ver. 2からVer. 6までの価値の変遷を見ると、次のようなことがわかる。
と金の価値が2倍近くに高騰しており、成香・成桂の価値も約1.5倍に上昇している。
飛車や角を成るより歩を成った方が価値が高く、Feliz以降では歩を成ることにより銀1枚分以上の価値が発生する。
相対的に生駒の価値は減少傾向にあり、バージョンが進むにつれて、Ver. 2では銀を下回っていた成銀も含めて、成駒を重要視する傾向にある。
2005年6月2日 Ver.1.0公開
2005年7月21日 Ver.1.1公開
2005年8月23日 Ver.1.2公開
2006年5月19日 Ver.2.0公開(同日、不具合を修正したVer.2.1公開)
2008年10月12日 Ver.3.0公開
2009年2月2日 Ver.4.0.4公開
2010年1月25日 Ver.4.1.3公開
2010年5月11日 Bonanza Feliz公開
2011年5月9日 Ver.6.0公開
2015年9月10日 Bonanza 6.0 にあてるパッチ公開(1)内容:ソースコードのエラー修正。
2015年11月16日 Bonanza 6.0 にあてるパッチ公開(2)内容:最近の Floodgate への対応を追加。
2019年3月31日 ジオシティーズサービス終了に伴いBonanzaのWebサイト閉鎖。無料公開版の実行ファイルがダウンロード不能となる。
作者の意向によりBonanzaは過去から現在までの全てのバージョンが無償で提供され続けていた(Bonanza Version 4.0.3よりマルチコアCPUの並列処理に対応)。一方、Bonanzaのエンジンを搭載したコンピュータ将棋ソフトも市販されている。
2006年11月17日 「Bonanza 2.1 Commercial Edition」マグノリアから発売。
2007年6月15日 「Bonanza Classic」マグノリアから発売。2005年に発表された当時のBonanzaを搭載。
2008年3月14日 「Bonanza 3.0 Commercial Edition」マグノリアから発売。USB扇風機が付属。「4コアまで対応」と書かれているが、実際には8コアまで対応する。
2008年12月18日 「最強将棋 BONANZA」株式会社サクセスからPlayStation Portable版が発売。
2009年3月13日 「世界最強銀星将棋8」シルバースタージャパンから発売。
2011年4月29日 「Bonanza5.1 Commercial Edition」マグノリアから発売。2010年10月10日に行われた、あから2010対清水市代の対局に参加したバージョン。
2013年7月22日 「BONANZA THE FINAL 優勝記念版」マグノリアから発売。2013年の第23回世界コンピュータ将棋選手権で優勝した思考エンジンを搭載。ソフトの実力が上がりすぎたため市場が縮小したことを理由とし、これ以後マグノリアからBonanzaの製品版は発売されないことが発表された。
ソースコードは公開されている。営利目的での利用の禁止などの制限により、Open Source Initiativeによる「オープンソースの定義」には合致しない。
BonanzaはVer.2当時、「ボナンザ囲い」と呼ばれる、他に例を見ない「片矢倉」の変形版を多用していた。これはボナンザの数式の結果として現れたものである。渡辺明によれば、一見すると素人臭い筋悪な形のようでいて、実際に攻略するとなると厄介であるという。角交換が前提となる上、ボナンザ自体が機械学習の結果この形を使わなくなった結果あまり見られなくなった。