電王トーナメントの強豪ソフトのアピール文書にツッコミ

今回の将棋電王トーナメントのアピール文書が公開されました。(遅すぎ!)

将棋電王トーナメント 出場ソフト
http://info.nicovideo.jp/denou/tournament2015/soft.html

気になった強豪ソフトのアピール文書にざっとコメントを。

Ponanza

目新しいことが書かれていません。秘密主義?

大樹の枝(Apery)

最近気付いたんですが、僕がいくら改良しても、それを GitHub で公開してたら Apery ライブラリ使う人のソフトまで勝手に強くなってしまうので、差が付かない!という事で GitHub への push は大会終わるまではサボり気味にしておこうかなーとか思ってます。仕方ないよね。僕も勝ちたいです!

このくだり、ほんと好き。GitHubへのpush、1年遅れでもいいんじゃないでしょうか。それでも1年前の自分に大差で勝たなければならないという足かせはあるわけで…。

tanuki-

AVX2 拡張命令の VPGATHERDD 命令を用いた盤面評価関数ルーチンのベクトル化
” ベクトル化しない場合に加え 3%程度速くなりました

VPGATHERDD!?ああ、KPP配列をkpp[sq][p1][p2]だとしたら、kpp[sq][p1]のアドレスをbaseとして指定して、8つずつ要素をまとめて取ってくるということなのでしょうか。評価関数って、メモリ帯域がボトルネックになっているから、どうせ速くならないと思ってたけど、そうでもないのね…。これはミラクル!

nozomi

• KPP = 絶対KPP + 相対KPP + 絶対PP + 相対PP
• KKP = 絶対KKP + 相対KKP + 絶対KP + 相対KP + 絶対KK + 相対KK
• KP要素についてはKPPとKKPで同じ値を使用するようにしています

相対KKなんて回転対称だから値がつくべきではないので入れないほうがいいです。ノイズになります。(手番を考慮するなら別) あと絶対KK、KKPに次元下げのときに入れてしまうと、FV38をやっているとして1回のevaluateで必ず同じ要素が38回出現することになるのでボナメソで値を2動かそうとしたときに、38*2 = 76も動いてしまいます。ゆえに、絶対KKをKKPの次元下げに含めるのはしないほうがいいです。同じ理屈で、KP要素もKPPとKKPに同じものを含めると値が二倍変動してしまうので、KKPのほうにだけでいいです。

大将軍

しかし、大会 PC のスペック変更により、搭載メモリが 32GB と減ったため、4 駒の評価関数をメモリ上に展開することができなくなりました。
このため、4 駒の評価関数の採用は断念し、3 駒の評価関数を今大会用に一から学習を開始し、出場することとしました。

お気の毒に…。本当、電王トーナメントの開催スケジュール、ルールやPCスペックの発表が遅れると開発のほうは色々振り回されますよね…。

技巧

初参加で強さは未知数ですが、私はこのソフト、相当強いと思います。

各マスの利き数の計算をSIMD演算により高速化
・ 1マスにつき1〜2バイトのデータ構造(byteboard / wordboard)
・ SSEを使った場合、最大16マスの利き数をいっぺんに計算でき
るので、1マスずつ処理するのに比べて高速に計算可能です。

利きの数、1升1byte(先後で2byte)確保しておいて、SSEでまとめて加算してしまうのはまあ、利きの数を必要とする評価関数であれば、最近はそうしますよね。利きの数を用いる評価関数を使ってるの、KPP/KKP勢にはいないと思いますが、私は今後主流になる可能性があると思っています。

ちなみに1升の利きの数は最大で4bitで収まるのでsoftware packed bitとみなして加算/減算すれば、盤面更新の効率は上がります。AVX512が使えれば、4bit*81升の利きの更新が1回の更新で済むので…。(そのあと利きのある升を取り出すのに苦労するかも知れないので良し悪しではありますが。)

利き情報をsoftware packed bitのMSBに集めるためには1升5bitにして5bit*81升(512bitに収まる!)みたいにするのがベストだと思いますけども。software packed addについては、以下の記事をどうぞ。

縦型Bitboardの唯一の弱点を克服する

あと各升での利きの優劣も、software bit演算のテクニックを使えば(1升が)5bitであれば簡単に出来ますね。引き算で引かれる側のMSBを事前に1にしておけば、負の数になったときにMSBが0になりますので…。

まあ、利きを評価関数に取り入れている強豪ソフトって一握りだけなので、いまこの話を延々と書いても、ほとんどの開発者にとって「だから何?」ぐらいの話だと思いますが、あと5年か10年後には「やねうらおさんは先見の明があった!」「利きを5bitで持つのがベストであることを2015年の時点で予言していたとか、マジで天才!」と言われるはず。(笑)

習甦

Bonanza型の3駒関係を導入したらしいです。非線形な評価関数を導入しているのは習甦ぐらいのものなのでそういう意味では注目株なのですが、非線形な評価関数で本当に強くなるかは実際のところ立証はされていなくて…。

Selene

PR文書のリンク間違っていて見れないです。(2015/11/16 19:55現在)
http://info.nicovideo.jp/denou/tournament2015/img/PR/Selene.pdf
が正しいようです。

指し⼿の評価が他の指し⼿と⽐べて極端に⾼い指し⼿については、探索深さを深くして学習を⾏っています。

これ、わりと面白いアイデアですね。

まとめ

今回棋力だけで言えば、
Ponanza > Apery ≒ 大合神クジラちゃん ≧ tanuki- ≧ nozomi ≒ Apery(WCSC25) ←R100〜150の差→ 昨年のApery
ぐらいの感じだと思います。

あと技巧は上図のAperyからnozomiの間には来るはず。

超やねうら王はまだ開発中なのでよくわかりません。Apery(WCSC25)よりは上に来るようにいま頑張っていますが、新しい評価関数、そもそも昨年のものより弱い可能性も…。

追記

クジラちゃん、探索部がAperyからではなく、なのはminiベースなのでApery(WCSC25)ほどは強くなってないそうです。Apery(WCSC25)の探索部に調整面、速度面等で負けているんですかね。興味深いです。

電王トーナメントの強豪ソフトのアピール文書にツッコミ」への16件のフィードバック

  1. CGP作成者のwainです。
    VGATHERDDですけどこれ16bitデータでもうまく読み出せます。
    ハックは16bit左シフトしてから16bit算術右シフトすれば目的の値を取り出せます。
    また4バイト刻みではなく2バイトでも上位ビットにごみはついてきますがデータを取ることもできます。
    CGPではその方法で実装済みです。

    • ああ、なるほど!しゅごい!

      意味のわからない人のために以下に詳しく書いておきます。

      VPGATHERDDを使うのにkpp配列を32bit化して倍のメモリを消費するようになるわけですが、これを32bit化せずに16bitのまま、VPGATHERDDを使う方法として、普通に32bitとみなしてアクセスして(上位16bitにゴミが載ってくる)、そのゴミを消すために本来ならば符号拡張命令を用いてbit15(MSB)を上位16bit(bit16〜31)に同じ値を埋めないといけないわけですが、そんな都合のいい命令がないので16回左シフトしたあと16回算術右シフトするとbit15がbit16〜31にコピーされるというhackを用いているという意味です。

      このシフトの演算コストが嫌ならkpp配列を32bit化するのはアリだと思いますが。

      • いまどきのKPPの評価関数は手番込みらしいので(私は手番まだ導入してませんが)、先手番用の16bit + 後手番用の16bitをVPGATHERDDで一度で取ってきてこれを個別に集計したくて…それはどうすればいいのですかな…?

        VPUNPCKLWDとかでバラしてから上のhackで符号拡張?もっといい命令SSEにはないんですかね…。

        具体的なコード、誰か貼り付けてくだされ!!(他力本願)

        • てかね、合計が16bitに収まらないのがいけないわけで、ΣKP1P2の計算のうち、KP1ΣP2は16bitに収まると思うので、そんだけずつ求めたほうがいいかも知れないですね。

          VPGATHERDDでKPP配列の要素を32bit(先手番16bit + 後手番16bit)ごとに取ってきて、VPHADDWで16bitごとに加算。

          どうですか、このアイデア!?

          • しゅごい!俺、しゅごい!(自画自賛)

            いやまあ、冗談はともかく、VPGATHERDD + VPHADDWでファイナルアンサーかも知れん…。

            これは後世に残るわ。

          • 手番なしの場合でもKP1ΣP2の分だけVPGATHERDDで集めてきて、そののちにさっきのhackで符号拡張してVPHADDDで加算していけばいいのでは…。そうすると、さっきのhackを使うタイミングはKP1ΣP2の計算ごとに1回(トータル38回?)で済むと…。

          • てかVPGATHERDDをKP1ΣP2のループで使うと、ループの最後のほう、P2が数枚しかなくてさぶい気がする…。これ、もっと均等にループ回せないものか…。

            ああ、kp(i)Σp(j) のループと kp(37-i)Σp(j)のループをペアにして回してしまうだとか?そうすると1回のループは39回固定になって…。いや、VPGATHERDDのbaseアドレスが違うからそれだとうまくいかないのか。

            うわー。誰か助けてくれー。

    • hackの解説ありがとうございます

      VGATHERDDでデータを取ってきて符号拡張した後ですが
      VPADDDで38駒分足し合わせていくのが普通だと思っております。(最後のVGATHERDDはマスクつきで余計な2駒分を0にしておく)
      そして最後にVPHADDDなりシャッフル+足し算でまとめるとhackのシフト5往復分+足し算7回+シャッフル3回
      もしくはhackのシフト5往復分+足し算4回+水平足し算3回で済みます。

      手番考慮の場合は上位16bitに置いたデータをhackに変えて
      算術右シフトするだけでうまくいくと思います。

  2. >Deep Learningで事前に「意味のありそうなところ」を抽出しておき、探索時にはそこだけを計算する?

    やねんざメソッドとは
    1、棋譜集合からDeep Learningで重要な特徴量を抽出する。
    2、それに合わせた評価関数を設計する。ーー>それはライトなN駒関係の評価関数の形になる。
    3、評価関数のパラメータを棋譜集合をつかって機械学習させる。

    どうか、こんな感じでやっておられる事を説明していただけると助かるのでありますが、、、。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です