多数決合議と楽観合議とモンテカルロ。
コンピュータ将棋の話である。電気通信大学の伊藤研究室が作った手法に関する話である。
現在、合議と呼ばれるアルゴリズムがある。同一局面に対して複数のCPUを同時に走らせてその結果から次の一手を多数決で決めようというアルゴリズムである。これをあとに出てくる「楽観合議」と区別するために「多数決合議」と呼ぶことにする。この多数決合議は数式としては以下のように書ける。番目の合法手が番目のCPUの次の一手だったときとし、次の一手でなかったらとする。
このの値が最も大きかったの手を最終的な出力とする。ところでこの式は次のように変えてもだいたい成り立つだろう。すなわち、の部分を次の一手の評価関数のスコアとする。次の一手として選ばれればどのCPUでもおよそ似たような高い値になるだろうし、選ばれなければである。混乱を招かないように、を次の一手の評価関数のスコアとしよう。そして、を求める式はこうなる。
多数決合議の話題はとりあえずここで止めておいて、次は楽観合議(PDF)である。いろいろと改良はされているようだが、もともとは最も高いスコアの次の一手を選ぶというものであるらしい。つまり、の求め方は次のようになる。
回りくどく書いたが、こうなる(ここからさらにargmax xiを計算して次の一手を決める)。ところで、最大値の演算というのは、次のように書ける。
再び、多数決合議に戻ると、先ほどの合計の式は次のようになる。
つまり、多数決合議と楽観合議はパラメータが異なるだけで、同じことを計算しているのではないかと思えるのである。
ここでさらにモンテカルロ法が入ってくる。次の一手から勝利が導ければとし、負けるのならとする。ただし、kは試行回数を示すインデックスである。次の一手に関して試行回数の偏りがなければ、モンテカルロ法は次のように書ける。
試行の一つ一つをCPUの一つ一つだと考えれば、多数決合議と楽観合議の式に一致する(ただし)。
というわけで、多数決合議と楽観合議とモンテカルロがつながった気がする。というか、駆け足で雑に書きすぎた。かといって、丁寧に書く気はしない。何が言いたいかといえば、最後のモンテカルロは蛇足だが、多数決合議と楽観合議の中間はパラメータを変えれば簡単に求まるということである。