コンピュータ囲碁とモンテカルロ法

スポンサードリンク

コンピュータ囲碁とモンテカルロ

囲碁でモンテカルロ法を使うというのはどういうことか説明します。

 

次のような九路番があったとします。

九路

 

次の黒番の可能手というのは
9×9=81手から既に置かれている4手を差し引いた
【77種類の手】が存在します。

 

本当のモンテカルロ法というのは
全77手に対して計算するのですが・・・

 

参考までに3つに限定してお話を進めます。

 

次は黒番です。
あなたならどこに着手しますか?

 

候補手を3種類考えてみました。

 

候補A 候補B 候補C

 

さて、あなたならこの3つの手の中で
どれが優れていると思いますか?

 

左から順位A、B、Cの候補手としましょう。

 

A:右辺を強化する手
B:右下を強化しつつ、左下への攻めを狙う手
C:直接、割打つ手

 

モンテカルロ法はここで乱数を使います。

 

Aに黒石を置いてから
あとは終局するまで乱数で白黒交互に石を置いていきます。
(B、Cも同様です。)

 

それぞれの手に対して終局するまで100回ずつ試したとしましょう。

 

Aの手・・・黒が70/100回勝った(勝率70%)
Bの手・・・黒が60/100回勝った(勝率60%)
Cの手・・・黒が50/100回勝った(勝率50%)

 

Aに黒をおいてから適当に最後まで打ってみたら
Aが一番勝率が高いみたいだぞ!?

 

だったらAが良い手だろう!

 

このようにして着手を決定する方法がモンテカルロ法です。

最後まで打つと地がないじゃないか?

囲碁には実はルールが複数あります。
日本人に最も馴染み深いのは日本ルールの囲碁なのです。

 

コンピュータ囲碁では
中国ルールというものを使用します。

 

日本ルール

ポイント=地+相手から取ったアゲハマ

 

中国ルール

ポイント=地+生きている石の数

 

この違いが分かりますか?

 

次のような陣地があったとします。

囲碁陣地

 

この時のルールの違いを見てみましょう。

 

日本ルール

黒番=地:10目+アゲハマ:0目
白番=地:5目+アゲハマ:0目

 

差し引き 黒番が5目勝ち

 

中国ルール

黒番=地:10目+生きている黒石:5目
白番=地:5目+生きている白石:5目

 

差し引き:黒番が5目勝ち

 

結果が同じになりました。

 

違いがあるとすれば・・・

 

中国ルールの場合、
地が確定してから相手の陣地や自分の陣地に石をおいても結果が変わりません。

 

次は黒番ですが、白の陣地に石を打った場合、
日本ルールだと手抜きをされてアゲハマとして取られますが・・・
中国ルールの場合、地と生きている石の数を数えるだけです。

 

実質、終了している局面において相手の陣地や自分の陣地に手を加えても
結果が変わらないというのが特徴です。

 

コンピュータが計算を行う上で
中国ルールで計算したほうが非常に簡単なのです。

 

しかしながら
これだけでは全然弱いです!

 

更に色んなアルゴリズムを使っています。
その方法を歴史とともに一部紹介します。

 

【続き】コンピュータ囲碁が強くなった理由

スポンサードリンク

コンピュータ囲碁とモンテカルロ法関連ページ

モンテカルロ法
天頂の囲碁、銀星囲碁、最強の囲碁の3つの囲碁ソフトが使っているモンテカルロ法について解説します。
強くなった理由
モンテカルロ法を使用して、コンピュータ囲碁が強くなった真の理由を歴史と共にお話します。
多腕バンディットとUCB
スロットマシンの報酬を最大にするアルゴリズムとして知られる多腕バンディット問題とUCBアルゴリズムの関係を紹介。
UCT探索
コンピュータ囲碁におけるUCT探索について簡単に紹介します。
学習によるシミュレーション改良
コンピュータ囲碁(モンテカルロ法)の改良として学習によるシミュレーションの改良などが行われています。ELOレーティング・Bradley-Terryモデル・パターン学習など。
並列化
コンピュータ囲碁の並列化に関する簡単なお話です。
定石データベース・詰碁探索
コンピュータ囲碁に使われている定石データベースや詰碁探索についてお話します。

logo logo logo