Eyes, JAPAN Blog > コンピュータで問題を解くということ

コンピュータで問題を解くということ

tayama

この記事は1年以上前に書かれたもので、内容が古い可能性がありますのでご注意ください。

あからマスコットキャラクター

昨年の10月に行われた将棋のプロ棋士とコンピュータとの対局は、皆様の記憶にも新しいかと思います。この対局は、激指・YSS・Bonanza・GPS将棋という4つのプログラムと計676個のCPUからなるシステム「あから2010」が叩き付けた挑戦状を、清水女流王将が迎え撃つ形で行われました。結果はあからの勝利に終わりましたが、これは私のような情報系の人にとってはよいニュースであった半面、将棋愛好家たちの間では悔しいニュースになったようです。

余談ですが、インパクトの強い左図のあからのマスコットキャラクター。あからが勝利するたびに、歩 -> 香車 -> 桂馬 … とレベルアップしていくとかいかないとか。[要出展]

さて、この対局の感想を記したブログ記事などを見ていくと、次のような論旨の主張が見受けられます。「1つしか脳のない人間に対して676個もCPUを使うとは、数の暴力ではないか。単純な計算の速さによってではなく、巧みな戦略によって勝利するようなプログラムであってほしい。」
さて、そんなプログラムはどのようにしたら作れるのでしょうか?

私が思うに、数の暴力云々はさておき、巧みな戦略によって名人に勝利するようなプログラムを書くことは不可能です。なぜならば、そんな素晴らしい戦略が存在するのなら、そもそも人間がそれを使ってしまえばいいからです。それで勝負は五分五分です。
プログラム (program) というものは、「こうなったらこうしなさい」「ああなったらああしなさい」という命令を、始めに (pro) 書いておいた (gram) ものです。したがって、プログラム、コンピュータの賢さは、それを書いた人間の賢さを超えることはありません。むしろ、大きく下回ることがほとんどです。コンピュータのすごいところはただ一つ、プログラムを圧倒的な速さで実行できることだけなのです。

このように言ってしまうと、コンピュータに作業させるというのは、単純で、泥臭く、面白みのないことだ、と思われるかもしれません。しかし、それは大きな誤解です。
将棋の思考ルーチンは、主に次のようにして作られます。

  • 盤面の評価関数を定義する
    その盤面が自分にとってどれぐらい好ましいか、を数値化できるようにします。例えば、自分が歩を1個持ってたら+1点、桂馬なら+3点、飛車なら+20点、などとするものが考えられます。
  • 自分と相手の可能な手を全てシミュレートし、数手先の評価値を最も高く出来るような手を選択する

ここで問題になるのが「可能な手を全てシミュレートし」という部分です。というのも、将棋において登場しうる盤面の数は、なんと 10224 近くにもなるのです。これに対して676CPUというのは、雀の涙と呼ぶには程遠いほど小さな数です。律儀に一つ一つシミュレートしていては、例え持ち時間が8時間あったとしても、最初の1手を打ち終わる前に使い切ってしまいます。

将棋に限らず多くの問題をコンピュータで解くにあたって、この爆発的に大きな数との戦いが要求されます。大きな数とはいえ、その大部分は実は無視できるのではないか?より簡単な部分問題に適切に分割したとき、それぞれの部分問題は簡単に解けてしまうのではないか?こういったアプローチを模索することがコンピュータで問題を解くことの難しさであり、また醍醐味でもあります。

将棋の例であれば、例えば飛車を捨てて相手の桂馬を取るような手は、断言は出来ないけれどもうまくいく見込みはほとんどないでしょう。こういった見込みのない手をさっさと諦める、というアプローチが考えられます。これを一般化したものが、α-β法として知られています。

一から十まで全てをスマートにこなす必要はありません。簡単なところだけ上手くやって、難しいところはコンピュータの計算の速さに頼ればいいじゃないですか。そんな考え方を許してくれるところが、私がコンピュータを好きな理由だったりします。

田山

Comments are closed.