再びモンテカルロへ
確定勝利優先アルゴリズムにここで書いた修正を加えてみました。
ここで書いた問題を、30,000playoutで5回解かせたところ、1回だけ約20,000playoutで解けましたが、後の4回は解けませんでした。
倍の60,000poでやらせてみたら、58,673poでやっと解けました。
確定勝利優先アルゴリズムは、一度詰みを見つけて初めて有効になるわけですが、見つけるかどうかは運次第、というところがあります。
この問題では、正解の手順で詰みを見つけたのが55,000poを過ぎてからで、それからはあっという間だったようです。
で、別の問題を解かせてみました。
後手の持駒:角 金三 銀 桂 歩七 9 8 7 6 5 4 3 2 1
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- +
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
v香v桂 ・v玉 ・ ・ ・ ・ ・ | 一 |
・ 金 ・ ・ ・v歩 ・ ・ ・ | 二 |
v歩 歩v歩v歩 ・ 全 馬 ・ ・ | 三 |
・ ・ ・ ・ ・ ・v歩 ・v歩 | 四 |
・ ・ ・ ・v歩 ・ ・v銀 ・ | 五 |
・ ・ ・ ・ ・ 龍 ・ ・ ・ | 六 |
歩 ・ 歩v杏 歩 ・ ・ ・ 香 | 七 |
・ ・ ・ ・ 銀 ・ ・ ・v龍 | 八 |
香 桂 ・ 玉 ・ ・ ・ ・ ・ | 九 |
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- +
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
おなじく将棋タウンの「やさしい実戦の詰み」第28問で、5手詰ですが、あっさり500poくらいで解いてしまいました。*1
これが速く解けた原因は、先手玉が△68金打の詰めろになっていて、後手玉を詰ませない限り先手の負けになるため、王手以外の手に全部負けフラグが立った(=探索がスキップされる)ためだと思われます。
この手法の概念はすでに書いたとおりですが、気づいた点としては、
「残りのノードがたくさんあるなら優先度は低く、もう少しで証明が終わるなら優先度を高く」
というだけではダメ、ということです。
たとえば、合法手が2手しかなくて、片方は詰みだがもう一方は不明、という場合、不明のノードは1ノードだけなので、優先度は高くなり、たくさんのpoを割り当てたくなります。
しかし、その手が結局不詰だった場合、モンテカルロでは不詰ということが分からないので、「不明」のまま、どんどんpoを割り当て続けてしまいます。
対応としては、もう少しで証明が終わる場合でも、その指し手を選択した回数が多ければ優先度を下げていく、という方法をとっています。*2
2/2 本文の一部を脚注に移す