【DiGRA公開講座】モンテカルロ木探索とは何か？
2008年は囲碁の思考プログラムが急速に進化した年だった。その原動力となっている「モンテカルロ木探索」いわゆる「モンテカルロ法」について、
伊藤毅志・電気通信大学情報工学科助教
美添一樹・科学技術振興機構研究員
山下 宏・囲碁ＡＩ「彩」プログラマ
の３氏を講師に招いて紹介いただいた。その内容を遠藤なりにまとめてみたので、ゲームのＡＩ作りの参考にしてもらいたい。
--------------------------------------------------
◆人口知能とゲームの親和性
チェスは欧米では「知性の象徴」としてのステイタスがある。例えば「２００１年宇宙の旅」に登場するＨＡＬはチェスをするということで、知性を持つと表現をしている。
このチェスの思考プログラム、いわゆるＡＩ(Artificial Intelligence／人工知能)は、ＡＩ研究の黎明期から盛んで、1840年から解析が始まっているが、1960年代後半から短時間で大きく進化を遂げている。
チェスをはじめとする古典ゲームは
・ルールが明らかである
・勝敗が明らかである
・馴染みがある
・プレイヤーが多く、強さを測る尺度がある
などの理由で題材として扱いやすく、
・情報探索
・推論
・知識データベース
・データ探索
・機械学習
・ニューラルネット
など、認知科学上の理解・問題解決・思考・教育のエッセンスも持つ。そのため、色々なゲームでＡＩが考えられている。
特に、１対１で交互に１手ずつ進めていく「ターン制２人対戦」、トランプの手札などのように隠蔽された情報のない「完全情報」、サイコロなどの乱数要素がない「確定」、勝敗など結果の優劣が等価値の「ゼロ和」なゲームは、コンピュータによる解析との相性がよい。また、リバーシ(オセロ)や囲碁のように、ルール上ゲームが進行すれば必ず終了する「有限」なゲームでは必勝法が存在し、完全解析することができれば「先手必勝、引き分け、後手必勝」のいずれかに収束する。
◆囲碁以外のゲームＡＩの歴史
『チェス』
67年に最初のコンピュータチェスが登場し、97年には「Deep Blue」が世界チャンピオンのカスパロフ氏を２勝１敗３分けで破った。
『チェッカー』
50年代に遺伝的アルゴリズムによる解析がなされ、92年に探索型アルゴリズム「Chinook」が42年間で５敗しかしていないチャンピオンのティンズレー氏を破った。07年には完全解が発見され、双方が最適の手を打つと引き分けになることが判明している。
『リバーシ』
75年にチェスの探索手法を用いたプログラムが発表され、90年代には自動的に静的評価関数を学習方法が登場。97年に自動定石学習、パターン学習を搭載した「logistello」が世界チャンピオンの村上氏に６戦全勝した。
『将棋』
79年に２ヶ月掛けてプログラム同士の対戦が行われ、80年代には市販プログラムが次々と発表された。90年より選手権が開かれるようになり、アマチュア有段者レベルの強さが実現、2000年代に入って、実現確率探索の「激指」、全幅検索・評価関数自動学習の「Bonanza」が登場。「棚瀬将棋」「ＡＩ将棋」などアマチュア高段者からプロ棋士レベルへと進化している。
◆囲碁のルール
ここで囲碁の基本的なルールを紹介する。
・盤面に黒白交互に石を置いていく。
・19×19の盤が一般的だが、小路盤と呼ばれる13×13(13路盤)、９×９(９路盤)などのものもある。
・四方を囲めば相手の石を取れる。
黒が▲に打てば、囲まれた白の石は取れる
・四方を囲まれた場所に石を置くことはできない。ただし、そこに置くことによって相手の石を取ることが可能で、それによって置いた石が四方を囲まれた状態ではなくなる場合は構わない。⇒『着手禁止点』と例外
Ａに白石があると黒に取られてしまうため、Ａに打つことはできない。Ｂも同様だが、Ｂに打つことによって下２つの黒石を取ることができ、黒石を取るとＢの白石は囲まれた状態を脱する
・ある石を置くことにより一手前と同じ状態に戻る場合、そこに置いてはいけない。⇒『同型反復禁止』
この形になると、▲の石を黒が取ったり、再び同じ場所に白石を置くことで簡単に同型反復状態となる
・着手禁止点のことを「眼」と言う。眼が２つ以上ある石の繋がり「連」は絶対に取られることがない。これを「生き」ている、と言う。
極端な例、黒石の連を取ることはできない
・囲碁では先手の黒が有利であることが周知であり、それを是正するために黒にハンデを負わせる。これを「コミ」と言い、6.5目あるいは7.5目が一般的。
◆囲碁ＡＩの難しさ
チェスや将棋のＡＩの強さと比較すると、囲碁のＡＩは問題にならないくらいに弱かった。その原因は次の２つ。
・探索空間が大きい
ルールに従って着手できる点(合法手)の数を、終局までの手数だけ掛けると探索空間が概算できる。これをゲーム別に比べると、
チェッカー 10の20～30乗
リバーシ 10の28～60乗
チェス 10の50～120乗
将棋 10の71～220乗
囲碁 10の171～360乗
と囲碁が他を圧倒している。それだけ最適手を求めるのに時間が掛かるため、同じスペックのコンピュータでは相対的に弱いものしかできない。
・評価関数が作りにくい
囲碁は全体を広く見渡す大局観が必要となり、局面ごとの最適手が勝利に必ずしも結び付かない場合がある。そのため、その場の状況だけで判断する静的評価関数を作ることが困難。
つまり、ある局面における良い手が多く存在し、正確に最適手を選ぶことができないのだ。
◆囲碁の評価関数
評価関数を考えるにあたり、囲碁と将棋の違いは次のようになる。
| 囲碁 | 将棋 | |
| 盤面 | 19×19 | 9×9 |
| 駒・石 | 白石・黒石 機能差なし |
８種類の駒 機能差あり |
| 合法手 | 361手から減少 | 平均80手程度 |
| 終了手数 | 200手程度 | 100手程度 |
| 評価関数 | 石の繋がり 地 石の強さ |
駒の損得 駒の効率 王の危険度 |
将棋と比べて囲碁の評価関数を難しくしているのは、
・将棋の駒は種類ごとに機能と優劣に差があるが、囲碁の石にはそれがない。
・リバーシにおける角のように、明らかな特徴を持った場所が少ない。
・支配領域の広さを基準としても、領域が確定するのはゲーム終了時になる。
・局所的な最善手が全体の最善手ではなく、相手に取らせるためにわざと置く「捨石」というテクニックが常套となっている。
などの点で、さらに上級者の間でしか理解できないような評価基準が存在する。
・石の厚い薄い
石の厚みは物理的厚さではなく、ある石の配置が全局的に与える影響のこと。
・形の良し悪し
複数の石の配置の評価。良い形になるように、悪い形にならないように注意することにより、「打ち筋が良くなる」効果がある。ただし「愚形の妙手」も多数存在する。
「代表的な悪い形」
┼┼┼┼┼┼
┼┼●┼┼┼
┼┼●●┼┼ アキ三角
┼┼┼┼┼┼
┼┼●┼┼┼
┼●●●┼┼ 陣笠
┼┼┼┼┼┼
「代表的な良い形」
┼┼┼┼┼┼
┼●●┼┼┼
┼○○●┼┼ 二目の頭
┼┼┼┼┼┼
┼●●●┼┼
┼○○┼┼┼
┼┼┼●○┼ ケイマにツケコシ
┼┼┼┼┼┼
・味の良し悪し
後々の状況変化による可能性を「味」と言う。棋力が高くなるほど、必要のないを打たずに可能性を残すようになる。
・地への甘辛
地の確定具合を表現する言葉が「甘さ」。ある領域を確定させるような手は「辛い」ということになる。
・石の重い軽い
重い石とは逃げたりサバいたりする必要がある石。対処になければならない重要度をさす。
これらの定量的評価は、現状ではたいへん難しい。
また、評価関数は速く正確な必要があるが、今のところ囲碁の評価関数は遅いか不正確、あるいはその両方となっている。
◆囲碁ＡＩの歴史
そんなコンピュータ囲碁の歴史は、60年代に始まる。62年にコンピュータ囲碁関連初の論文となる、「囲碁の好手、悪手に関する研究」が発表され、64年には3x3程度までの小路盤の解析が完了した。
68年に初の囲碁プログラム「Zobrist」が登場、38級程度の強さであった。
70年代に入って、置かれた石の周辺に発生する影響力を関数として扱う手法。石の生死を判定するアルゴリズムなど生まれ、79年にReitmanとWilcoxによって、攻撃と防御の基本的戦略と、連と群の階層パターンを持ったプログラムが作られ、15級程度の強さを見せた。
80年代に入って、囲碁の複雑さに関する研究が進んだ結果、囲碁の難しさが数学的に証明される一方、84年にロンドンで開かれた13路盤のコンピュータ囲碁大会が開かれた。続く86年に台北で19路盤の大会が開始され(2000年まで開催された)、「Many Faces of Go」「Go Intellect」「Goliath」など、ある程度の強さを持ったプログラムが出現した。この時期に商用プログラムの発売も始まっている。
大会が定期開催されるようになったことから、90年代は新たなＡＩ技術や認知科学(機械学習、ニューラルネットワーク、組み合わせゲーム理論など)によって囲碁AIは進化し、95年に５級、97年に３級の認定を受けている。
2000年代に入ると、コンピュータによる７路盤までの解析が完了。01年には初段の認定も受けている。
一方モンテカルロ法は、93年に初めて組み込まれたＡＩが登場しているが、当時はパッとした成績を残してはいない。これがPCの性能が向上した06年、モンテカルロ法を改良したアルゴリズムである「モンテカルロ木探索」を実装した「CrazyStone」が、CO2006(Computer Olympiad 2006)世界大会の9路盤部門で優勝。この方法は続く07年のCO2007の19路盤部門でも猛威を振るい、同年のUEC杯では優勝の「CrazyStone」をはじめ、上位４プログラム中３つがモンテカルロ法(木探索)を用いていた。
08年はコンピュータ囲碁にとって革命の年となった。３月のパリ囲碁トーナメントのエキシビジョンで、「MoGo」というソフトがプロ棋士カタリン五段と対戦。19路盤では９子のハンデをもらったものの敗れたが、ハンデなしの9路盤では３局対戦したうちの１局に勝利するという快挙を挙げた。
これ以降の躍進は驚異的で、８月のUS Go Congressにおいて、９子のハンデをもらったものの、MoGoが韓国のプロ棋士金明完八段に勝利。９月のFIT2008では、８子のハンデで「Crazy Stone」が日本の女流棋士青葉かおり四段を破った。
モンテカルロ木探索実装ソフトは、CO2008でも優勝した「Many Faces of Go」を筆頭に、全13プログラム中上位９位までを独占。それまでのインテリジェントな手法を「強さ」だけで駆逐してしまった。
◆従来方式の囲碁ＡＩ
モンテカルロ法を搭載していない囲碁ＡＩは、基本的に人間が考えていることを模倣している。
まずは「盤面の認識、局面の判断」を行う。石の連結、眼の存在、確定している地などから、着手点を評価。この際、群の強さや石の影響力、安全度なども考慮する。
次に「候補手を生成」する。特徴的な形になった場合の定石や死活、ヨセをパターンから判断して知識データベースと照らし合わせる。また相手の石を取る可能性についても考慮して、状況に見合った深さまでの探索を行い、有利な手を見つけ評価値を出す。
そして「着手を決定」する。候補手の中から、着手の目的別に各々の評価値を比較して、次の１手を打つ。ここでは複数の評価値の依存関係も考慮しなければならない。
探索の方法として一般的なのは、「mini-max探索」と呼ばれているもので、自らの手はできるだけ高い評価に、そこから想定される相手の候補手はできるだけ低い評価になるように探索していく。その結果を理想的な順番に並べ、可能性の低い選択肢を切り捨てる「αβ枝刈り」を行うことで、探索を効率化させることもできる。
◆モンテカルロ法とは
乱数を用いてシミュレートを行う統計的な方法。
囲碁は終盤に近づくに連れて合法手が減少し、合法手の中からランダムに選んで打つだけでも必ず終局となる。このような方法でゲームをお終いまでプレイすることを「プレイアウト」と言う。
囲碁の評価関数は難しいが、プレイアウトした結果だけを見て、どちらが勝ったかを判断することは非常に簡単。そこで、「自分の眼には打たない」「２つ眼を持つ石は取られない」など、合法手の中から囲碁の基本的禁忌を排除してプレイアウトを行い、その結果から勝てそうな手を選ぶモンテカルロ法は実装が容易である。
この方式を用いた局面評価は、たくさんのプレイアウトを行った結果だけを利用するが、目数の差の平均ではなく、単に勝率だけを使う方が強くなる。ちなみに勝率評価方式対目数差評価方式で模擬戦を行うと、８割以上勝率評価が勝つ。これは、囲碁においては大勝することの意味があまりないことによる。
しかし最善手を返す保証がないため、
・相手に正しく応じられると損をする手を打ちやすい
・相手のミスを待つ手を打ちやすい
・正解の手が少ない局面では間違える確率が高い
などの欠点があり、これだけでは従来の囲碁ＡＩに対してもほとんど勝つことができなかった。
◆木探索への改良
このモンテカルロ法でのプレイアウトの方法を改良し、有利な手に多くのプレイアウトを割り当て、プレイアウトの回数が閾値を超えたら、木が成長するように一段深い階層まで検索するアルゴリズム「モンテカルロ木探索」を持った「CrazyStone」の登場は、コンピュータ囲碁界だけでなく、ゲームＡＩ研究に革命を起こしたと言える。
その理論的背景は「Multi-Armed Bandit」という、統計学や機械学習の分野で研究されてきた問題の解決である。Multi-Armed Bandit問題とは、複数のスロットマシンがある状況で、与えられたコインを使ってできるだけ多くの報酬を得るための戦略を考えるようなもの。この最善の戦略は85年に見つけられているが、計算量、メモリ消費ともに大きいため実用にはならない。そのため、計算量が少なくて優秀な戦略が必要となる。
これに単純なモンテカルロ法を当てはめると、「全部に同じ枚数を投入して平均結果を比べる」だが、これでは優秀な戦略とは言い難い。
ここで登場するのが「Upper Confidence Bound(UCB)／信頼上限」という考え方。これは確率的に結果が悪かった場合、試した回数が多いほど本当にダメなので見捨て、逆に少ない場合は運悪くダメだったのかも知れないので見捨てないでプレイアウトを続ける。
具体的な式は下のようになるが、UCB値が高い手からプレイアウトするように選ぶと、浅い読みで良さそうな手を優先的に深く読む「最良優先探索」のようになる。
このUCBを木探索に応用したものを「UCT(UCB applied Trees)」と呼び、UCB値の高い候補により多くのプレイアウトを割り振り、末端でのプレイアウト回数が閾値を超えたら、その手を展開する。これを行うことにより、探索回数が大きくなるに従って、結果が期待値そのものに収束することが証明されている。
このUCTを最初に取り入れた囲碁ＡＩが、平手９路盤で初めてプロ棋士から勝ち星をあげたMoGoになる。
◆木探索自体の効率化
現在の囲碁ＡＩの主流は、この木探索をいかに効率化するか、という部分に知恵が絞られている。
「Progressive Widening」
囲碁の知識を用い、良さそうな手から候補手をソートして探索木を効率化する。この手法を取り入れることにより、より「囲碁っぽい」手を打たせることができる。
人間の棋譜から統計を取って学習し、着手確率の高いところを重点的に探索する。山下氏による実装例では、３×３のパターンを利用して着手点の周りの状況を判断している。これは
・対称性の無視
・盤端の判断
・着手点の周り８マスに直前に石が置かれたか
・白黒用を別に持つ
を考えて、295万のパターンをプロ棋譜１万局から収集し保持している。
高確率のパターンの例
低確率のパターンの例
このパターンを利用して
・全ての手に確率をつける
・取られそうな石を防ぐ手の確率を上げる
・相手の石が取れる手の確率を上げる
・数手で相手の石が取れるパターン(シチョウ)がある場合、確率を上げる
などの工夫をしてプレイアウトを行っている。
「AMAF(All Move As First)」
囲碁のプレイアウトの場合、最終形で打たれている石は、どの順番で打ったとしても結果が同じになると考え、全ての手が１手目に打たれたことにして、擬似的にプレイアウトの回数を稼ぐ方法。乱暴な方法だが、９路盤の場合なら１回のプレイアウトで50手くらいが更新できるため、評価速度は50倍になったと換算できる。
実装する場合には、各手ごとに「通常のUCBの値」と「AMAFでの値」を持ち、探索回数が少ないうちは、AMAFの評価を重視するように、両方をミックスして候補手を選ぶ。
「Rave(Rapid Action Value Estimate)」もAMAFと同じ意味に使われている。
「候補手の絞り込み」
囲碁は合法手の数が多いため、モッテンカルロ法を使ったＡＩでは手をしぼらないと強くできない。そこで
・パターン参照
・盤端からの距離
・直前の相手の手からの距離
・２手前の自分の手との距離
・連の死活探索の結果
などを考慮した上位手からのみ探索を行うことで、強くすることも可能。
「メモリの節約」
探索の基本は、まだ一度も探索したことのない局面で１回プレイアウトを行い、既に１回でもプレイアウトを行った局面では、そこで可能な手を選んでプレイアウトを行う。しかし、この方法だと膨大なメモリが必要となるため効率が悪い。
そこで、ある手に関して一定量のプレイアウトを繰り返し、その後に別の局面に移ってメモリを節約する方法もある(CrazyStoneに実装)。
これらの方法で探索を効率化することにより、速度が数分の１に高速化されているにも関わらず、棋力は大幅に向上しているのが囲碁ＡＩの現状だ。
◆囲碁におけるモンテカルロ法の利点と弱点
モンテカルロ法はなぜ囲碁ＡＩに有効なのか？
最大の理由は、将棋やチェスなどと違い、プレイアウトで普通に終局するゲームであることだ。これはリバーシにも言えることだが、リバーシは評価関数が組みやすく、探索空間も狭いため、モンテカルロ法を利用するまでもなく充分に強いＡＩがある。
また、他のゲームと比較すると、最善手と次善手の価値の差が一般的に小さい。そのため確率論的な解法と馴染みやすい。手順に関係なくある位置を占めておく「布石」などで有利な状況が作れるというのも、乱雑さを逆に活かせることになる。
逆に囲碁に用いる上での弱点も多い。最大の弱点は、隅の死活や攻め合いなど、手順が強制されるケース。勝てる手順が一本だけで、他は全部負けるような場合は正解にたどり着かない。
「シチョウ(逃げても取れる形)」
「ナカデ(2眼を作らせない目的で相手の陣地の中に打ち込む)」
「セキ(お互いに相手の石を取ろうとすると自分の石が取られてしまうので手を出せない状態)」
などのありがちな手を考慮したり、死活の判断をプレイアウトに組み込んだりすることで、この弱点を緩和することはできる。現在は「ありがちではない一本道」の克服が課題になっている。
このような現状での最大の利点は、プレイアウト回数を増やすことにより棋力が顕著に向上すること。これには並列化が効果的で、「コア数が４倍になればハンデが１子減る」と言われ、MoGoが256コアのクラスタを用いていたのに対し、最近の探索方法の進化を考えると、1000コア以上のクラスタを使えば、プロとの対戦も実現できるのではないかと思われる。
ちなみに山下氏の検証例として、将棋プログラム「YSS」と囲碁プログラム「彩」を使い、共に２倍の思考時間を使ったところ、ほぼ同じくらい棋力が上昇した。これを並列化で比較してみると、２コアで約1.4倍、４コアで約2.0倍、８コアだと約2.6倍、囲碁のプログラムが将棋の速度上昇を上回る。
ひょっとすると、このペースで進むなら、将棋ＡＩよりも先に囲碁ＡＩの方が名人に勝ってしまうかも知れない。
モンテカルロ木探索では評価に勝率を使うのだが、勝率を最大にしようとするＡＩと対戦すると、勝つときはおもしろいのだが、負けるときはつまらないという傾向がある。このＡＩは、勝っている場合は確実で無難な手を打つ。対戦している方から見ると、これは「手を抜かれている」「弄ばれている」ように感じられる。負けている場合は、ジリ貧で負けることを避けるように働くので、逆転を狙って無理な手を打ってくる。これを返り討ちにして圧勝するのは、対戦していて楽しい。
負ける時につまらないという問題は、ＡＩの強さを多少犠牲にすることで解決できる。このＡＩは、プレイアウト回数が少ない場合でもそれなりの答を返す。また、回数を減らすと「自然な弱さ」になる、一本道手順を考慮しないと「うっかりミスをしてるように見える」など、エンターテインメント性も高い。もちろん制限時間のある競技などでも、時間切れで着手の解析ができないことがなく、持ち時間に応じた強さを発揮する。
◆他のゲームへのモンテカルロ木探索の応用
将棋のように終局が確定していないゲームは難しいが、終局が確定しているゲームへの応用は充分な成果を既に上げている。
「さめがめ(SameGame)」
問題集を解かせてスコアを競う。モンテカルロ木探索ベースのプログラムが記録を更新。
「ハーツ(Hearts)」
モンテカルロ木探索を用いたプログラムが、既存のプログラム以上の強さを示す研究がある。
「General Game Player Competition」という汎用ゲームプレイヤー大会がある。これは大会の場で架空のゲームルールが提示され、その場でプログラムがルールを分析し、直後に対戦するというもので、１人ゲーム、２人ゲーム、多人数ゲームなどがごちゃまぜになっている。総合点が高い方が勝ちというこの大会で、UCTをベースとした「CADIA Player」が２年連続で優勝している。
このようにモンテカルロ木探索は応用性が高く、麻雀のような不完全情報で不確定なゲームであっても、終局が確定しているので組み込みは可能だと思われる。また、プレイアウトに評価関数と組み合わせるなどの工夫をすれば、必ず終局しないゲームでも効果が見込まれる。もちろん、ゲーム以外の分野であっても、戦略が木構造で表すことができて、プレイアウトが可能なら、モンテカルロ木探索を用いることができるのは言うまでもない。
--------------------------------------------------
遠藤は囲碁のルールを知っている程度なので、今回の講座はものすごく敷居が高かった。完全に理解できていない可能性もあるので、このレポートには間違いがあるかも知れない。
技術の進歩がコンセプト自体を変えてしまうというのは、コンピュータの歴史の中では珍しくない。いわゆる「パラダイムシフト」なわけだが、ＡＩの世界では「いかに人間の考え方を体系化して、その上を目指すか」だったのが、コンピュータのスピードの進化が「数百万人のバカに試しにやらせてみて１人の名人を倒す」を可能にしたのだろう。
伊藤先生の言葉の中に、
「囲碁ＡＩ研究者の中では、モンテカルロ法を取り入れることを『暗黒面に堕ちる』と揶揄する場合もある(笑)」
というのがあったが、遠藤にしてみれば「コンピュータＡＩに必勝法を解析させる」ことが、そもそも暗黒面だと思うので、逆にクローン軍団を手に入れたと思えた。
今までの囲碁ＡＩでは読み切れていなかった部分を、モンテカルロ法という検証システムを使って確率論的に読み切れるようになったと考えると、モンテカルロ法の実装は従来の囲碁ＡＩに座布団を敷いただけだった、というのが後世の評価になるのではないか？
講演終了後に講師の御三方に「いずれ囲碁が解析完了してしまったら？」という話を振ってみた。既に解析され、引き分けが確定しているチェッカーもプレイに対する興味が失われていないくらいだから、ゲームとしての囲碁は解析されたとしても面白さは何も変わらないとのことだった。むしろ、時代によって変動する「コミ(先手有利を是正するハンデ)」を確定できるメリットがある。優秀なＡＩに相手をしてもらえれば、自分の棋力が上がるし、囲碁人口が増えるキッカケにもなると前向きだった。
山下氏の「彩 」はフリーソフトとして公開されているので、皆さんもこれを機会に囲碁を楽しんでみてはいかがだろうか？