2016年03月12日

よく誤解されるモンテカルロ木探索

アルファ碁が世界的碁打ちイ・セドルに3連勝しましたね。ついに言い訳の余地なく人類は負けた。ぼくはこの衝撃をオセロで既に経験してるのですが、それでも衝撃は衝撃です。
だって
「人間が作ったものが人間より頭いい」
のだもの。
子供の頃そのことを酷く不思議に思ったものです。
まとめると
・コンピュータは勝手読みしないから強いぞー
・コンピュータは感情の乱れに左右されないから強いぞー
・なんだかんだ言ってコンピュータは本気出せば強いぞー

今回の囲碁プログラムのアルゴリズムは、それなりに複雑です。でも一言で言い表せば
「ディープラーニング×モンテカルロ木探索」
このエントリではディープラーニングはひとまず置いといてモンテカルロ木探索についてお話したい。
でもその前にミニマックス法の説明をしなくちゃいけないな。

盤面には形勢というものがあって、「今黒勝ってるな」とか「今白勝ってるな」とかは形勢と呼ばれます。
プロの碁とか形勢判断ができれば楽しいのだろうけど
ボードゲームのプログラムというのはその形勢を判断する機能がほぼ確実に備わってます。
なんでかというと、「形勢を自分の方に近づけるため」
囲碁はなぜ難しいかというとその形勢判断が他のボードゲームに比べ極端に複雑なんですね。
一見同じような石の配列でも「厚い」だとか「薄い」だとか、
ボードゲームでは一手打つごとにその形勢が変わっていくんですね。
コンピュータ囲碁においてその形勢判断が強くなるための一つのボトルネックだった。

自分が「局面が一番形勢がよくなる手を打つ」すると相手も同じ事を考えてるから相手は相手で形勢を自分の方に持っていこうとする。
「自分にとって都合の悪い手」を読まないのはいわゆる勝手読みです。
ミニマックス法では「相手が自分にとって都合が悪い手を打ったときに形勢が自分にとって一番よくなる」手を探します。
それだけの話なんですが。

たとえば株式相場をイメージしてみてください。株式相場というのは刻一刻と変化していきます。何の株を買えばリスクが最小か。また利益を最大限出すことが出来るか。
利益ばかり考えていては駄目でリスクのことも考えないといけない。

ミニマックス法で検索すればここら辺の話がたくさん出てきます。

では昨今の囲碁プログラムではこの形勢判断をどのように行っているか。
「CrazyStone」によって囲碁プログラムの形勢判断の仕方に革命が起きました。
それが「プレイアウト」と呼ばれる、「何でもいいから最後まで打ってみる」手法です。
この「何でもいいから」というのがモンテカルロ木探索の名前の由来で、要は何回も(ランダムに)終局まで打って勝つ確立が高いときは優勢、低いときは劣勢としましょうという、形勢判断の手法です。

よく誤解されるのが、この手法によって「昨今の囲碁プログラムは感覚で打ってる」と言われますがそれは誤解です。
プレイアウトが使われるのは形勢判断のときだけで、ベースとなるのはミニマックス法です。
プレイアウトだけしてたのでは単なるモンテカルロ法です。

ここまで説明して「アルファ碁」の何がそんなにすごいか説明できそうな気がしたけどそれはまた次回。
posted by かげろう at 21:33| Comment(0) | その他 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前: [必須入力]

メールアドレス:

ホームページアドレス:

コメント: [必須入力]

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


※画像の中の文字を半角で入力してください。
×

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