【連載】評価関数を作ってみよう！その7

前回の続き。今回は、テーブルを作って高速化します。

評価関数テーブルの導入

int16_t effect_table[先手玉のいる升][後手玉のいる升][対象升][その升の先手の利きの数][その升の後手の利きの数]

というテーブルを考えましょう。1升の利きは最大で10個ですのです。(0個も含めると11通り)

このテーブルサイズは、81×81×81×11×11×size_of(int16_t) ≒ 128MB となります。

ここに対象升にある駒も加えたいですが、駒は先後の区別ありだと、成り駒も含めて、やねうら王では32通り(未使用の番号あり)なので、テーブルサイズが128MBの32倍(= 4GB)となります。いまどきのPCであればどうってことのないサイズですが、32bit OSでは確保できないサイズですし、1GB以上のテーブルを導入するのはいまはやめておきましょう。

// 利きの価値を合算した値を求めるテーブル
// &#91;先手玉の升]&#91;後手玉の升]&#91;対象升]&#91;その升の先手の利きの数]&#91;その升の後手の利きの数]
// 81*81*81*11*11*size_of(int16_t) = 128MB
int16_t effect_table&#91;SQ_NB]&#91;SQ_NB]&#91;SQ_NB]&#91;11]&#91;11];

void init() {

    // 王様からの距離に応じたある升の利きの価値。
    int our_effect_value&#91;9];
    int their_effect_value&#91;9];

    // 利きが一つの升に複数あるときの価値
    // 1024倍した値を格納する。
    // optimizerの答えは、{ 0 , 1024/* == 1.0 */ , 1800, 2300 , 2900,3500,3900,4300,4650,5000,5300 }
    //   6365 - pow(0.8525,m-1)*5341 　みたいな感じ？
    int multi_effect_value&#91;11];

    for (int d = 0; d &lt; 9; ++d)
    {
        // 利きには、王様からの距離に反比例する価値がある。
        our_effect_value&#91;d]   = 85 * 1024 / (d + 1);
        their_effect_value&#91;d] = 98 * 1024 / (d + 1);
    }

    // 利きがm個ある時に、our_effect_value(their_effect_value)の価値は何倍されるのか？
    // 利きは最大で10個のことがある。
    for (int m = 0; m &lt; 11; ++m)
        multi_effect_value&#91;m] = m == 0 ? 0 : int(6365 - std::pow(0.8525, m - 1) * 5341);

    // 利きを評価するテーブル
    //    &#91;自玉の位置]&#91;対象となる升]&#91;利きの数(0～10)]
    int our_effect_table  &#91;SQ_NB]&#91;SQ_NB]&#91;11];
    int their_effect_table&#91;SQ_NB]&#91;SQ_NB]&#91;11];

    for(auto king_sq : SQ)
        for (auto sq : SQ)
            for(int m = 0 ; m &lt; 11 ; ++m) // 利きの数
            {
                // 筋と段でたくさん離れているほうの数をその距離とする。
                int d = dist(sq, king_sq);

                our_effect_table  &#91;king_sq]&#91;sq]&#91;m] = multi_effect_value&#91;m] * our_effect_value  &#91;d] / (1024 * 1024);
                their_effect_table&#91;king_sq]&#91;sq]&#91;m] = multi_effect_value&#91;m] * their_effect_value&#91;d] / (1024 * 1024);
            }

    // ある升の利きの価値のテーブルの初期化
    for (auto king_black : SQ)
        for (auto king_white : SQ)
            for (auto sq : SQ)
                for(int m1 = 0; m1&lt;11;++m1) // 先手の利きの数
                    for (int m2 = 0; m2 &lt; 11; ++m2) // 後手の利きの数
                    {
                        int score = 0;
                        score += our_effect_table  &#91;    king_black ]&#91;    sq ]&#91;m1];
                        score -= their_effect_table&#91;    king_black ]&#91;    sq ]&#91;m2];
                        score -= our_effect_table  &#91;Inv(king_white)]&#91;Inv(sq)]&#91;m2];
                        score += their_effect_table&#91;Inv(king_white)]&#91;Inv(sq)]&#91;m1];
                        effect_table&#91;king_black]&#91;king_white]&#91;sq]&#91;m1]&#91;m2] = int16_t(score);
                    }

}

Value compute_eval(const Position&amp; pos) {

    auto score = pos.state()->materialValue;

    for (auto sq : SQ)
    {
        // 盤上の升の利きの価値
        score += effect_table&#91;pos.king_square(BLACK)]&#91;pos.king_square(WHITE)]&#91;sq]&#91;pos.board_effect&#91;BLACK].effect(sq)]&#91;pos.board_effect&#91;WHITE].effect(sq)];

        auto pc = pos.piece_on(sq);
        if (pc == NO_PIECE)
            continue;

        // 盤上の駒に対しては、その価値を1/10ほど減ずる。
        auto piece_value = PieceValue&#91;pc];
        score -= piece_value * 104 / 1024;
    }

    return pos.side_to_move() == BLACK ? score : -score;
}

// 利きの価値を合算した値を求めるテーブル

// [先手玉の升][後手玉の升][対象升][その升の先手の利きの数][その升の後手の利きの数]

// 81*81*81*11*11*size_of(int16_t) = 128MB

int16_t effect_table[SQ_NB][SQ_NB][SQ_NB][11][11];

void init() {

// 王様からの距離に応じたある升の利きの価値。

int our_effect_value[9];

int their_effect_value[9];

// 利きが一つの升に複数あるときの価値

// 1024倍した値を格納する。

// optimizerの答えは、{ 0 , 1024/* == 1.0 */ , 1800, 2300 , 2900,3500,3900,4300,4650,5000,5300 }

// 6365 - pow(0.8525,m-1)*5341 　みたいな感じ？

int multi_effect_value[11];

for (int d = 0; d < 9; ++d)

{

// 利きには、王様からの距離に反比例する価値がある。

our_effect_value[d] = 85 * 1024 / (d + 1);

their_effect_value[d] = 98 * 1024 / (d + 1);

}

// 利きがm個ある時に、our_effect_value(their_effect_value)の価値は何倍されるのか？

// 利きは最大で10個のことがある。

for (int m = 0; m < 11; ++m)

multi_effect_value[m] = m == 0 ? 0 : int(6365 - std::pow(0.8525, m - 1) * 5341);

// 利きを評価するテーブル

// [自玉の位置][対象となる升][利きの数(0～10)]

int our_effect_table [SQ_NB][SQ_NB][11];

int their_effect_table[SQ_NB][SQ_NB][11];

for(auto king_sq : SQ)

for (auto sq : SQ)

for(int m = 0 ; m < 11 ; ++m) // 利きの数

{

// 筋と段でたくさん離れているほうの数をその距離とする。

int d = dist(sq, king_sq);

our_effect_table [king_sq][sq][m] = multi_effect_value[m] * our_effect_value [d] / (1024 * 1024);

their_effect_table[king_sq][sq][m] = multi_effect_value[m] * their_effect_value[d] / (1024 * 1024);

}

// ある升の利きの価値のテーブルの初期化

for (auto king_black : SQ)

for (auto king_white : SQ)

for (auto sq : SQ)

for(int m1 = 0; m1<11;++m1) // 先手の利きの数

for (int m2 = 0; m2 < 11; ++m2) // 後手の利きの数

{

int score = 0;

score += our_effect_table [ king_black ][ sq ][m1];

score -= their_effect_table[ king_black ][ sq ][m2];

score -= our_effect_table [Inv(king_white)][Inv(sq)][m2];

score += their_effect_table[Inv(king_white)][Inv(sq)][m1];

effect_table[king_black][king_white][sq][m1][m2] = int16_t(score);

}

Value compute_eval(const Position& pos) {

auto score = pos.state()->materialValue;

for (auto sq : SQ)

{

// 盤上の升の利きの価値

score += effect_table[pos.king_square(BLACK)][pos.king_square(WHITE)][sq][pos.board_effect[BLACK].effect(sq)][pos.board_effect[WHITE].effect(sq)];

auto pc = pos.piece_on(sq);

if (pc == NO_PIECE)

continue;

// 盤上の駒に対しては、その価値を1/10ほど減ずる。

auto piece_value = PieceValue[pc];

score -= piece_value * 104 / 1024;

}

return pos.side_to_move() == BLACK ? score : -score;

}

評価関数本体がわずか13行になりました。(その代わり、テーブル初期化のコードが少し長くなってきましたが)

これでどれだけ強くなるの？

これでnps(探索速度)は2,3割増し。+R70ぐらい強くなります。
Ryzen Threadripper 3990XでR2620～2720程度でしょうか。(もう少し強いかも)

奨励会三段、あるかないかぐらいでしょうか。もう少しテーブルをシュリンクすることを考えましょう。

N個以上の利きはN個と同一とみなす

では、N個以上の利きがある場合、それをN個の利きだとみなすとしたら？

N = 2でいいなら、利きは 0(なし),1(1個),2(2個以上)の3通りで済みます。

そうすると、対象升の駒(32通り)を追加しても、81×81×81×3×3×32×sizeof(int16_t) ≒ 306MBのテーブルサイズとなります。これなら、メモリに収まりそうですね。

ちょっと待ってください。それだと弱くなりませんか？

実験したところ N = 2 の場合、元のと同じぐらいの強さでした。

N = 3だとR10ほど強かったです。(その代わりテーブルサイズがN = 2の9/4倍)

N = 4だとN = 2のときとほぼ同じ強さでした。これは、テーブルサイズが4倍(×306MB = 1224MB)になり、CPU cacheにあまり載らなくなってしまうため、探索速度が落ちるからだと思われます。N = 5以降はほぼ変わりませんでした。

いまはまだ利きの価値ぐらいしか評価しておらず、それ以上に色々評価しだすと、N = 3よりN = 4のほうが強いとなるかも知れませんが、いまのところ、N = 2で十分そうです。

NNUE評価関数で駒のある升の利きも考慮するように拡張された、NNUE halfKPE9という評価関数があるのですが(tttakさん作)、これは先手の利き3通り(なし、1個、2個以上)、後手の利きも3通りで、組み合わせとして3×3 = 9通りあるので「E9」が評価関数名の末尾についています。

NNUE halfKPE9の拡張として先手、後手の利きを4通り(なし、1個、2個、3個以上)にすればhalfKPE16とか、利きを5通りにすればhalfKPE25とか、そちらのほうが強いのではないか？と誰しも思うところではありますが、上の実験からすると、強くなる量はごくわずかであり、その分、CPU cacheに載らなくなり探索速度が落ちるのであまり強くならないのではないかと予想されます。

評価関数本体、わずか7行になったんですけど？

まあそんなわけで、駒も合わせたテーブルを用意しました。

先後の王様、対象升の駒、そこの先後の利き(3通り×3通り)なので、この評価関数をKKPEE9と呼ぶことにします。(言いにくいのでKKPE9でも可)

// 利きの価値を合算した値を求めるテーブル
// &#91;先手玉の升]&#91;後手玉の升]&#91;対象升]&#91;その升の先手の利きの数(最大2)]&#91;その升の後手の利きの数(最大2)]&#91;駒(先後区別あり)]
// 81*81*81*3*3*size_of(int16_t)*32 = 306MB
// 1つの升にある利きは、2つ以上の利きは同一視。
int16_t KKPEE&#91;SQ_NB]&#91;SQ_NB]&#91;SQ_NB]&#91;3]&#91;3]&#91;PIECE_NB];

// 利きの価値を合算した値を求めるテーブル

// [先手玉の升][後手玉の升][対象升][その升の先手の利きの数(最大2)][その升の後手の利きの数(最大2)][駒(先後区別あり)]

// 81*81*81*3*3*size_of(int16_t)*32 = 306MB

// 1つの升にある利きは、2つ以上の利きは同一視。

int16_t KKPEE[SQ_NB][SQ_NB][SQ_NB][3][3][PIECE_NB];

そうしますと、評価関数本体は、駒割に加えて、盤上の各升(81升)に対して、このテーブルを表引きして加算(81回)するだけのシンプルな構造になります。わずか7行。変数名をもう少し短くすれば140文字に収まるので１ツイートでつぶやけます。1ツイートでつぶやける評価関数ってヤバくないですか？😊

Value compute_eval(const Position&amp; pos) {

    auto score = pos.state()->materialValue;

    for (auto sq : SQ)
        score += KKPEE&#91;pos.king_square(BLACK)]&#91;pos.king_square(WHITE)]&#91;sq]
            &#91;std::min(int(pos.board_effect&#91;BLACK].effect(sq)),2)]&#91;std::min(int(pos.board_effect&#91;WHITE].effect(sq)),2)]&#91;pos.piece_on(sq)];

    return pos.side_to_move() == BLACK ? score : -score;
}

Value compute_eval(const Position& pos) {

auto score = pos.state()->materialValue;

for (auto sq : SQ)

score += KKPEE[pos.king_square(BLACK)][pos.king_square(WHITE)][sq]

[std::min(int(pos.board_effect[BLACK].effect(sq)),2)][std::min(int(pos.board_effect[WHITE].effect(sq)),2)][pos.piece_on(sq)];

return pos.side_to_move() == BLACK ? score : -score;

}

初期化処理は少し長くなってきましたが、まあ許容範囲でしょう…。

void init() {

    // 王様からの距離に応じたある升の利きの価値。

    int our_effect_value&#91;9];
    int their_effect_value&#91;9];

    for (int d = 0; d &lt; 9; ++d)
    {
        // 利きには、王様からの距離に反比例する価値がある。
        our_effect_value&#91;d]   = 83 * 1024  / (d + 1);
        their_effect_value&#91;d] = 92 * 1024  / (d + 1);
    }

    // 利きが1つの升にm個ある時に、our_effect_value(their_effect_value)の価値は何倍されるのか？
    // 利きは最大で10個のことがある。格納されている値は1024を1.0とみなす固定小数。
    // optimizerの答えは、{ 0 , 1024/* == 1.0 */ , 1800, 2300 , 2900,3500,3900,4300,4650,5000,5300 }
    //   6365 - pow(0.8525,m-1)*5341 　みたいな感じ？

    int multi_effect_value&#91;11];

    for (int m = 0; m &lt; 11; ++m)
        multi_effect_value&#91;m] = m == 0 ? 0 : int(6365 - std::pow(0.8525, m - 1) * 5341);

    // 利きを評価するテーブル
    //    &#91;自玉の位置]&#91;対象となる升]&#91;利きの数(0～10)]
    double our_effect_table  &#91;SQ_NB]&#91;SQ_NB]&#91;11];
    double their_effect_table&#91;SQ_NB]&#91;SQ_NB]&#91;11];

    for(auto king_sq : SQ)
        for (auto sq : SQ)
            for(int m = 0 ; m &lt; 3 ; ++m) // 利きの数
            {
                // 筋と段でたくさん離れているほうの数をその距離とする。
                int d = dist(sq, king_sq);

                our_effect_table  &#91;king_sq]&#91;sq]&#91;m] = double(multi_effect_value&#91;m] * our_effect_value  &#91;d]) / (1024 * 1024);
                their_effect_table&#91;king_sq]&#91;sq]&#91;m] = double(multi_effect_value&#91;m] * their_effect_value&#91;d]) / (1024 * 1024);
            }

    // ある升の利きの価値のテーブルの初期化
    for (auto king_black : SQ)
        for (auto king_white : SQ)
            for (auto sq : SQ)
                for(int m1 = 0; m1&lt;3;++m1) // 先手の利きの数
                    for (int m2 = 0; m2 &lt;3; ++m2) // 後手の利きの数
                        for(Piece pc = NO_PIECE;pc &lt; PIECE_NB ; ++pc) // 駒(先後の区別あり)
                        {
                            double score = 0;

                            score += our_effect_table  &#91;    king_black ]&#91;    sq ]&#91;m1];
                            score -= their_effect_table&#91;    king_black ]&#91;    sq ]&#91;m2];
                            score -= our_effect_table  &#91;Inv(king_white)]&#91;Inv(sq)]&#91;m2];
                            score += their_effect_table&#91;Inv(king_white)]&#91;Inv(sq)]&#91;m1];

                            if (pc != NO_PIECE)
                            {
                                // 盤上の駒に対しては、その価値を1/10ほど減ずる。
                                auto piece_value = PieceValue&#91;pc];
                                score -= piece_value * 104 / 1024;
                            }

                            KKPEE&#91;king_black]&#91;king_white]&#91;sq]&#91;m1]&#91;m2]&#91;pc] = int16_t(score);
                        }

}

void init() {

// 王様からの距離に応じたある升の利きの価値。

int our_effect_value[9];

int their_effect_value[9];

for (int d = 0; d < 9; ++d)

{

// 利きには、王様からの距離に反比例する価値がある。

our_effect_value[d] = 83 * 1024 / (d + 1);

their_effect_value[d] = 92 * 1024 / (d + 1);

}

// 利きが1つの升にm個ある時に、our_effect_value(their_effect_value)の価値は何倍されるのか？

// 利きは最大で10個のことがある。格納されている値は1024を1.0とみなす固定小数。

// optimizerの答えは、{ 0 , 1024/* == 1.0 */ , 1800, 2300 , 2900,3500,3900,4300,4650,5000,5300 }

// 6365 - pow(0.8525,m-1)*5341 　みたいな感じ？

int multi_effect_value[11];

for (int m = 0; m < 11; ++m)

multi_effect_value[m] = m == 0 ? 0 : int(6365 - std::pow(0.8525, m - 1) * 5341);

// 利きを評価するテーブル

// [自玉の位置][対象となる升][利きの数(0～10)]

double our_effect_table [SQ_NB][SQ_NB][11];

double their_effect_table[SQ_NB][SQ_NB][11];

for(auto king_sq : SQ)

for (auto sq : SQ)

for(int m = 0 ; m < 3 ; ++m) // 利きの数

{

// 筋と段でたくさん離れているほうの数をその距離とする。

int d = dist(sq, king_sq);

our_effect_table [king_sq][sq][m] = double(multi_effect_value[m] * our_effect_value [d]) / (1024 * 1024);

their_effect_table[king_sq][sq][m] = double(multi_effect_value[m] * their_effect_value[d]) / (1024 * 1024);

}

// ある升の利きの価値のテーブルの初期化

for (auto king_black : SQ)

for (auto king_white : SQ)

for (auto sq : SQ)

for(int m1 = 0; m1<3;++m1) // 先手の利きの数

for (int m2 = 0; m2 <3; ++m2) // 後手の利きの数

for(Piece pc = NO_PIECE;pc < PIECE_NB ; ++pc) // 駒(先後の区別あり)

{

double score = 0;

score += our_effect_table [ king_black ][ sq ][m1];

score -= their_effect_table[ king_black ][ sq ][m2];

score -= our_effect_table [Inv(king_white)][Inv(sq)][m2];

score += their_effect_table[Inv(king_white)][Inv(sq)][m1];

if (pc != NO_PIECE)

{

// 盤上の駒に対しては、その価値を1/10ほど減ずる。

auto piece_value = PieceValue[pc];

score -= piece_value * 104 / 1024;

}

KKPEE[king_black][king_white][sq][m1][m2][pc] = int16_t(score);

}

計算精度足りてる？

利きの価値自体は端数がわりと出るので、途中まではdouble(倍精度浮動小数点数)で計算しています。テーブル自体はint16_t(16bit符号つき整数)ですが、それぞれの値は小さいので、テーブル自体を32倍にしておいて、評価関数本体で81升分足し合わせたのちに32で割るほうが計算精度は上がります。古くはBonanzaにFV_SCALEという定数(32)があって、そんな処理をしていました。

いまのところ余り細かいチューニングはしていないのでそこまでしなくてもあまり意味はありませんが、実行時にコストが追加でかかるわけでもなく(32で割るのはシフト演算で済むのでほぼノーコスト)、計算精度が32倍になるのは美味しいので、やっておきます。

KKPEE9で強くなった？

KKPEE9化ではほとんど強くなってません。しかし、駒も含めたテーブルになったことにより、当たりになっている駒の点数を減点するなど、事前にいくらでも計算してこのテーブルに書き込んでおくことができるので、可能性はずいぶん広がりました。

テーブルの事前計算はいくら複雑なことをやっても、探索時に評価関数の処理時間が増えるわけではないので、どんどん複雑なことを試せます。

将棋ベーシックのこと

先日の電竜戦に『将棋ベーシック』というVisual Basicで書かれた将棋ソフトが出場していました。その棋力は3級程度だそうで、いまどきの将棋ソフトと比べると弱い部類に入るソフトなのですが、面白い特徴があったのでここ取り上げたいと思います。ちなみに、この作者の宮澤さんと私は15年来の知り合いです。

以下、将棋ベーシック PR文書より引用します。

強くするポイントは事前にモンテカルロ法からアルファベータ探索に切り替え、駒得を狙うようにしてから、探索深度を深くすると思考時間が長くなるために、探索深度を深くしないで盤面評価するときに盤の駒と手駒の合計得点以外に「自駒に他の自駒の行き先が効いているか」という点に歩を100点と換算したときに駒利きに1点の評価値を付加しました。
これにより、駒得に於いて互角局面となる時に互いの駒が効き合うように駒を固めて守るようになり、手詰まりで全手互角で候補手行列の端に当たる端歩や行列を逆読みした時の端歩の反対の香上げなどを指してしまう局面で待ち手を金上げなどの囲い有効手として評価させることに成功しました。
問題点としては駒の利きと駒の点数に相関関係はなく、玉も歩も同じように守ると1点、効いている駒が多いと高得点となるので、58金のように歩をたくさん守る手に出てしまうこと。ここを改良できればさらに強くなりそうです。ここに課題を残します。
電竜戦将棋ベーシック PR文書
https://drive.google.com/file/d/1iNSeQLfA96IST6P7VZMC2dXcNgAvX2-7/view

このPR文書には、「自駒に他の自駒の行き先が効いているか」(ある駒に味方の利きがあるか)に対して1点加点すると書いてあります。

これだけで、「互いの駒が効き合うように駒を固めて守るように」なったそうで、たった1点足すだけで棋風が大きく変わるという、将棋ソフトの面白さが垣間見えます。

ある駒に味方の利きがあるときの評価

駒に味方の利きがある時、どのようにこれを評価すれば良いのでしょうか？

タダ取りされることを防ぐ意味からすれば、味方利きがあることでタダ取りが防げるので、利きがあれば、その駒の価値×10%のような、その駒の価値に比例する何らかの価値が生じてそうに思えます。

逆にある駒に相手の利きがあれば、これは質(しち)に入っている(何かの時に取られかねない)わけですから、これまた、その駒の価値×20%のような、その駒の価値に比例する何らかのペナルティが生じてそうに思えます。

この仮説は正しいのでしょうか？optimizerに聞いてみました。

次回予告

次回「将棋ベーシック、敗れる！」です。お楽しみに！(予告とは、異なる内容の場合がございます。予めご了承願います。)

つづく