モンテカルロ法で囲碁、将棋

2006/02/17 興味がわいて作成

囲碁の場合
１．モンテカルロ法とは？
２．モンテカルロ法を囲碁に適用すると？
３．５路盤での結果
４．９路盤と１９路盤の結果
５．終局までの平均手数と平均目数、最大の手の目数
６．実際の囲碁プログラムでのモンテカルロ法
７．少し強く？したモンテカルロ法
８．実際にモンテカルロ法で対局させてみると？

将棋の場合はこちらを

モンテカルロ法がコンピュータ囲碁ではちょっとしたブームらしいです

2005年9月のコンピュータオリンピックの囲碁の9路盤部門でモンテカルロ法を採用したフランスの囲碁プログラムが
好成績を収めました。（3位と5位、9チーム中）

こんなお手軽でインチキくさい？方法がどこまで効果があるものか自分でも少し調べてみました。



１．モンテカルロ法とは？

モンテカルロ法、で真っ先に思い浮かべるのは、正方形の中に乱数で点を打っていって、
円の範囲内に収まる点の個数から円周率、πを求める手法ではないでしょうか？

1 x 1 の正方形の内部に半径0.5の円を書きます。
この中に乱数で点を打って生きます。
この円の面積は　πr2 = π*0.5*0.5 = π*0.25、正方形の面積は 1 、なので、
無限回繰り返せば、

円の中の点の個数 ： 全部の点の個数　＝　円の面積 ： 正方形の面積　＝　π*0.25 ： 1

になるので、

円の中の個数を4倍 ／ 全部の点の個数 ＝ π
になります。

　　　最初　　　　　　100個　　　　　　1000個　　　　　10000個
モンテカルロ法でπを求める
　　内部の点　　　　　 82個　　　　　　 802個　　　　　 7886個
　　　πの値　　　　　　 3.28　　　　　　　　 3.208　　　　　 　　3.154



２．モンテカルロ法を囲碁に適用すると？

囲碁に適用すると、

1. 全ての着手可能な場所に乱数で石を置く。
2. 1.を白黒交互に繰り返す。打つ場所がなくなってパスが2回続けば終局。
3. 点数を計算する。
4. 1. - 3. を何度も繰り返して点数の平均値を求める。

となります。

ここで注意しないといけないのは本当に完全に乱数で打っていくと、終局しない、という点です。

例えば下の図で、次に白がＢ４に打ってしまうと、黒はＡ５に打って、全部の石が
取られてしまいます。これを繰り返すため、無限に続きます。

  ＡＢＣＤＥ         ＡＢＣＤＥ           ＡＢＣＤＥ 
１○○○●┐       １○○○●┐         １┌┬┬●┐
２○●●┼●       ２○●●┼●         ２├●●┼●
３○○●●┤       ３○○●●┤         ３├┼●●┤ 
４○＋○●●       ４○☆○●●         ４├┼┼●●
５└○○●┘       ５└○○●┘         ５★┴┴●┘ 

　　　　　　　　　　Ｂ４に打つと・・・　　全部取られてしまう！

そのため、「眼」には打たない、というルールを付け加えないといけません。
「眼」の定義は「４方向が全て自分の石か壁で、なおかつ自分の石のダメは２以上」
という風にしています。


もう一つ、ルールは中国ルールを採用しています。
これは終局図の点数計算が楽なためです。
中国ルールは簡単に言うと「盤上に残った自分の石と陣地の合計」を数える方法です。
日本ルールは「アゲハマ（取った石）と自分の陣地の合計」です。
最大の違いは「自分の陣地に石を置いても損にならない」という点でしょうか。
そのため、相手の死石を全部打ち上げても損になりません。
またアゲハマ（取った石）は無視できます。

  ＡＢＣＤＥ         
１○○○●┐　アゲハマを無視すると、日本ルールでは黒地４目、白地２目なので黒２目勝ち。
２○●●┼●
３○○●●┤　中国ルールでは黒地４目＋黒石９個、白地２目＋白石１０個なので黒１目勝ち。
４○＋○●●
５└○○●┘

このため、終局図で残っている石は全部活きた石（死石は全部取られている）と
考えることができます。



３．５路盤での結果

下は５路盤でそれぞれの場所打った後に、100万局、乱数対戦を行った場合の
点数の平均値です。
例えば、5路盤の天元、Ｃ３に打った場合は、黒が平均+7.57目勝てる、という意味です。
逆に、隅のＡ１に打った場合は黒は-3.20目負ける（白が3.20目勝つ）になります。


5路盤の位置の平均点数（100万局の乱数対戦）

　　　Ａ　　 Ｂ　　 Ｃ　　 Ｄ　　 Ｅ
１  -3.20   1.27   1.09   1.26  -3.21 
２   1.26   4.89   6.07   4.97   1.27 
３   1.02   6.14   7.57   6.09   1.05 
４   1.26   4.95   6.09   4.93   1.29 
５  -3.24   1.28   1.03   1.32  -3.24 

なんだか意味ありげな数値が出ているようにも思えます。
実は5路盤は完全に解かれていて、解析された結果があります。

原論文は作者のページからダウンロードできます。
Solving Go on Small Boards.
 E.C.D. van der Werf, H.J. van den Herik, J.W.H.M. Uiterwijk (2003).
 ICGA Journal Vol.26, No. 2, pp.92-107. [ ps.gz ]
http://erikvanderwerf.tengen.nl/5x5/5x5solved.html

完全解析の結果は、天元に黒が打って白全滅の黒25目勝ちです。
地の計算は中国ルールで数えてるので日本ルールなら黒24目勝ちが25目勝ち
になっています。その他の初手は下の通りです。

　黒25目勝ち     　黒3目勝ち       　白1目勝ち  
  ＡＢＣＤＥ       ＡＢＣＤＥ        ＡＢＣＤＥ
１┌┬┬┬┐     １┌┬┬┬┐      １┌┬┬┬┐
２├┼┼┼┤     ２├┼┼┼┤      ２├┼┼┼┤
３├┼●┼┤     ３├┼┼┼┤      ３├┼┼┼┤
４├┼┼┼┤     ４├┼●┼┤      ４├●┼┼┤
５└┴┴┴┘     ５└┴┴┴┘      ５└┴┴┴┘

上3つ以外の初手は白25目勝ちです。

これを碁盤上に書くと、

  -25 -25 -25 -25 -25
  -25  -1  +3  -1 -25
  -25  +3 +25  +3 -25
  -25  -1  +3  -1 -25
  -25 -25 -25 -25 -25

となります。
これをさっきのモンテカルロの結果と並べてみます。

　　　100万回乱数で打った場合の平均　　　　　　　　　　正しい答え

　　　Ａ　　 Ｂ　　 Ｃ　　 Ｄ　　 Ｅ　　　　　　　　Ａ  Ｂ　Ｃ　Ｄ　Ｅ
１  -3.20   1.27   1.09   1.26  -3.21              -25 -25 -25 -25 -25
２   1.26   4.89   6.07   4.97   1.27              -25  -1  +3  -1 -25
３   1.02   6.14   7.57   6.09   1.05              -25  +3 +25  +3 -25
４   1.26   4.95   6.09   4.93   1.29              -25  -1  +3  -1 -25
５  -3.24   1.28   1.03   1.32  -3.24              -25 -25 -25 -25 -25
                                               
どうでしょう？
個人的には5路盤という小さな盤ですら真の値とはかけ離れた結果が出ているように
思えます。特に実際は全滅するはずのＢ１、Ｃ１などの位置がモンテカルロでは+1.27、+1.09
と＋で出ている点です。



４．９路盤と１９路盤の結果

同じように９路盤と１９路盤で実行した結果です。

9路盤の各位置の平均点数（それぞれに100万局の乱数対戦）
　　　Ａ　　 Ｂ　　 Ｃ　　 Ｄ　　 Ｅ　　 Ｆ　　 Ｇ　　 Ｈ　　 Ｊ
１  -2.70   0.36   0.31   0.69   0.77   0.69   0.30   0.31  -2.69
２   0.31   2.22   3.31   3.57   3.61   3.58   3.28   2.24   0.28
３   0.34   3.32   4.06   4.01   4.03   4.10   4.01   3.30   0.30
４   0.69   3.55   4.11   4.05   4.09   4.08   4.08   3.66   0.68
５   0.79   3.62   4.11   4.08   4.01   4.07   4.12   3.65   0.79
６   0.75   3.51   4.12   4.06   4.09   4.07   4.03   3.55   0.73
７   0.30   3.31   4.03   4.10   4.02   4.04   3.93   3.30   0.30
８   0.34   2.21   3.29   3.50   3.63   3.64   3.21   2.16   0.35
９  -2.72   0.33   0.28   0.70   0.76   0.65   0.33   0.37  -2.70

計算時間 10時間46分(Opteron248)


19路盤の各位置の平均点数（それぞれに10万局の乱数対戦）

　　　Ａ　　 Ｂ　　 Ｃ　　 Ｄ　　 Ｅ　　 Ｆ　　 Ｇ　　 Ｈ　　 Ｊ　　 Ｋ　　 Ｌ　　 Ｍ　　 Ｎ　　 Ｏ　　 Ｐ　　 Ｑ　　 Ｒ　　 Ｓ　　 Ｔ
１  -1.93   0.15  -0.33   0.53   0.35   0.10   0.66   0.12   0.14   0.56   0.20   0.23   0.03   0.42   0.59   0.35  -0.11   0.15  -1.98
２  -0.15   1.24   2.18   2.34   2.03   2.04   2.22   2.19   2.34   2.28   2.52   1.83   2.08   1.91   2.04   2.23   1.73   1.27   0.02
３   0.12   1.84   2.74   2.45   2.34   1.96   2.82   2.60   2.47   2.40   2.51   2.46   2.40   2.29   2.52   2.23   2.38   1.94   0.12
４   0.32   2.02   1.82   2.35   2.14   2.38   2.40   2.55   2.25   2.26   2.13   2.01   2.44   2.40   2.55   2.33   2.46   2.37   0.47
５   0.07   1.98   2.19   2.22   2.06   2.16   2.25   2.44   2.47   2.03   2.48   2.42   1.98   2.22   2.27   2.38   2.25   2.03   0.29
６   0.47   1.96   2.43   2.52   2.16   2.35   2.20   2.40   2.38   2.03   2.33   2.51   2.56   2.68   1.97   2.20   2.32   1.82   0.30
７   0.39   2.32   2.66   2.62   2.26   2.45   2.73   2.42   2.16   2.55   2.53   2.50   2.59   2.57   1.91   2.66   2.48   2.44   0.61
８   0.27   1.87   2.46   2.41   2.54   2.40   2.17   2.16   2.36   2.67   2.08   2.54   2.23   3.00   1.74   2.39   2.67   2.46   0.37
９   0.31   2.00   2.37   2.46   2.35   2.41   2.22   2.44   1.96   2.67   2.08   2.23   2.10   2.09   2.12   2.56   2.57   2.07   0.30
10   0.17   2.24   2.49   2.54   2.43   2.75   2.35   2.43   2.32   2.58   2.61   2.26   2.50   2.64   2.24   2.52   2.24   2.50  -0.00
11   0.20   2.51   2.67   2.30   2.47   2.64   2.38   2.47   2.50   2.07   2.42   2.28   2.05   2.43   2.54   2.75   2.69   2.41   0.40
12   0.15   2.03   2.73   2.58   2.74   2.29   2.21   1.84   2.44   2.68   2.40   2.41   2.40   2.39   2.67   2.69   2.39   2.42  -0.01
13   0.04   2.18   2.48   2.40   2.30   2.31   2.58   2.43   2.12   2.64   2.22   2.69   2.75   2.27   2.34   2.46   1.95   2.16   0.36
14   0.59   2.10   2.47   2.35   2.63   2.52   2.33   2.44   2.45   2.42   2.55   2.00   2.33   2.16   2.57   2.66   2.49   2.14   0.21
15   0.38   1.78   2.27   1.98   2.17   2.29   2.22   2.26   2.12   2.27   2.25   2.41   2.33   2.35   2.31   2.56   2.88   1.99   0.13
16   0.40   2.49   2.59   2.57   2.16   2.40   2.53   2.50   2.37   2.38   2.17   2.38   2.43   2.54   2.27   2.19   2.85   2.10   0.16
17   0.27   2.02   2.57   2.53   2.66   2.58   2.33   2.73   2.84   2.23   2.50   2.49   2.56   2.50   2.48   2.67   2.75   2.41  -0.06
18  -0.04   1.45   2.11   2.31   1.90   2.20   2.27   2.25   2.47   2.26   2.20   2.19   2.54   2.00   2.15   2.17   1.91   1.30   0.14
19  -2.31   0.14  -0.22  -0.08   0.03   0.41   0.52   0.14   0.32   0.27   0.30   0.37   0.49   0.57   0.51   0.36  -0.05   0.14  -2.25

計算時間 61時間(Opteron248)


19路は時間がかかるのでかなり回数が少ないです。

９路盤ではほぼ結果は収束しているようなのですが、１９路盤では１０万局の平均では
かなりばらばらな値になっていて安定してるとは言いがたい数値になってます。
１９路盤ではモンテカルロ法はかなり使い物にならない感じです。１９路は参考程度で。



５．終局までの平均手数と平均目数、最大の手の目数






5路盤9路盤19路盤


平均手数41.9手110手443手


平均目数+2.12目+2.26目+1.89目


最大の手の目数（当座の最善手) +7.54目+4.12目+3.00目


回数1000万回100万回10万回







６．実際の囲碁プログラムでのモンテカルロ法

大会で好成績を収めた２つのプログラム(IndigoとGolois)は、完全に乱数で手を選んでいるわけでは
ありません。
まず、アタリになっている石を逃げる手や、石が取れる場合は、その手を打つ確率を上げています。
また、3x3のパターンで好形になる手の打つ確率を上げています。
例えば下図で、中央に打つ手、などです。

？○？
●┼●
？○？

さらに、盤面全部の場所で十分な乱数対局を行う時間がないために、
最初の候補手として19路盤で5手ほど、独自の囲碁知識によって候補手を選び、
その5手に対してだけ、乱数対局をたくさん行っています。

つまり最初の候補手の選び出しで、かなりの囲碁知識が使われているため、
あまり純粋な乱数の結果とは言えなくなってます。



７．少し強く？したモンテカルロ法

実は、上に挙げたデータもアタリを受ける手、石を取る手の確率を若干上げています。
では、何にもしてない純粋な乱数とはどのように変わるのでしょうか？
下はそれぞれ10万回乱数で打たせた場合です。


　アタリを受け、石を取りやすくした場合　　　　　　全ての手を均等に乱数で
　　　Ａ　　 Ｂ　　 Ｃ　　 Ｄ　　 Ｅ　　　　　　　Ａ　　 Ｂ　　 Ｃ　　 Ｄ　　 Ｅ　
１  -3.27   1.29   1.02   1.32  -3.41       １  -2.86   1.26   0.82   1.33  -2.80
２   1.46   4.97   6.16   4.88   1.24       ２   1.26   4.58   5.22   4.49   1.32
３   1.06   6.06   7.56   6.22   0.87       ３   0.92   5.25   6.59   5.21   0.81
４   1.33   4.88   6.26   4.94   1.25       ４   1.30   4.43   5.26   4.35   1.21
５  -3.18   1.28   0.97   1.29  -3.10       ５  -2.86   1.40   0.81   1.16  -2.91

　　　　全体の平均目数 = +2.13　　　　　　　　　　　全体の平均目数 = +1.90

天元（Ｃ３）の点数を比較してみると、アタリを受けやすくした方が +7.56目、均等乱数は+6.59
隅のＡ１の点数はアタリを受ける方が -3.27目、均等は -2.86目。
それぞれ差が小さくなっています。恐らく、好手を打つ手の確率を高くしていくと、点数の差が大きくなって、
最終的には天元は+25、隅は-25に近づいていくのではないかと思います。

個人的な感想は、αβ法の全幅で反復深化させて適当な評価関数で制限時間まで探索させた方が
モンテカルロよりは強くなると思います。
モンテカルロ法の最大の欠点は可能な手が１００手あって、好手は１手だけ、といった状況に
弱い点です。逆に「局面の形勢」と「好手の数」が比例するようなゲームだとなかなか
うまく働くのではないかと思います。



８．実際にモンテカルロ法で対局させてみると？

下は実際に９路盤でモンテカルロ法同士で対局した棋譜です。
それぞれの局面で１手につき1万回の乱数対戦を行って平均点の一番高い手を選んでます。




モンテカルロ囲碁同士の対戦彩（黒）とモンテカルロ囲碁（白）の対戦

  







  
  







  





なかなかそれっぽい棋譜が出来ています。乱数恐るべし。
意外と、モンテカルロ法だけでも１２級ぐらいのプログラムは作れるかもしれません。
計算時間はかかりますけど。（この１局で２時間半かかってます。Opteron248 2.2GHz）

また、モンテカルロ法の特徴がよく出ているのは１５手目にアタリを打っているところです。
この局面では図抜けてこの手が高い点数になってました。これは次に白がポン抜かれるを
防ぐ手が１手だけ、なのでアタリを打てば取れる！と思ってるのですね。

特徴としては、

・アタリが好き。
・死石をダメ１にしたがる（１手で取れるように）。
・ヨセが打てない。

でしょうか。







将棋の場合

えーと、将棋は実験してません。
しかし昔（1999年）試したデータがあるのでそれでお茶を濁してみます。

乱数で駒を動かした20万局のデータ

平均手数　　 　630.8手（2000手以上は引き分け扱い）
最短手数　　　　12手
先手勝率 　　　0.50165 （互角）
勝率の高い初手 30手、ほぼ同じ。

乱数でもちゃんと王を詰ませるのが少し驚きです。

これだけだと面白いデータは出なかったので、61手以上の対局は全部引き分け、
として60手以内で決着が付いた将棋を調べてみると、

500万局を試したうちの5837局（全体の0.12％）が該当。
（先手勝ち=2901, 後手勝ち=2936,引き分け=4994163,全=5000000, 先手勝率=0.497002）

勝率の高い手の順に並べると、

 1:48飛(28):110/179=0.614525  ▲48飛が最善手（サンプルが少ないので怪しいです）
 2:58金(49): 97/169=0.573964
 3:96歩(97):112/197=0.568528
 4:76歩(77):184/331=0.555891  ▲76歩も勝率が高い。それ以上に、速く終わりやすい（局数が多い）
 5:58飛(28):107/193=0.554404
 6:26歩(27): 95/175=0.542857
 7:68銀(79):104/194=0.536082
 8:48金(49):104/195=0.533333
 9:18飛(28): 99/186=0.532258
10:18香(19): 98/185=0.529730
11:78金(69): 99/190=0.521053
12:38銀(39):100/192=0.520833
13:78銀(79): 91/175=0.520000
14:68金(69): 89/173=0.514451
15:86歩(87): 93/183=0.508197
16:36歩(37): 96/190=0.505263
17:66歩(67): 83/167=0.497006
18:38金(49): 95/194=0.489691
19:16歩(17): 87/178=0.488764
20:98香(99): 94/195=0.482051
21:38飛(28): 83/173=0.479769
22:68飛(28): 85/178=0.477528
23:48銀(39): 90/194=0.463918
24:58金(69): 92/205=0.448780
25:46歩(47):100/226=0.442478
26:56歩(57): 92/209=0.440191
27:48王(59): 83/195=0.425641
28:78飛(28): 67/165=0.406061
29:58王(59): 89/224=0.397321
30:68王(59): 83/227=0.365639  王が前進する▲68玉とか▲58玉、▲48玉などは危険地帯に近づく？ため短手数で負けやすい。


サンプル数が少ないので適当な事しか言えないのですが、乱数対戦の場合に、初手に

▲76歩、を指した場合は短手数で終わりやすい。
▲58玉、などと王が前進する手は短手数で負けやすい。

ぐらいは言えそうです。
（元データは1999年の5月ごろにCSAのMLで菊池さんと議論した時のものです）

・・・将棋でも４０手ぐらい乱数で動かして最後の駒得で判定すれば結構まともな
プログラムが動きそうな気もします。

またちょっと面白いのは上は61手以上は引き分け、としていますが、
62手以上を引き分けとすると先手勝率がちょっと上がることです（先手勝率が0.497から0.529に上昇）。
これは先手が1手だけ多く指せるので、先手が詰ませる確率が上がるためと思われます。

1000万局の結果(62手以上を引き分け)
先手勝ち=6599, 後手勝ち=5882,引き分け=9987519,全=10000000, 先手勝率=0.528724

リンクなど


元のページに戻る