終わるんです 〜 ランダムプレイヤーは何故賢いのか
なんか最近、コンピューター将棋界にはモンテカルロブームが到来しているらしいので、モンテカルロ型の探索についてつらつらと書いてみます。
まず、ランダムプレイヤーを実装するとします。ここで言うランダムプレイヤーとは、合法なすべての指し手を生成し、そのなかの一つをランダムに選ぶというものです。もう少し効率的な実装はできますが、まずは愚直にそう実装してあるものとします。
このようなランダムプレイヤーは予想以上に終局します。(ここで言う終局とは合法な指す手がなくなった局面を言います。)
完全にランダムに指し手を進めるだけでこんなに終局していいのかというほど終局します。
1万局シミュレーションにおいて1000手以内に8075局したという結果があります。*1
私はランダムに進めてまさかそんなに簡単に終局するとは思っていなかったので、ランダムプレイヤーって意外と賢いんだなぁというのが正直な感想でして、虫けらにも五分の魂と言いますか、ランダムプレイヤーにも五分の頭脳と言いますか。
何故そんなに簡単に終局するのかについては自明ではないと思うので(私も最初、理由がわかりませんでした)、以下にその理由を書きます。
例えば次図は、ランダムプレイヤーによって1000手までかけて、決着がつかなかった図です。
相入玉模様で、まるで人間が指しているかのような図ですね。本当にこれランダムプレイヤーなの？と思ってしまいます。しかしよく見ると敵の飛車と馬が変なところに存在しています。それ以外は人間が対局したものと比べてもそれほど変哲はないでしょう。
さて、何故このような図が出来上がるのでしょうか。
賢明な読者は、もうおわかりかも知れません。
すべての指し手を生成するということは、駒を持ったらすぐに打つんですよね。生成される手のうち半数以上が打つ手なので。よって手駒はすぐに盤上に放り投げられ、無くなります。
また、移動に関して金は前進が3通り、後退が1通り。銀は前進が3通り。後退が2通り。
指し手をランダムに選びますから、ゆえに、金・銀は前進する可能性のほうが高いのです。
そこで、金も銀は上ずっていきます。歩・香・桂は前方にしか行けませんし、成ると金相当になるので、これまた上ずっていきます。
角と飛車は、移動に上下の対称性があるので上ずることはありません。上図で角と飛車にだけその配置に違和感があるのは、そういうことなんです。
では玉はどうなるでしょうか。玉も移動に上下の対称性があるので、上ずるということもなく、単にブラウン運動をしていきます。しかし敵の駒は次第に上ずってくるので、自陣に居座ったままですと、いずれ大量の成り駒がやってきて詰まされてしまいます。ゆえに、終局しない図はかなりの確率で相入玉の将棋になります。
これが完全なランダムプレイヤーが意外と賢く見える理由です。
では、ここで問題をひとつ。
すべての指し手を毎回生成するのは明らかに無駄です。そこで、次のような高速化を考えるとします。
盤上および手駒のなかから駒をひとつ等確率でランダムに選んで、その駒を使った指し手のなかからランダムに一つ選んで局面を進める。
さて、この場合は、完全なランダムプレイヤーと比べて終局は遅くなるのでしょうか？
