WCSC29(第29回 世界コンピュータ将棋選手権)ではアピール文書を3月末までにいったん提出しないといけないらしい。

そこで昨日『やねうら王 with お多福ラボ 2019』のアピール文書を書いて提出したので、それをそっくりそのままここに掲載しておく。なお、この文書は実験中の内容などを含むため、大会開始日までに最終的な内容を反映させて更新する。

教師局面の生成効率の改善

『やねうら王 with お多福ラボ 2019』(以下、「やねうら王」と記す)では、教師局面の生成部に工夫を施した。

やねうら王では、自己対局を行い、それを教師として機械学習により学習させる。このとき学習に用いるのは、WCSC27でelmoが採用したelmo式である。

※　『elmoがもたらしたオーパーツについて』

elmo式には勝敗項と勝率項がある。勝敗項は、その局面から同じぐらいの棋力のプレイヤーが対局を引き継いだ時にどちらが勝つかという情報であり、勝率項は、その局面で深い探索を行ったときの評価値から計算される期待勝率である。

いま、質の良い教師をなるべく小さな計算コストで生成したいわけであるが、質の良い教師というのは、この勝敗項と勝率項のどちらの精度も上げなければならない。そこでそれぞれ個別に考察を行った。

質の良い勝敗項について

勝敗項は、「その局面から同じぐらいの棋力のプレイヤーが対局を引き継いだ時にどちらが勝つかという情報」だと上で書いた。本当は、どちらが勝つかは100%先手勝ち/100%後手勝ちというような確定的な情報ではなく、「(同じぐらいの棋力のプレイヤー同士だと)先手側が8割ぐらい勝つ」のように確率的な情報であるが、その部分を掘り下げても話がややこしくなるだけなのでここでは細かい議論はしない。

ともかく、この「同じぐらいの棋力のプレイヤー」というところが問題である。例えば先手だけ神様レベルのプレイヤーで後手は並程度の棋力のプレイヤーであれば、先手ばかりが勝ってしまうことになる。これではelmo式の勝敗項はノイズにしかならない。だから「同じぐらいの棋力」であることは必要不可欠な条件である。

そして、このときの棋力は高ければ高いほうがより正確な局面の情報を反映すると考えられる。

このため、深い探索深さ(high depth)での教師局面の生成を必要とする。(ここで言う「深い」とはdepth 6～14ぐらいのことを指す。これは実際の対局時よりはかなり低い数値が、大量の教師局面を生成する都合、仕方がない。以下では「低ノード」「低いdepth」などと言う言葉が出てくるが、実際の対局時よりは相対的に低いという意味であり、これらはすべて教師生成時の探索のことを指している。)

探索深さが深いと指数関数的に探索時間が増加するので、high depthでの教師生成にはすこぶる計算資源を使う。やねうら王では、まず、これを少ない計算資源で抑えることができるかという工夫をした。

そのために、まず教師を生成するときの対局シミュレーションでの思考深さにおける勝率が上がるように探索パラメーターのチューニングを行った。簡単に言ってしまえば、短い時間で最強となるようにチューニングを施した。

1) 短い時間で最強
2) 少ない探索ノード数で最強
3) 低いdepth固定で最強

1)と2)はほとんど同じ意味だが、3)だけは大きく意味が異なる。3)でチューニングしてはならない。なぜなら、探索の時の枝刈りを甘くすれば、強くはなるが、思考時間は相対的に増えるからである。そのようなチューニングをしても何ら意味がない。よって、1)か2)の方法でチューニングすべきである。

やねうら王では、短い時間で最強の状態にチューニングすることにより、質の良い勝敗項(勝敗情報)を得ることに注力した。

同じ探索部で比較すると、0.1秒でその棋力を比較したときに探索パラメーターのチューニングだけで+R160程度の棋力上昇を確認した。その他、低depth(depth8や10)に向け、各種枝刈りの適用/非適用を調整することにより、+R100程度の棋力上昇を確認した。合計で+R260である。

つまり、従来と同じ計算資源で教師局面の生成時に+R260強いプレイヤーでの対局シミュレーションが行えるようになった。これは計算資源を2倍使うのと同等以上の効果があると考えられる。

質の良い勝率項について

勝率項は、深い探索の評価値から計算されるものである。しかし、評価値が“ぶれる”と学習しにくい。ここで言う、ぶれるとは、同一局面、もしくは類似局面なのに評価値に差がありすぎることを言う。

例えば、近年、探索部は枝刈りをどんどん激しく調整する傾向にある。やねうら王の場合、2年前の探索部と1年前の探索部を比較するとdepth 8で同士で比較したときに平均思考時間が6,7割程度少ない。つまり、枝刈りがそれだけ激しくなってきているということである。このように枝刈りを激しくして、見込みのなさそうな指し手を早い段階で切り捨て、そして深くまで探索して“お宝”(評価値の高い局面)を発見し、現局面からそこに到達する指し手を選んだほうが、強くなる傾向がある。

確かに強くするという観点からはそうするのが正しいのであろうが、同じ局面を探索した場合であっても、たまたま“お宝”を見つけられた時は比較的高くなり、“お宝”を見つけられなかった時は比較的低くなってしまう傾向がある。このことは、同じ局面を持ってきて、探索パラメーターを少しだけ変更したときの探索の評価値の分散が、昔の探索部より大きくなっているということから示すことができる。

このような評価値のぶれは、教師として好ましい性質ではない。

そこで、評価値を平滑化するためにメディアンフィルタのようなものを適用する(前後の5手の評価値の平均をその局面の評価値とする)ことも考えられるが、平滑化したいのは、本来は対局シミュレーションのその一局に対してではなく、同一局面、もしくは類似局面の評価値に対してである。

一つの解決策として、枝刈りを甘くする方法が考えられる。つまり、そのdepth圏内の局面に存在する“お宝”を確実に見つけるのである。こうすることにより、評価値のぶれは多少抑えることができる。ただし、枝刈りを甘くすると、棋力自体は弱くなるのが普通であるから、教師データの勝敗項の精度が下がる。

また別の解決策として、評価値がぶれにくい評価関数を用いるというのがある。きちんとしたデータを取ったわけではないが、例えば、NNUE型の評価関数は、非線形な評価関数であるためか、(体感的には)評価値の分散が大きいように思う。(これも示せるようなデータは取っていない。)

この意味で、KPPT型の評価関数から教師を生成するのはアリだと思う。やねうら王では、やねうら王2018(2018年にマイナビから発売した『将棋神やねうら王』に収録している、やねうら王2018の評価関数)から教師を作成する予定である。

質の良い勝敗項・質の良い勝率項

勝敗項の精度を上げるには短い時間で最強にする必要があった。これは枝刈りを激しくすることを意味しているのだろうか？

『将棋神やねうら王』の開発の時の実験において、1スレッド3000ノードと2スレッド1500ノードとを対局させると後者のほうが勝率が高かった。普通、並列探索にすると探索効率が下がるので弱くなるはずなのだが、やねうら王の場合、低ノード(低ノード数に固定しての対局)ではそうではなく、枝刈りが相対的に甘くなるので強くなる傾向があるようである。やねうら王にとって、低ノードでは枝刈りが激しすぎる意味があるようだ。

そこで短い時間で最強に調整すれば自動的に枝刈りは甘くなり、評価値のぶれがなくなると思われるであろうが、実はそうでもない。

以下に一つの実験結果を示す。

これは、futility pruningという枝刈り(初期のBonanzaにも採用されている)のパラメーターをどのように調整すれば勝率が上がるかということを別のソフトと対局させてgrid searchしたものである。なお、わずかなRの差まで検出したいため、0.1秒で30万対局以上させている。

PARAM_FUTILITY_MARGIN_ALPHA1: // 元の値は172
162 : 35451 – 391 – 14546(70.91% R154.75)
164 : 35584 – 417 – 14807(70.62% R152.32)
166 : 34531 – 445 – 14599(70.28% R149.55)
168 : 34481 – 414 – 14749(70.04% R147.53)
170 : 34955 – 392 – 15052(69.9% R146.37)
172 : 34926 – 404 – 14913(70.08% R147.83)
174 : 34363 – 387 – 14958(69.67% R144.49)

PARAM_FUTILITY_MARGIN_ALPHA2: // 元の値は50
48 : 34508 – 398 – 14876(69.88% R146.17)
50 : 34622 – 436 – 14851(69.98% R147.04)
52 : 34331 – 400 – 14833(69.83% R145.78)
54 : 35110 – 370 – 14924(70.17% R148.62)
56 : 34920 – 401 – 14728(70.34% R149.97)
58 : 35114 – 429 – 14682(70.52% R151.48)
60 : 35686 – 416 – 14730(70.78% R153.72)

また、やねうら王のfutility marginは以下の計算式になっている。(C++で書かれた実際のコード)

// depth(残り探索深さ)に応じたfutility margin。
Value futility_margin(Depth d, bool improving) {
return Value((PARAM_FUTILITY_MARGIN_ALPHA1 – PARAM_FUTILITY_MARGIN_ALPHA2 * improving) * d / ONE_PLY);
}

futility pruningは以下のように、その局面の評価値(eval)が、beta値 + marginを超えていれば、枝刈りするというものなので、このfutility marginの値が小さければ小さいほど適用されやすくなる。

if (!PvNode
&&  depth < PARAM_FUTILITY_RETURN_DEPTH/*7*/ * ONE_PLY
&&  eval – futility_margin(depth, improving) >= beta
&&  eval < VALUE_KNOWN_WIN) // 詰み絡み等だとmate distance pruningで枝刈りされるはずで、ここでは枝刈りしない。
return eval;

上のgrid searchの結果は、勝率がPARAM_FUTILITY_MARGIN_ALPHA1,PARAM_FUTILITY_MARGIN_ALPHA2の関数だとして、関数の単峰性が見てとれる。

また、この結果は、0.1秒で強くするためには、PARAM_FUTILITY_MARGIN_ALPHA1をもっと下げよ(枝刈りを激しくせよ)、PARAM_FUTILITY_MARGIN_ALPHA2をもっと上げよ(枝刈りをさらに激しくせよ)と訴えかけている。(ちなみに、この２つの定数は、長い持ち時間で棋力が最大になるように調整したときのそれぞれのベストな値は、172と50であった。)

つまり、このgrid searchの結果に素直に従い、0.1秒で最強に調整していくと、枝刈りが激しくなり、評価値のぶれが大きくなり、勝率項の精度が下がると考えられる。

そこで、やねうら王では、無作為に抽出された局面の評価値の分散を著しく上げないという拘束条件を追加しつつ、探索パラメーターを0.1秒で最強に調整する。

■　結論

以上により、質の良い勝敗項と質の良い勝率項という相矛盾する要素を持つ教師生成を従来より2倍以上低い計算コストで実現が可能になった。

しかし何故かまだ昨年のものから強くならない。ゲロ吐きそうである。大会当日までにこのPR文書を書き直す。とりあえず、現時点[2019/03/19]ではこんな感じで取り組んでいますよ、ということで。

[2019/03/26追記] とりあえず、新しい評価関数が、SDT5(第5回 将棋電王トーナメント[2017])のときと同じぐらいの強さになった。まだマイナビから発売した『将棋神やねうら王』に収録したtanuki-(2018年度版)にR60ぐらい負けている。理由はわからない。禿げそう。

[2019/03/31追記] 使用しているライブラリについて書き忘れていたので以下に追記。
・やねうら王ライブラリ 選定理由：自作のライブラリですが、申請が必要なのかどうか理解できていないのでルール上の地雷回避のために申請しておきます。
・tanuki-ライブラリ 選定理由 : やねうら王のGitHubにNNUE評価関数のプルリクエストをもらったのでマージしたのですが、 これについて申請が必要なのかどうか理解できていないのでルール上の地雷回避のために申請しておきます。 tanuki-ライブラリに関して、やねうら王のGitHubにあるコード以外は使用しておりません。

[2019/05/09追記] 選手権直前に、強くならなかった理由が少しわかった。上の方針自体は間違っていなかった。

また、本大会のためにテラショック定跡という定跡を用いた。生成手法は以下に書いた。本大会では700T(700兆)局面を探索して35万局面を生成した。

テラショック定跡の生成手法