Google が作った囲碁プログラム (AlphaGO) が、ヨーロッパチャンピオンと対戦して勝利したそうだ。
昨年秋に対戦したらしいのだけど、ニュースになったのは昨日。
囲碁はチェスや将棋に比べてずっと難しいので、このニュースにはちょっと驚いた。
でも、なんで囲碁が難しいのか、という話に触れている記事を見かけない。
（僕が探せていないだけかもしれないけど）
ちょっと解説してみよう。
まず、僕は囲碁についてそれほど知識を持っていない。
ルール詳細すら知らず、「陣形を作るゲーム」であることは知っている、という程度。
以前に将棋について少し書いたのだけど、将棋も囲碁も、シミュレーションゲームだ。
将棋は、局所戦…小さな戦いを表現している。駒が人で、人と人が殺しあう。
＃日本の将棋は、殺さずに捕虜にして、仲間にすることができる。
それに対して、囲碁は国家レベルの戦略をシミュレートしている。
局所的な戦いは関係ない。そもそも、国家レベルの戦いでは、実際の戦闘がおこらない「にらみ合い」が多い。
お互いににらみ合い、前線を形成しつつ、相手の補給路を断つ。
補給路を断たれた相手は降伏するなり野垂れ死ぬなどして、いずれその領地は自分のものとなる。
こうして、前線で相手を囲い込みながら領土を広げるゲームが「囲碁」だ。
ここで、ゲーム性が大きく違うことに気づいただろうか。
将棋もチェスも、駒を動かして、相手を取る。
つまりは、「点」から「点」への動きだ。
ある地点の駒を別の地点に動かせば、相手の駒をとれる。
もしくは、自分の駒を動かさないと、相手にとられる。
盤面がいくら広くても、駒の数は有限だ。
その駒すべてについて、動かせる手を全部試すことは、実はそれほど難しいことではない。
…チェスならね。
いや、本当はチェスだって全部なんて試せないのだけど、それは後で書く方法でカバーできる。
ともかく、チェスの動きはそれほど多くはない。
特に、終盤に向かって駒が減っていくので、先読みが簡単になっていく。
チェスを指す機械が作れるだろう、という考えは、コンピューター以前からあったくらいだ。
将棋は、取った駒をいつでも盤上に投入できる。
これにより、盤上の駒が少なくなる終盤は、駒を「動かす」のではなく、どこでも好きな位置における、という可能性が高まる。
これによって、終盤に向かって複雑さがどんどん増していく。先読みが難しくなっていく。
チェスより将棋のほうが難しい、というのはこのためだ。
囲碁は、石を「好きなところに置く」ことの連続で、動かさない。
また、相手の上に乗る、というようなこともない。
相手の動きを阻止するために「すぐ横に置く」ことは多いのだけど、これも絶対ではない。
状況によっては、全く異なるところに置くことがある。
つまり、自分も相手も、石を置く場所の手がかりがない。
手がかりがないからどこに置いていいのかわからないし、相手がどこに置くのか読みづらい。
これが、囲碁の難しさの一因になっている。
google もルールから説明するのは面倒だからか、単純に「盤面の広さ」から、取り得る局面の数を示して「囲碁は非常に大きい」と言っている。
チェスは 8x8で、将棋は 9x9 、囲碁は 19x19 だから、囲碁は圧倒的に「取り得る局面」は多い。
でも、局面の多さが難しさを示すのだとしたら、同じく碁盤で行う五目並べも、囲碁と同程度に難しいということになってしまう。
盤面の大きさが難しさにつながる部分は確かにあるのだけど、それほど重要ではない。
本当に囲碁が難しいのはここからだ。
先に書いたように、将棋は「点から点」の動きだった。
でも、囲碁は「線で囲む」ゲームだ。より正確に言うと、線を「形作っていく」ゲームだ。
人間なら、星と星をつないで星座を作ることができる。
「点」をつないで線を「形作り」、そこに絵や物語を見出すのだ。
でも、コンピューターはそんなことできない。点はいつまでたっても点であり、線になることはない。
点を伸ばしてやがて前線を作り、相手を囲い込む…というゲームは、コンピューターにはどこに手を打つべきかもわからない。
もちろん、石と石の間が１マス開いていたら、そこに石を置いたらつながるな、程度の判断ならできる。
でも、５マスも離れていたら、そこを埋められるかもしれない、なんて思わない。
同じような局面が多数あった時に、どちらのほうがつながりそうだ、とか判断できない。
「判断できない」というのは、非常に致命的な問題をもたらす。
話は戻るだけど、チェスや将棋は、駒が有限だから動かすことは簡単、と書いた。
でも、もっと重要なのは、「意味が分かりやすい」ことだ。
駒が相手の駒に乗れば、取ることができる。乗られれば取られる。
できれば取られないのが一番いい。でも、歩を犠牲にすることで王を守れるのであれば、王を優先して守ったほうがいい。
こうした「手の評価」が簡単にできる。
手の評価ができるからこそ、駒の動きをいくつも試してみて、「一番いい手」を選び出すことができる。
将棋の場合、数手先まで読んだりする。
でも、「１手」でも、動かせる駒は非常に多い。そのまま２手、３手と先読みすると、そのたびに駒の数だけ動かせる可能性が増えて、調べきれなくなる。
この場合も、「手の評価」を使うことで、大幅に可能性を減らすことができる。
王手がかかっているのに、無視して別の駒を動かす必要はない。自分の王がとられるのは最悪の結果なのだから、とにかくそれを防ぐ手を考える。
それ以外の手を採用する必要はないので、先読みすべき手を大幅に減らすことができる。
王手は極端な例なのだけど、自分がわざわざ悪い手を打つ必要はないのだ。
同様に、相手も悪い手を打つ必要はない。これで、先読みの「可能性」を大きく減らすことができる。
最終的に一番いい手を選ぶにも、先読みをするのにも、とにかく「手の評価」が大切なのだ。
ところが囲碁は、基本である「どうやれば線がつながるか」がわからない。
繋がりそうな箇所がいくつかあったとして、どれを優先すべきかわからない。
つまり、もしコンピューターが超高速で、すべての手を総当たりで試せたとしても、その結果から「一番いい手」を選び出せない。
ここが囲碁の難しさの本質だ。
何がいい手なのか。
これ、実はコンピューターだけでなく、人間にもわからない。
もちろん慣れた人にはわかるのだけど、初心者にはとっかかりがなさ過ぎて入門しづらい。
囲碁人口が少ない理由の一つだ。
同時に、わかっている人にとっては、単純ではない、非常に奥深いゲームとなる。
余談なのだけど、米国のゲーム会社…ビデオゲーム業界を生み出した「ATARI」社の社名は、囲碁の用語「あたり」からきている。
子会社に SENTE 、TENGEN という会社もあった。これも囲碁用語の「先手」「天元」からきている。
ATARI 社の創始者が、囲碁を「世界で一番面白いゲーム」だと考えていたことに由来する。
唐突だけど、大学の時のコンピューターサークルの先輩が、卒業研究に「コンピューター囲碁」を考えていた。
90年代の頭かな。
今調べたら、このときには後で書く GNU GO がもうできていたようなのだけど、今と違ってネットは普通ではなかったので知らなかった。
で、コンピューターにルールを教えることすらできない。
「コンピューターに囲碁を教えるのは何が難しいか」という、失敗談をまとめるのが精いっぱいだった。
学生が１年間で研究するには、ちょっと荷が重かったテーマなのだ。
で、GNU GO なのだけど、これ以前にも囲碁ソフトがなかったわけではない。
でも、GNU GO は、GNU だからソースを公開していた。他の人が研究して、さらに強いものを作る土台となった。
GNU GO は、少なくとも「全く無意味ではない」手を打てる程度には囲碁のルールを学べていた。
手を考えるときは、碁盤を配列として用意し、数値を入れられるようにしておく。
石が置いてある「周囲」のマスに、+1 する。すべての石について行う。
これが第１段階。
すでに数値が入っているところを、すべて +1 する。
そして、数値が入っているマスを石と同じように見なして、また「周囲」を +1 する。
これが第２段階。
以降、同じ操作を繰り返し、数値を大きくしていく。
石の周りに「濃度」を持つ勢力範囲が染み出していく…そんな雰囲気を感じ取ってもらうといい。
何段階行うかは任意。というか、その時によって最適な回数は異なるので、状況を見ながら調整。
５段階までやったとしたら、最後にすべてのマスの数値から、５を引く。
マイナスになるところは 0 だと考えて無視。
石の周囲に増やした数字は、0 に戻るはず。
でも、「周囲を +1」した時に重なっていた部分は、重複してカウントされているので 0 に戻らない。
ここはつまり、周囲の石の間を埋めて、前線を作るのに役立ちそうな場所、ということになる。
これで、少なくとも「石を打つとよさそうな場所」がわかる。
複数ある場合にどう評価するか、状況によって全く新しいところに打たないといけないときにどうするか、などは別問題。
ともかく、GNU GO がこの手法を広めて、しばらくはこれ以外の良い方法がなかったらしい。
90年代の中ごろ、画期的なアルゴリズムが考案される。
どこに打てばいいのかわからないなら、乱数で打てばいいじゃん、という割り切り。
もちろん、本当に乱数だけで勝負していたら、とんでもなく弱い。
ここに「学習機械」を組み合わせる。
ランダムに打った手のデータを覚えておいて、とにかく、むちゃくちゃなうち筋でもいいのでゲームを終了させる。
（ランダム同士で打ち合えばいい）
ゲームが終われば勝敗がわかる。きっと、負けたほうの「ランダム」は弱い手だ。データは覚えているから、同じような局面になった時には避けよう。
逆に、勝ったほうの手は、同じような局面ではまだ使おう。
これをひたすら繰り返すと、強そうな手と弱そうな手がわかってくる。
あるとき勝った手が、同じ局面で別の時に打ったら負けたとする。
この手は強いと思っていたけどそうじゃなかった、ということだ。
逆に、何回も打ってすべて勝った手があったら、これは本当に重要な手なのだ。
今後も同じ局面では打つのがいい。
ここにあるのは、ひたすら過去のデータを積み上げるだけで、打った手の評価は「しない」という方針だ。
囲碁の手の評価は、先に書いたように難しい。だったら、評価しないでもいい。
でも、最後に勝ったかどうかだけは覚えておいて、途中の手すべてに「勝ち負け」のフラグを積み重ねていく。
…これ、マッチ箱エンジンだよね。
ただのマッチ箱でも、マルバツゲームの思考ルーチン程度は作れてしまう、というアルゴリズムの実験。
もちろん最初は弱かった。
でも、2006 年に、この手法をさらに応用して学習部分を強くしたプログラムが作られる。
ひたすら戦って「勝った」「負けた」を記録するだけではなくて、勝った打ち筋なら、途中から手を変えたらどうなるか、などを試すようにしたのだ。
これによって、勝てそうな局面で、さらに強い手を探すことができるようになった。
このプログラムは、コンピューター囲碁大会で優勝した。
以降、この手法が主流になっていく。
実は、こういう「ランダムを使ってひたすら学習する」のは、囲碁の世界に限った話ではない。
最初のほうに書いたけど、チェスや将棋では、一手ごとに「その手が良いか悪いか」を評価している。
この評価部分は、昔は人間が作っていた。そして、評価方法の善し悪しが強さに直結した。
評価方法の善し悪しというのは、つまりパラメーター調整のことだ。
昔は職人芸でプログラマがやっていたのだけど、最近の流行は「ランダムに設定したパラメーターでひたすら戦わせ、勝ったものだけを残す」というような手法だ。
これにより、コンピューターが自分で最適なパラメーターを学習するようになった。
評価方法の調整は職人芸の時代から、コンピューターオートメーションの時代に入ったのだ。
そして、囲碁でもそれが適用された、に過ぎない。
元々評価手法自体が作りづらかったので、思い切って評価をしないことにした。
評価は、試合結果によってのみ決まる。
そして、ひたすら試合を繰り返して、結果から学習する。
機械が勝手に学習したものなので、機械が「良い手」だと思っているものが、なんでいい手なのかは誰にも説明がつかない。
でも、実際強くなったのだからいい手なのだろう。
今回プロに勝ったという Google の囲碁プログラムも、こうして作られたものだ。
何で勝ったのか、どういう仕組みで考えているのかは誰にもわからない。
わかるのは、強くなったという事実だけだ。
今回の Google のプログラムでは、学習部分にニューラルネットワークを使っているそうだ。
ニューラルネットワークは、十分な学習を積んだ場合に、まだ見ぬ問題であっても「正解に近いと思われる回答」を得られる特徴がある。
以降は、詳細が明かされていないので想像に過ぎない話。
単純に「過去に打った手」を参照するのではなく、盤上の局所的な形勢などを見て、それらしい正解を出せるように学習させてあるのではないだろうか。
囲碁は「線を形作る」と最初のほうに書いたのだけど、これはパターン認識の世界だ。
そして、パターン認識ではニューラルネットワークは非常に役立つことがわかっている。
近年流行のパターン認識では、局所的なパターンの特徴を、「局所」のサイズを様々に変えながら抽出し、それらをパラメータとして組み合わせたうえでニューラルネットワークの入力とする。
この方法だと、局所的な特徴も捉えられているし、ニューラルネットによって全体のバランスも考慮される。
囲碁の広い盤面を全部「記憶」するのではなく、局所的なパターンを元に判断を下すこともできるだろう。
そして、実はこのパターン認識方法は、人間の「目」の働きを模倣したものだ。
目は局所パターンを識別し、局所的な形状を「特徴」として不可逆圧縮し、その組み合わせとしてデータを脳に送っている。
この「特徴抽出」によって、人間は線を線と感じたり、丸いものを丸いと感じたりすることがわかっている。
点に過ぎない星を見て、それがつながった「星座」を思い浮かべるのもこれに近い働きだ。
なので、「前線を作る」ゲームである囲碁が、パターン認識の世界に踏みこんだというのも、ある意味当然なのかもしれない。
話はここまでの部分で終わっていて、以降は余談。
途中で書いた「マッチ箱エンジン」だけど、マッチ箱エンジンで囲碁の19路盤を学習させたらどうなるか…という解説記事があった。
英語だけど、図表が多数入っているのでわかりやすく、面白い。
ざっと解説すると、多数のマッチ箱に９色のビーズを入れておくと、マルバツゲームの相手をすることができる。
箱は、現在の「盤面」の状況を示している。対応する箱から、ビーズを１個取り出すと、その色が「どこに打つか」を示している。
最初は、すべての色のビーズを入れてある。
当然、打てない場所の色も出てしまう。マッチ箱は、最初はマルバツのルールも知らないのだ。
それは捨ててやり直す。つまり、人間がルールを教える。
正しい手を打った場合も、マッチ箱はランダムに打つことになるので、おそらく負けるだろう。
マッチ箱が負けたら、最後の手順で打ったビーズは捨てる。その手を打ってはいけなかったのだ。
もしもマッチ箱が勝ったら、途中で使ったビーズをすべて１個増やしてやる。勝ったご褒美だ。次からはこの手を打ちやすくなる。
マッチ箱はだんだんと良い手を打つようになってくるし、究極的には絶対負けない、最強プレイヤーとなる。
…というのがマッチ箱エンジンなのだけど、解説記事は途中までこの解説をしつつ、最後に19路盤への応用の話になる。
打てる可能性が非常に多いので、マッチ箱が大量に必要になる。
最後の画像は、必要なマッチ箱を置くための面積を、わかりやすいものと比較した図だ。
なるほど、ゲームの規模がわかりやすい。
というか、先に書いた通り Google の囲碁プログラムは基本的にマッチ箱エンジンだ。
（多少工夫して、知らない手でも打てるようにはなっているけど）
マッチ箱じゃなくてコンピューターを使っているけど、この図にあるようなものを実現してしまったということですよ！
最近の囲碁のアルゴリズム詳細について、詳しい資料がありました。
今回、いくらかはこの資料を参考に書かせていただいています。
2016.3.20追記
３月中旬、AlphaGO は世界最高峰の棋士である韓国人、イ・セドル九段と対局し、４対１で勝ちました。
と同時に、上記記事を書いたときにはあまり報じられていなかった詳細が報じられました。
やはり、推察したとおり盤面を画像として認識しているそうです。
チェスや将棋では駒の位置関係など、データを中心に扱いますが、画像として「なんとなく」状況把握している。
今までの AI などにはなかった新しい手法です。
と同時に、駒の位置関係だけが重要で、駒の価値や動きに意味がないからこそできる手法だとも思います。
AlphaGO を開発したディープマインド社は、汎用性のある AI を目指して研究しているそうです。
実際、AlphaGO と同じ仕組みをインベーダーゲームやブロック崩しなどの単純なゲームに応用し、スーパープレイヤーを作り出すことに成功しています。
とはいえ、パックマンのルールは複雑すぎて理解できません。
ニューラルネットワークは、なんにでも応用できる汎用性がある一方で、単純な問題にしか対応できません。
囲碁もまた、十分に奥深いゲームではあるが、ルール自体は非常に単純。
だからニューラルネットワークが活きてきます。
DeepMind 社の創始者の詳細記事が、昨年末発売の Wired に掲載されていたようです。
AlphaGO がイ・セドル九段との対局初日に、WEB ページでも公開されたようです。
今日知って読んだところ、非常に面白かったのでこの追記を行った次第です。
同じテーマの日記(最近の一覧)
関連ページ
【訃報】ジョン・ホートン・コンウェイ氏【日記 20/04/15】
ケン・トンプソンの誕生日(1943)【日記 16/02/04】
シーモア・パパート 誕生日(1928)【日記 16/03/01】
別年同日の日記
申し訳ありませんが、現在意見投稿をできない状態にしています。 |