だいたい47度

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

PageTop

囲碁のアルゴリズム [レビュー]コンピュータ囲碁 モンテカルロ法の理論と実践

ボードゲームにおいてコンピュータの強さは年々上がっている。チェスでは1997年にDeep Blueが世界チャンピオンを破っているし、将棋においてもほぼプロ同等の強さにまでなっている。

その中で、囲碁に関してはコンピュータの成長が遅かった。2005年まではアマ初段以下と言われていた。理由としては、囲碁というゲームの性質がコンピュータで扱うのに向いていなかったことが大きい。詳しくは後述する。

しかし2006年、モンテカルロ木探索というアルゴリズムが発明されたことで囲碁プログラムの強さは一変する。このブレークスルーは、成長が止まっていた囲碁プログラムを一気にアマ5段程度の強さまで引き上げた。

ここでは、コンピュータがボードゲームをするときの考え方から始めて、囲碁が難しい理由、モンテカルロ木探索の取っ掛かりまで書こうと思う。というのもコンピュータ囲碁 ―モンテカルロ法の理論と実践―というコンピュータ囲碁の本として面白い本を見つけたからで、この本へのリードとしてこのブログを書きたいと思う。本については最後に触れる。

コンピュータにとってのボードゲーム
ボードゲームをするとき、人は、言語化されない感覚を大いに使う。人は「概ねこの辺に打つ」ということがわかっているので、幾つかの候補手を考え、相手が対応するだろう手を幾つか考え、それに対して……といった形で考える。最初から経験・感覚で候補手を絞っているのだ。もっと言うと、この手は数手先にやばそうという事さえ、感覚でわかってしまう。

一方で、コンピュータは計算をフルに使う。コンピュータには感覚というものがない。すべては数で表される。「だいたいこのへんに打つ」という感覚ではなく「A地点には確率◯%で打つ」というデジタルな形式で処理される。そのため、手を考える場合も、どうしてその手になるのかを明示的に示せなくてはならない。その代わり、コンピュータの計算処理能は人間とは比べ物にならない速度である。よって、膨大な計算を行うことで「感覚」をデジタルに作り出すことがコンピュータの考え方になる。

例えば、数独の解法を比較すると面白い(ボードゲームではないが)。数独を解くとき、人であれば数値がある程度集まっている怪しそうな領域を調べてみて、数値を一つ一つ書き込んでいくという解法になる。一方のコンピュータの解法はすごい。開いているマス全てにランダムに数字をいれていき、膨大な盤面を生成、たまたまどれかで整合性が取れたらその盤面を正解とする。一々候補を考える手間を取らずに、計算力だけで押し切ってしまうのだ(もちろんもっと効率的にうめていく方法もある)。

コンピュータにとって、全ての手を計算しきれるかどうかで戦略が大きく変わる。コンピュータの計算速度は非常に速いとはいえ、有限である以上、全てのパターンを現実的な時間では試せないこともある。つまりゲームによっては、全部の手を検証できる場合と、全部の手を検証することが時間的に許されない場合があるのだ。3x3の◯×ゲームのような人間でも全パターン読めるような問題は前者にあたるが、多くのボードゲームは後者にあたる。前者であれば全件計算した後で最善手を打てばいい(というか計算し終えた時点で勝敗も決してしまう)のに対し、後者は何かしらの方法で計算を打ち切り、かつその途中までの計算が有用である必要がある。

全ての手を検証できない場合、限られた計算でどれだけ有用な結果を返せるかは、アルゴリズムにかかっている。アルゴリズムとは何を計算するかを規定したものだ。状況に応じて限られたリソースを最大限にいかせるようなルールをアルゴリズムが実現しているかどうかによって、コンピュータの強さは大きく変わってくる。

多くのボードゲームは計算しきれないだけの局面が存在するため、アルゴリズム如何で強さが大きく左右されることになる。よって、ボードゲームに強いコンピュータを作るということは、よりよいアルゴリズムを探索していくことに近い。

囲碁の難しさ
数あるボードゲームの中でも囲碁はコンピュータに向いていない。

まず局面の数が多い。囲碁は19x19であらゆるところに着手できる。8x8かつ相手をひっくり返す部分にしか着することができないオセロとは比べ物にならないくらい局面がありうるだろう。後述する本によれば、オセロは局面数10^28、将棋でも10^69であるのに対し、囲碁は10^170である。

更に途中で勝敗を規定するのが難しい。勝敗が決する最後になるまで、黒白どっちが勝っているかをコンピュータでは判断しにくいのだ。例えば将棋であれば、駒の優劣などがあるので、それらを指標にどちらが優勢かを計算できる。しかし、囲碁では多くの陣地が完全に決定するのが最終盤である上、一時的に損することが将来的な得につながることも多い。よって完全に計算し切らない限り、優勢劣勢の判断をコンピュータが間違えやすい。

つまり、ゲームが最後まで行かないと優劣を決めるのがコンピュータには難しいにも関わらず、ゲームの局面を計算し切るには局面の数が多すぎるというのが囲碁の難しさにつながっている。

モンテカルロ木探索概略
アルゴリズムの一つにモンテカルロ法というものがある。完全な答えを導き出すリソースが膨大になってしまう場合に、乱数を用いて正解に近い値を求める方法だ。よくある例が、円周率を求めるもの。四角の中に内接するような円を描き、四角の中にランダムに点を打ち、円の中に含まれた点の数を数えることで、円周率の近似値を求める。

囲碁においてモンテカルロ法を使うとすると、ある手Aを打ったあとに、ランダムに盤面を埋めていって勝敗を求めることで、Aの勝率を出していくことになる。現在着手可能な手すべてに関して、ランダム盤面埋め処理を複数回ずつ行うことで、各手の勝率を出し、次の手を決めることになる。

このランダムに盤面を埋めていく処理をプレイアウトという。プレイアウトはランダムに埋めていくものではあるが、そのランダムな選択がより人に近いほど(人が選ぶべき手が選択される可能性を高くしてランダム処理するほど)、プレイアウトによって得られる勝率の正確性は上がり、結果的にプログラムが強くなる。よってプレイアウトは囲碁プログラムにおいて大事な位置を占める。

しかし、ただプレイアウトを繰り返していっても、囲碁のプログラムは強くならない。なぜなら、プレイアウトはランダムな手だけで成立するため、相手がミスすると得する手を打ちやすくなるからだ。相手が万一ミスすると大きく儲かるが、きちんと応じると自分が損したりする手があったとすると、期待値的にコンピュータはこの手を打ちたくなってしまう。

つまり、良さげな手があったとしても、その先を読まなくてはいけないのだ。相手が次にどう対応するか、また更に自分がどう対応するか。先を読んで一手目を打つ確率を補正し無くてはならない。

これを実現したのがモンテカルロ木探索である。モンテカルロ木探索は、最初は上述のモンテカルロ法と同様にプレイアウトを繰り返すが、ある程度有望な手が見つかると、その手に関しては打ったものとして相手の手番のプレイアウトを行い始める。普通の手は1段階目のプレイアウトを行いつつ、有望な手に関してはより深くまで調べていくのだ。この探索がnodeをたどっていく木探索の形式をしているので、モンテカルロ木探索と呼ばれる。

本の紹介
ここまでの話に加えて、モンテカルロ木探索を詳しく説明してくれるのが、コンピュータ囲碁 ―モンテカルロ法の理論と実践―である。あまり詳しくない僕でもスラスラと理解できる良著だ。

この本は理論編と実践編で別れており、それぞれ著者も異なる。理論編でコンピュータ囲碁の理論を頭に入れた後、実装をしながらもう一度理論を辿っていけるので、理解がしやすい。

著者はもちろん両者とも第一線の方々であるが、特に実践編の山下さんはコンピュータ将棋の世界大会で優勝していたり、コンピュータ囲碁の大会で3位になっていたりする方だ。実践編ではその実装の詳細をパラメータの数値まで絡めて記述してあって圧巻である。ここまで必要なのかというレベルで書いてある。

理論編を読んでいると、いとも簡単にコンピュータ囲碁が作れる気がしてくる。実際に僕は作ってみようと思った。その後、実践編を読んでいると、ちゃんと強いプログラムにするためには夥しい数の状況に対応を考え、実装して行かないといけないことを痛感して挫折できる。理論と実装の違いを改めて味わえて、そういう意味でも面白い本だった。

囲碁はなかなか難しそうだけど、同じような考え方を使って、何かボードゲームのAIを作ってみようかと思った。もちろん理論以外に機械学習などの知識も必要になってくるので、ハードルは高そうだけど(この本でも機械学習について一定のページは割いてくれているが主題ではない)。

最後に付記しておくが、この本を読む場合は、囲碁のコウやセキという単語はわかるレベルでないとキツい。理論編はついてこれるかもしれないが、実践編は囲碁の知識があることが前提で書かれている。とはいえ、定石を知っている必要などはないので、ちょっと勉強すればすぐ読める本ではあると思う。

コンピュータ囲碁 ―モンテカルロ法の理論と実践―コンピュータ囲碁 ―モンテカルロ法の理論と実践―
(2012/11/10)
美添 一樹、山下 宏 他

商品詳細を見る
関連記事
スポンサーサイト

PageTop

コメント


管理者にだけ表示を許可する
 

No title

とても魅力的な記事でした。
また遊びに来ます!!

履歴書の書き方の見本 | URL | 2013-08-26(Mon)06:25 [編集]


上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。