コンピュータエンターテインメント協会(CESA)はゲーム開発者向けカンファレンス「CESA ディベロッパーカンファレンス 2003」(CEDEC 2003)を、明治大学リバティタワーにて9月4日・5日の日程で開催した。

会場ではプログラマー、デザイナー、プロデューサーを始めとするゲーム開発に携わる人々に向けた多彩なセッションが2日間に渡って開催されているほか、CRIやクライテリオン、メトロワークスなどが開発者向けのソフトウェアやミドルウェアの展示を行っている。また、協賛セッションとしてMicrosoftの「meltdown」やNVIDIAの「開発の鉄人」なども開催されている。

ここでは、将棋や囲碁、チェスなどの思考ゲームに用いられる人工知能について述べた、公立はこだて未来大学 松原仁教授の講演「思考ゲームのプログラムで用いられている最新の人工知能技術について」をご紹介する。

○攻略法の存在しないゲームは存在するか

はこだて未来大学 松原仁教授

松原氏はまず、ゲームを「人数」(何人でゲームをするのか)、「零和-非零和」(勝ち負けがあるか無いか)、「有限-無限」(終わりがあるのかないのか)、「完全情報-不完全情報」(ゲームを行う上で、相手の情報を全て把握した上で行うのか行わないのか)、「確定-不確定」(偶然性がないのかあるのか)に分類、"必勝法"が存在するかという観点から話をスタートさせた。

数学的な必勝法から言えば、「2人で行う・零和・有限・完全情報・確定」のゲームには必勝法が存在するそうで、5目並べや6マス×6マスのオセロなどでは既に必勝法が解明されているそうだ(ちなみに6マス×6マスのオセロは後手必勝で、完全にミスがなければ後手が15:21で勝ちを収めるそうだ。また、将棋についても先手の方が3%ほど勝率の高いことが分かっているそうだ)。

囲碁や将棋にも必勝法は存在するはずだが、検証しなくてはならない手数は膨大

上記の条件を満たすゲームとしては、チェスや将棋、囲碁も含まれており、これらにも必勝法が存在することになる。しかし、数学的な必勝法を実証する為には指すことのできる手を全て検証することが必要になる。松原氏によるとその数はチェッカーで10の30乗、オセロで10の60乗、チェスで10の120乗、将棋で10の220乗、囲碁に至っては10の360乗という天文学的な数になるという。「(初手から勝負がつくまでを計算するには膨大な計算力が必要になるので)おそらく半永久的にこれらのゲームの必勝法は見付からないのではないか」と松原氏は述べる。

そうした(力ずくな手法によって)必勝法を求めることができないならば、最善の手を計算によって求めようというアプローチが行われており、ミニマックス法、アルファーベータ法、静的評価関数などの方法によって「強いコンピュータ」を作ろうということが行われているが、今のところ絶対的なアプローチは存在せず、試行錯誤の段階だという。

○基礎を作り出したチェス - 将棋・囲碁はどれほどの強さを身につけたか

1950年代に、C.Shannon氏とA.Turing氏がコンピュータチェスの存在しうる可能性を提言し、コンピュータチェスが誕生した。そうして1967年にはMachack(ソフト名)がアマ初段レベルに達したが、ここまでは人間と同じように「局面に応じた判断をおこなう」タイプであった。しかし、その後1970年代には「CHESS」をはじめとした、ルール上指すことのできる手をすべて検討する探索主導型ソフトが登場した。

探索主導型は「その局面で指すことのできる手を全て計算で求める」ため、計算機の能力が高ければ高いほど、強い人工知能となる。1980年代にはチェス専用コンピュータが登場し、1990年にはIBMの開発したDeep Blueが当時の世界チャンピオン、カスパロフ氏と対戦し、1997年には初勝利を飾るまでになった。1997年時のDeep Blueはスーパーコンピュータにチェス専用コンピュータを512台並列で接続したもので、1秒間に2億手、3分間で14手の先読みが可能になっていたという。

そこでコンピュータチェスの開発はいったん下火となったわけであるが、日本人にとってなじみ深い「将棋」「囲碁」についてはどうなのだろうか。松原氏はコンピュータ将棋の難しさとして、「平均分岐数の大きさ」(終盤になればなるほど指せる手が増える)、「勝負の長さ」(チェスに比べ将棋は終了までの手数が1.5倍程多い)、「静的評価関数の難しさ」(小駒の多さ)の3点を挙げた。静的評価関数については、「将棋はチェスに比べ小さな局面が多くなりがちで、実際の駒の取り合いになるまで形勢判断を下すのが難しい」という。

しかしながら、コンピュータ将棋も1983年に初の市販プログラムが登場、その後も様々なソフトが登場し、現在はアマ4～5段のレベルに達しているという。松原氏によれば、2015年から2020年ごろには名人クラスの強さになるのではないかと言うことだ。囲碁については、研究自体は将棋よりも早く行われており、2001年には初段認定されるソフトが現れるなど徐々に強くなってきているが、現在はアマ3～4級レベルで、プロレベルは2030年、タイトル保持者レベルの強さを身につけるのは2040年ごろだろうというのが松原氏の予測だ。

なぜコンピュータ囲碁がなかなか強くならないかという点について、松原氏は「ゲームのアルゴリズムやルールから言うと、将棋とチェスは似ている部分もあるが、囲碁は全く違うので非常に難しい」と述べている。

○人工知能から得られたもの - 人間を楽しませるアルゴリズム

人工知能進歩の背後には演算能力の向上というハードウェア的な進歩があるのは間違いないが、もちろん強い知能を作り出す為に様々なアプローチが考案され、ハードウェアの進歩と共に「強い」コンピュータを作り出すための一助となっている。

終盤データベース

コンピュータチェスが強化される過程に考え出された各種のアプローチの中で、松原氏が代表的なものとして挙げたのが「終盤データベース」と「反復深化」の2つ。「終盤データベース」は、チェスはコマの総数が単純に減っていくゲームなので、「盤上に残るコマ数がある程度少なくなれば指せる手全てを検索することによって最善手(必勝法)を見つけることができる、このデータベースを作成しよう」というアプローチ方法。現在、残り5コマの状態からの最善手までは判明しており、このデータベースの作成については後退解析の手法が用いられているという。

反復深化は、n手先まで解析する際、まず1手先までを読み、評価関数を用いて点数をつけ、点数が高い順にソートする。そしてソートした順番に2手先までを読んでまた評価関数による評価を行い…という手順を繰り返すというもので、最終的な最善手を探し出すには回りくどい手法のように見えるが、松原氏によれば「アルファーベータ法の効率が非常に良くなり、読みを途中で打ち切ってもその時点での最善手がわかるなどのメリットも大きい」という。この反復深化はコンピュータチェスを開発していく中で生まれ、現在はさまざまな分野で応用されているという。

☆

「人間よりも強い」を目指して開発されてきた人工知能だが、チェスでは世界チャンピオンを破り、詰め将棋については1521手詰めなどという大がかりなものも数時間で解けるようになるなど、ある面では人を凌駕している面も見せ始めてきた。

しかし、人と上手にゲームができる人工知能というと実現はまだまだ先のようだ。松原氏によると「人間の指した手を分析し、敗因を指摘・指導するということまではある程度できているが、敵(人間)の評価関数や研究手法を学習し、対戦相手の実力に合わせた"いい勝負"を展開するというところまでは未だ至っていない」という。

「強いコンピュータ」の実現ももちろん楽しみではあるが、対戦相手として「楽しい」コンピュータの実現も非常に待ち遠しい。あたかも友人と対戦しているような感覚になれるコンピュータの登場を楽しみにしたいものだ。

(渡邊宏)

CEDEC 2003
http://cedec.cesa.or.jp/

コンピュ－タエンタ－テインメント協会(CESA)
http://www.cesa.or.jp/

はこだて未来大学
http://www.fun.ac.jp/