モンテカルロ・ゲーム探索

モンテカルロ・ゲーム探索はモンテカルロ法が分かれば楽勝ですにゃ。

一番原始的な実装は

現在の局面から…

1.各候補手から_ランダム_にゲームを進め勝ち負けの回数を記録。これを何回も繰り返します。 ⇐ やっぱりコンピュータ向き。並列処理できればなおヨロシ。
2.(1)終了後、勝率が一番高い手を選びます。

「お互いにランダムにゲームを進めるので有利な指し手程勝ちやすいであろう」…の仮定が根幹にあります。

…と信じ難い程単純ですね。

ですがこの場合、選択肢が多過ぎるゲーム(囲碁・将棋)では非効率過ぎます。

なので…(1)試す候補手を賢く選ぶ、(2)『_ランダム_にゲームを進める』部分…を改良して効率を上げます。

~~~~~~~~~~~~~~

コメントをスレに引き上げました。

http://www.tokinclub.com/dp/node/3990#comment-47550

投稿者: webMaster 投稿日時: 木, 03/22/2018 - 01:17 categories [ ]

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。

混沌の創造主は嘘が大好き

> 願うならば 出来るだけあり得そうな手 を集中的に頑張るのが賢いやり方でしょう。

…結果として 駄目 でした。評価関数が大きくなる盤面は大抵 駒を取る なので取るべきではない局面でもドンドン取り込んでいくので突撃自爆王になってしまいました。

(例)▲7七歩から3三の歩を角で取り込んではダメでしょう

ここは構造的な変更が必要ですな。 ⇒ モンテカルロ・ゲーム「樹」探索に続きます。

混沌の創造主よ、我により精度の高い混沌を与えたもう

プレイアウトの部分は原則ランダムに指すのが仕様ですが、あり得ない手順は探索の質の向上に貢献しない…でしょうね。

下手な鉄砲も数撃ちゃ当たる…かもしれませんが、弾・時間は有限です。明日の天気予報に3日掛かってはイケマセン。

願うならば 出来るだけあり得そうな手 を集中的に頑張るのが賢いやり方でしょう。

劣勢でも最良の手を指す P4

> 「劣勢でも最良の手を指す」 これってとても難しそうです。 

将棋・チェス・囲碁は 悪手を最後に指した方が負け なので形勢に関係なく最善手を指すべきでしょう。

> 以前に教えてもらった「水平線効果(?)」。 PCはこれをやってしまいそうです。

まあ、ハッキリ敗勢(詰みが見えている)の場合は 何やっても無駄 なのでこの場合はそうなりますね。

> 2日(水)と3日(木祝)に応援できると思います。

おいでませ、川崎へ。(笑)

> 一日に120~150通のmailが来て探すのがたいへんです・・・

前の職場ではそ~でした。休暇から戻ってくると1,000通以上溜まることになります。
そんな時は 無視 が一番効率の良い対処法でした。 ⇒ 重要な案件ならあちらからまたメールなり連絡がくるだろう…と、他力本願。
(上司からのメールは別ですよ)

劣勢でも最良の手を指す P3

だんだん付いて行けなくなっています・・・ どうもすみません。

「劣勢でも最良の手を指す」 これってとても難しそうです。 以前に教えてもらった「水平線効果(?)」。 PCはこれをやってしまいそうです。

羽生は、不利に陥ってもギリギリのところで付いて行って、緩手を見逃さず一気に逆転する、と表現されていました。

不利な時にどんな手を選ぶのか? これは重要だと思います。

オズ魔 ! 笑いました。 星一徹が中日ドラゴンズで指導して、確か「消える魔球」を打った、んでしたか。

それと。 mailありがとうございました。 返信していませんが届いています。 2日(水)と3日(木祝)に応援できると思います。 一日に120~150通のmailが来て探すのがたいへんです・・・

劣勢でも最良の手を指す P2

>当然のようにも見えまするが、最良な手だが必敗に近い手と、相手が間違いやすい手とは違うことが有りませぬか。

対人間ならともかく、完全情報ゼロサムゲームでは最良手以外は墓穴を掘ることに加担すると同義ですね。

> 羽生が読み切ってない手を指すと、相手は疑心暗鬼を生じて不必要に読み過ぎてへとへとに疲れ

同一局面、同一手でも、名人が指せば 名人に定跡無し ですし、アマが指せば 筋が悪い です。

で、勝敗の代わりに末端での評価値(静的探索無し)を返して単純平均を評価値とするなら…

{[P1:FU (7,7)-(7,6) ..], original eval: 169, visit count: 5904, average eval: 172}
{[P1:GI (3,9)-(4,8) ..], original eval: 80, visit count: 5841, average eval: 119}
{[P1:OH (5,9)-(6,8) ..], original eval: 34, visit count: 5843, average eval: 97}
{[P1:FU (5,7)-(5,6) ..], original eval: 86, visit count: 5669, average eval: 81}
{[P1:FU (3,7)-(3,6) ..], original eval: -107, visit count: 5698, average eval: 71}
{[P1:FU (6,7)-(6,6) ..], original eval: -32, visit count: 5634, average eval: 71}
{[P1:KI (6,9)-(7,8) ..], original eval: 23, visit count: 5649, average eval: 65}
{[P1:FU (2,7)-(2,6) ..], original eval: 129, visit count: 5511, average eval: 53}
{[P1:GI (7,9)-(6,8) ..], original eval: 6, visit count: 5582, average eval: 47}
{[P1:FU (4,7)-(4,6) ..], original eval: -99, visit count: 5477, average eval: 47}
{[P1:GI (3,9)-(3,8) ..], original eval: -88, visit count: 5429, average eval: 35}
{[P1:GI (7,9)-(7,8) ..], original eval: -14, visit count: 5295, average eval: 34}
{[P1:HI (2,8)-(5,8) ..], original eval: -185, visit count: 5255, average eval: 26}
{[P1:KI (4,9)-(5,8) ..], original eval: -106, visit count: 5241, average eval: 20}
{[P1:HI (2,8)-(6,8) ..], original eval: -179, visit count: 5051, average eval: -1}
{[P1:FU (1,7)-(1,6) ..], original eval: 33, visit count: 4811, average eval: -4}
{[P1:FU (9,7)-(9,6) ..], original eval: 63, visit count: 5024, average eval: -4}
{[P1:KI (6,9)-(5,8) ..], original eval: -205, visit count: 4907, average eval: -5}
{[P1:HI (2,8)-(4,8) ..], original eval: -209, visit count: 4865, average eval: -8}
{[P1:HI (2,8)-(7,8) ..], original eval: -167, visit count: 4633, average eval: -22}
{[P1:HI (2,8)-(1,8) ..], original eval: -376, visit count: 4637, average eval: -23}
{[P1:HI (2,8)-(3,8) ..], original eval: -253, visit count: 4528, average eval: -26}
{[P1:OH (5,9)-(4,8) ..], original eval: -289, visit count: 4680, average eval: -39}
{[P1:KI (4,9)-(3,8) ..], original eval: -265, visit count: 4348, average eval: -40}
{[P1:FU (8,7)-(8,6) ..], original eval: -179, visit count: 4317, average eval: -43}
{[P1:KI (6,9)-(6,8) ..], original eval: -232, visit count: 4216, average eval: -43}
{[P1:KI (4,9)-(4,8) ..], original eval: -275, visit count: 4182, average eval: -53}
{[P1:OH (5,9)-(5,8) ..], original eval: -875, visit count: 3963, average eval: -126}
{[P1:KY (1,9)-(1,8) ..], original eval: -380, visit count: 3917, average eval: -233}
{[P1:KY (9,9)-(9,8) ..], original eval: -377, visit count: 3923, average eval: -253}

…と、何気によさげな結果…なのかな?

劣勢でも最良の手を指す

当然のようにも見えまするが、最良な手だが必敗に近い手と、相手が間違いやすい手とは違うことが有りませぬか。

再び、

寅○様(新選組関係建物)>往時の羽生の基礎棋力+天性の勝負術的ケレン味

羽生が読み切ってない手を指すと、相手は疑心暗鬼を生じて不必要に読み過ぎてへとへとに疲れ、一局の内にそれが繰り返されると、脳に対するボディブローのようにじわじわ効いて、どこかで致命的に誤るとか。

(これは、コントラクトブリッジのような不完全情報ゲームでは、必須の技術なれども、将棋でも「手の内を明かさない」ことの一部として「どこまで分かっているかは悟らせない」ことは、見方によっては同じではないだろうかなー。少なくとも序盤研究はその筈。)

コンピュータ同士だと、間違うことの意味や可能性が、人間の場合とは異質になりうるやも知れぬが、ディープブルーがカスパロフを破ったとき(愚が知る限り真相はダイアナ妃の死同様未だ不明。計算マタはプログラムのミスが幸いしたという説もある。)のように、それぞれの機械マタは人間が時間内に読める範囲内での、評価関数の値の逆転なら、原理的には違う機械なら起こりうるから。

やっぱり評価値は偉大だ。勲章あげたいくらい

ふと考えました。

勝率で手の優劣を決めるのはいいけど…不利な状況の場合、程度の差はあれど全候補手の勝率は ゼロ になるから不味いのでは???

…おっと、これはイケナイですね。劣勢でも最良の手を指すのが大切ですね。

最高の高速化はやらなくてもよいことをやらないこと

先ず誰でも思いつくのは…終局までプレイアウトする必要ないんじゃね?優勢を確認出来れば十分なのでは?…ですね。
おまけに途中で精度を落とさず打ち切ることが出来るならその分速くなるのは自明であ~る。

…で、そこで引き出すのは 評価関数 です。??手進めた後、評価値で暫定勝利者を決めて打ち切ります。(*)

(*)評価値そのものを集計して判断するのも当然ありです。

{[P1:FU (7,7)-(7,6) ..], eval=169, trials=4501.0, p1Win=4303.0, p2Win=198.0, p1WinRate=95.601}
{[P1:GI (7,9)-(6,8) ..], eval=6, trials=4142.0, p1Win=2302.5, p2Win=1839.5, p1WinRate=55.589}
{[P1:GI (3,9)-(4,8) ..], eval=80, trials=4272.0, p1Win=2357.5, p2Win=1914.5, p1WinRate=55.185}
{[P1:FU (3,7)-(3,6) ..], eval=-107, trials=4259.0, p1Win=2349.5, p2Win=1909.5, p1WinRate=55.166}
{[P1:KI (6,9)-(7,8) ..], eval=23, trials=3964.0, p1Win=2117.5, p2Win=1846.5, p1WinRate=53.418}
{[P1:FU (4,7)-(4,6) ..], eval=-99, trials=3688.0, p1Win=1969.5, p2Win=1718.5, p1WinRate=53.403}
{[P1:FU (6,7)-(6,6) ..], eval=-32, trials=3918.0, p1Win=2091.5, p2Win=1826.5, p1WinRate=53.382}
{[P1:HI (2,8)-(6,8) ..], eval=-179, trials=3465.0, p1Win=1823.0, p2Win=1642.0, p1WinRate=52.612}
{[P1:GI (3,9)-(3,8) ..], eval=-88, trials=3864.0, p1Win=2030.0, p2Win=1834.0, p1WinRate=52.536}
{[P1:FU (2,7)-(2,6) ..], eval=129, trials=3860.0, p1Win=2024.0, p2Win=1836.0, p1WinRate=52.435}
{[P1:GI (7,9)-(7,8) ..], eval=-14, trials=3505.0, p1Win=1825.5, p2Win=1679.5, p1WinRate=52.083}
{[P1:OH (5,9)-(4,8) ..], eval=-289, trials=3708.0, p1Win=1931.0, p2Win=1777.0, p1WinRate=52.077}
{[P1:HI (2,8)-(5,8) ..], eval=-185, trials=3558.0, p1Win=1834.5, p2Win=1723.5, p1WinRate=51.56}
{[P1:KI (6,9)-(5,8) ..], eval=-205, trials=3647.0, p1Win=1880.0, p2Win=1767.0, p1WinRate=51.549}
{[P1:KI (4,9)-(5,8) ..], eval=-106, trials=2945.0, p1Win=1516.5, p2Win=1428.5, p1WinRate=51.494}
{[P1:KI (6,9)-(6,8) ..], eval=-232, trials=3873.0, p1Win=1987.0, p2Win=1886.0, p1WinRate=51.304}
{[P1:FU (5,7)-(5,6) ..], eval=86, trials=3632.0, p1Win=1860.0, p2Win=1772.0, p1WinRate=51.211}
{[P1:FU (9,7)-(9,6) ..], eval=63, trials=3305.0, p1Win=1679.0, p2Win=1626.0, p1WinRate=50.802}
{[P1:HI (2,8)-(1,8) ..], eval=-376, trials=3384.0, p1Win=1695.0, p2Win=1689.0, p1WinRate=50.089}
{[P1:OH (5,9)-(6,8) ..], eval=34, trials=3265.0, p1Win=1634.0, p2Win=1631.0, p1WinRate=50.046}
{[P1:HI (2,8)-(7,8) ..], eval=-167, trials=3387.0, p1Win=1689.5, p2Win=1697.5, p1WinRate=49.882}
{[P1:HI (2,8)-(3,8) ..], eval=-253, trials=3086.0, p1Win=1533.5, p2Win=1552.5, p1WinRate=49.692}
{[P1:KI (4,9)-(3,8) ..], eval=-265, trials=3334.0, p1Win=1656.5, p2Win=1677.5, p1WinRate=49.685}
{[P1:FU (1,7)-(1,6) ..], eval=33, trials=2580.0, p1Win=1267.5, p2Win=1312.5, p1WinRate=49.128}
{[P1:HI (2,8)-(4,8) ..], eval=-209, trials=2445.0, p1Win=1196.0, p2Win=1249.0, p1WinRate=48.916}
{[P1:KI (4,9)-(4,8) ..], eval=-275, trials=2511.0, p1Win=1222.0, p2Win=1289.0, p1WinRate=48.666}
{[P1:OH (5,9)-(5,8) ..], eval=-875, trials=2364.0, p1Win=1134.0, p2Win=1230.0, p1WinRate=47.97}
{[P1:FU (8,7)-(8,6) ..], eval=-179, trials=2086.0, p1Win=992.5, p2Win=1093.5, p1WinRate=47.579}
{[P1:KY (1,9)-(1,8) ..], eval=-380, trials=1816.0, p1Win=772.0, p2Win=1044.0, p1WinRate=42.511}
{[P1:KY (9,9)-(9,8) ..], eval=-377, trials=1636.0, p1Win=669.5, p2Win=966.5, p1WinRate=40.923}

程よく初手の中で多分最悪の手が三つ最下位に落ちてくれました。

~~~~~~~~~~~~~~~~~

アルファ・ゼロの中身については全然調べていませんが、NN(ニューラルネットワーク)使用から想像するにNNを実現確率推定に使っている…と想像します。

これでモンテ探索時に 起こりそうもない 手筋は最初から試さないですむ ⇒ 精度・速度UP…になると。
我はボナンザ先生の評価にお任せします。

楽々並列探索

この手の探索アルゴリズムは 並列探索 が楽ちんですにゃ。

マルチスレッドで走らせるとスレッド数の分だけ素直に労せずして加速します。

落ちている勝利を拾わない程お人好しではない

前回は 純・ランダム でゲーム終了(もしくは200手で引き分け)でした。

でも、これは将棋では 超不自然 です。一手詰みがあるならその手をと~ぜん指すべきです。

囲碁の場合、ランダムでも石を置いていけば自然に終了しますが、将棋は駒が勝手にチョロチョロ動き回って (ほぼ)無限ループ が可能なので 終了時に終了させる のはと~ぜんですにゃ。

変更後の実験で1,000回程グリグリしたら、あ~ら不思議。

{[P1:FU (7,7)-(7,6) ..], win=9527.0, loss=473.0, rate=0.9527}
{[P1:FU (9,7)-(9,6) ..], win=5413.0, loss=4587.0, rate=0.5413}
{[P1:GI (7,9)-(6,8) ..], win=5318.0, loss=4682.0, rate=0.5318}
{[P1:KI (6,9)-(6,8) ..], win=5289.0, loss=4711.0, rate=0.5289}
{[P1:FU (3,7)-(3,6) ..], win=5203.0, loss=4797.0, rate=0.5203}
{[P1:HI (2,8)-(6,8) ..], win=5125.0, loss=4875.0, rate=0.5125}
{[P1:OH (5,9)-(4,8) ..], win=5113.0, loss=4887.0, rate=0.5113}
{[P1:KI (4,9)-(5,8) ..], win=5098.0, loss=4902.0, rate=0.5098}
{[P1:KI (6,9)-(5,8) ..], win=5077.0, loss=4923.0, rate=0.5077}
{[P1:KI (4,9)-(3,8) ..], win=5066.0, loss=4934.0, rate=0.5066}
{[P1:KI (6,9)-(7,8) ..], win=5053.0, loss=4947.0, rate=0.5053}
{[P1:KI (4,9)-(4,8) ..], win=5016.0, loss=4984.0, rate=0.5016}
{[P1:FU (4,7)-(4,6) ..], win=5004.0, loss=4996.0, rate=0.5004}
{[P1:HI (2,8)-(7,8) ..], win=4998.0, loss=5002.0, rate=0.4998}
{[P1:KY (1,9)-(1,8) ..], win=4999.0, loss=5001.0, rate=0.4999}
{[P1:OH (5,9)-(5,8) ..], win=4963.0, loss=5037.0, rate=0.4963}
{[P1:GI (3,9)-(3,8) ..], win=4949.0, loss=5051.0, rate=0.4949}
{[P1:GI (3,9)-(4,8) ..], win=4943.0, loss=5057.0, rate=0.4943}
{[P1:FU (1,7)-(1,6) ..], win=4941.0, loss=5059.0, rate=0.4941}
{[P1:HI (2,8)-(4,8) ..], win=4941.0, loss=5059.0, rate=0.4941}
{[P1:HI (2,8)-(5,8) ..], win=4933.0, loss=5067.0, rate=0.4933}
{[P1:HI (2,8)-(1,8) ..], win=4882.0, loss=5118.0, rate=0.4882}
{[P1:FU (2,7)-(2,6) ..], win=4867.0, loss=5133.0, rate=0.4867}
{[P1:HI (2,8)-(3,8) ..], win=4868.0, loss=5132.0, rate=0.4868}
{[P1:GI (7,9)-(7,8) ..], win=4863.0, loss=5137.0, rate=0.4863}
{[P1:FU (8,7)-(8,6) ..], win=4846.0, loss=5154.0, rate=0.4846}
{[P1:KY (9,9)-(9,8) ..], win=4779.0, loss=5221.0, rate=0.4779}
{[P1:FU (5,7)-(5,6) ..], win=4691.0, loss=5309.0, rate=0.4691}
{[P1:FU (6,7)-(6,6) ..], win=4676.0, loss=5324.0, rate=0.4676}
{[P1:OH (5,9)-(6,8) ..], win=4341.0, loss=5659.0, rate=0.4341}

▲7七歩がダントツ一位ですね。

理由は簡単です。角道を先にあけたので 先に駒を獲れる 状態にあるのが_埋められない差_になったのでしょう。

海は広し、そして深し

純真な心の持ち主である我は早速、原始的実装を試してみました。

将棋の初手は30あります… 全部10,000回ランダムに「対局」させてみました。
200手指し手決着がつかない場合、引き分け扱いします。

結果は…

{[P1:FU (6,7)-(6,6) ..], win=5014.5, loss=4985.5, rate=0.50145}
{[P1:HI (2,8)-(5,8) ..], win=5013.0, loss=4987.0, rate=0.5013}
{[P1:FU (4,7)-(4,6) ..], win=5013.0, loss=4987.0, rate=0.5013}
{[P1:KI (4,9)-(3,8) ..], win=5010.0, loss=4990.0, rate=0.501}
{[P1:HI (2,8)-(7,8) ..], win=5003.0, loss=4997.0, rate=0.5003}
{[P1:KI (4,9)-(4,8) ..], win=5002.5, loss=4997.5, rate=0.50025}
{[P1:FU (2,7)-(2,6) ..], win=5002.5, loss=4997.5, rate=0.50025}
{[P1:GI (7,9)-(6,8) ..], win=5001.0, loss=4999.0, rate=0.5001}
{[P1:OH (5,9)-(5,8) ..], win=4995.5, loss=5004.5, rate=0.49955}
{[P1:OH (5,9)-(4,8) ..], win=4995.0, loss=5005.0, rate=0.4995}
{[P1:KY (1,9)-(1,8) ..], win=4994.5, loss=5005.5, rate=0.49945}
{[P1:HI (2,8)-(6,8) ..], win=4992.5, loss=5007.5, rate=0.49925}
{[P1:KI (4,9)-(5,8) ..], win=4990.5, loss=5009.5, rate=0.49905}
{[P1:FU (5,7)-(5,6) ..], win=4990.5, loss=5009.5, rate=0.49905}
{[P1:KI (6,9)-(7,8) ..], win=4988.0, loss=5012.0, rate=0.4988}
{[P1:FU (3,7)-(3,6) ..], win=4981.5, loss=5018.5, rate=0.49815}
{[P1:KY (9,9)-(9,8) ..], win=4989.0, loss=5011.0, rate=0.4989}
{[P1:HI (2,8)-(1,8) ..], win=4989.0, loss=5011.0, rate=0.4989}
{[P1:GI (3,9)-(4,8) ..], win=4987.5, loss=5012.5, rate=0.49875}
{[P1:HI (2,8)-(4,8) ..], win=4986.5, loss=5013.5, rate=0.49865}
{[P1:FU (7,7)-(7,6) ..], win=4985.5, loss=5014.5, rate=0.49855}
{[P1:KI (6,9)-(5,8) ..], win=4985.0, loss=5015.0, rate=0.4985}
{[P1:OH (5,9)-(6,8) ..], win=4984.0, loss=5016.0, rate=0.4984}
{[P1:GI (7,9)-(7,8) ..], win=4983.0, loss=5017.0, rate=0.4983}
{[P1:GI (3,9)-(3,8) ..], win=4982.5, loss=5017.5, rate=0.49825}
{[P1:KI (6,9)-(6,8) ..], win=4979.5, loss=5020.5, rate=0.49795}
{[P1:FU (8,7)-(8,6) ..], win=4978.0, loss=5022.0, rate=0.4978}
{[P1:FU (1,7)-(1,6) ..], win=4976.0, loss=5024.0, rate=0.4976}
{[P1:HI (2,8)-(3,8) ..], win=4967.5, loss=5032.5, rate=0.49675}
{[P1:FU (9,7)-(9,6) ..], win=4963.0, loss=5037.0, rate=0.4963}

…駄目ですね。初手だけでは違いが少なすぎて10,000回程度では 意味なし ですね。

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。