コンピュータ将棋の現状：三人寄れば文殊の知恵は正しいか？

4月2日に情報処理学会が日本将棋連盟に「コンピュータ将棋」で挑戦状を送ったことが話題になった*1。日本将棋連盟は挑戦を受諾、女流棋界の第一人者、清水市代女流王将・女流王位が対戦相手と決まった。対戦は今秋から順次行われるという。

情報処理学会の挑戦状に関するFAQによれば、対戦ソフトウェアに関して次のように記されている。

Q：	対戦ソフトウェアは既に決まっているか
A：	合議アルゴリズムを用いる方針になっています。複数のソフトウェアを疎結合で並列計算させて、それらの意見を集約して、次の一手を決定する手法です。現在のところ、限られた実験では効果が認められており、これを実際の対局に用いる方向で検討しています。個々の参加ソフトウェアの候補は、プロジェクトに現時点で参加しているGPS将棋、Bonanza、激指、YSS、TACOS、柿木将棋などです。これを実用的にどのように組みあわせるのかは、実験を元に決めていきます。合議より単独が強ければ単独の可能性もあります。決定は本番一か月前までを予定しています。

挑戦状に関するFAQ

合議アルゴリズムとは何なのか？ そもそも現在のコンピュータ将棋のレベルはどの程度なのか？ 実は当の情報処理学会の学会誌である情報処理2009年9月号では「コンピュータ将棋の新しい波」という小特集が組まれており、コンピュータ将棋の現状を知る事ができる。現在までのコンピュータ将棋の歴史に関しては俺の邪悪なメモさんが『人間VSコンピューター　この世紀の決戦を楽しむために』という素晴らしいエントリをアップされているので、そちらを参照してもらうとして、本エントリでは前述の特集を参照して、現在のコンピュータ将棋のレベルを紹介したい。

【告知】@LunarModule7でつぶやいています。 興味のあるかたはフォローください。

プロ棋士が見たコンピュータ将棋の棋力

コンピュータ将棋を長年フォローしている勝又六段が「プロ棋士から見たコンピュータ将棋」という論文で、現在のコンピュータ将棋の棋力を評価している。

Bonanzaメソッド(後述)の浸透により、機械学習により評価関数を鍛える事によって、形勢判断を正確に行えるようになった。一昔前は数値化しやすい駒の損得に大きなウェイトが与えられてていたため、遊び駒を大量に作る傾向が見られたが、最近では駒の損得よりも効率を重視するようになってきているようだ。

勝又六段は昨年の世界コンピュータ将棋選手権の盤面の中から2つの象徴的な場面を上げている。1つ目は決勝リーグ1回戦GPS将棋対KCC*2戦である。図1は相矢倉から▲2五桂と銀取りに跳ねた場面である。

図1	図2

図1以下の手順は次の通りだ。

△4五歩！	▲3三桂成	△同角	▲3七角
△5三桂	▲6六銀	△6五桂左	▲2八飛
△8六歩	▲同歩	△7五銀！	▲同歩
△8六飛（図2）

勝又六段は次のように解説している（図番号のみエントリにあわせて修正している）。

将棋が詳しくない方は、駒の損得だけ見ていただきたい。いきなりの銀桂交換からさらに銀を捨てている。中盤に入ったばかりの場面でこんな駒損の攻めは今まで見られなかった。Bonanzaよりも過激だ。

何でこの攻めができたかというと評価関数が精密になったためである。銀桂交換でも玉をにらむ位置に角が移動する事で、角の価値を大幅にアップさせ、先手の家（囲い）の資産価値を大幅にダウンさせる。そのため得な取引と読み、先の△7五銀の銀捨てまでたどりついたのだ。図2で十字飛車が決まって後手優勢。図からは▲9八玉に△8八歩▲同金△6六飛▲同金△同角と飛車を捨て、さらには角までも切って攻め、すべての攻め駒をさばいて金銀5枚の持ち駒という資産に変えて快勝した。

ただし、厳密に言えばGPS将棋のこの攻めが成立していたかは微妙だという。途中△3三角に▲2八飛ではなく▲7九玉△2四角▲6九玉と、囲いの外へ出れば攻めるのは大変だった。玉が囲いの外に出る手は先手にとって評価値を大きく下げる手であるので、後手は読む事ができなかったのではないかと推測される。

2つ目はGPS将棋対激指の盤面である。図3はGPSが▲5八桂と打ち、飛車角の利きを消した場面だ。

図3	図4

図3以下の手順は次の通りだ。

△4七歩成	▲同金直	△6六銀	▲9二馬！
△6七飛成	▲4六桂！	△4三銀打	▲同歩成
△同金	▲4四歩	△同金	▲5三銀
△4五歩	▲同桂	△同金	▲3四桂
△1三玉	▲4二銀不成	△同金	▲同桂成（図4）

勝又六段の解説は次の通りだ。

激指は△6六銀の銀捨てで速度を上げてくるが、ここで▲9二馬と引いて4七の金にヒモを付けてから、▲4六桂がうまい手順。5八の桂は受けのためではなく、攻めのためだったのだ。結局桂が5八〜4六〜3四〜4二と天使の跳躍で寄せきった。

攻めだけではなく、受けの手をはさみながら正確な速度計算をする。寄せるまでの構図が絶品で、プロでも時間をかけなければ読み切る事ができない困難な手順である。これを指せたGPSには感嘆せざるを得ない。

ちなみにこの将棋、駒がぶつかって一段落した後、GPSは高美濃→銀冠へと囲いを改築している。攻め合いを制したのはこの囲いの価値で差が出たものだ。戦っている途中でも攻めずに形を整えるという手が指せたのも今年の進歩だ。

勝又六段は昨年の世界コンピュータ将棋選手権において改良された点を次のように総括している。

1. 駒の効率を正しく理解できるようになった。
2. GPS-激指戦のように詰みの前の段階から、終盤の入り口から正確に指せるようになった。
3. 局面によって差し手に強弱が付けられるようになった。

そして、現在の棋力は早指しで四段、長い将棋で二段以上、三段近くはあり、今年はプロ四段認定となりそうだという。トッププロに追いつくのはさらに3年の間と勝又六段は予想している。

最近のコンピュータ将棋のアルゴリズム

「最近のコンピュータ将棋の技術背景とGPS将棋」では昨年の世界コンピュータ将棋選手権の覇者となったGPS将棋のアルゴリズムについて概略が述べられている。

ほとんどのコンピュータ将棋では自分の手と相手の手を網羅的に記述したゲーム木を用いて、自分の差し手を決めている。ゲーム木の各ノードには局面の形勢判断、すなわち勝ちやすさを表す評価値が与えられており、先手番（Max node）では最大の評価値を、後手番（Min node）では最小の評価値を選択していく。将棋のような2人/零和/確定/完全情報ゲームに分類されるゲームは、原理的には、このMaxMin探索を行う事で必勝法を求める事ができることが知られている*3。

少しでも深く分岐を読む

評価値には誤りが含まれるため、少しでも深い探索（一手でも先を読む）ことがコンピュータ将棋の強さに直結する。そのための戦略は2つあり、1つは単位時間あたりの探索局面数、すなわち探索速度を上げる戦略である。これには、マシン性能の向上、複数CPU/コアによる並列計算、ハードウェア化*4による高速演算などの手法が採られている。毎年コンピュータの性能は向上していくことから、コンピュータ将棋は毎年確実に強くなると期待される。

もう1つの戦略はメリハリを付けて読むことである。ゲーム木の全ての分岐を同じように読むのではなく、重要な分岐は深く、重要でない分岐は浅い段階で思い切って切り捨てればよい。これを枝刈と呼ぶが、論理的に読む必要がない部分の枝刈（αβ法）に加えて、多少のリスクを覚悟の上で、重要度の低い部分の枝刈を行う。

コンピュータ将棋では、王手や取り返しの場合は深く読むなど、将棋の特徴を活かした枝刈の手法が考案されており、中には非常に複雑な条件が指定されているものもあるようだ。このようなゲームの特徴を用いた枝刈は選択的探索と呼ばれる。一方、Bonanzaは、ゲーム特徴を用いず汎用的な枝刈のみを行う戦略を採っており、全幅探索と呼ばれる。もともと将棋では分岐の数が極めて多くなる事から将棋の特性を活かした選択的探索が有効であるとされていたが、全幅探索を行うBonanzaの成功から、全幅探索の有効性が見直されつつあるようだ。

世界コンピュータ将棋選手権で過去3回の優勝経験を持つ激指は実現関数と呼ばれる独自の探索を行っている。実現関数探索では、実際にその指し手が実現する確率を用意し、ルート局面から当該局面までの実現確率の積が閾値を下回ると探索を打ち切る。実現確率は、動かす駒の範囲、指手の履歴、指す駒に関する損得などプロ棋士の棋譜を利用して求められる。こうして、実現可能性の高い指し手を優先的に探索する事が可能となっている。

正確な評価値を得るには

正確な評価値を得る事は難しい。評価値を定める関数を評価関数と呼ぶが、ある局面の勝ちやすさを数値化する事は困難を極める。もともと評価関数は手作業でチューニングが施されるのが普通で、制作者が試行錯誤を積み重ねて、良い評価関数を追い求めてきた経緯がある。評価関数をどう調整するかは各プログラムが個性を発揮する部分であったわけだが、Bonanzaの登場が大きなブレークスルーとなった。

Bonanzaはこの評価関数を学習によって調整する手法、Bonanzaメソッドを初めて導入した。学習を導入する事で制作者は手作業で評価関数を調整する手間を省く事ができるようになり、膨大なプロの対戦棋譜データベースに基づいて評価関数を鍛える事が可能となった。昨年の世界コンピュータ将棋選手権では、学習を採用したプログラムが上位を占め、Bonanzaメソッドが有望視されている。

将棋の形勢判断を行うためには、駒の損得、働き、玉の危険度等を評価する必要がある。これは言葉にしてしまうと簡単だが、これをコンピュータに評価させる事は大変難しい。Bonanzaでは局面に登場する3駒の組合せそれぞれに値を付けて合計する事で評価値としている。全ての組合せを計算するのではなく、一定の制限が加えられているがそれでもパラメタ数は2億近くとなる。一方、GPS将棋では、人間が考える特徴に近いルールを100程度用意し、300万程度のパラメタを扱っているようだ。これらのパラメタは学習によって調整され、より妥当な形勢判断が行えるようにチューニングされる。

ここで上げた技術の積み重ねによってコンピュータ将棋は今やトッププロの背中が見える位置までその棋力を向上させてきたのである。

合議アルゴリズムの登場

そして、台風の目となり、物議を醸したのが合議アルゴリズムの登場である。「合議アルゴリズム「文殊」 単純多数決で勝率を上げる新技術」では、この新技術によってコンピュータ将棋界に一大センセーションを巻き起こした「文殊」の開発者がその概要について解説を行っている。文殊は初登場ながら、昨年の世界コンピュータ将棋選手権において3位という成績を収めた。しかしその成績以上に文殊は注目を浴びる事となった。

「文殊」の合議アルゴリズムとは簡単に言えば、複数のプログラムに独立に候補手を考えさせて、単純多数決により最も多い手を次の一手とするものだ。三人寄れば文殊の知恵という諺があるが、単純に数を増やすだけで強くなるのではないかというのが最初の発想である。とはいえ、当初は「そんな単純な方法で強くなるはずはない」「一貫した思考が行えず、かえって弱くなるのではないか」といった批判が圧倒的だったようだ。しかし、市販ソフトを用いて簡単な初期実験を行ったところ、合議させた方が勝率が有意に上がる結果が得られたという。

そして、2008年後半から2009年初頭にかけて、コンピュータ将棋において大きな転換期が訪れる。2006年世界コンピュータ将棋選手権の覇者であり、最強プログラムの一つであるBonanzaのソースコードが公開され、2009年1月には世界コンピュータ将棋選手権用のライブラリも提供されたのである。このライブラリを利用すれば誰でもBonanzaの強さを有する将棋プログラムを労せずして作る事ができるようになったのだ。

Bonanzaのようなトップレベルのプログラムのライブラリが提供される事は、世界コンピュータ将棋選手権としても想定外のことであった。全体としてのレベルは上がるかも知れないが、一からコツコツと独自のプログラムを作って来た開発者の意欲を失わせかねず、ひいては世界コンピュータ将棋選手権の有効性を失わせかねない事態であると危惧されたのだ。Bonanzaライブラリを用いたプログラムが上位を独占したらどうするのか？ そのあたりの議論の一端は、世界コンピュータ将棋選手権・オープンな価値との葛藤でも見る事ができる。

そうした懸念が渦巻く中、投入されたのが8コアのXeonマシンを3台連ねた「文殊」である。文殊は各4コアに配置された6つのBonanzaを並列して走らせ、合議によって次の1手を決めるプログラムである。各Bonanzaの用いる評価関数には正規乱数が加えられ、評価関数の異なるパフォーマンスが得られるように調整されていた。

ある一定の探索時間を経て多数決を行うわけだが、6つのBonanzaのうち5つ以上候補結果が一致しなかった場合、意見が分かれるという事は難しい局面であろうという推定の元、探索延長を3段階まで行う処理が追加された。

また、相手の思考時間中にも継続して探索を行うために、指し手を返す時には、読み筋もあわせて返すようにして、二手先の手を合議で予測手とし、それを全てのBonanzaに伝え、相手の思考時間中にもその予測手に応じて先読みを継続させたという。

文殊は順調に予選を勝ち上がり、決勝リーグに駒を進めた。次に決勝リーグの対戦成績を示す。

	プログラム名	1	2	3	4	5	6	7	勝	負	SB	MD	順位
1	激指	5×	6×	7○	8×	3○	4×	2×	2	5	2.0	0.0	6
2	Bonanza	8×	7○	6×	4×	5○	3×	1○	3	4	8.0	2.0	5
3	YSS	7×	5×	8×	6×	1×	2○	4×	1	6	3.0	0.0	7
4	KCC将棋	6×	8×	5×	2○	7○	1○	3○	4	3	7.0	3.0	4
5	文殊	1○	3○	4○	7○	2×	8×	6○	5	2	14.0	7.0	3
6	GPS将棋	4○	1○	2○	3○	8○	7○	5×	6	1	17.0	10.0	1
7	習甦	3○	2×	1×	5×	4×	6×	8×	1	6	1.0	0.0	8
8	大槻将棋	2○	4○	3○	1○	6×	5○	7○	6	1	16.0	10.0	2

文殊はBonanzaとの直接対決では敗れたものの、総合順位では5位のBonanzaを上回る3位という上々の結果を残した（なぜ合議の文殊が単体のBonanzaに負けたのか原因を推測することは興味深い）。一度のみの対戦で結論を導く事はできないが、少なくとも合議アルゴリズムが有効に機能する事は十分に示されていると考えて良いだろう。合議アルゴリズムにおいては個々のプログラムは任意であり、Bonanza以外のプログラムも問題なく利用できる。事実、YSSを用いた実験においても効果が認められている。清水市代女流王将・女流王位との対戦においては、複数のプログラムを組み合わせた合議システムを検討しているとされる。

現在のところ、三人寄れば文殊の知恵という諺は成立しているようだが、これがいつまで正しいかは分からない。せっかく一つのプログラムが神の手に到達したとしても、多数決によって否定されてしまうのではかえって弱くなってしまうのではないかと考えるのは極めて真っ当だ。特集では次のような識者の見解が紹介されている。

合議が一定の結果を得ているのは、先に悪手を指してしまうとなかなか勝てないが、妙手を連発しなくてもなんとか均衡を保って、相手が先に悪手を指せば勝てる、という将棋の特性ではないかと思います。個々のレベルは互角でそのうち悪手を指すレベル同士ならば、合議の意味があるのではないかと思います。相手が格上だと駄目かも知れません。

清水市代女流王将・女流王位との対戦において合議がうまく機能するのか、あるいは単一のプログラムの方が良い勝負ができるのか、今秋に予定されている対戦が楽しみだ。

実は5月4日から2010年の世界コンピュータ将棋選手権が開催される予定となっている。参加チーム一覧を見ると、Bonanzaメソッドの浸透により、学習によって評価関数の精度を向上させたプログラムが多く参戦しているようだ。またBonanzaを並列に結合させた合議アルゴリズムを採るプログラムの姿も見える。

選手権の様子はインターネット上で中継される上に、5月4日の決勝は一般向けにプロ棋士による解説会も行われるようだ。第20回世界コンピュータ将棋選手権 10のみどころが挙げられているので、興味のある方は見てみてはいかがだろうか（宣伝）。

今年は一体どのようなイノベーションが生まれるのか、コンピュータ将棋はどれだけ強くなっているのか、プロ棋士に一矢報いる日は早まりそうなのか、世界コンピュータ将棋選手権における各プログラムの活躍に期待したい。

*1:このプレスリリースはお堅い（と思われている）学会が出すプレスリリースとしては異色の出来で大変素晴らしい。是非とも今後ともこの路線を踏襲してもらいたいモノだ。

*2:KCC将棋：北朝鮮製の強豪プログラム。2009年の選手権に2年ぶりに復帰、予選を負け無しの16勝トップで通過したものの、決勝でソフトを入れ替えて3連敗、元に戻して4連勝の3勝4敗で4位となった。ソフトの入れ替えをしなければ優勝していたかも知れない強いプログラムである。

*3:実際には評価値に誤りが含まれる上、全ての分岐を読み切る事は不可能なので、必勝法を求める事はできない。

*4:世界コンピュータ将棋選手権にはA級リーグ指し手1号という名のFPGAを用いたプログラムが参加しているようだ。