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の思考ルーチンは、以前のコンピュータ将棋ソフトでは採用されていなかった独自のアイデアが用いられている。
既存のソフトとは全く異なるアプローチをとったため、世界コンピュータ将棋選手権に初出場した際は、保木はBonanzaが極端に強いか、弱いかのどちらかだと考えており、結果として優勝こそしたものの既存の強豪ソフトとほぼ同じ棋力であったことに愕然としたと記している。これらの特徴はコンピュータ将棋の過去の蓄積を知らなかったために実現したことであって、日本にいて情報が入ってくる環境であれば、個人が1年で完成させることは不可能であったと述べている。
以上のように、既存の常識に反する要素が多かったが、保木の試みはコンピュータ将棋の一大革新として、他の開発者が一斉に追随することになった。特に「評価関数のパラメータの自動生成」に関しては、ソースコード公開後のコンピュータ将棋界で「ボナンザ・メソッド」と呼ばれ、2010年には世界コンピュータ将棋選手権の上位ソフト全てがこの方法を導入するようになった。
数式.
以下、第11回 ゲーム・プログラミングワークショップ 2006にて発表されたVer. 2時点でのアルゴリズムに基づく。
各盤面の判断となる評価関数が、強い棋士が実際に指した手と同じになるようなパラメータを探索する。以下の誤差関数Jを最小にするパラメータvを最適化問題として探す。
右辺2項は過学習を防ぐための正則化項。N は学習データの局面数（対局数×手数）、formula_2は局面、M はその局面の合法手の数。T は T(0) 近辺で傾きが最大になる適当な関数（シグモイド関数など）。formula_3 は一手先の次の局面で、formula_4 は実際に強い棋士が指した手の局面。formula_5 は局面の評価関数。formula_6, formula_7 は過学習防止の定数値の正則化係数。formula_8 は各駒の価値（駒割り）の総和（一次正則化）。formula_9 は駒の位置関係に対するパラメータの2乗（二次正則化）に勾配ベクトルへの寄与度をかけた値の総和。vの各値は16ビット整数値に限定。
Jをvで偏微分をとり、勾配ベクトルに沿って確率的勾配降下法で下っていく。勾配ベクトルを求める際、formula_10 の部分は、このまま使わずに、評価関数の考える最善手と強い棋士が実際に指した手が一致した場合は、食い違うところまで手をたどっていき、食い違ったところの評価関数の差を使う。勾配を下る学習率パラメータは学習が進むにつれ徐々に小さくしていく。この探索は1カ月以上計算させ続けている。
評価関数は、以下の項目の総和（線形モデル）。2つ目以降は、駒の位置関係に対するパラメータ。
ただし、これは、Ver. 4以降、Ver. 6現在は単純化しており、以下の3項目だけになっている。4つ以上の駒の関係も3つの駒の関係から近似的に合成できるとしている。この変更によりパラメータ数は大きく増え、パラメータを保存しているfv.binは177 MBになった。下記の駒の位置738通りにおいて、持ち駒も含まれるが、成金と金の区別はしない。
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までの価値の変遷を見ると、次のようなことがわかる。
パッケージ製品.
作者の意向によりBonanzaは過去から現在までの全てのバージョンが無償で提供され続けていた（Bonanza Version 4.0.3よりマルチコアCPUの並列処理に対応）。一方、Bonanzaのエンジンを搭載したコンピュータ将棋ソフトも市販されている。
ソースコードのライセンス.
ソースコードは公開されている。営利目的での利用の禁止などの制限により、Open Source Initiativeによる「オープンソースの定義」には合致しない。
ボナンザ囲い.
BonanzaはVer.2当時、「ボナンザ囲い」と呼ばれる、他に例を見ない「片矢倉」の変形版を多用していた。これはボナンザの数式の結果として現れたものである。渡辺明によれば、一見すると素人臭い筋悪な形のようでいて、実際に攻略するとなると厄介であるという。角交換が前提となる上、ボナンザ自体が機械学習の結果この形を使わなくなった結果あまり見られなくなった。