●NineDayFever

あいかわらず局面評価の極北を目指しています。プログラムはbonanza 6.0からそれほど変わっていませんが、一部手が入っています。

今年の版では項目4、5が追加されています。

1. 対戦中や探索中に現れた局面を調べ、機械学習結果の欠陥を探して修正しています。
2. 未知の局面への対応力を増加させるため、3駒関係を共通するパラメータに分解し、2次の正則化項を使っています(詳細は 2014年のアピール文書 www.computer-shogi.org/wcsc24/appeal/NineDayFever/NDF.txt 参照)。
3. 評価値の計算で手番を考慮しています。
4. 従来の3駒関係では考慮しにくかった飛角香の働きを考慮するパラメータを導入しています。
5. 自己対戦結果に基づいて bonanza の book.bin から一部の手を削ることにしました。

プログラムに関しては、以下の点でオリジナルのボナンザに手が入っています。今年追加したのは 6、7 の一部と9 になります。

6. kpp(pc_on_sq) を 3次元配列にしています。さらに、持ち駒数0に対応するインデックスを削ることでちょっと高速化しています。
7. 上で述べた手番考慮eval処理、飛角香の働き考慮eval処理などを実装しています。
8. stockfish を参考にして探索部分を一部アップデートしています。
9. スレッド数が多いときの並列処理効率低下を防ぐため、探索ツリーのスケジューリング機能を入れました。

●2014年からのアップデート詳細

1. 局面解析
　改善作業は今でも継続していて多少は効果があるようですが、あまり大きく変わってはいません。

2. 学習パラメータ増加
　AWAKE が KPP を構成する要素として KPA(A:アタックされているマス) を使うことで効果を上げているということなので入れてみました。
　歩18枚の持ち駒といったレアケースに対応するため、持ち駒に対応するKPP は 「持ち駒(n-1)枚以下のときのパラメータ」+「持ち駒n枚のパラメータ」と分解しています。とはいっても、歩十数枚の持ち駒というのは結局実戦ではめったなことでは出てこないので、気休めです。

4. 飛角香評価パラメータ
　従来の3駒関係では、飛角香がどこまで利いているかが表現されていませんでした。評価関数を改善するなら、次は飛角の働きをより正確に見積もる方式だろうということで、新しいパラメータを追加してみました。
　基本的な考え方は、従来の KPP で、Pのうち一つが飛角香で、もう一つのPに利きが届いている場合に、ボーナスを与えるというものです。正確にいうと、KPPとはちょっと違うところがあって、「もう一つのP」が自分や相手の王、盤面の端のマスまで空白だった場合のボーナスがあります。
(ところが学習でオオボケをかましていたため、まだ収束していないという)。
　これに関連して飛角香の当たりを調べるコードの自由度向上のため、mm_and_si128()+mm_shuffle_epi8()+mm_cmpeq_epi8()+mm_movemask_epi8() を使って magic bitboard相当の処理をやるものを作ったのですが、Haswell で pext 命令が追加されたため、なくても良くなってしまいました。

5. book.bin 改善
　序盤の定跡を抜けた瞬間、-500ぐらいのスコアがつくことがあるので、book.bin から悪い手を削って勝率を上げようと試みています。
　最初は悪いスコアがついている局面を削れば少しは改善するだろう程度に思っていたのですが、世の中それほど甘くありませんでした。悪いスコアがつく局面はそれほど多いわけではなく、全体の数%の失敗例を勝率 .500の局面に置き換えたときの勝率改善を測定するのは数千回の試行が必要になり、効果の確認は困難でした。さらに、スコア自体は悪くなくても不利な局面もあるようです。
　というわけで、book.binの改善でレーティングを上げようとするなら、一部の局面だけいじっても無駄で、すべての局面でちょっとずつ改善する必要があります。
　今までもいろいろ試みられていると思うのですが、調べている時間がなかったので、book.bin の最後の局面に対して、自己対戦でその局面を経由したときの勝率に基づいて手を選ぶ確率を調整することにしました。
　考え方は以下の通りです(多分同じようなことをやっている人はすでにいるのではないかと思います)。
　　・60万局程度の自己対戦結果を読み込み、book.binの最後の局面ごとにそこからの勝率を求める。
　　・ある局面からの局数が n、勝率が p だった場合、その局面での真の勝率の分布は 平均 p、分散 pq/n (q == 1 - p)の正規分布になっていると考えられる。
　　・最終局面の一つ前の局面を考える。その局面で選択可能な各手に対し、真の勝率の分布が正規分布として求められていることになる。
　　・各手に対して、その手が一番勝率が高い確率を計算する。これはF(x)==(その手の勝率がxである確率*他の手が勝率x以下の確率)を x = 0〜1で積分すればよい。得られた結果に比例して、それぞれの手を選択する確率を決定する。
　　・と言っても、実戦で選ばれた数が少ない手は誤差が大きくて選ぶのが怖い。勝率が高く出ていてもほとんどは単なる偶然で、現在のbook.binで選択確率が低くなっているということは、その手はあまりよくない可能性が高いだろうということで、現在の book.bin で選ばれる確率の2倍は超えないようにする(ちょっと根性なし)。
　　・各手を選択する確率が決まったら、その局面でその選択確率を採用したときの勝率分布が計算できる。結果は正規分布になる。
　　・同様の操作を初手に向かって進める。
　自己対戦での検証では、既存の book.bin を使ったものに対して .550(レーティング40程度)ぐらいの勝率になっています。ちょっと怖いのは自己対戦の結果を使っているところで、地雷に向かって一直線につっこんでいる可能性もあります。もともと book.bin に入っている手だから一部の先後同形角換わりの局面以外は多分大丈夫だろうということにしています。

　4月に入ってから floodgate に投入した NDF が古い横歩取りの実験をしていたのはこのコードが原因です。これはこの定跡が良いと思ってやったのではなく、従来よく指されている後手も86歩で飛先の歩を交換して先手34飛の手順だと、後手の勝率見積もりが .420 ぐらいになってしまったのが原因です。あまり指されていない古い手の自己対戦での勝率が .480 程度あって、こっちの方がましということで生き残ったので、どんなものかと思って試したのですが、予想通りあまりよくないようです。本番では採用しないことになると思いますが、その代わりに現れる変化がやっぱり悪い可能性もあるので難しいところです。

6. パラメータテーブル
　kpp の持ち駒0に対応するエントリを持たないことで、リストの最大長さを52から40に減らして高速化できると聞いたので入れてみました。

9. 並列処理効率化
　スレッド数が増えてくると、探索の効率が悪くなります。その原因の一つは、ゲーム木探索の最初と最後の部分で並列度が低くなることがあります。スレッド数を増やすと、最初と最後に1スレッドしか動かない時間が次第に大きく見えてきます。
この問題の対策のひとつが、rootノードの探索でsplit することです。NDFでは、2013年の版でこの対策を入れています。これで、root ノードの2番目以降の候補手の探索は常に並列化されるので、1スレッドしか動かない時間を削減することが可能になります。しかし、alpha がアップデートされたとき、探索の効率が悪くなるという問題点が残っていました。
alpha のアップデートがあったときも効率を上げるため、今年のNDFでは、以下のような実装を取り入れています。
・探索に優先度をつける。1CPUの場合に先に探索される木のほうが優先順位が高いと考える。
・現在探索している木よりも優先順位が高い木に split ポイントがあるときは、そちらの探索を実行する。
・PVnode の search から返ってきたところで、木をrootに向かってたどり、ベストスコアが改善されたものがあったら、それにしたがって alpha, beta の値を更新する。場合によっては beta cut が発生する。PVnode の search から返ってきたところでチェックすることで、呼び出し側でも alpha, beta が更新され、この beta cut で矛盾が発生しないようすることは可能である。
この実装により、遊んでいるコアがあるときは後で必要になる処理に割り付けつつ、できるだけ1スレッドの場合と同じ順序、同じalpha、betaで探索を実行することが可能になっています。