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

自力で機械学習に取り組んでおられる方もそうでない方もこんにちは!
電王トーナメント直前対策ということで、いまから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行で書けます。

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

追記 2017/06/18 19:30

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

30分でBonanzaの評価関数の要点を話します!」への12件のフィードバック

  1. やねうらおさんの既存プログラムを丸裸にする記事、毎回楽しみにしてます。

    時間があるときでいいので(笑)、GPSfishのこの点を教えてください。
    Stockfish編のthread編を読んでも分かりませんでした…(恥

    >hyper threadingが有効の場合は、弱くなってしまうかもしれません。無効に出来ない場合は、threads.h 内の以下の定数を、物理コア数に設定すると良いと思います。

    const int MAX_THREADS = 32;
    hyper threading をBIOSで無効にするのが一番良いでしょう。無効にできていれば上述の対策は不要です。

    • 例えば、4コアでもHT(Hyper Threading)ありだと論理スレッドは8スレッドあるように見えるので、スレッド数を取得するAPIを使うと8が返ってきます。

      しかし、実際は4コアしかないので4コアで探索したほうが棋力が上がるのでHTをBIOSでオフにして欲しいけど、それが出来ない人は、そのMAX_THREADSのところで物理コア数(この例では4)を指定してくださいと。

      • さっそく回答ありがとうございます。

        言葉足らずな質問ですみません。HTありで弱くなる理由が知りたかったんですよね。

        • コンピューター将棋は並列探索の効率はスレッド数(並列数)の平方根ぐらいだと言われています。(実際はもう少し良いのですが、まあ仮にそうだとして。)

          HTありで探索スレッド数を倍にすれば、2倍探索できるようになると言いたいところですが、色んなところで足を引っ張られるので1.3倍ぐらいしか探索できないようです。つまり、1スレッド当たりで言うと0.65倍ですので、元より性能が劣化しています。

          本来4コア4スレッドであれば、1コア1スレッド時と比べると(その性能が平方根だとすれば)√4 = 2倍の性能が出るはずです。

          ところが4コア8スレッドだと、0.65×√8 ≒ 1.838倍なので、これは2倍より下回ります。これがHTをオンにして探索スレッド数を増やすと弱くなる理由です。

          HTありで1.3倍のところの数字がもう少し大きくなるか、並列探索時の効率がもう少し上がるかすれば話は違ってくるのですが、まあ…いまのところHTをオンにして探索スレッドを倍にすると棋力は弱くなるというのが通説です。

          • 以前に、Apreyで、スレッド数を4,5,6,8、の4通り、持ち時間を3通り、各条件100局(先後各50局)で比較した事があるのですが、スレッド数で、5>=6>4>8 の順で勝率が良かったです。CPUは、4コアの i7 です。
            個人的には、5スレッドはありかなと思っています。

          • >色んなところで足を引っ張られるので1.3倍ぐらいしか探索できないようです。

            思っていたよりも厳しい数字で驚きました。ぼんやりとですが、HTの効果が現れ辛いものがあるというのは認識していましたが。。。

            具体的な数字を教えていただきありがとうございました。

          • 5スレッド最強説は、
            GUIなどの雑務に1スレッドを渡すことで、ピュアな処理は4スレッドで能力2倍になる計算でしょうか。
            なかなか深いですね。

          • 5スレッド最強説は、5スレッドで並列探索するの意味で、何故、これで最強になるのかと言うと、通例、HTありの4コア8スレッドですと、メモリアクセスなどが足を引っ張って効率が著しく落ちるのですが、(並列探索数が)5スレッドならそこまで足を引っ張らないというのもあるのでしょうね。

          • 将棋の現在のプログラムの場合は、各スレッドで評価(探索)が重複しており、スレッド数が増えるにしたがってこの重複が無視できなくなる(スレッド数の平方根でしか速度が伸びない。)と理解しています。
            囲碁等は、この影響が少なく(盤面が広く分担しやすい?)スレッド数に応じて比較的リニアに速度が向上するようです。
            5x5の魔方陣を解くプログラムを書いた事があるのですが、異なる初期配置から各スレッドにデータを渡せるので、重複計算はまったく無く8スレッドが最も高速でした。(5PC,40スレッドまでリニアに伸びました。)
            リソースの競合もありますが、将棋の場合、この重複計算部分が無視できないのが速度低下の主な原因かと思っています。
            (合っていますでしょうか。)

          • masaさんへ。
            >(合っていますでしょうか。)

            はい、そうですね。あと、将棋ソフトの場合、評価関数やら置換表やらでメモリアクセスが結構ありまして、CPU cacheに収まらなくて、各コアがメモリバスの帯域を取り合いしているような状況がありますね。4コアHT8スレッドのPCって4コア分ぐらいのメモリ帯域しか確保されてませんしね。

            魔法陣のプログラムが理論値(HT8スレッドで8倍)近く出るのは、データがすべてCPU cacheに載っているからというのが大きいような気はします。

  2. スレッドあたりの効率は落ちても全体では改善してるのにHTT onで棋力が落ちるのは、CPUの演算装置がbusyになって他の部分の足を引っ張るからかなと思って読んでいたら、
    物理コア数+αなら改善することもあるんですね。

    以前からの疑問が解消しました。

やねうらお へ返信する コメントをキャンセル

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