AtCoder Grand Contest 024 参加ログ

結果

 A,B,Cの3完で597位。C問題で7WAも出してしまったのが反省点だけど、簡単めとはいえ700点問題を通せたので個人的には悪くない結果だと思った。

 パフォーマンスは1621、レートは1598(+3)で、惜しくも青コーダー復帰とはならず。 f:id:tokumini:20180521093647p:plain

思考ログ

 解法はほぼ公式の解説PDFの通りなので、そこに至るまでの思考過程を中心に記録。

A問題

 300点問題なのでちょっとひねるのかなとは思いつつ、まずは愚直に式変形をしてみるとそのまま法則性が見えたのですぐAC。単純に設問の操作通り式変形して法則性が見える問題というのも多くはないだろうけど、初手としてやる価値はあるんだろう。

B問題

 抽象的に考えるのは難しそうだったので入力例を紙の上で解いてみてまずは解法を探る。

 やっていると、先頭に入れていく数字は1ずつ小さくする、末尾に入れていく数字は1ずつ大きくすることで整列した形で入れられることに気づく。そうなると挿入しないでも整列している数字が何個あるかがわかれば解けそうだという考えに至った。

 その後すぐは、もとの数列内で単調増加する最長の部分列かなと考えたけど、入力例3などでそれはダメ。で、ちょっと考えているとより厳しく1ずつ増えていく最長の部分列じゃないかという発想に至り、理屈を考えてもそれでうまくいきそうだと確認した。つまり先頭にx, x-1, ..., 1、末尾にy, y+1, ..., Nを入れていくことになるわけで、x+1 から y-1がもとの数列で整列していれば良いということ。

 あとはその実装なんだけど、競技プログラミングに慣れて一番伸びたのはこういう実装がすぐにできるところなんじゃないかと思う。

num[i] := iから始まる1ずつ増加する部分列の長さ

として、数列の後ろから見ていけばいいと考えてAC。25分弱で解けてなかなか良いペースだと感じた。

#include"bits/stdc++.h"
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> P(N);
    for (int i = 0; i < N; i++) {
        cin >> P[i];
    }

    vector<int> num(N + 2, 0);
    for (int i = N - 1; i >= 0; i--) {
        num[P[i]] = num[P[i] + 1] + 1;
    }

    cout << N - *max_element(num.begin(), num.end()) << endl;
}

C問題

 やっぱり入力例を手で解いていくわけだけど、まず先頭は0でないといけないということはすぐわかる。また連続した2つの差が2以上あるのもダメだなというのは気づいた。

 これで多分ダメなケースは弾けたと感じて最小回数の方を考えてみると、やはり後ろから山を作っていくイメージで最小になるんじゃないかと考えた。

 最終的にみるとこれでおおむね合っていたわけだけど、最小回数を求める方の実装がバグっておりWA。しかしダメな例の判定の方がバグっていそうと感じてそっちを修正しに行ってしまった。0の次に2が来る場合だけとか、0からの距離が数字以上に離れていたらダメとか、変なことを考えてWAを重ねていく。

 そのせいで最小回数を求める方のバグに気づいても負例の除去がバグっていてさらにWA。なにもわからなくなってしまいassertを仕込んで負例の除去がちゃんとできているか確認したところ、どうもそれがおかしいと気づいて、一番最初の条件に戻してやっとAC。

 一回WAを出したあと、もうちょっと冷静にどこが間違っているのか考える必要がある。これは今までに何回も思っていることなんだけど、性格にもかかわることでそう簡単に直せるものでもないなぁ。

 数列を後ろから見ていくという発想がB問題と同じだったのが多少幸運だったか。

#include"bits/stdc++.h"
using namespace std;

int main() {
    int64_t N;
    cin >> N;
    vector<int64_t> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    if (A[0] != 0) {
        cout << -1 << endl;
        return 0;
    }

    for (int i = 1; i < N; i++) {
        if (A[i] - A[i - 1] > 1) {
            cout << -1 << endl;
            return 0;
        }
    }

    uint64_t ans = 0;
    vector<int64_t> X(N, 0);
    for (int64_t i = N - 1; i >= 1; i--) {
        if (X[i] != A[i]) {
            ans += A[i];
        }
        X[i - 1] = A[i] - 1;
    }

    cout << ans << endl;
}

D問題

 問題の意味さえあまりわからなかった。なんか対称性? を作ればいいのかなという感じに思ったけど、それをグラフとしてどう実装するのかもさっぱりわからず、残り時間は座っているだけだった。1100点という数字を見るだけで思考が停止してしまうようなところがあり、ダメだなぁと感じる。

将棋ソフトの自己対局による強化学習

 評価関数の特徴量をkkp_kpptに変更し、駒割のみのゼロベクトルから自己対局による強化学習を行っています。学習用局面をsfenなどで出力することなく、ある程度の対局数を貯めてミニバッチとして更新しています。教師探索深さは3であり、ミニバッチサイズは100としました。

 このようにするメリットは自己対局によって強くなっていることを確認しながら学習を進められることであり、以下が勝率のグラフとなります。

f:id:tokumini:20180519094517p:plain

 指数移動平均を取っている勝率が52.88%を超えたら対局相手とするパラメータをアップデートしています。並列化の関係でアップデートした直後にも高い勝率が発生してしまうため、アップデートが起きたら平均を取る初期値を30%から再スタートしています。つまり上のグラフで溝の個数がパラメータのアップデート回数であり、今回は

学習時間 対局数 更新回数
7時間51分 21600局 11回

 という結果になりました。まだバグがあるようで、ここでエラーが発生しプログラムが止まってしまいました……。

 52.88%はEloレートでいうと+20であり、これが11回ということで理想的には+220、勝率では78.01%となってほしいところです。これを1手1秒,全100局による自己対局により検証してみると、

勝ち 引き分け 負け
82 13 5

 となりました。引き分けは0.5勝0.5敗とすると勝率は88.5%、Eloレートでいうと354.5の差ということになります。多少高めに出てしまいましたが、もとが駒割りのみということで、そういうこともあるのかもしれません。

 問題はこの先ちゃんと強くなるかどうかで、手元ではあまりうまくいっていません。やはり棋譜を出力していく形式でないと難しいのでしょうか。まだ教師あり学習を施した2駒関係のプログラムには勝ち越せないので、しばらくはそれを超えることを目標にやっていきたいと思います。

SIMDを用いて評価関数計算を高速化したかった話

 コンピュータ将棋において評価関数を計算する際にSIMDによって高速化する手法が知られています。

 基本的には野田さんのブログが詳しいので、深く知りたい方はそちらを参照してください。

 今僕が開発している将棋ソフトでは手番なしの絶対2駒(kp, pp)のみを評価項目として利用しており、パラメータはすべてint型(32bit)で確保しているという違いがあるため、そのままコピペでは動きません。

 命令レベルの高速化なんてさっぱりやったことないのですが、まぁやるしかないようです。

 とりあえずいきなり将棋ソフトに実装する前にテスト用のコードを書いてみました。

#include<vector>
#include<random>
#include<iostream>
#include<chrono>
#include<cassert>
#include<immintrin.h>

using namespace std;
using namespace chrono;

//疑似的なKP, PP
constexpr int K_NUM = 81, P_NUM = 1534;
int kp[K_NUM][P_NUM];
int pp[P_NUM][P_NUM];
constexpr int LIST_SIZE = 38;

int calcByForLoop(int k1, int k2, const vector<int>& list) {
    //forループで計算
    int sum = 0;
    for (int i = 0; i < LIST_SIZE; i++) {
        //KPの計算
        sum += kp[k1][list[i]];
        sum += kp[k2][list[i]];

        for (int j = i; j < LIST_SIZE; j++) {
            sum += pp[list[i]][list[j]];
        }
    }
    return sum;
}

int calcBySIMD(int k1, int k2, const vector<int>& list) {
    //SIMD計算
    int sum = 0;

    //0初期化したものを準備
    __m256i sum256 = _mm256_setzero_si256();
    for (int i = 0; i < LIST_SIZE; i++) {
        //kpはそのまま足す
        sum += kp[k1][list[i]];
        sum += kp[k2][list[i]];

        int j = i;
        for (; j + 8 < LIST_SIZE; j += 8) {
            //まずはlist[j]から8要素ロード
            __m256i indexes = _mm256_load_si256(reinterpret_cast<const __m256i*>(&list[j]));

            //indexesをオフセットとしてppから8要素ギャザー
            __m256i gathered = _mm256_i32gather_epi32(reinterpret_cast<const int*>(&pp[list[i]]), indexes, 4);

            //足し合わせる
            sum256 = _mm256_add_epi32(sum256, gathered);
        }

        for (; j + 4 < LIST_SIZE; j += 4) {
            //list[j]から4要素ロード
            __m128i indexes = _mm_load_si128(reinterpret_cast<const __m128i*>(&list[j]));

            //indexesをオフセットとしてppから4要素ギャザー
            __m128i gathered = _mm_i32gather_epi32(reinterpret_cast<const int*>(&pp[list[i]]), indexes, 4);

            //256bitに拡張
            __m256i expanded = _mm256_insertf128_si256(_mm256_setzero_si256(), gathered, 0);

            //足し合わせる
            sum256 = _mm256_add_epi32(sum256, expanded);
        }
        for (; j < LIST_SIZE; j++) {
            sum += pp[list[i]][list[j]];
        }
    }

    //64bitずらして足し合わせる
    sum256 = _mm256_add_epi32(sum256, _mm256_srli_si256(sum256, 8));

    //128bitずらして足し合わせる
    __m128i sum128 = _mm_add_epi32(_mm256_extracti128_si256(sum256, 0), _mm256_extracti128_si256(sum256, 1));

    //上位64bitを32bitずつにバラして足す
    int sum32[2];
    _mm_storel_epi64(reinterpret_cast<__m128i*>(sum32), sum128);
    sum += sum32[0];
    sum += sum32[1];

    return sum;
}

int main() {
    //適当にkp,ppの値を設定
    random_device seed_gen;
    default_random_engine engine(seed_gen());
    uniform_int_distribution<int> dist_param(-2000, 2000);

    int cnt = 1;
    for (int i = 0; i < K_NUM; i++) {
        for (int j = 0; j < P_NUM; j++) {
            kp[i][j] = dist_param(engine);
        }
    }
    for (int i = 0; i < P_NUM; i++) {
        for (int j = 0; j < P_NUM; j++) {
            pp[i][j] = dist_param(engine);
        }
    }

    //ランダムにK, Pを設定
    uniform_int_distribution<int> dist_K(0, 81);
    uniform_int_distribution<int> dist_P(0, 1534);

    constexpr int num = 1000000;

    for (int i = 0; i < num; i++) {
        int k1 = dist_K(engine), k2 = dist_K(engine);
        vector<int> list(LIST_SIZE);
        for (int i = 0; i < LIST_SIZE; i++) {
            list[i] = dist_P(engine);
        }
        assert(calcByForLoop(k1, k2, list) == calcBySIMD(k1, k2, list));
    }

    double time_of_ForLoop = 0, time_of_SIMD = 0;
    for (int i = 0; i < num; i++) {
        int k1 = dist_K(engine), k2 = dist_K(engine);
        vector<int> list(LIST_SIZE);
        for (int i = 0; i < LIST_SIZE; i++) {
            list[i] = dist_P(engine);
        }

        auto start = high_resolution_clock::now();
        calcByForLoop(k1, k2, list);
        auto end = high_resolution_clock::now();
        auto elapsed = end - start;
        time_of_ForLoop += duration_cast<duration<double>>(elapsed).count();
    }

    for (int i = 0; i < num; i++) {
        int k1 = dist_K(engine), k2 = dist_K(engine);
        vector<int> list(LIST_SIZE);
        for (int i = 0; i < LIST_SIZE; i++) {
            list[i] = dist_P(engine);
        }

        auto start = high_resolution_clock::now();
        calcBySIMD(k1, k2, list);
        auto end = high_resolution_clock::now();
        auto elapsed = end - start;
        time_of_SIMD += duration_cast<duration<double>>(elapsed).count();
    }

    cout << "ForLoop : " << time_of_ForLoop / num << endl;
    cout << "SIMD    : " << time_of_SIMD / num << endl;
}

 値が同じかどうかのチェックは抜けてくれるので計算としては合っているようです。しかし速度の結果は

ForLoop : 1.787e-08
SIMD : 1.566e-08

 と、ものすごく速くなっているわけではない感じでした。キャッシュの影響とかがあるかもしれないので導入してみないとわからないところですが、"NPS全体で約9%の高速化"というほどには至らないような気がします。手番なしの2駒関係だと恩恵が薄いということなのでしょうか。プログラムが遅いと学習にも時間がかかるためできるだけ高速化したいところですが、なかなか上手くはいかないようです。