あなたが知らない(かもしれない)コンピュータ将棋の世界

essay 】 2010 / 04 / 08
 先週末、情報処理学会が日本将棋連盟に対してコンピュータ将棋とトップ棋士との対戦を求める挑戦状を送りつけ、日本将棋連盟が今秋にも清水市代女流王位・女流王将を対戦相手として送り出すとのニュースが流れた。
 情報処理学会は4月2日、コンピュータ将棋でトッププロ棋士との公開対局を求める挑戦状を日本将棋連盟に送った。日本将棋連盟もこれを受諾、清水市代女流王位・女流王将を対戦相手とすることを明らかにした。対戦は今秋に実施予定。

情報処理学会、日本将棋連盟に「コンピュータ将棋」で挑戦状をたたきつける - ITmedia エンタープライズ
 日本将棋連盟は2005年に会長に就任した米長邦夫がその年の10月の理事会で現役棋士とコンピュータ将棋との公開対局を原則禁止し、確か2007年3月のBonanza対渡辺明竜王戦以来、対局は行われていないと記憶している。ちなみにこのときの対局はBonanzaの開発者保木邦仁氏と渡辺明竜王の共著「ボナンザVS勝負脳 」(角川oneテーマ21)に詳しい。

 女流棋士対コンピュータ将棋。「最強将棋ソフトは人間を超えるか」? という興味深いテーマについてはすでに「俺の邪悪なメモ」「人間VSコンピューター この世紀の決戦を楽しむために」にコンピュータ将棋の歴史の概観を含め、その背景がわかりやすく紹介されている。しかし、個人的にはもう1本、楽しむための線を引いておいた方がいいと思っている。それは何か?

 コンピュータ将棋同士の潰しあい、コンピュータ将棋協会(CSA)が主催する世界コンピュータ将棋選手権である。毎年5月のGWに行われる世界選手権、第20回の今年は5/2〜5/4の3日間で開催される。

 先述のニュースを見たときに思ったのは、今秋の対戦ということならば、この第20回世界コンピュータ将棋選手権の優勝チームにプロへの挑戦権が与えられるのではないか、ということだが、どうやらそういう単純なことではないらしい。
 今秋に実施される予定の対局では、コンピュータ将棋のソフトウェアに合議アルゴリズムと呼ばれる方針を採用する予定。これは、複数のソフトウェアを疎結合で並列計算させ、それらを集約して、次の一手を決定する手法。具体的なソフトウェアとしては、2009年の世界コンピュータ将棋選手権で優勝した「GPS 将棋」のほか、Bonanza、激指、YSSなど世界コンピュータ将棋選手権で優勝経験があるソフトウェアの名が挙がっている。また、計算を行うハードウェアは、東大、京大、筑波大などの並列処理大規模計算機環境のグリッドを使う方向で検討しているという。

情報処理学会、日本将棋連盟に「コンピュータ将棋」で挑戦状をたたきつける - ITmedia エンタープライズ
 コンピュータ将棋界の総力を結集し、本気でプロに勝ちにいく気まんまんである。

 とまれ、まず楽しむべきは秋の大一番よりも5月の選手権である。以下、ごく大ざっぱに見どころを書いていこうとしているが、あまりにもコンピュータ将棋が進化してしまって棋力も知力もぼくには到底余る。この面白さ、伝わるんだろうか。適宜、リンク先を参照してほしい。




 なお、上にアフィリエイトリンクで将棋対局ソフトを貼っているが、BonanzaGPS将棋などダウンロードできるソフトが存在しているので購入しなくともコンピュータ将棋との勝負は楽しめる。笑い。どちらも思考ルーチン部が公開され、別途対局用のUIソフトが必要となるので「Bonanza用GUI マイボナ」のページからBonanzaと合わせて入手するのがよいかと。

Bonanzaという革命
 恐らく現在コンピュータ将棋で最も有名なのは先に渡辺明竜王との対戦でも触れた、保木邦仁氏が開発したBonanzaだろう。Bonanzaは第16回選手権で初出場初優勝を飾り一躍話題になった。すごかったのは、他のチームがOpteronのようなパワフルなプロセッサを積んだデスクトップ機を持ち込んでいるのに対して、BonanzaはCoreDuo T2600搭載のノートPCで勝ってしまったこと。当時、開発者の保木氏はカナダに留学中で、代理人が持参したのはVAIOノートに冷却用のUSB外付けファンというあまりにも質素な構成。これで決勝リーグを6勝1敗で制した。1年間かけてソフトを開発し、少しでも上位を狙うべくハイスペックのデスクトップPCを担いで大会にはせ参じた他チームの悔しさたるや想像するに難くない。

 しかし、Bonanzaが世界コンピュータ将棋選手権で優勝したのは2006年の第16回の1回のみだ。翌年の渡辺明竜王戦では選手権優勝バージョンをチューニングしたものが用いられている。そして第17回4位、第18回3位、第19回5位。すでにBonanzaと互角以上に戦うコンピュータ将棋は存在する。それでも今日のコンピュータ将棋は、おそらくBonanzaという革命を抜きに語りえない。それはおおよそ以下のような点にあるとぼくは考えている。
  • 全幅探索の採用
     Bonanzaを開発した保木氏は化学の研究者で、カナダのトロント大学に在籍中にディープブルーに関する論文を読み、コンピュータチェスで採用されていた全幅探索(一局の将棋の特定の局面における有効手すべてを探索する)を当然のものとして受け入れ、これをBonanzaに採用した。それまでコンピュータ将棋ではいくつかのありえそうな手を抽出して読んでいく選択的探索が一般的で、全幅探索は不可能だと考えられていたように思う。Bonanzaはミニマックス戦略(交互に自分のターンが回ってくるゲームで自分の打ち手に対して相手は最大の利益を得る打ち手を選択するものとして行動する)に基づくαβ法の枝狩り(3手読みで相手の選択手に対する自手の全幅探索を行う際、三手目の変化手順で最大値が出る分岐はミニマックス戦略から相手が選択しないものとして評価を打ち切るβカット、2手目の相手の指し手により自手の評価が最小になる組み合わせとなる初手が現れる分岐はミニマックス戦略から相手がその応手を選択するものとして評価を打ち切るαカット)や、盤面の2段目と8段目で特定の駒の不成りを探索から除外するなどの現実的な省力化で高速化を図っている。

  • 静的評価関数の大規模な生成
     コンピュータ将棋では駒自体の価値や駒組みなどをポイント化して評価する評価関数に基づいて指し手を決定する。それまで評価関数は開発者自身が将棋の棋力があり、自らの思考に基づいて評価関数をチューニングするのが一般的だったと思う。これは、1982年に谷川浩司(現九段)が著した「将棋に勝つ考え方―異次元の大局観」まで遡ることができるかもしれない。この本の中で谷川は各駒に具体的なポイントを割り振り、彼我の駒のポイント差や玉の堅さの比較による形勢判断という、それまでになかった考え方を示した。
     一方、Bonanzaの開発者である保木氏は将棋をほとんど指さないらしく、こうした評価関数を自力で作り出すことは困難だった。そこで彼はプロ棋士の棋譜3万局に加え、プロの対局にはほとんど現れない入玉戦(自玉を相手陣に進める形)についてオンライン上の対戦将棋サーバ「将棋倶楽部24」で公開されている棋譜3万局から補った約6万局をベースに、機械学習で評価関数を生成する手法を取った。これにより、人力では設定不可能な1万以上のパラメータで局面を評価することが可能になった。

  • 研究成果の積極的な公開
     Bonanzaのもたらした最も大きな革命は、こうした取り組みを前述の書籍「ボナンザVS勝負脳 」(角川oneテーマ21)ゲームプログラミングワークショップ2006(GPW-06)での講演、2009年のCSAライブラリとしてソースコード提供などを通じて、その手法をあますところなく公開したことだろう。これによって、Bonanzaの手法をベースに自らの手法を取り入れる、Bonanzaとは別の方向からのアプローチを探る、といった形でコンピュータ将棋自体の進化が加速したような気がしている。おもしろいのだけれど、もはやぼく程度の知識では歯が立たないところでみんな戦っているのである。
 そんなわけで、Bonanza以降のコンピュータ将棋は極めて高度に知的な戦いが繰り広げられている、という感じ。
 もちろん、Bonanzaだけが突き抜けていたわけではないと思う。他の開発者たちもきっと同様のチャレンジをずっと続けていたのだ。ここでは書籍にまとめられてわかりやすかったのでとりあえずBonanzaを取り上げた、ということで。

世界コンピュータ将棋選手権とは
 世界コンピュータ将棋選手権とは、コンピュータ将棋協会(CSA)が主催するコンピュータ将棋同士の対局により争われる大会で1990年の第1回より毎年開催され今年で第20回を迎える。「世界」と銘打っているがほんとうに海外からの参戦もあり、過去には北朝鮮のKCC将棋(第15回準優勝ほか3位3回)、イギリスのShotest(3位2回)などが活躍している。

 参加チームの増加により1996年の第6回より予選、決勝の2ラウンドとなり、1999年の第9回より現行の1次予選、2次予選、決勝リーグの方式となった。前年の成績により決勝シード、2次予選シードが与えられる。参加チーム(開発者が一人で参加するもののほか、チームで開発されるものも多く、こう呼ぶらしい)は第1回の6チームから増え続け、2001年の第11回の55チームを頂点にだいたい40チーム前後。LAN、あるいはRS-232Cによる通信、手入力での対戦で持ち時間25分切れ負け。千日手は指し直しではなく引き分けとなる。第16回大会以降、開催中のインターネット中継(確か対戦盤が表示される)も行われている。

 過去の優勝ソフトは世界コンピュータ将棋選手権のページで確認できる。PC用将棋ソフトの草分け的存在、森田将棋は第2回の優勝。

 世界コンピュータ将棋選手権はコンピュータ将棋の大会としては最も大きなそれだが、この他に過去2年間の主要大会で優勝した4ソフトが争うJAIST主催の「コンピュータ将棋 世界最強決定戦」、ゲームプログラミングワークショップで行われるGPW杯(カップはないらしい)、CSA主催のオープン戦のほか、2008年2月よりネットワーク経由で連続対戦(30分に1回)を行うfloodgate上での対戦が行われている。

第20回世界コンピュータ選手権のみどころ
 さて、今年は5/2〜5/4の3日間にわたって行われる第20回世界コンピュータ将棋選手権。参加チームを数えてみたら4/8現在決勝シード3、2次予選シード16、過去出場19、初出場16の計54チーム。
 で、みどころを書こうとしたら、「やねうら王」で初参加予定だった(キャンセルになってる!やねうらお氏「Bonanzaソース完全解析ブログ」にあった「第20回世界コンピュータ将棋選手権の参加申込者リスト」にほぼまとまってました。ぼくが興味を持った部分はこのエントリにほぼ含まれていた。がっくし。

 それでもまあ、せっかくなので気になるチーム紹介を一応書いていきます。あ、参加チーム一覧の見どころとしてはCPUに何を使っているか、がひとつのポイントだとか。なんか裏ではIntel派とAMD派の確執があるとかないとか。微妙にAMD頑張れという気がしなくもないAthlon64ユーザです。VIA C3とかCyrix MIIとかIBMのBlue Lightningとかも使ってたような記憶が。どんだけインテル入ってないんだよ、自分。

「Bonanza Feliz」(Team Bonanza)
 前回優勝の「GPS将棋」を差し置いてまずはこれ。名前からしてBonanzaの後継。で、前回大会3位の「文殊」が参加していないと思ってよく見ると、Bonanza Felizの開発者はTeam Bonanzaとなっており、「文殊」の開発者が合流していた。東北大の保木氏+電気通信大伊藤研究室。
 元々Bonanzaのライブラリ公開は文殊開発チームの「合議制」のアイデアを保木氏が評価し、大会参加を可能にするために行われたという話らしい。

 アピールポイントには
1.合議法による疎結合並列思考
2.静的評価関数の大規模な機械学習
3.コンピュータチェスの探索および盤データ構造の将棋への応用
の3つを挙げている。

 ここで「疎結合並列思考」というのは秋の対清水市代女流王位・女流王将戦に関する記事でも触れられていたことに気づく。

 昨年の「文殊」の合議制は「Bonanzaの思考ルーティンをベースに評価関数に正規乱数を加えてバラつかせたN個のシステムを作って、単純多数決を行わせ」たもので、微妙に異なるBonanzaがそれぞれ思考をして出した答えで多数決を採って差し手を決めるというものだった。Bonanza FelizはこのN個のシステムをどう作っているのだろうか。いずれにせよ、これを他のソフトとの合議制にすればさらに強くなるのでは、という発想? なんかそんなにうまくいかなそうな気もするが。

「GPS将棋」(Team GPS)
 ディフェンディングチャンピオン。GPSの由来は東京大学大学院総合文化研究科のゲームプログラミングセミナー(Game Programming Seminar = GPS)らしい。

 アピールポイント
1.利きを管理する高速な将棋盤
2.実現確率を用いた探索
3.評価関数の自動学習
4.df-pn (並列協調) を用いた詰探索
5.評価関数は現在、序盤、中盤1、中盤2、終盤の4種類
となっており、全幅探索ではなく各局面での実現確率に基づいた指し手の絞り込みを行う模様。実現確率は「激指」が最初に採用したようだ。過去のプロ棋士の棋譜に登場した局面から指された手を有効として絞り込みを行う。

 評価関数を4種類用意、というのも注目。『Bonanzaはやたらと大駒を捨てる』、ということがかつて話題になったが、これは駒の価値を評価する関数が序盤から終盤まで共通で平均化されるため、終盤の寄せ合いの局面で大駒の価値が低くなったものが反映されている、という話があったはず。

 ただ、現在どの局面かを何らかの形で評価して適切な評価関数を選択する工夫が必要になるはず。ここはさらに評価関数の種類を増やすとか今後色々トライアルが出てきそう。CPUやメモリのリソースに比べHDDにはまだまだ空きがありそうだし。ただ、対局中に評価関数を読み込む時間がどの程度の影響を与えるのかよくわからないが。

「大槻将棋」(大槻知史)
 第19回準優勝で決勝シード。過去にはGPW杯2007で全勝優勝がある。

 主なアピールポイント
○探索
・Principal Variation Search 型のαβ法がペースであり、0.5手延長を採用している。
・前向き枝狩りを利用した選択的探索である。

○評価関数
・評価関数は、駒の位置関係による特徴と、玉の安全度による特徴との和で表現される
・駒の位置関係による特徴は、20万程度の評価項目の線形和からなる。
で、ここまでくるともはや理解しようという意欲がなしくずしになる。苦笑。駒の位置関係について20万の評価項目というのも迫力ありすぎ。

 「大槻将棋」は以前どこかで評価関数の生成にBonanza methodを採用しているという話を目にした。これは「YSS」のアピールにも出てくるのだが、Bonanza methodとは「他の選択肢との比較優位を学習し、評価の計算にminimax探索の結果を用い、報酬の計算に最急降下法を用いる強化学習法(TDLeaf の親子ノード比較を兄弟ノード比較に替えたもの)」だそうだ。学習に過去の棋譜データを使用するところまでを含めてmethodと呼ぶのかは不明。

「激指」(激指チーム)
 東京大学近山研究室の有志数名が1999年に開発を始めた将棋プログラム。第12回、第15回、第18回の過去3回優勝を誇る強豪の1つ。4/8現在、floodgateの14日間レーティングで2634、勝率.747。これは末尾に"1c"とついているのでたぶん1CPUで接続しているのだろう。本番では2CPU8コアらしい。

 アピールポイント
・探索アルゴリズムは、局面の実現確率を打ち切り条件に利用する
・探索の有効分岐数は、約2〜2.5程度におさまる
・短時間でも20手以上先の局面を読む
とあり、有効手を実現確率で絞り込んで読みの深さを追及している模様。有効分岐数の絞り込まれ方がすごい。どんな局面でもだいたい三手以内に見切れるということなのか。

「YSS」(山下宏)
 第7回、第14回、第17回優勝。第9回、第10回、第13回、第16回準優勝の強豪の1つ。選手権の順位別記録のまとめがあり、第2回以降連続出場してすべて決勝リーグ(第6回以降)に勝ち残っている。

 アピールポイント
・選択的探索(手の生成の種類、数を残りの探索深さにより変える)
・局面が終盤ならより少数の手しか生成しない
・探索の延長は反復深化法で前回の最善手を0.5手延長
・終盤でも20手程度の深さの最善応手手順を生成
・評価関数はBonanza Methodを使って1から作り直したものを今年から利用
とあり、初手はほぼ全幅に近い範囲で探索し、深くなるにつれて選択探索になっている模様。Bonanza Methodによる評価関数の仕上がり具合やいかに。囲碁ソフトで効果を上げたというモンテカルロは使われていないのだろうか。

 これ以外にも気になるチームがいくつもあるがきりがない。以下、短め。

・「習甦」(竹内章)
 名前が読めないのがすごい。笑い。「しゅうえそ」「しゅうそ」、らしい。4/8現在、floodgateの14日間レーティングで2660、勝率.755。アピール文がニューラルネットワークとかベイズ推定とかすごそうだし。

「ぼんくらーず」(伊藤英紀)
 第19回大会にFPGAボードを使った「A級リーグ指し手1号」で参加した開発者が今度はクラスタ並列処理に挑戦している。マスタ側で探索木を作ってスレーブに投げると以降の探索をスレーブ側で行ってマスタに返すとか。スレーブはいくつでも増やせてネットワーク経由での通信も可能。遅延がなく予算があればクラウドでスケールアウトできるらしい。

・「芝浦将棋」(芝浦工業大学)
 Bonanzaライブラリ使用。2台のBonanzaを自動対戦させ、片側を強化学習仕様にしてパラメータを変化させ強くするという試みらしい。

・「メカウーサー」(木村健)
 Linux環境上でNVIDIAのCUDA技術によるGPUを使った並列処理の実装に挑戦している模様。が、アピール文書には今年は限りなく無理っぽい雰囲気が漂う。この他にも「歩角GPU将棋」(今石正夫)がCUDAを使う模様。

・「神の一手」(杜貴崇)
 iPhoneアプリらしい……。

Appendix
 それにしても、何でこんな自分にはわかりもしないものが面白いのだろうか。うむ、さもわかったかのように書いているが全然わかってはいないのだ。

 ちなみにぼく自身は小中学生の頃に割と将棋を指していた。全盛時の棋力は将棋会館で5級、街の将棋道場で3級くらいだ。今はもう定跡をほとんど覚えていないレベル。それでもかろうじて、「藤井システム」の盛衰を見てその凄さに驚ける程度(そしてぼくは藤井猛の章がない、というだけで読みもせずに梅田望夫「シリコンバレーから将棋を観る」は怪しい本だと思っている)。ちなみにこのレベルでも、ごく普通の人と将棋を指すとまず負けない。定跡はすっかり忘れていても、手筋は意外と覚えているし、7手詰めくらいまでなら何とか詰め将棋も解けそうだし。

 ところが、あるときBonanzaをふとダウンロードして、持ち時間10分程度でやってみたら、圧倒的に負けた。ほんとに、いいところなく負けた。形すら作れない。これはほんとうに驚いた。

 つまり、ここに書いてあることをはじめて聞いた、というような人は、たぶんみんなBonanzaには勝てないということだ。

 いったいなんでこんなに強くなったんだ、と思ってコンピュータ将棋について検索をして見つけたのが、今年も「GA将!!!!」でエントリーしている森岡祐一氏のブログ「GA将!!!! 作ってます」だった。ちょうど、第19回大会が終わった直後だったと思う。ぼくはこのブログを最初から最新の日付に向かって読んだ。

 あるプロトコルに則ってコミュニケーションするソフトウェアが、ひとつのルールに基づいて戦う。見返りのない、純粋に知的なゲームの記録は、全てを理解できないにもかかわらず、面白かった。この面白さは、ぼくだけが感じるものなのか? 絶対に、そんなはずはない。

 ということで、衰弱堂はコンピュータ将棋の世界への入り口を開いてくれた、GA将!!!!応援してます。森岡さんが1次予選突破できますように。あと丸山スペシャルの「稲庭将棋」に切れ負けしませんように(ひどい応援だな)。

 というわけで、あなたもどれか一つチームを選んで応援してみるとコンピュータ将棋選手権をより楽しめるんじゃないかと思います。

【2010/04/09 追記】
 「詰将棋で遊ぼう! 詰将棋おもちゃ箱」のTETSUさんのブログ「詰将棋メモ」のまとめ記事、

 ・「情報処理学会が日本将棋連盟に『コンピュータ将棋』で挑戦状」
 ・「第20回世界コンピュータ将棋選手権」

からリンクしていただきました。後者は特に選手権関係の情報を網羅しており見逃せません。また前者の記事に社団法人情報処理学会「挑戦状に関するFAQ」へのリンクがあり、
Q: 5月4日の世界コンピュータ将棋選手権の優勝プログラムが対戦するのか
A: 既に準備に入っているので、今年の選手権の結果を元に参加プログラムを変更することはありません。今後の挑戦にあたっては関係する可能性はあります。
との記載がありました。部外者としてあえて余計な一言を添えますが、非常に残念なことだと思います。

 さらにhiroki_fさんの「hiroki_fの日記」「将棋プログラム」より、

 「この記事おもしろいですね。」

という言葉とともにリンクしていただきました。自己紹介を拝見して、かなりびびりました。


タグ:PC game





Comment(1) | TrackBack(0) | essay

この記事へのコメント
難しい世界ですなあ。
Posted by 百鬼堂 at 2010年04月23日 01:22
コメントを書く
お名前: [必須入力]

メールアドレス:

ホームページアドレス:

コメント: [必須入力]

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
※ブログオーナーが承認したコメントのみ表示されます。

この記事へのトラックバック
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。