読者です 読者をやめる 読者になる 読者になる

fastapple's blog

時系列関係なく、情報を追記・分割・統合などします。ブログに記載の内容のうち、引用ではなく、私自身が記載している文章・コードなどについては、自由にご利用ください。

最善手を数値化する試み


将棋のようなボードゲームでは通常、最善手とよばれる手が一手ごとに存在する。*1

このようなゲームでは、勝っているほうは最善手を指し続けていれば理論上100%勝つことが出来るわけである。それなら一手一手の価値というものを、もっと定量的に測ることが出来るのではないかと考えている。

それでは、定量化するにはどのような尺度を用いるのが便利だろうか?

まず思いつくものとして、自分がこのまま指し続ければ勝てるという手を1とし、このまま指し続けて引き分けになる場合を0.5、それ以外を0としてみるとどうだろう。負けている側は、どんな手を指しても評価は0になってしまう。これは、勝敗をひっくり返せる可能性がある局面がいくつあるかを確認するのには向いているが*2、負け確定の手だからといってその手の価値を全て同じとするのは直観に反するのではないだろうか。

例えば詰将棋にこの尺度を適用すると、攻め方は常に評価1になる手を選べばよいという事になるが、玉方はどうだろうか。
詰将棋では、玉方は最長手順を使って逃げることになっている。例えば極端な話、Aという手で逃げればあと30手で詰みだが、Bという手で逃げれば3手で詰みという場合、玉方はAという手で逃げる。これはつまり、最長手順で逃げる方が逆転の目があるという暗黙の了解からきていると考えられる。大抵の場合、最長手順で逃げる方が相手は勝ちにくくなる。

それでは今度はこのような尺度はどうだろうか。勝っている方の評価を無限大∞として、負けている方は自分が最長であと何手で詰むかというのを尺度としてもつ。(既に詰んでいる場合は0)。このとき、引き分けをどう扱うのがいいかというのはなかなか興味深いが、とりあえずE(even)という数になることとしておく。

例えばどうぶつしょうぎの場合、後手必勝であることがわかっている。
http://media.itc.u-tokyo.ac.jp/ktanaka/dobutsushogi/animal-private.pdf
http://media.itc.u-tokyo.ac.jp/ktanaka/dobutsushogi/20090626.pptx.pdf
この解析結果によると、初期局面から78手で後手勝ちとなることがわかっており、これを先ほどの尺度に当てはめると、初期局面は、(先手78、後手∞)という結果になる。ここで気付いたがこれは先手か、後手は必ずどちらかが∞になるか、若しくはどちらもEとなるような尺度なので、マイナスを使えば、単純に先手が勝てる場合を正、後手が勝てる場合を負として、引き分けを0とすることで、一数直線上に表わすことができる。例えば初期局面は-78となる。

上記のような尺度は最初の尺度よりはだいぶマシになったと思うし、十分に実用的なものだとは思うがここでもう少し掘り下げて考えたい。将棋のようなゲームは、人間の考えられる局面の数に対して、実際にゲーム終了までに起こり得る局面の数のほうが圧倒的に多い。

つまり、 人間の考えらえる局面 ≪ 起こり得る局面 という状態である。(≪はここでは十分に大きいという意味とする)

このような場合、すべての局面を読み切ることは不可能なので、いくつかの局面をピックアップして読まなければいけない。

ここでただ探索することしかできない(手の良さを直観的に評価できない)プレーヤーがいると仮定しよう。このプレーヤーは、1回の思考で例えば5つの合法手を読むことができる。これはたとえば5手先まで直線で読んでもいいし、5つの局面をそれぞれ1手先まで読んでもいい。また、詰みであれば詰みとすぐ判断できるものとする。そうなってくると、最善の手を読めるかどうかは単純に確率の問題になってくる。こういう性質のプレーヤー同士が対局しているとすると、例えば一方が指した手によって、相手の読む必要がある局面のうち最善ではない手が増えれば、相手はそれを選んでしまう可能性が増える。つまりわざと相手にとって次善の手を、最善手と遜色ない形で紛れ込ませるわけだ。そういう選択肢を提供する手のほうが強い手と呼べるのではないだろうか。それなら、そういう手を評価できる尺度がほしいところである。

*1:最善手は複数の場合もあり得る

*2:つまり評価が変わってしまった局面の数を数えればいい。