2007年3月21日、大和証券杯ネット将棋・最強戦の創設を記念して、渡辺明竜王との平手一番特別対局が組まれた。結果は渡辺が勝利した。
この対局の模様は2007年4月21日にNHK衛星第2テレビで『運命の一手 渡辺竜王VS.人工知能・ボナンザ』というタイトルで90分間のドキュメントとして放送された。
Bonanzaの思考ルーチンは、以前のコンピュータ将棋ソフトでは採用されていなかった独自のアイデアが用いられている。
- コンピュータチェスの思考を応用
- 保木は当初コンピュータ将棋ではなく、コンピュータチェスの論文をベースとして思考ルーチンの基本部分を作成した。ベースとなるデータは、インターネットなどで入手できた6万局[19]に及ぶ将棋の棋譜データを元にしている。
- 全幅探索
- Bonanza登場以前のコンピュータ将棋では、その局面で可能なすべての指し手を評価する（全幅探索）のではなく、自然な指し手を重視して探索（選択探索）していた。全幅探索では全ての指し手を評価すると選択肢が膨大になり、現実的ではないと考えられていたからである。しかしBonanzaはその常識を覆し、全幅探索を採用することで、これまでの他のソフトが見落としていた（あるいは開発者が軽視していた）指し手に高い評価を与えることが可能となった。現在では後述のように全幅探索と選択探索のハイブリッドである。
- 開発当時の保木は将棋に対する造詣は深くなく、チェスと同じようなものであると考えていた。そのためコンピュータチェスで一般的な全幅探索を採用したが、保木によると「選択的探索は選択を行う処理が複雑になるため、全幅探索よりも負荷がかかる」としている[20]。
- 評価関数のパラメータの自動生成
- これは保木の本業である化学反応の制御理論を応用したものである[21]。保木自身の棋力ではコンピュータを強くする設定を行うことができず、既存の機械学習で成果を上げたプログラムがなかったため、制御理論をもとに自作することにしたという。
- ボナンザは元にした6万局の棋譜データから、評価関数のパラメータを自動生成している。他のソフトは開発者がパラメータを定めた評価関数を用いているため、開発者の固定観念や棋力の影響を受けることがあった。ただし、パラメータは自動生成だが、何を評価するかは保木自身が決めている。棋譜からパラメータを自動生成することで、開発者の主観を排除した評価関数は強みでもあるが、同時に弱みでもある。当初、Bonanzaは序盤で大駒を切る[22]ことが多かったが、これは大駒の点数が他のソフトに比べて低く設定されている[23]ためであり、人間の感覚に反するこの設定は、自動生成に由来するものであった。後述の渡辺との対局でも、この特性を利用した角銀交換を迫られたが、その時には既に極端な大駒切りに関しては対策されていたため、交換はしなかった。
- 詰将棋
- チェスがベースであるため[24]、開発当初は終盤の詰将棋のルーチンが搭載されておらず、詰める状況でも相手の駒をとり続けていた。2007年の世界コンピュータ将棋選手権からは、3手詰めのルーチンが搭載された。他のソフトでは最初から詰将棋専用のルーチンを用意しており、後で組み込んだBonanzaが特殊である。これについて保木は、終盤において王手以外の指し手を考慮することは、力の向上につながるともしている[25]。もっとも、詰将棋非対応のため、詰将棋ルーチンを搭載したコンピュータソフトとの対局においては、長手数の即詰みを見落として頓死することがままあり、2011年の世界選手権では詰将棋専用マシンを一台用意して構成に加えた。また、ボナンザを利用した市販のソフトでは、詰め将棋ルーチンを別途搭載することで補っているものもある。
既存のソフトとは全く異なるアプローチをとったため、世界コンピュータ将棋選手権に初出場した際は、保木はBonanzaが極端に強いか、弱いかのどちらかだと考えており、結果として優勝こそしたものの既存の強豪ソフトとほぼ同じ棋力であったことに愕然としたと記している[26]。これらの特徴はコンピュータ将棋の過去の蓄積を知らなかったために実現したことであって、日本にいて情報が入ってくる環境であれば、個人が1年で完成させることは不可能であったと述べている[27]。
以上のように、既存の常識に反する要素が多かったが、保木の試みはコンピュータ将棋の一大革新として、他の開発者が一斉に追随することになった。特に「評価関数のパラメータの自動生成」に関しては、ソースコード公開後のコンピュータ将棋界で「ボナンザ・メソッド」と呼ばれ[28]、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})](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f00b3f16b10437b134fc0ca476beb60ded9c81c)
右辺2項は過学習を防ぐための正則化項。N は学習データの局面数（対局数×手数）、
Jをvで偏微分をとり、勾配ベクトルに沿って確率的勾配降下法で下っていく。勾配ベクトルを求める際、
評価関数は、以下の項目の総和（線形モデル）。2つ目以降は、駒の位置関係に対するパラメータ。
- 各駒の価値（駒割り）
- 王、他の駒2つの位置
- 王、隣接した味方の駒、他の味方の駒3つの位置
- 隣接しあった駒2つの位置関係
- 竜馬飛角桂香の利き上にいる駒の種類
- 竜馬飛角香が動けるマスの数
- ピンされている駒の種類、方向、王との距離
- 角と同じ色のマスにいる味方の歩の数
- 歩桂銀が前進できるか
- 竜飛香の前・後の歩
- 王の周囲25マスの利きの配置
ただし、これは、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| が大きい手、つまり、最善手から大きく離れた手は、計算量を減らすため省略する。盤面の表現はビットボードを使い、高速化する。
将棋に関係ない部分の基本的なモデルは、機械学習の基本的なモデル[29]に基づいており、そこに独自の工夫を加えている。
駒の価値
Ver. 6現在、src/client/param.hに駒割りの値[30]が記載されている。それ以外のパラメータは177 MBのwinbin/fv.binに保存されている。
Ver. 2からVer. 6までの価値の変遷を見ると、次のようなことがわかる。
- と金の価値が2倍近くに高騰しており、成香・成桂の価値も約1.5倍に上昇している。
- 飛車や角を成るより歩を成った方が価値が高く、Feliz以降では歩を成ることにより銀1枚分以上の価値が発生する。
- 相対的に生駒の価値は減少傾向にあり、バージョンが進むにつれて、Ver. 2では銀を下回っていた成銀も含めて、成駒を重要視する傾向にある。
0 Comments:
コメントを投稿
<< Home