30分でBonanzaの評価関数の要点を話します！

投稿日時: 2015年11月2日投稿者: やねうらお

自力で機械学習に取り組んでおられる方もそうでない方もこんにちは！
電王トーナメント直前対策ということで、いまから30分でBonanzaの評価関数の要点を話します。

私のほうも時間があまりないので書きなぐります。

まず、BonanzaではKKP/KPPのために駒に番号がついています。
BonanzaはC(C++ではなく)で書かれているので、この番号の格納されている型はenumですが、ここではこの型をBonaPieceと呼ぶことにします。

BonaPieceは先手の歩が0枚のとき0、先手の歩が1枚のとき1、…というように1500ほどあります。

f_hand_pawnに始まり、末尾はfe_endとなっています。

このfとかeとかfeとかは何でしょうか？

これはfはfriend、eはenemyの略です。手番側、相手番側、みたいな意味です。

とは言え、evaluate関数は先手番から見た評価値を計算したのちに、後手番であれば符号を反転させて返す設計になっているので、実質的にf = 先手 , e = 後手の意味だと考えて問題ありません。

次に評価関数の計算ですが、ΣKKPとΣKPPを計算します。fv.bin(評価関数のパラメーターの格納されているファイル)にはFV_SCALEという倍率がかけられて格納されているものとしてあるので、計算したあと、最後にFV_SCALEで割り算します。

せこいことを言わずに全部32bitで計算すれば良さそうなものですが、評価関数の特徴因子を16bitにしておかないとメモリもったいない(頻繁にアクセスするところがCPU cacheに載らない)みたいな問題や、置換表に格納するときに評価値が16bit程度であって欲しいだとか、将棋所などのGUIに出力するときに「私の評価値は530000です」のように表示されても、ゼロの数をかぞえるのが大変であるなど、さまざまな問題があって、FV_SCALEを掛け算したものを格納しておき、evaluateの最後ではFV_SCALEで割ったものを返すようにしてあります。

BonaPieceの番号の問題にちょっと話を戻します。

先手の歩や香は1段目には置けないので、Bonanzaではここの番号を不要として詰めてあります。(先手の1,2段目の桂、後手の9段目の歩・香、8,9段目の桂についても同様)

また、KKPのPの番号とKPPのPの番号は違います。kkpのほうはkkp_hand_pawnみたいな定数が出てきます。ここにはfもeもついていません。どうしてかというと、KKPのPは先手から見た駒だと仮定しているからです。

KKPについて、kkp[k1][k2][p]というようにテーブルを参照するとして、後手のpに対しては、盤面を180度回転させて(ひふみんアイで見た)kkp[Inv(K2)][Inv(K1)][InvPiece(p)]の値の符号を反転させたものだというわけですね。

※ Inv(sq)は盤面を180度回転させた升を返す関数。Inv(sq) = 80-sq 。
※ InvPiece(p)は盤面を180度回転させたときの駒を返す関数。[例] InvPiece(先手の78の金) = 後手の23の金

こうしておけば、pを先手の駒だとして計算できるので、テーブルサイズがおおよそ半分で済みますし、180度盤面を回転させたkkpとは符号違いで同じ値になりますので、一種の次元下げのような効果があるわけですね。いまどきの機械学習のテクニックでは、また違ってくるのですが、当時は次元下げは主流ではなかったので、次元下げの代わりにこういうテクニックが使われています。

要するに、p1を先手の駒、p2を後手の駒として
ΣKKP = Σkkp[k1][k2][p1] – Σkkp[Inv(k2)][Inv(k1)][InvPiece(p2)]
ってことですね。

Aperyなどいまどきのソフトでは、KKPのPの番号とKPPのPの番号は同じものを割り振っておくのが主流です。そうしてあれば、KPPの計算のついでにKKPの計算も出来ますからね。

次に、KPPの計算について説明します。

ここでもテーブルサイズを縮小するためにkpp[k][p1][p2]において、p1 <= p2という大小関係を仮定しています。これでテーブルサイズはおおよそ半分になります。そしてさきほどと同様に次元下げの代わりにもなります。p1 > p2なら、p1とp2を入れ替えてしまえばいいわけですね。実際には、ソートしておけばループの内側でこの大小比較は不要になります。

また、KPPテーブルも先手から見たテーブルとなっているので、後手から見たKPPを計算するときは、kpp[Inv(k2)][InvPiece(p2)][InvPiece(p1)]のようになります。

つまり、k1を先手玉の升、k2を後手玉の升として、p1 <= p2の関係があるとして、
ΣKPP = ΣΣ kpp[k1][p1][p2] – ΣΣkpp[Inv(k2)][InvPiece(p2)][InvPiece(p1)]
となります。

ここで察しのいい人は気づいたかも知れません。p1 == p2のケースは不要なのじゃないかと。

kppにおける、p1 == p2は、結局、KPです。これはkkpに載せておけば、kppで計算する必要はなくなります。

保木さんに7年ぐらい前に私がそのことについてメールで質問したとき、「KKPに含めてしまうとうまく学習できないかも知れないのでこれはこれで…」みたいな回答を頂戴しました。

当時はいまのような次元下げのテクニックがなかったので、そうするのが正しい選択だったのでしょう。いまどきのソフトではきちんと次元下げをしてKKPのほうに含めてしまい、p1 == p2のケースは計算しないのが普通だと思います。ただし、差分計算をするときにp1 == p2のケースを除外しようとするとループを展開できなかったりするので、kppのp1 == p2の要素には0を突っ込んでおくのがよろしいかと思います。

ここで察しのいい人はもう一つ気づいたことがあるかも知れません。KKPとKPPの駒番号をBonaPieceで統一するなら、

ΣKKP = Σkkp[k1][k2][p]

と単純に書くことが出来るようになります。ところが、これはさきほどのΣKPPと比較すると

ΣKPP = ΣΣ kpp[k1][p1][p2] – ΣΣkpp[Inv(k2)][InvPiece(p2)][InvPiece(p1)]

のようになっており、前者に出てくるのはk2で後者はInv(k2)です。後者はkppテーブルを先手から見たときと後手から見たときとで使いまわしているので後者のInv(k2)は変更できませんが、前者のk2は変更できます。つまりkkpテーブルの第二添字は、Inv(sq)を指定するものとしてテーブルをひっくり返して(?)おけば、前者の式は

ΣKKP = Σkkp[k1][Inv(k2)][p]

と書くことが出来ます。これにより、ΣKKPとΣKPPからk2が消え、すべてInv(k2)で統一できます。大変せこい、本当にセコすぎてこんなことしている人は女性にモテないんじゃないかと思えるほどですが、これはAperyの平岡さんのアイデアです。(笑)

3年ぐらい前に平岡さんにこれを教えてもらったときに「せこい、ほんま、平岡さんはせこい！(褒め言葉)」と思わず連呼してしまいました。

さて、Inv(k2)で統一できたのでΣKKPの計算はΣKPPの計算のループのなかに入れることが出来ます。さきほどのp1==p2のケースをKKPに載せてあるものとして、かつ、FV38はやっているものとします。FV38については以下の記事をどうぞ。

Bonanzaのmake_listの38要素化
http://d.hatena.ne.jp/LS3600/20141024

ここまですれば先手から見た評価値を返す関数は以下のようになります。わずか10行で書けます。

Square k1 = pos.king_square(BLACK);
Square k2 = Inv(pos.king_square(WHITE));
sum = 0;
for(int i = 0 ; i < 38 ; ++ i)
{
 sum += kkp[k1][k2][p[i]]
 for(int j = 0 ; j < i ; ++j)
   sum += kpp[k1][p[i]][p[j]] - kpp[k2][InvPiece(p[j])][InvPiece(p[i])];
}
return sum / FV_SCALE;

Square k1 = pos.king_square(BLACK);

Square k2 = Inv(pos.king_square(WHITE));

sum = 0;

for(int i = 0 ; i < 38 ; ++ i)

{

sum += kkp[k1][k2][p[i]]

for(int j = 0 ; j < i ; ++j)

sum += kpp[k1][p[i]][p[j]] - kpp[k2][InvPiece(p[j])][InvPiece(p[i])];

}

return sum / FV_SCALE;

おっと、時間が来てしまいました。今回はここまで。

追記 2017/06/18 19:30

KPP高速化技法について : 以上をまとめますと、KPP = ΣBKPP + ΣWKPPでWKPPを求めるときに、BKPPで用いているテーブルを使いまわしたいのでWKPPのPを180度回転させたものを用いて、BKPPのテーブルをlook upしているわけです。しかしPを180度回転させる処理が必要なので、もしメモリに余裕があるならWKPP用のテーブルも用意したほうが高速化するはずです。(CPU cache汚染の問題があって単純ではないかも..)