連載「人間VSコンピュータ 10番勝負！」
囲碁対決・第2回 「ランダム手法」から伸び悩む囲碁ソフト
第3回電王戦に先だって行われた安倍首相の振り駒イベントは、コンピュータ将棋をさらに盛り上げるものになった。一方の囲碁も、第2回電聖戦を2014年3月21日に開催する。依田紀基9段は、どのような対応をするのか。
「モンテカルロ法」によって飛躍的に棋力が向上したコンピュータ囲碁。ハンデ戦ながらも、本因坊タイトル保持者と互角に渡り合うレベルまで達した。
ただ、「モンテカルロ法」のアルゴリズムは「頭打ち」になっているという。どんなアルゴリズムがコンピュータ囲碁のブレークスルーとなるのだろうか？
モンテカルロ法の効率化
ランダムに手を選び、最終局面まで打ち続けて勝率の高い手を選ぶモンテカルロ法。コンピュータ囲碁のブレークスルーにおいて、切っても切れないものだが、このアルゴリズムだけではコンピュータ側は強くならない。そのままでは「多腕バンディット問題」と呼ばれる課題があるからだ。
例えば、当たりの出る確率がバラバラなスロットマシンが10台あるとする。手持ちのコインは100枚で、一番出る台はどれか分からない。この状態で、手持ちのコインをより増やすにはどうすればよいだろうか？ 全ての台に同じコインを入れても、「より多くの」コインは得られない。また、スロットマシンを試せる回数が限られている中では、たとえ30枚ずつマシンに投入しても、これだけでは当たりの確率が他より大きいかどうかは判断できない。
仮に全ての台で30枚プレイした中で一番出た台を（当たり確率が他の台より低いかもしれないが）継続的に選ぶか。それとも、あまりプレイしていない台でコインを投入する「冒険」をしてみるか…、というジレンマが発生する。これが「多腕バンディット問題」である。
囲碁で言えば、次の1手の数がスロットマシンの台数に当てはまる。コインはコンピュータの計算時間としていいだろう。この「多腕バンディット問題」を解決するのに使われるのがUCB（Upper Confidence Bound）と呼ばれる手法だ。これは、1手毎のシミュレーションに数学式を当てはめて、答えが大きい手を選んでいくもの。これでシミュレーションを効率的に行うのだ。
他にも、AMAF（All Move At First）というアルゴリズムがある。囲碁の場合、手順が逆になっても最善手になることが多い。この性質を利用し、シミュレーションをして出てきた手を「全て1手目に打った」とみなすものだ。1回目のシミュレーションで、黒1でA、黒3（黒の3手目）でB、黒5でCと出た場合、BもCも「全て黒1に来たもの」とみなすのである。こうして組み合わせのカウントを減らし、シミュレーション計算数を軽減して時間の節約をするのである。
 |
|---|
| 2009年コンピュータオリンピックのフランスチーム。 フランスはコンピュータ囲碁の研究が進んでいる |
囲碁ソフト、「足踏み状態」の理由は…
モンテカルロ法の「行き当たりばったり」で発生する取り越し苦労（最終的に勝率の低い手を考えるタイムロス）を、なるべく減らす努力がなされているのである。しかし、モンテカルロ法にも限界がある。どれだけ工夫と改良を重ねたところで、「行き当たりばったり」という手法は変わらないからだ。
実践で終局までの手が決まっている局面が出た場合。詰め碁のような状況でも、モンテカルロ法を利用した囲碁ソフトでは、ランダムに打ち筋を決めて手を進めてしまうのである。「ランダムでやって結果オーライ」（Zen開発者・加藤英樹氏）では、理詰めの局面で正確な対処ができない。
次のブレークスルーは？
コンピュータが囲碁界のトップに勝てるのだろうか。将棋では、はこだて未来大学の松原仁教授が「（スペックが整えば）渡辺明氏でも羽生善治氏でも、5戦やって4連敗することはない」と公言している。
「名人は定石を作る」という格言の通り、コンピュータが自分の打ち筋を振り返り、それこそ「自動学習」していくレベルに達しない限り、厳しいと言われている。「詰みの局面を読むシステムを別に用意して、終盤戦に近づいたら切り替えていく」などの効果的なアルゴリズムが待たれるところだが、実際はどうなのだろうか。
現在のコンピュータ囲碁は、もっぱらモンテカルロ法を知らしめた「Crazy Stone」を開発したレミ・クーロン氏の開発スキルがずば抜けているという。「頼みの綱」の彼に、今後のブレークスルーを期待している状態である。
コンピュータ囲碁が名人レベルの棋士と張り合うには、まだまだ時間がかかりそうだ。
HH News & Reports 関連おすすめ記事
コンピュータ囲碁ソフト「Zen」の開発者が第2回電王戦を振り返った（2013/7/4）「ビッグデータ」解析に使われる“機械学習”（2012/12/6）
人間が自在に機械を動かせる技術「テレイグジスタンス」（2012/3/22）
過去の連載
人間VSコンピュータ 10番勝負！囲碁対決・第1回 逆転の発想、モンテカルロ法（2013/11/28）
将棋対決・第3回 人間を超えたかに見える、将棋ソフトの弱点（2013/10/28）
将棋対決・第2回 しのぎを削る将棋ソフトと、Bonanzaの登場（2013/9/12）
将棋対決・第1回 チェスコンピュータからの応用でもアマ20級（2013/8/8）
チェス対決・第4回 カスパロフとディープ・ブルー、対決の後に（2013/6/27）
チェス対決・第3回 チェスマシン「ディープ・ブルー」誕生前夜（2013/5/30）
以前の連載一覧
コンピュータウイルス事件簿［全12回］（2012/3/15～2013/2/28）
暗号と暗号史［全12回］（2011/3/22～2012/2/16）
【関連カテゴリ】
