ICPC2018国内予選参加記

チーム紹介

 ICPC2018国内予選に、CatKOderというチームの一員として参加しました。メンバーは次の通りです。

 CatKOderのt担当、tokumini(@kaitei_shogi)です。基本的には将棋ソフトの開発をメインでやっており、競技プログラミングは毎週AtCoderのコンテストにだけ出ています。

 AtCoderのレートはチームの中では僕が一番高くて1556。一度偶然にも青コーダーになったことはありますが、実力は1500中盤くらいだと思っています。

f:id:tokumini:20180707082411p:plain

 あと二人は僕の少し下くらいですかね?(よく知らない) そこまで大きな差はなく、バランスの取れたチームという感じです。

結果

 4完1WAで52位でした。

f:id:tokumini:20180706233252p:plain

 大した順位ではありませんが、学内ではトップということで予選抜けらしいです。嬉しい。

当日まで

 そもそも僕はほぼAtCoderしかやってない人間で、ICPCは存在を認識している程度でした。後にチームを組むことになるalbicilla氏に声をかけられたのが2か月くらい前のことで、そこから学内で行われている競技プログラミングの練習会等に参加しICPC対策を始めました。ICPCの問題はAtCoderとは毛色が違う印象があり、2か月という付け焼き刃的なものでしたが効果は大きかったと思います。

本番

 方針としては二人がA,Bを解いて、僕はCと残りからどれか簡単そうなの一つを解くという完全分業制。考察/実装という分け方をしているチームもあるみたいだけど、日頃やってた練習会でうまく考えを伝えられないことがあったのでこういう感じに。

 開始してすぐに僕はC問題へ。20分くらいで解法に気づく。Aはもう通してくれてて、Bも通してくれるのを待とうと思っていたけど、どうも手こずっているようだったので機を見て先にCを書かせてもらった。最初に考えていた式が間違っていて一瞬焦ったけどすぐ修正できてAC。Bは読んでないのでよくわからないけど、Cよりも実装が重い感じだったらしいのでもっと早めに書きにいっても良かったかもしれない。

 D以降をサラッと眺めて第一感で解きやすそうなのはDかEかなという印象で、ちょくちょく順位表をチラ見してもDを解いているところが多かったので本格的にDを考え始める。

  2^{81}は通らないよなーということで、何かしら状態を上手く持つタイプの問題だと思った。しかしさっぱり思いつかずしばらく時間が経つ。チームメンバーもB問題に結構手間取っていて、ここら辺はちょっと暗雲が立ち込めているという感じだった。

 しばらくして状態を減らせばなんかメモ化再帰っぽいことがやれそうと思いついた。後から振り返ると意味不明なんだけど、この時はそれで通ると勘違いしたのでメンバーがBを通してからDを書き始める。

 しかしどうもサンプルの最後の3つあたり、数が大きくなると答えが合わず、うんうん唸っているうちに残り40分くらいになる。同じ状態に2回以上訪問しない全探索なのでメモ化しているのが無駄で、途中でなんとなく入れた枝刈りが本質だったみたい。しかし解いているときはそんなことには気づかない。

 もうD以外に行く時間はないと思ったので他の問題を考えていたチームメンバーにもDへの救援を要求し、サンプルを作ってもらったりコードを読んでもらったりした中で、メモ化がバグってそうなんだよねーとメモを調べて返す部分をコメントアウトすると上手くいくことに気づく。ここで残り15分くらい。しかしこれでは時間がかかって間に合わない……とか思いながらプログラムを放置していたらなんかそれなりな時間で計算が終わっていた。「じゃあそれで出してみりゃいいんじゃね?」というチームメンバーの一声でとりあえずデータ落として回したらそこそこの時間で計算が終わる。1個目のデータが無事通ったので2番目のデータも同様に数分待ってAC。メモ化に思考が囚われていたので愚直な全探索っていうのは完全に自分では思いつかなかった。チームに救われたACだった。

 改めて順位表を見るとDを通したのが2:51:10でかなりぎりぎり。本当に危なかった。

反省

 始める前は基本的に4完早解きを目指していて、あわよくば5完を、という感じだった。本番だとDを解けるかどうかすら怪しかったわけで目標は目標にすぎなかった。

 しかしDで詰まっていたところで、いいタイミングでチームメンバーに助言を求めることができたのは良かったと思う。一人でやっていたら確実にハマっていた。チーム戦の良さを存分に活かすことができた。

 個人としてはやはりD問題で苦しんでしまったのが反省点。意味のないメモ化をしていたり、計算量を全く把握できていなかったり、冷静さが足りなかった。自分がどういうコードを書いているのかはっきりとわかっていないまま書いていた感じもあって、通せたのは本当に運が良かっただけだった。

 次の機会も貰えそうだということで、また頑張ります。

2018W杯予選・日本vsポーランドで面白かったところ

はじめに

 日本時間で昨夜から今日にかけて行われた2018ワールドカップ予選・日本vsポーランドの試合は、最終的に0-1で日本が敗れる結果となりましたが、セネガルと勝ち点や得失点差、総得点数などで並んだ結果、フェアプレーポイントの差により日本が決勝トーナメント進出となりました。

 終盤には同時に行われていたセネガルvsコロンビア戦がコロンビアリードで進行していることを受け、両試合がこのままのスコアで行けば日本が予選抜けとなる状況になっていました。その結果、日本は攻める様子を見せず最終ライン付近でボールを回し時間が切れるのを待つ戦術を取り、そのことが話題となっています。

 私もこの試合をリアルタイムで視聴していたわけですが、善悪を超えてここにエンターテイメントがあるということを感じて一人でかなり盛り上がっていました。時間つぶしが倫理的に良かったかどうか、あるいは戦略的に最善であったかどうかには触れず、ここからはこの時間つぶしに感じたエンタメ性についてできるだけ言語化していきたいと思います。

 私が感じたエンタメ性はおおむね以下の2点となります。

  • 大舞台で行われる博打に漂う強い感情
  • ファンの祈りと転倒

 この2点について詳しく書いていきます。

博打と強い感情

 先ほど「両試合がこのままのスコアで行けば」と書いた通り、時間つぶしの戦略を取った時点で予選抜けの命運は日本の手から離れました。全てはセネガルvsコロンビアの戦いがどうなるかに委ねられ、これは大きな博打であったと思います。

 まず一つ目のエンタメ性は単純に大博打がこの大舞台で行われたという事実で、私は長谷部投入からの明確な意思表示を観て「よくやるなぁ!」と感じたものです。

 そしてこの博打は、セネガルとコロンビアの力量を鑑みての冷静な選択とする向きもありますが、個人的には感情的に行われたものであったと想定したいところです。「このままいけば予選抜け」の文字が頭の中で踊り、その抗いがたい魅力に憑りつかれた結果の産物として考えたいわけです。

 そこにあった強い感情を私は勝手に想像して楽しむことができます。実際どうだったのかはわかりません。理屈も何もかも跳ね飛ばす執心は「どうしても予選抜けしたかった」というような言葉にした瞬間陳腐なものとなってしまいます。後から冷静に振り返るのではなく、すぐに決断を迫られるあの瞬間における強い感情。そのようなものを(錯覚だとしても)予測させるものは、エンターテイメント以外の何物でもないと考えます。

祈りの転倒

 もう一点はファンが期待する構造におけるものです。我々ファンが(少なくとも私が)できることは応援だけであり、現地で声援を送るわけでもなくテレビ、パソコンの前にいるだけともなれば、本質的にこの応援は無力です。こうした無力感と共にある願望を、私は祈りと呼んでいます。

 祈りの根底に無力感がありますが、しかしそんな中でも「こうあって欲しいな」という形が実現することに、いくらかの希望があると思うのです。祈りが本質的に無力であることを知りつつ、しかしその有効性を錯覚したいという願望が少なくとも私の中には存在しています。ワールドカップにおいて「我々の祈りの結果選手たちが奮闘し良い結果を得る」という物語を期待する点が私の中に無かったとは思えません。

 しかし結果的には祈りの対象であるところの選手(監督)が、他チームの結果を祈り始めるという転倒が発生しました。選手たちは他チームの同士の戦いに対して介入できるわけではないため、やはりそこにあったのは確かに祈りとしか言えないものでした。こうした祈りの空転に私は非常に強いエンタメ性を感じざるを得ません。

 これは「選手たちは頑張ったが、結果は良くなかった」というような祈りの失敗とは性質が異なります。むしろ祈りの構造が暴かれたような状況であると感じます。物事が上手くいく、あるいはいかないという地平においてサスペンス性を期待していた状況であったのに、そこに待っていたのはその期待を抱える気持ち自体を暴き立てる仕組みでした。考えもしなかった方向から面白さが開かれていく、これは上質なエンターテイメントだと感じます。

終わりに

 もう一点エンタメ性として付け加えるとすれば、日本代表が弱さ、特に自信のなさを見せたことそのものでしょうか。彼らは結局、自身の点を取りきる攻撃力や、カウンターを防ぎきる防御力を信じませんでした。ここまでコロンビア戦では運を味方につけたようなところもありましたが、セネガル戦では非常に良い戦いを行っており、どこか普段と違うような日本代表の姿に感じられていました。安易にこのようなことを言って良いのかわかりませんが、ここにきて弱さを見せるところに、肩すかし感があったと同時に何かしらの親近感があったことも確かだと思います。

 繰り返しますが、私は時間つぶしという行為が倫理的にどうであったかや、戦略的に正しかったかどうかについてはあまり興味がありません。私にとって重要なことは、あのシーンを観て精神が昂った原因がどこにあるのか、あのシーンにおけるエンターテイメント性とはなんなのか、ということでした。

 少しでも良い言語化をしたいと思って記事を書いてみましたが、そこまで成功しているとも思えていません。この先もいくらか意見が変わることもあるでしょう。しかしあの瞬間に感じた精神の高揚だけは確かなものであり、スポーツ観戦が紛れもないエンターテイメントであることは再度強く感じることとなりました。このような機会を与えてくれた日本代表に感謝し、また決勝トーナメントにおける活躍も祈りつつ、この記事を締めさせていただきます。

tensorflowのC++APIで変数を保存する

 前回はtensorflowのC++APIを用いて学習をできるようなコードを書いた。

 今回は学習した変数をファイルに書き出し及び読み出しできるように変更した。なかなか難しく、まだ理解できていないところが多い。

書き込み

 Saveシグネチャ公式ドキュメントの通り

Save(const ::tensorflow::Scope & scope, ::tensorflow::Input filename, ::tensorflow::Input tensor_names, ::tensorflow::InputList data)

であり、引数に必要なものは

  • scope
  • filename
  • tensor_names
  • data

の4つである。したがっておおむね

auto save = Save(scope, "file_name", { "w1", "w2", "b1", "b2" }, { w1, w2, b1, b2 });

のような形でノードを生成し、Runで走らせれば良い。しかしfilename,tensor_namesstringであるため(?)直接埋め込むことはできず、またInputListもそのままでは各変数がInputOutputの2通りで解釈可能であるため初期化できないというエラーが出る。

 したがって、まず各stringに対してはデータを格納するPlaceholderと実際のデータであるTensorを準備する。

    //保存するファイル名
    auto file_name_op = Placeholder(scope, DT_STRING);
    Tensor file_name(DT_STRING, TensorShape{ 1 });
    file_name.scalar<string>()() = "model.ckpt";

    //保存する変数につける名前
    auto tensor_names_op = Placeholder(scope, DT_STRING);
    Tensor tensor_names(DT_STRING, TensorShape{ 4 });
    tensor_names.vec<string>()(0) = "w1";
    tensor_names.vec<string>()(1) = "w2";
    tensor_names.vec<string>()(2) = "b1";
    tensor_names.vec<string>()(3) = "b2";

 InputListにはInput(w1)などとするとコンパイルが通った。ここの理由はまだよくわかっていない。

    //保存する変数
    auto tensors = InputList({ Input(w1), Input(w2), Input(b1), Input(b2) });

 この順番はfile_namesで指定する順番と一致していなければならない。

 このように引数を準備してから(少なくともPlaceholderを準備してから)ノードを生成し、feed_dictでデータを与えつつセッションを走らせる。

    //保存するOp
    auto save = Save(scope, file_name_op, tensor_names_op, tensors);

    //実行
    TF_CHECK_OK(session.Run({ {file_name_op, file_name}, {tensor_names_op, tensor_names} }, {}, { save }, nullptr));

 fetchするものではないため(?)第2引数は空にし、第3引数にsaveを与える。

読み出し

 Resroreシグネチャ公式ドキュメントの通り

Restore(const ::tensorflow::Scope & scope, ::tensorflow::Input file_pattern, ::tensorflow::Input tensor_name, DataType dt) 

であり、必要な引数は

  • scope
  • file_pattern
  • tensor_name
  • dt

である。気を付けるべき点としては(筆者の理解では)、Restoreは一つのTensorを読み出すものであり、読み出したい変数の数だけ読み出しノードを作る必要がある。また読み出しただけでは変数に割り当てられていないため、Assignを用いて対応する変数ノードに割り当てる必要がある。

 引数についてはfile_patternにはSaveでのfile_nameと同じものを与えればよく、Saveと同様に型がstringであるtensor_nameについてはPlaceholderを作りTensorにデータを入れて実行時に流し込むということを行う。

    //1変数に対して1個ずつPlaceholderとTensorを作る
    auto w1_name_op = Placeholder(scope, DT_STRING);
    Tensor w1_name(DT_STRING, TensorShape{ 1 });
    w1_name.scalar<string>()() = "w1";
    auto w2_name_op = Placeholder(scope, DT_STRING);
    Tensor w2_name(DT_STRING, TensorShape{ 1 });
    w2_name.scalar<string>()() = "w2";
    auto b1_name_op = Placeholder(scope, DT_STRING);
    Tensor b1_name(DT_STRING, TensorShape{ 1 });
    b1_name.scalar<string>()() = "b1";
    auto b2_name_op = Placeholder(scope, DT_STRING);
    Tensor b2_name(DT_STRING, TensorShape{ 1 });
    b2_name.scalar<string>()() = "b2";

    //読みだすOp
    auto restore_w1 = Restore(scope, file_name_op, w1_name_op, DT_FLOAT);
    auto restore_assign_w1 = Assign(scope, w1, restore_w1);
    auto restore_w2 = Restore(scope, file_name_op, w2_name_op, DT_FLOAT);
    auto restore_assign_w2 = Assign(scope, w2, restore_w2);
    auto restore_b1 = Restore(scope, file_name_op, b1_name_op, DT_FLOAT);
    auto restore_assign_b1 = Assign(scope, b1, restore_b1);
    auto restore_b2 = Restore(scope, file_name_op, b2_name_op, DT_FLOAT);
    auto restore_assign_b2 = Assign(scope, b2, restore_b2);

    //実行
    TF_CHECK_OK(session.Run({ { file_name_op, file_name }, { w1_name_op, w1_name } }, { restore_assign_w1 }, nullptr));
    TF_CHECK_OK(session.Run({ { file_name_op, file_name }, { w2_name_op, w2_name } }, { restore_assign_w2 }, nullptr));
    TF_CHECK_OK(session.Run({ { file_name_op, file_name }, { b1_name_op, b1_name } }, { restore_assign_b1 }, nullptr));
    TF_CHECK_OK(session.Run({ { file_name_op, file_name }, { b2_name_op, b2_name } }, { restore_assign_b2 }, nullptr));

 こちらはfetchするものであるため(?)第二引数に与える。

 かなり冗長なコードになってしまい、可読性や保守性が低い。より大きいネットワークを構築しようとすると変数も多くなるため、効率的な書き方を模索する必要がある。

全体

 全体のコードは以下の様になった。

#define COMPILER_MSVC

#include "tensorflow/cc/client/client_session.h"
#include "tensorflow/core/public/session.h"
#include "tensorflow/cc/ops/standard_ops.h"
#include "tensorflow/core/framework/tensor.h"
#include "tensorflow/cc/framework/gradients.h"

using namespace tensorflow;
using namespace tensorflow::ops;

double targetFunction(double x1, double x2) {
    return 2.0 * x1 * x2 - 2.4 * x1 * x1 + 3.1 * x2 * x2 + 2.7 * x1 - 10.0 * x2 + 5.0;
}

int main() {
    int unit_num;
    std::cout << "ユニット数 : ";
    std::cin >> unit_num;
    float learning_rate;
    std::cout << "学習率 : ";
    std::cin >> learning_rate;
    int batch_size;
    std::cout << "バッチサイズ : ";
    std::cin >> batch_size;
    int epoch_num;
    std::cout << "エポック数 : ";
    std::cin >> epoch_num;
    int restore_flag;
    std::cout << "変数の設定(0->初期化, 1->ファイルから読み込む) : ";
    std::cin >> restore_flag;

    Scope scope = Scope::NewRootScope();

    //入力,教師データのPlaceholder
    auto x = Placeholder(scope.WithOpName("x"), DT_FLOAT);
    auto y = Placeholder(scope.WithOpName("y"), DT_FLOAT);

    //中間層への重み、バイアス
    auto w1 = Variable(scope, { unit_num, 2 }, DT_FLOAT);
    auto assign_w1 = Assign(scope, w1, RandomNormal(scope, { unit_num, 2 }, DT_FLOAT));
    auto b1 = Variable(scope, { unit_num, 1 }, DT_FLOAT);
    auto assign_b1 = Assign(scope, b1, RandomNormal(scope, { unit_num, 1 }, DT_FLOAT));

    //出力層への重み、バイアス
    auto w2 = Variable(scope, { 1, unit_num  }, DT_FLOAT);
    auto assign_w2 = Assign(scope, w2, RandomNormal(scope, { 1, unit_num }, DT_FLOAT));
    auto b2 = Variable(scope, { 1, 1 }, DT_FLOAT);
    auto assign_b2 = Assign(scope, b2, RandomNormal(scope, { 1, 1 }, DT_FLOAT));

    //中間層
    auto hidden_layer = Relu(scope, Add(scope, MatMul(scope, w1, x), b1));

    //出力層
    auto output_layer = Add(scope.WithOpName("output_layer"), MatMul(scope, w2, hidden_layer), b2);

    //損失
    auto loss = ReduceMean(scope, Square(scope, Sub(scope, output_layer, y)), {0, 1});

    //勾配
    std::vector<Output> grad_outputs;
    TF_CHECK_OK(AddSymbolicGradients(scope, { loss }, { w1, w2, b1, b2 }, &grad_outputs));

    //勾配降下を各変数に適用
    auto apply_w1 = ApplyGradientDescent(scope, w1, learning_rate, { grad_outputs[0] });
    auto apply_w2 = ApplyGradientDescent(scope, w2, learning_rate, { grad_outputs[1] });
    auto apply_b1 = ApplyGradientDescent(scope, b1, learning_rate, { grad_outputs[2] });
    auto apply_b2 = ApplyGradientDescent(scope, b2, learning_rate, { grad_outputs[3] });
    
    //入力、教師データのPlaceholderに流す実際のデータ
    Tensor x_data(DT_FLOAT, TensorShape{ 2, batch_size });
    Tensor y_data(DT_FLOAT, TensorShape{ 1, batch_size });

    //x_dataとy_dataにbatch_size分のランダムデータを格納する関数
    auto setData = [&x_data, &y_data](int batch_size) {
        static std::random_device seed_gen;
        static std::default_random_engine engine(seed_gen());
        static std::uniform_real_distribution<> dist(-10.0, 10.0);

        for (int i = 0; i < batch_size; i++) {
            double x1 = dist(engine), x2 = dist(engine);
            x_data.matrix<float>()(0, i) = (float)x1;
            x_data.matrix<float>()(1, i) = (float)x2;

            y_data.matrix<float>()(0, i) = (float)targetFunction(x1, x2);
        }
    };

    //出力を受け取るための変数
    std::vector<Tensor> outputs;

    //保存する変数
    auto tensors = InputList({ Input(w1), Input(w2), Input(b1), Input(b2) });

    //保存するファイル名 stringのデータは直接埋め込めないらしい?
    //learning_rateとかは直接floatを書けるのに
    //なのでいちいちPlaceholderとTensorを作って流し込むということをやる
    auto file_name_op = Placeholder(scope, DT_STRING);
    Tensor file_name(DT_STRING, TensorShape{ 1 });
    file_name.scalar<string>()() = "model.ckpt";

    //保存する変数につける名前
    auto tensor_names_op = Placeholder(scope, DT_STRING);
    Tensor tensor_names(DT_STRING, TensorShape{ 4 });
    tensor_names.vec<string>()(0) = "w1";
    tensor_names.vec<string>()(1) = "w2";
    tensor_names.vec<string>()(2) = "b1";
    tensor_names.vec<string>()(3) = "b2";

    //Restoreするときは1変数ずつやっていく必要があるので1個ずつPlaceholderとTensorを作る
    auto w1_name_op = Placeholder(scope, DT_STRING);
    Tensor w1_name(DT_STRING, TensorShape{ 1 });
    w1_name.scalar<string>()() = "w1";
    auto w2_name_op = Placeholder(scope, DT_STRING);
    Tensor w2_name(DT_STRING, TensorShape{ 1 });
    w2_name.scalar<string>()() = "w2";
    auto b1_name_op = Placeholder(scope, DT_STRING);
    Tensor b1_name(DT_STRING, TensorShape{ 1 });
    b1_name.scalar<string>()() = "b1";
    auto b2_name_op = Placeholder(scope, DT_STRING);
    Tensor b2_name(DT_STRING, TensorShape{ 1 });
    b2_name.scalar<string>()() = "b2";

    //保存するOp
    auto save = Save(scope, file_name_op, tensor_names_op, tensors);

    //読みだすOp
    auto restore_w1 = Restore(scope, file_name_op, w1_name_op, DT_FLOAT);
    auto restore_assign_w1 = Assign(scope, w1, restore_w1);
    auto restore_w2 = Restore(scope, file_name_op, w2_name_op, DT_FLOAT);
    auto restore_assign_w2 = Assign(scope, w2, restore_w2);
    auto restore_b1 = Restore(scope, file_name_op, b1_name_op, DT_FLOAT);
    auto restore_assign_b1 = Assign(scope, b1, restore_b1);
    auto restore_b2 = Restore(scope, file_name_op, b2_name_op, DT_FLOAT);
    auto restore_assign_b2 = Assign(scope, b2, restore_b2);

    //セッションを作成
    ClientSession session(scope);

    if (restore_flag == 0) {
        //重みとバイアスを初期化
        TF_CHECK_OK(session.Run({ assign_w1, assign_w2, assign_b1, assign_b2 }, nullptr));
    } else {
        //ファイルから読み込む
        TF_CHECK_OK(session.Run({ { file_name_op, file_name }, { w1_name_op, w1_name } }, { restore_assign_w1 }, nullptr));
        TF_CHECK_OK(session.Run({ { file_name_op, file_name }, { w2_name_op, w2_name } }, { restore_assign_w2 }, nullptr));
        TF_CHECK_OK(session.Run({ { file_name_op, file_name }, { b1_name_op, b1_name } }, { restore_assign_b1 }, nullptr));
        TF_CHECK_OK(session.Run({ { file_name_op, file_name }, { b2_name_op, b2_name } }, { restore_assign_b2 }, nullptr));
    }

    for (int e = 0; e <= epoch_num; e++) {
        //検証
        setData(batch_size);
        TF_CHECK_OK(session.Run({ { x, x_data }, { y, y_data } }, { loss }, &outputs));

        printf("epoch = %5d, loss = %12.1f\n", e, outputs[0].scalar<float>()());
        if (e == epoch_num) {
            break;
        }

        //学習
        setData(batch_size);
        TF_CHECK_OK(session.Run({ { x, x_data },{ y, y_data } }, { apply_w1, apply_b1, apply_w2, apply_b2 }, nullptr));
    }

    TF_CHECK_OK(session.Run({ {file_name_op, file_name}, {tensor_names_op, tensor_names} }, {}, { save }, nullptr));
}

 入力を

項目
ユニット数 1000
学習率 0.00001
バッチサイズ 1000
エポック数 100
変数の設定 0

のようにして実行するとmodel.ckptが生成され、その後変数の設定を1にして繰り返し実行すると直前で実行された損失とほとんど同じ損失(ランダム性があるのでぴったり同じとはならない)から始まり、着実に損失が減っていくことが確認できた。