Bonanza
作者 | 保木邦仁 |
---|---|
最新版 |
6.0
/ 2011年5月9日 |
プログラミング 言語 | C言語 |
対応OS | Windows |
対応言語 | 英語 |
種別 | コンピュータ将棋 |
公式サイト | www.geocities.jp/bonanza_shogi/ |
Bonanza(ボナンザ) は、コンピュータ将棋のプログラム。Windows用のフリーウェアとして公開されており、誰でも無償でダウンロードして利用することができる。ソースコードも公開されている。
概要
作者は公開当時カナダ在住だった日本人の化学者保木邦仁。作成当時は将棋についてはほとんど知らないことも話題となった[1]。後に発行した本では、自らの棋力を「11級」と評した[2]。
2005年6月にver.1.0が公開。その棋力の高さは公開直後から渡辺明がブログで「プロが平手で餌食になった」「奨励会有段者クラスがコロコロ負けているらしい」とたびたび話題にし、渡辺自身も「10秒将棋[3]だと10回に1、2回はやられる」と告白した[4]。また、コンピュータらしくない人間らしく自然な手を指すとの評が確立した。棋力の指標となる将棋倶楽部24でのレイティングは2006年当時で2400以上(アマチュア五段相当)に達した。
メジャーアップデートされたver.2.0は2006年5月に行われた第16回世界コンピュータ将棋選手権大会にBonanzaとして初出場し、歴戦の将棋ソフトが居並ぶ中で初優勝という鮮烈なデビューを飾る[5]。高性能なワークステーションで参加する者も多い中、Bonanzaは一般向けのノートパソコン(VAIO SZ-90S)、筐体を冷却するのは小型USB扇風機と、低スペックの環境での優勝であった。この赤い扇風機は、後に市販された初回限定版に同梱されるなどBonanzaの象徴となり、後述する竜王との対局でも、Bonanzaのシンボルマークとして筐体の上に設置された(風は送っていない)。既に草創期を脱し強豪ソフトが固定化されてきた中の初出場初優勝、ノートパソコンでの優勝、フリーウェアの優勝という三重の「初づくし」は、コンピュータ将棋界に巨大な衝撃を与えた。
ソースコード公開後
2006年11月11日の第11回 ゲーム・プログラミングワークショップ 2006にて、アルゴリズムの詳細を発表した[6]。
2009年1月、保木はBonanza Version 4.0.3の思考ルーチンのソースプログラムを公開し、他の開発者の利用を認めた。これにより、Bonanzaの思考ルーチンの詳細が明らかになった。これを利用し、2009年の第19回世界コンピュータ将棋選手権には電気通信大学の開発チームが、乱数によって異なる思考を行う複数のBonanzaライブラリの合議制アルゴリズムによって指し手を決定する「文殊」を開発して初出場し、本家Bonanzaに直接対決では敗れたものの、総合成績ではBonanzaの5位を上回る3位となった。
2010年5月2日の第20回世界コンピュータ将棋選手権では、保木と文殊チームが連合し合議制アルゴリズムを採用した「Bonanza Feliz」(Ver.5.0に相当)を擁して出場し5位となったほか、3チームがBonanzaライブラリ採用のソフトで出場し、「ボンクラーズ」が本家を上回る4位、芝浦工業大学の「芝浦将棋」が初出場ながら決勝に進出して7位となった。
2011年5月5日の第21回世界コンピュータ選手権では、電気通信大学の特任助教に就任した保木が自らの単独名義において、ver.6.0でエントリーし2位となる。この大会では、17台のパソコンによる並列処理を行い、うち1台はこれまで搭載していなかった長手数の詰将棋専用のルーチンを搭載して即詰みに対応した。また、保木以外に4チームがBonanzaライブラリ採用のソフトで参加し[7]、「Ponanza」が決勝に進出して5位となった。
思考ルーチン
Bonanzaの思考ルーチンは、Bonanza以前のコンピュータ将棋ソフトでは採用されていなかった独自のアイディアが用いられている。括弧内のページ数は『ボナンザ VS 勝負脳』を参考にしている。
- コンピュータチェスの思考を応用
- 保木は当初コンピュータ将棋ではなく、コンピュータチェスの論文をベースとして思考ルーチンの基本部分を作成した。ベースとなるデータは、インターネットなどで入手できた6万局[8]に及ぶ将棋の棋譜データを元にしている。
- 全幅検索
- Bonanza登場以前のコンピュータ将棋では、その局面で可能なすべての指し手を評価する(全幅検索)のではなく、自然な指し手を重視して検索(選択検索)していた。全幅検索では全ての指し手を評価すると選択肢が膨大になり、現実的ではないと考えられていたからである。しかしBonanzaはその常識を覆し、全幅検索を採用することで、これまでの他のソフトが見落としていた(あるいは開発者が軽視していた)指し手に高い評価を与えることが可能となった。現在では後述のように全幅検索と選択検索のハイブリッドである。
- 開発当時の保木は将棋に対する造詣は深くなく、チェスと同じようなものであると考えていた。そのためコンピュータチェスで一般的な全幅検索を採用したが、保木によると「選択的探索は選択を行う処理が複雑になるため、全幅探索よりも負荷がかかる」としている(33ページ)。
- 評価関数のパラメータの自動生成
- これは保木の本業である化学反応の制御理論を応用したものである(26ページ)。保木自身の棋力ではコンピュータを強くする設定を行うことができず、既存の機械学習で成果を上げたプログラムがなかったため、制御理論をもとに自作することにしたという。
- ボナンザは元にした6万局の棋譜データから、評価関数のパラメータを自動生成している。他のソフトは開発者がパラメータを定めた評価関数を用いているため、開発者の固定観念や棋力の影響を受けることがあった。ただし、パラメータは自動生成だが、何を評価するかは保木自身が決めている。棋譜からパラメータを自動生成することで、開発者の主観を排除した評価関数は強みでもあるが、同時に弱みでもある。当初、Bonanzaは序盤で大駒を切る[9]ことが多かったが、これは大駒の点数が他のソフトに比べて低く設定されている[10]ためであり、人間の感覚に反するこの設定は、自動生成に由来するものであった。後述の渡辺との対局でも、この特性を利用した角銀交換を迫られたが、その時には既に極端な大駒切りに関しては対策されていたため、交換はしなかった。
- 詰将棋
- チェスがベースであるため[11]、開発当初は終盤の詰将棋のルーチンが搭載されていなかったため、詰める状況でも相手の駒をとり続けていた。2007年の世界コンピュータ将棋選手権からは、3手詰めのルーチンが搭載された。他のソフトでは最初から詰将棋専用のルーチンを用意しており、後で組み込んだBonanzaが特殊である。これについて渡辺は、終盤において王手以外の指し手を考慮することは、力の向上につながるともしている(130ページ)。もっとも、詰将棋非対応のため、詰将棋ルーチンを搭載したコンピュータソフトとの対局においては、長手数の即詰みを見落として頓死することがままあり、ボナンザを利用した市販のソフトでは、詰め将棋ルーチンを別途搭載することで補っているものもある。
既存のソフトとは全く異なるアプローチをとったため、世界コンピュータ将棋選手権に初出場した際は、保木はBonanzaが極端に強いか、弱いかのどちらかだと考えており、既存の強豪ソフトとほぼ同じ棋力であったことに愕然としたと記している(32ページ)。これらの特徴はコンピュータ将棋の過去の蓄積を知らなかったために実現したことであって、日本にいて情報が入ってくる環境であれば、個人が1年で完成させることは不可能であったと述べている(29ページ)。
以上のように、既存の常識に反する要素が多かったが、保木の試みはコンピュータ将棋の一大革新として、他の開発者が一斉に追随することになった。「全幅探索」と「評価関数のパラメータの自動生成」は、2010年までには世界コンピュータ将棋選手権の上位ソフト全てがこの方法を導入するようになった。「評価関数のパラメータの自動生成」に関しては、Bonanza登場以降のコンピュータ将棋界で「ボナンザ・メソッド/Bonanza Method」と表現[12]されるほどのインパクトがあった。
数式
以下、第11回 ゲーム・プログラミングワークショップ 2006にて発表された Ver. 2 時点でのアルゴリズムに基づく。
各盤面の判断となる評価関数が、強い棋士が実際に指した手と同じになるようなパラメータを探索する。以下の誤差関数 J を最小にするパラメータ v を最適化問題として探す。
右辺2項は過学習を防ぐための正則化項。N は学習データの局面数(対局数×手数)、は局面、M はその局面の合法手の数。T は T(0) 近辺で傾きが最大になる適当な関数(シグモイド関数など)。 は一手先の次の局面で、 は実際に強い棋士が指した手の局面。 は局面の評価関数。, は過学習防止の定数値の正則化係数。 は各駒の価値(駒割り)の総和(一次正則化)。 は駒の位置関係に対するパラメータの2乗(二次正則化)に勾配ベクトルへの寄与度をかけた値の総和。v の各値は整数値に限定。
J を v で偏微分をとり、勾配ベクトルに沿って最急降下法で下っていく。勾配ベクトルを求める際、 の部分は、このまま使わずに、評価関数の考える最善手と強い棋士が実際に指した手が一致した場合は、食い違うところまで手をたどっていき、食い違ったところの評価関数の差を使う。勾配を下る学習率パラメータは学習が進むにつれ徐々に小さくしていく。
評価関数は、以下の項目の総和(線形モデル)。2つ目以降は、駒の位置関係に対するパラメータ。
- 各駒の価値(駒割り)
- 王、他の駒2つの位置
- 王、隣接した味方の駒、他の味方の駒3つの位置
- 隣接しあった駒2つの位置関係
- 竜馬飛角桂香の利き上にいる駒の種類
- 竜馬飛角香が動けるマスの数
- ピンされている駒の種類、方向、王との距離
- 角と同じ色のマスにいる味方の歩の数
- 歩桂銀が前進できるか
- 竜飛香の前・後の歩
- 王の周囲25マスの利きの配置
T(x) の |x| が大きい手、つまり、最善手から大きく離れた手は、計算量を減らすため省略する。盤面の表現はビットボードを使い、高速化する。
将棋に関係ない部分の基本的なモデルは、機械学習の基本的なモデルに基づいており、例えば、C.M.ビショップの『パターン認識と機械学習』(ISBN 443110013X)の第3章『線形回帰モデル』などを参照すると良い。そこに独自の工夫を加えている。
駒の価値
Ver. 6 現在、src/client/param.h に駒の価値が記載されている。それ以外のパラメータは171MBのwinbin/fv.binに保存されている。
駒 | Ver. 2 | Ver. 6 |
---|---|---|
歩 | 106 | 87 |
香車 | 272 | 232 |
と | 279 | 534 |
桂馬 | 304 | 257 |
成香 | 323 | 489 |
成桂 | 363 | 510 |
成銀 | 415 | 495 |
銀 | 428 | 369 |
金 | 527 | 444 |
角 | 617 | 569 |
馬 | 698 | 827 |
飛 | 700 | 642 |
竜 | 854 | 945 |
更新履歴
- 2005年6月2日 Ver.1.0公開
- 2006年5月19日 Ver.2.0公開
- 2008年10月12日 Ver.3.0公開
- 2009年2月2日 Ver.4.0.4公開
- 2010年5月11日 Bonanza Feliz公開
- 2011年5月9日 Ver.6.0公開
パッケージ製品
作者の意向によりBonanzaは過去から現在までの全てのバージョンが無償で提供され続けている(Bonanza Version 4.0.3よりマルチコアCPUの並列処理に対応)。一方、Bonanzaのエンジンを搭載したコンピュータ将棋ソフトも市販されている。
- 2008年3月14日 「Bonanza 3.0 Commercial Edition」マグノリアから発売。
- 2008年12月18日 「最強将棋 BONANZA」株式会社サクセスからプレイステーション・ポータブル版が発売。
- 2009年3月13日 「世界最強銀星将棋8」シルバースタージャパンから発売。
- 2011年4月29日 「Bonanza5.1 Commercial Edition」マグノリアから発売。2010年10月10日に行われた、あから2010対清水市代の対局に参加したバージョン。
ソースコードのライセンス
ソースコードは公開されているものの、営利目的での利用が禁止されているなど制限があるため、Open Source Initiative の定めるオープンソースでもなければ、フリーソフトウェアでもない。
竜王との対局
2007年3月21日、大和証券杯ネット将棋・最強戦の創設を記念して、渡辺明竜王[13][14](当時)との特別対局が組まれた。対局は品川プリンスホテルでの公開対局となり、手合いは平手で、Bonanzaの先手、持ち時間はそれぞれ2時間とされた。公の場で、コンピュータ将棋がタイトル保持者と平手で対局するのは初めてのことであったが、渡辺は「私は嫌でしたが、頼まれたので引き受けました、と公表すること」を条件として、これを引き受けた[15]
この対局に用いられたBonanzaは、当時公開されていたver.2.1と比較しても、探索手数を大幅に増やし、戦法の選択を改善するなどチューニングをほどこしたものであった。またハードウェアもリアルコンピューティングの「RC Server Calm2000」(CPU:Intel Xeon X5355 2.66GHz×8cores、メモリ:8GB)と、市販のPCよりは高性能のものを使用した。これにより将棋倶楽部24でのレーティングは2800相当(アマチュア最強レベル)に達したという。結果は112手[16]で渡辺の勝ちとなったが、対局した渡辺が「奨励会初段~三段」[17]、勝又清和六段が「奨励会三段レベル」とBonanzaの実力を評価するなど、将棋ソフトの実力がプロに迫ってきていることを示す結果にもなった。渡辺はこの対局をブログで振り返り、「人間では発想できない良手を指した中盤での意外な強さ」と「コンピュータが絶対的な強さを持つと思われていた終盤での意外な見落とし」を指摘している。一方、開発者の保木は、「美しい棋譜を残すことができた」、すなわち第一人者相手に頓珍漢ではない自然な将棋を指せたことをもって評価とした。 この対局の模様は2007年4月21日にNHK衛星第2テレビで『運命の一手 渡辺竜王VS.人工知能・ボナンザ』というタイトルで90分間のドキュメントとして放送された。番組では、奨励会員らと共にボナンザ対策[18]を練る真剣な表情の渡辺や、対局中の「いやぁ、強すぎる、本当に」の嘆息を捉えている。
勝負の明暗を分けた一手
対局は中盤までBonanzaが優位に進め、対局を観戦していた棋士、Bonanzaの駒を動かしていた田中も互角もしくはBonanza優勢との見解を示していた。対局した渡辺は89手目にBonanzaが▲24歩と指した段階で自身の勝利を確信したがこの時Bonanzaが▲24歩ではなく▲27香と指していたら自身の敗北を予測していたという。 Bonanzaの指した▲24歩は渡辺の玉の囲いを一気に攻めこむ積極的な手であり、対する▲27香は飛車取りを防ぎつつ一旦受けにまわる手だった。 ▲27香を指されると数手先でBonanzaの玉に馬がはりつき、渡辺の攻めが続かず、負けに至ると読んだと渡辺本人が対局後に語っている。 [19]開発者の保木はその時、席を外していたが廊下でBonanzaが▲24歩と指したのを聞き「(Bonanzaが)そろそろ悪手を指しているころではないか」と取材陣に語っていた。
関連項目
- 矢倉囲い - 理由は不明だが「ボナンザ囲い」と呼ばれる、他に例を見ない「片矢倉」の変形版を多用する。渡辺によれば、一見すると素人臭い筋悪な形のようでいて、実際に攻略するとなると厄介であるという。
- 天下一将棋会 - 全国のプレイヤーと対戦できるアーケード将棋ゲーム。コンピュータとの対戦時、コンピュータの思考エンジンにBonanzaを使用している。
参考文献
- 『ボナンザ VS 勝負脳――最強将棋ソフトは人間を超えるか』(保木邦仁・渡辺明共著、角川書店、ISBN 978-4-04-710107-4)
脚注・出典
- ^ 通常コンピュータ将棋の開発者の中には、アマ強豪クラスも珍しくない。
- ^ 通常、将棋には11級という段級位の設定はない。『ボナンザ VS 勝負脳』の53ページで、渡辺は保木の棋力を「アマ5級程度」と評する。これは初心者がどうにか形になり始めた程度の棋力である。
- ^ 持ち時間を1手10秒に制限する。渡辺によれば、10秒将棋では思考・読みを行う余裕が全くないため、人間であれば直感・第一感で指すしかなく、その時間でもそれなりに読めるコンピュータが圧倒的に有利な条件であるという。
- ^ 渡辺明ブログ ボナンザとか。
- ^ 第16回世界コンピュータ将棋選手権 (2006年5月3日~5日開催)にて、Bonanzaが優勝(マグノリア、2006年5月6日)、 【レポート】フリーソフト「Bonanza」が初出場で優勝 - 第16回コンピュータ将棋選手権( マイコミジャーナル、2006年5月8日)。【NEWS】世界コンピュータ将棋選手権で優勝したフリーの将棋ソフト「Bonanza」(窓の杜、2006年5月17日)。
- ^ 第11回 ゲーム・プログラミングワークショップ 2006 プログラム
- ^ 前年度にBonanzaライブラリを採用した「ボンクラーズ」は独自のライブラリを開発して出場し、Bonanzaを抑えて優勝している。
- ^ 『ボナンザ VS 勝負脳』の27ページによる。CD-ROMで販売されているものも含め、プロの公式戦の対局3万局と将棋倶楽部24の3万局を利用している。玉が敵陣近くにあるときのデータを利用するため、後者は入玉の状態になったものを主に採用したという。
- ^ 大駒と小駒と交換する
- ^ 『将棋世界』2007年7月号「特集 第17回世界コンピュータ将棋選手権」より。
- ^ コンピュータチェスでは、駒数が少ない場合の解析結果が公開されており、そのファイルを利用するのが一般的である
- ^ 第18回世界コンピュータ将棋選手権に参加した奈良将棋開発者のレポートによると保木が開発者向けの発表で使った表現だったが、現在では論文などにも使用されているなど、用語として定着しつつある。
- ^ 竜王は名人とともに将棋界序列1位である。竜王と名人が別人であれば棋士番号が若い方が上位になり、同一人物であれば竜王・名人の称号(竜王が名人の上位)になる。
- ^ 2008年、羽生善治との激闘を制し初代永世竜王資格者となった。
- ^ 米長邦雄「名勝負今昔物語 - 人間 v.s コンピューター」週刊現代 2010年10月30日号
- ^ 保木は渡辺の110手目終了後での投了を意図したが、投了の手続きをアシスタント(将棋盤の前に座り、実際の駒を動かす係)の田中悠一(当時奨励会3段)に確認している間にBonanzaが手を指し進めたため、なお2手進行ののち改めて投了した。
- ^ コンピュータ戦迫る。 渡辺明ブログ 2010年9月15日
- ^ 保木が対策をしていたため失敗はしたが、ボナンザの癖であった大駒と小駒の交換が偶然ではないことを確信しているなど、熟知している様子が見て取れる
- ^ NHK衛星第2テレビ 『運命の一手 渡辺竜王VS.人工知能・ボナンザ』
外部リンク
- BonanzaのVer.1から4、Felizおよび6の歴代プログラムがすべて無料でダウンロードできる。
- Bonanza 3.0 Commercial Edition (マグノリアの製品ページ)
- 世界最強銀星将棋8 (シルバースタージャパンの製品ページ)