手駒の価値を正しく学習させる
知っての通り、Bonanza6では、手駒の価値は駒割の値 + KPのP=手駒としての値の合計値となる。(実際にはKPPの一つ目のPと二つ目のPが等しいときのKPと、 KKPのP=手駒のほうとがあるが、細かい話は割愛する)
さて、駒割の値というのは、盤上の駒と手駒をひっくるめて、歩 = 100点のように点数化してある。
KPのP=手駒というのは、「先手の持ち駒の歩が0枚」「先手の持ち駒の歩が1枚」「先手の持ち駒の歩が2枚」のような状態を一つの駒(P)とみなしてある。
1枚目の歩だけ価値が100点よりは少し高く120点の価値があるとしよう。そうすると「先手の持ち駒の歩が1枚」のKP値には20点がつくことになる。
2枚目の歩は逆に80点の価値しかないとしよう。そうすると「先手の持ち駒の歩が2枚」の価値は-20点がつくことになる。
以下、同様であるのだが、歩を10枚以上持っているような局面はなかなか出てこないので、「先手の持ち駒の歩が10枚」のKP値は0に収束する。(出現しない特徴は0に収束する！)
そうすると、先手の持ち駒の歩が10枚の局面は駒割の100点×10枚 = 1000点がつくことになる。これが正しいのかどうかという問題について考えなくてはならない。
【手駒の価値モデルを考える】
1枚目の持ち駒の歩が100点だとしよう。2枚目の持ち駒の歩はそれより低い価値であるはずだ。0枚と1枚の差は明瞭だが、1枚と2枚の差は前者ほどのインパクトはないからだ。だから、ここは仮に80点だとしよう。問題は3枚目の持ち駒の歩は80点より低いのかどうかということだ。
仮に、3枚目は60点、4枚目が40点、5枚目は20点、6枚目は0点、7枚目は-20点みたいな点数だとしたら、7枚目の歩はむしろないほうが良いことになってしまう。これはおかしい。
そこで、3枚目の歩が2枚目の歩より価値が下がるとしても、どこかに収束するはずだ。すなわち、3枚目は70点、4枚目は65点、5枚目以降は60点、みたいな点数が正しい。(と思われる)
つまり
・0枚 = 0点
・1枚 = 100点
・2枚 = 100点 + 80点 = 180点
・3枚 = 100点 + 80点 + 70点 = 250点
・4枚 = 100点 + 80点 + 70点 + 65点 = 315点
・5枚 = 100点 + 80点 + 70点 + 65点 + 65点 = 380点
のように合計値はなる。
Bonanzaは駒割の点数自体も棋譜からの学習により調整するので、この場合、
・歩の駒割 = 60点
・KPのP=1枚目の持ち駒の歩 = 40点
・KPのP=2枚目の持ち駒の歩 = 60点
・KPのP=3枚目の持ち駒の歩 = 70点
・KPのP=4枚目の持ち駒の歩 = 75点
・KPのP=5枚目の持ち駒の歩 = 80点
・6枚目以降 = 80点
のような点数がつけば、辻褄が合うのだが、よく考えて欲しい。6枚目以降として80点がつかなければならない。ところが6枚以上の歩を手持ちにする局面というのはあまり存在しない。10枚以上などとなるとなおさらだ。そうなると、この評価因子は0に収束してしまう。ゆえに歩の枚数が多くなってくると、このような点数のつきかたでは手駒の枚数が多いときに破綻するのだ。
そこで、実際は、
・歩の駒割 = 80点
・KPのP=1枚目の持ち駒の歩 = 20点
・KPのP=2枚目の持ち駒の歩 = 20点
・KPのP=3枚目の持ち駒の歩 = 10点
・KPのP=4枚目の持ち駒の歩 = -5点
・KPのP=5枚目の持ち駒の歩 = -20点
のような点数がつく。こちらのほうが、それぞれの因子の絶対値の合計値がさきほどの点数より小さい。しかしこの場合であれ、やはり手駒が多い場合には、さきほどと同じ問題がある。
このように考えていくと、Bonanzaのように駒割 + 手駒N枚を一つの(KPの)Pとみなすような因子分解をするモデルを(出現頻度が少ない因子が0に行くような)機械学習で学習させると枚数が手駒の枚数が多い場合にうまく機能しない。(うまく機能しなくとも、そのような局面はなかなか実戦で出現しないのであまり表面化しないという見方もあるにはあるが…)
これに対して、先日紹介した「make_listの38要素化」*1であれば、歩を2枚手駒にしている状況であれば、「駒割 + 歩が手駒に1枚ある(というKPのP) + 歩が手駒に2枚ある(というKPのP)」という点数になる。
歩が手駒に10枚ある(というKPのP)に対しては、ほとんど棋譜に出現しないのでゼロに収束するだろうが、ここがゼロになったとしても、手駒が10枚あるという状況は、
・駒割 + 歩が手駒に1枚ある(というKPのP) + 歩が手駒に2枚ある(というKPのP) + …(中略)… + 歩が手駒に9枚ある(というKPのP) + 歩が手駒に10枚ある(というKPのP)
という合計値であり、あまり問題とならない。
要するに、「make_listの38要素化」してある状態で学習させたほうが駒割に対しては適切な値に収束すると思われる。
このことはPonanzaの山本君やAperyの平岡さんも同じ主張をしていたので、上位ソフトの開発者間では常識とみなされていることだとは思うが、比較実験をした人がいないので本当のところはよくわからない。
また、本当に、1枚目の歩の価値 > 2枚目の歩の価値 > 3枚目の歩の価値 > 4枚目の歩の価値 > … のような順序関係が成り立つなら、棋譜からの学習時にここ(「歩が手駒にN枚ある(というKPのP)」)にそのような制約条件を入れてやることで、より適切な値に収束するはずであるが、手駒の部分があまり適切な値に収束してなくとも、他の部分でうまく辻褄が合うように調整されるのが評価因子の多い大規模な機械学習の世界であるから、こういうところにいろいろ気を回しても結局は棋力にはあまり影響なかったりするのが現実である。
棋譜からの学習は何日で収束するのか
Bonanzaで1ヶ月+α*1と保木さんに教えてもらいましたが、当時のPCでBonanzaは1コア当たり250knpsぐらいしか出ませんでした。いまのPCでいまどきの作り(Stockfish風の探索部)であれば、1Mnpsぐらい出ます。
ということは探索速度は4倍になっていることになります。また、コア数も当時はXeonで4コア×dual = 8コアでしたが、いまはAWSなどでは16コア環境を使うことは容易です。ということは、ボナメソでやっても4倍×2倍 = 8倍早く収束するわけで1から学習させても4,5日+αがあれば収束することになります。
ここに相対KPP/KPAなどによる次元下げを併用した場合、さらに短い時間で収束することが予想されます。AWAKEの例でPC 6コア×1台+4コア×2台の3台構成で3日という話がありました。だいたい上記の計算と辻褄が合うように思います。
これくらい短かい期間で収束するのであれば、評価関数の形をいろいろ変えて実験したり、次元の下げ方を工夫してみたり、棋譜の数を増やしたりと夢広がりングですね。
そういう意味では、PC環境と探索部の高速化によって、コンピューター将棋の開発は新たな時代に突入したと言えそうです。
次元下げモジュールのプラグイン化計画
NDFがやったKPPの次元下げ
KPP = 絶対KPP + 絶対PP + 相対KPP + 相対PP
を綺麗にプログラムするための方法について考えてみます。このような次元下げは、KPPを与えるとそれに対応する絶対KPP、絶対PP、相対KPP、相対PPの配列のindexを返すものとして設計すると綺麗に書けます。
すなわち、
int* make_kpp(Square king , BonaPiece p1 , BonaPiece p2);
のように設計することです。この返し値をpとすると、
learn_kpp [ p[0] ] が絶対KPP
learn_kpp [ p[1] ] が絶対PP
learn_kpp [ p[2] ] が相対KPP
learn_kpp [ p[3] ] が相対PP
p[4] = INT_MAX(終端)
のようになります。
もう少し一般化すると、KPPを4個に分解するとは限らず、N個の場合であっても、この設計でうまく動くことがわかります。
また、次元下げをするときにマイナスの意味にしたいところでは、indexをマイナスの値をとるという約束にします。つまり、
if (p[0] < 0)
sum = sum - learn_kpp[-p[0] ];
else
sum = sum + learn_kpp[p[0] ];
のようにマイナスをつけて解釈されるものとします。
私は上記のように設計して、このindexを与えたときにK85S32G45のようにその意味を表示する関数を用意してデバッグしていました。そうすると、自分がやっている次元下げが合理的であるかだとか、(バグがあって)間違ったindexを参照していないかだとか、そういう諸々のチェックにつながるからです。この方法は、お勧めです。
さて、上記手法をさらに一般化すると、次元下げ自体をプラグイン化することが出来ます。(画像ビュアーのJPEGプラグインとか、そういう意味でのプラグイン)
つまり
1) プラグインは、読み込みのときにlearn_kpp配列の大きさを返します。
2) プラグインは、int* make_kpp(Square king , BonaPiece p1 , BonaPiece p2)を実装します。
このようになっていれば、KPPの次元下げを行なうモジュール自体を独立させることが出来ます。
NDF方式やAWAKE方式、deep learning方式など、いろんな次元下げモジュールを組み合わせることが出来るようになります。
次元下げは比較的複数の次元下げと併用することが出来ると私は考えています。合理性のない次元下げである場合、その因子にゼロの値がつくだけであり、よほどでない限りノイズにはならないので複数の次元下げを併用したほうがいい結果につながります。
そこで、次元下げ自体をモジュール化して、複数人で開発し、そしてそのモジュールを自動的に組み合わせて自動的に棋譜からの学習をさせ、自動的に対戦させ、勝率を調べ、自動的に最強の次元下げモジュールの組み合わせを発見するというフレームワークを作ることも出来ます。
まあ…次元下げを複数やるのには結構大きなメモリ空間が必要なので、こういうことをしだすと64GBでは足りなくなってきますが…。
ともかく、次元下げモジュール自体のプラグイン化というテーマについて考えてみました。
やね裏評価関数と38要素化の比較
(前の記事のつづき)
Bonanzaのmake_listは全体時間の5〜10%程度です。38要素化ではここが差分計算化できるのでほぼゼロとなります。やね裏評価関数ではここの差分化計算化が難しいのでこの5〜10%がほぼ残ったままとなります。
評価関数の差分計算自体は、やね裏評価関数のほうが計算コストは小さくて済むのですが、make_listの5〜10%が響いてきて、トータルで38要素化に勝っているとは言いがたいです。
しかし近年、評価関数パラメーターは増大する傾向にあって、NDFのようにBonanzaの3駒関係を三角配列に格納するのではなく、正方配列に格納するのが普通です。こうすると配列の大きさはほぼ倍サイズになりますが、make_listを差分計算化すると、直列化された駒番号の順序関係が保てないので三角配列が使えなくなるので仕方がないのです。(詳しい説明は時間がないので割愛。Bonanza6のmake_list()のソースコードを読むべし)
そこで私もやねうら王2014では38要素化＋正方配列を採用するように書き換えました。ところが、近年、NDFのように評価関数に手番を盛り込んだり、今年のPonanzaのように序盤と終盤で評価関数を分けたりするのが流行りです。評価関数パラメーターの数は今後どんどん増えることは確実で、そのときに三角配列にしたほうがメモリが節約できる(ひいては、L3 cacheに収まりやすくなる)というような効果が期待できる可能性があり、もしかするとどこかで、やね裏評価関数のほうが38要素化より高速であるという状況が出てくる可能性もあります。
あるいは、やね裏評価関数のほうが配列の要素数は少なくなるので、PPP、あるいはKKPPのような純粋な3駒、あるいは4駒関係に評価関数が発展していくとき、やね裏評価関数が日の目を見ることがあるのかも知れません。
Bonanzaのmake_listの38要素化
(前の記事の続き)
次に、別のやり方として、先手が歩を3枚持っているときに「先手の1枚目の歩」「先手の2枚目の歩」「先手の3枚目の歩」のような駒があるとみなす三駒関係の設計の仕方があります。
このようにすると、盤上にない駒は手駒にあるわけで、玉以外の38駒がどこかにはあります。例えば金は盤上の53にあったとして、それが取られて相手の手駒の3枚目の金になったら、この金は、「盤上の53金」という背番号から、「相手の手駒の3枚目の金」という背番号に変わります。
このように考えると、38駒がどこに行ったのか必ず追跡することが出来ます。このため、駒をmake_listで直列化したときに必ず38要素の配列が出来ます。こうなっているほうがmake_listの差分計算化がしやすいので、こちらのほうが優れている意味があります。この方法は、去年のPonanzaが採用していました。(いまも採用しているかは知りません。)
このmake_listを38要素化したときもBonanzaのfv.binから等価に変換できることを私が発見し、そして(数学的に)証明しました。このときもKKに応じた定数が一つ出てきます。
つまり、Bonanza方式の評価関数 ≡ やね裏評価関数 ≡ 38要素化 となります。(ここでの“≡”は、相互変換可能という意味)
これをAperyの平岡さんに説明して、平岡さんがその内容が正しいことを確認しました。(今年の1月ぐらいの話)
それで、先日、平岡さんがファジー学会誌にコンピュータ将棋について寄稿するときに、「評価関数の38回ループの所、Bonanzaの実装から等価なままで変換出来る(＆ そのことを、やねうらおさんが発見した)」ことについて書いたそうです。
次回は、やね裏評価関数とこのmake_list38要素化と、どちらが優れているかについて説明します。
やね裏評価関数とは何か？
電王トーナメントのアピール文書、「やる予定」「やる予定だけど効果かどうかはわからん」みたいな書き方をしているものもたくさんありますが、ソフトがアピール文通りになっていないからと言って罰則があるわけではないのでそれを見越してやねうら王は適当ぶっこいてるんだろうと邪推している人もおられるかも知れません。
今年はどうなるかはわかりませんが、しかし、去年は私は書いている通りのことはすべてやりました。
そのなかでも一つ説明を書いていなかった、去年の電王トーナメントのときの「やね裏評価関数」について、そろそろオープンにしてもいいかと思い、これについてざっと技術的な説明をします。
Bonanzaの三駒関係では盤上の駒だけでなく、手駒もひとつの駒とみなします。「歩が3枚」「香が0枚」「桂が4枚」というような駒が存在しているものとみなします。なので、KPP(玉と2駒)のときに、「先手88の玉」×「後手の歩が0枚」×「先手の香が1枚」のような3駒関係についても評価因子としてあります。これにより、「歩切れの後手に対して先手が香を持っている」というような評価が出来るという仕組みです。
この盤上＋手駒のリストを配列に格納する処理としてBonanzaではmake_listという処理があります。これは「盤上99の先手の香」「盤上89の先手の桂」…「先手の歩が0枚」「先手の香が3枚」…「後手の角が0枚」「後手の飛車が1枚」のように、盤上すべての駒と、先手・後手のすべての駒(7種×2 = 14駒あるものとして扱う)を配列に格納します。盤上最大38枚+手駒14駒 = 最大52駒となります。将棋の開始局面では52駒あることになります。
ところが、この手駒の0枚という手駒、実は消去できます。これについて最初に言い出したのはaki.さん(Ponanzaチーム下山さん)だったと思いますが、簡単に言えばmake_listするときに0枚の手駒は配列に突っ込まないという処理にします。
make_listするときに0枚の手駒を配列に突っ込まないようにして棋譜からの学習をすれば良いわけですが、たかだかこのためだけに棋譜からの学習をやりなおすのは結構な手間だったので、Bonanzaのfv.bin(評価関数パラメーター)を何とか変形してこのときの評価関数パラメーターを導けないかを考えました。
そうすると、Bonanzaのfv.binをごちゃごちゃやると全く等価な後者の形式の評価関数パラメーターが導けて、KKに応じた定数項がただ一つだけ余分に出てくることが(数学的に)証明できました。これが「やね裏評価関数」の正体です。
序盤では52枚から38枚に減るため、KPPの計算が激減します。終盤で盤上の駒が減ると配列に突っ込まれる駒数がずいぶんと減るため、評価関数の計算コストがさらに小さくなります。
(つづく)
BMI使ってますか？
知っている人は知っているかと思いますが、Haswellになってから、Bit Manipulation Instructions Sets (BMI sets)という命令セットが使えるようになりました。
SIMD用ではないので汎用レジスタ(64bit)に対してしか使えませんが、面白い命令がいくつかあります。
例えば、PEXTというParallel bits extract命令。これはなかなか使えます。
例えば、60bit目,30bit目,12bit目を1にしたbit maskを用意したとします。このmaskを指定してPEXTを使うと、入力レジスタの60bit目と30bit目と12bit目が、結果レジスタの2bit目,1bit目,0bit目に来ます。凄いですね。magic bitboardとは何だったのかという感じです。
そもそもmagic bit boardは将棋ではテーブルサイズが大きくなりすぎて使えないと私は考えています。magic bitboardで速くなったとか言って喜んでいられるのは、評価関数テーブルが小さくてメモリ帯域が無視できているうちだけで、評価関数をうまく設計するなら、評価関数のパラメーターはメモリ帯域の限界まで大きくしたほうがソフトの棋力は上がるわけですから、magic bitboardはいずれは使えなります。
まあ、それはそれとして、PEXTを用いて、玉の周辺24近傍の駒の有無を調べてテーブルを引くために、直列化された24bitを得るなんてことも簡単に出来ます。
mask = around24[king_sq];
serial24 = _pext_u64(occupied, mask);
※ 64bitの盤面ならば。将棋では盤面は64bitに収まらないのでこのコードではうまくいきませんが応用は容易ですよね..。
