レベルの意味

Edaxには「レベル」という値があります。PCで使われている方はレベル20以上で使われている方が多いでしょうか。スマホだとレベル12くらいでも結構重かったりしますね。この「レベル」ですが、レベルが高いほど強くなるのは当たり前なのですが、この値は何を意味するのでしょうか？

読みの深さだと思われた方。はい、正解です。なのですが、実は正解なのは中盤くらいまでで、終盤はちょっと違います。今回はこのあたりのことを調べてみましたので書いてみます。

レベルについて理解するためには、まずはEdaxがどのように評価値を出しているのかを知る必要があります。まずはEdaxの評価値の出し方について調べました。

まず、Edaxには盤面の状況だけを見て評価値を計算する機能があります。「盤面の状況だけを見て」というのは１手も先読みをせずに、という意味です。どのように計算しているかはまた機会があれば調べてみたいと思いますが、「レベル」を理解するためには盤面の状態から、とある計算式で「0手読みの評価値」を出しているということだけ押さえておけば大丈夫です。

0手読みの評価値はそれなりの値ではありますが、それほど精度が高いわけでもないので、Edaxは先読みをします。現局面から可能な候補手をリストアップし、すべての手について次の局面の候補手をまたリストアップし、またそのすべての手に対して・・・と、何手も網羅的に先読みをします。何手先読みをするかは先読みの「深さ(depth)」と呼ばれています。その深さまでの分岐をすべて読んだ時、自分も相手も最善の手を打った場合の末端の局面における「0手読み評価値」が先読み評価値です。結局は0手読み評価値を使ってはいるのですが、深読みしている分だけ精度が上がります。

Edaxは基本的には前記の「先読み評価値」を使うのですが、深さが深くなると考えなければならない手のパターンは爆発的に増えてしまいます。例えば1局面あたりの候補手が6手だったとしても、12手先読みしようとすると末端局面の数は$6^{12}=2,176,782,336$通り(約22億通り)になってしまいます。これでは計算が終わらないので、Edaxはうまいこと計算をサボります。このサボり方も複雑なのですが、レベルを理解するために必要な程度にざっくりと説明してみます。サボり方には大きく分けて2通りあります。

1つ目はサボっても結果に影響しないサボり方です。人間が考える場合でも、例えば終盤の何手空きかくらいの時に、少なくとも勝つパターンを1つ見つけたらそれより石数が少なくなるパターンは少なくなることが確定した時点で読みを打ち切るようなことがあると思いますが、このような「サボり方」です。

もう1つはサボることで結果に影響するサボり方です。先ほどの例でいくと、石数が少なくなることが確定しなくても、「まぁこのパターンは多分石数が足りなくなるだろう」と思った時点で打ち切るようなやり方です。「だろう」の見切りが甘くて、石数を獲得できる分岐が先の方にあると正しくない読み、つまり結果に影響するサボり方になってしまいます。

この2つのサボり方ですが、前者は特にデメリットがないのでEdaxは常にサボります。後者は読まなければならない局面の数(つまり計算時間)と精度とのトレードオフになっているので、Edaxは一定のポリシーを決めています。先ほどの「だろう」という見切りの確信度は、Edaxの内部的には「selectivity(適切な訳語がわかりませんが、選択性くらいですかね？)」と呼ばれていて、73%、87%、95%、98%、99%、100%の6段階存在しています。100%というのは確実な場合なので、実際にサボるのは99%以下の5つになります。このあたりもいろいろと興味深い点があるので、また別の機会にもう少し詳しく調べてみたいと思いますが、今回のところは「5手先まで読んでみて+4だったけど、この先さらに5手読んでみても+10にはならないよね、多分(87%くらい自信あり)」みたいなものだと思っておくことにしましょう。

Edaxのソースコードを見てみると、search.cというソースの中でレベルが定義されています。レベルは「何マス空きの時に」「何手先まで(深さ)」「どれくらいの選択性(selectivity)で」読むか、というポリシーの集合体です。例えば、レベル11というのは以下のようになっています。

• 残りマス数60〜25(1手目〜36手目)：深さ11手で、選択性=73%の読み
• 残りマス数24〜22(37手目〜39手目)：最終手まで、選択性=98%の読み
• 残りマス数21〜1(40手目〜60手目)：最終手まで、選択性=100%の読み

このように、レベルごとに読みのポリシーが決まっています。基本的には中盤までは「深さ=レベルの値」で選択性粗めの読み、それ以降は最終手まで読みますが、終盤に近づくほど選択性の値を高くしている、というパターンになっています。

1つずつ書いていくのは書く方も読む方も大変なので、図にしてみました。図中にも凡例を書きましたが、色が「選択性」を表しています。白い矢印は最終手まで読んでいる範囲を、矢印がない部分は深さ=レベルの値で読んでいる範囲を表します。あ、もちろん横軸が何手目かを表し、縦軸はレベルの値を表しています。レベル11のところについて、上の説明と下の図を見比べて、見方を確認してみてください。(レベル30の内容に誤りがあったため修正しました(2021/9/16)) これを見ると、レベル10までは実はサボらずにきちんと読んでいることがわかります。深さ10くらいまでだったらコンピュータ的には読み切れる範囲ということのようですね。レベル11の序盤からサボり始めていますが、レベルが上がるにつれて、最終手まで読み始めるのが早まっていきます。さらに、選択性を高めていくのも段々早くなっていきます。そして、夢のレベル60では初手からの完全読みが実現します。これはオセロの完全解明ということですから、「Edaxのレベル60=神」ということになりますね。

あと、私が持っていたVer4.3.2のソースの時点では、レベル34〜35の28〜30手目において、レベル33よりも選択性の値が低く設定されていました。最新のソースでは修正されているようですが、レベル34〜35を使用されている方はご注意ください。まぁ、私の場合はパソコンのスペック的にもこんなレベルは使えませんし、自分のスペック的にもこんなレベルでの解析をやったとしても宝の持ち腐れなのですが・・・(苦笑)

• Edaxは序中盤は深さ=レベルの値で読み、中終盤は最後まで読む
• レベルが高くなると、早いうちからより確実な読み方をし始めるので、読み抜けが減る
• レベル60は神