albicilla514’s blog

チーム名　KPCC Kamoike Team で参加しました。

すっごく体験記

ルール

SamurAI Coding 2017-18: ルール

やったこと

枝狩り探索+コース予測
SamurAI KPCC Kamoike Team 発表スライド

最終解法に至るまでの経緯

MMのノウハウがなかったので、とりあえず聞いたことのあるアルゴリズムを全部試した結果をみて一番いいものを選びました。
はじめに試したのはビームサーチです。

実装はtakaptさんのスライドを参考に実装しました。(takaptさんに感謝！)
ぷよぷよAIの新しい探索法
実装後にサンプルと対戦させて運営の用意したサンプルが強いということに気がつきました。
運営のサンプルは途中で障害点にぶつかるルートは削除し、それ以外のルートで7手先までみたときにもっともy座標の到達点が大きいものを選ぶというものでした。で、

一コースごとに対戦させて勝敗をみていたのですが、あるコースで勝てるように調整しても他のコースで勝てないという事態が発生し頭を抱えました。

問題点が2点あって
・ビームサーチ自体がこの問題にそこまであっていない。
・一つずつのコースを手作業でテストしたのでぬか喜びをする時間が生まれた。

一つ目。
ビームサーチですが今回の問題設定においてはビームサーチの評価関数設計が難しかったように感じます。というのは、途中のノードでの評価値の良しあしが終端のノードの評価値の良しあしと一致するような評価関数設定が困難だったためです。そのため、最終的に良い評価値であっても途中で落としてしまっていました。また、ビームサーチは評価値が低い枝の探索を打ち切りますが、探索空間が狭くその必要があまり感じられませんでした。

二つ目。こっちが大事です。
シェルコマンドを使ってまとめて対戦を実行し、その勝敗のログをpythonで読んで勝敗と勝率を出力するようにしました。このことで、以降の色々なアルゴリズムを実装してみてそれを考察するということが効率的にできるようになりました。期間の長めのコンテストではこうした環境構築から手をつけることができると以降の作業が効率的になると思います。

ビームサーチ以降はα-β法,Q学習なんかを試しました。しかし、結局のところ一番性能が安定して高かったのが運営のサンプルを障害物探索を含め、評価関数による幾らかの枝かりを含む形に書き直したものでした。ここでの枝かりは障害物に埋まり続けるなど明白な物にしました。(運営のサンプルの時点で同じ状態のノードを一つにまとめるなどはしてありました...)(また、視界内探索でゴールタイムできるときはもっとも早いタイムの物を採用する工夫もすでにされてました...)

これに加え、相手が自分と同じような行動選択アルゴリズムを採用していると仮定し、自分のアルゴリズムの浅い探索版を相手に適用させ、余裕があれば妨害をするようにしました。これは一手目だけに適用し、一手目での妨害可能性に応じた評価値を続く各ノードに伝搬させる形の実装をしました。

この状態で迎えたのが練習会1です。結果は予選落ちでしたが、サンプルがファイナルラウンド進出を決めたりしていたのでうーん(運)という感じがしてました。しかし、1位のpiyoさんは圧倒的な勝ち方をしており運ではなくアルゴリズムで勝つ方法があると感じモチベを取り戻しました。
(練習会、予選の結果はこちらから確認できます。SamurAI Coding 2017-18 Trial）

視界内での探索は終えてたので大元から変えることはもう考えられませんでした。そのため相手の行動から妨害について幾らかの妨害のパターンについて分類し、その重み付けを行うなどをしました。

そして迎えた練習会2でもpiyoさんは圧倒的でした。これはやっぱり運ではないなぁと確信しました。この時期はずっとpiyoさんのAIの動きをviewerで眺めてました。視界外にある障害物に反応して右にそれる動きをしたときにコース予測をしているという予想がたちました。しかし、コース予測は運営からコースの生成アルゴリズムが公開されていないこともあり、うーん(運)だなぁとなってました。解釈を変えて、途中経路で中央に寄るようなものを高く評価してるんじゃないか。や、障害物をギリギリ避けるルートを高く評価しているのではないかということも検討しましたが、結局擬似的にコース予測をしているに過ぎないという結論に達し、じゃあ予測やる?という感じでした。

迎えた本番(予選)ではコース予測はしませんでした(おい)。ただ、練習会1,2の結果を踏まえテストを重ねたところ視界外の続くコースは全て更地を仮定したものが良い結果を出すデータがあったのでそれを提出し、無事6位をとり進出できました。

ファイナルラウンド進出が確定した後はモチベが上がったのでなんとかして上位陣のアルゴリズムを見抜いてやろうと実験を重ねました。(練習会1,2 予選を通じて上位のチームは上位に居続けて居ました)。結果、やっぱりコース予測してるなぁとなったのでコース予測しました。

予測の手法ですが、機械学習をやってうまくやるというのがウケがいいと思いましたが力不足でうまくできませんでした。また、それまでのコースが人の手によるものだったので人力がよさそうにも感じ人力学習のルールベースで予測を組み立てました。例えば視界の端の障害物がy方向でみたときに連なって居たらy方向に追加するといった具合です。これだけでも予選のレーススコアが劇的に向上しました。
(余談ですが人力学習で運営のサンプルコースを3パターンに分けてたので懇親会で運営の先生が複数人がコース作成を担当していたとおっしゃってた時に妙に納得してました)

本番当日

競プロerと交流できる機会なので楽しみ。(事前に把握していたのはfmhrさんとhirokazuさんとkt_tenelさん)

受付でからっぽの筒と名札を渡される。

githubの公式レポジトリでarukukaさんを見かけていたので会場でarukukaさんを見つけてやっぱり〜となる。

会場がとにかく暑いのでつらい。

twitterを眺めてyumechiさんとiwashiさんがきていることを知る。

piyoさんがコース予測をしてると発表したので、やっぱり！となる。

一試合目でpiyoさんが負けたので驚愕

初戦で勝って舞い上がる.(前日まで初戦で負ける夢をみていてビクビクしてた)

満足。

いつの間にかついた自動字幕がめちゃくちゃでhedjet hedjet.

2戦目も勝利。(traPに勝てて嬉しい)

試合より字幕の方がおもしろくてそっちばかりみてた。

チームsc-samuraiが試合中バグる。

準決勝(VS tortoise)で僕のチームのもバグる。(ぎゃーーー)

迎えた3位決定戦は(VS sc-samurai)試合でバグったコード同士というわけで色々暑かった。

初戦で勝ったものの2戦目で僕のチームのAIがまたバグる。(おい)

試合終了

いい生活さんからスポンサー賞をいただく。(わーい)

というわけで4位/147中でした。

バグは要反省ですが、他の方のAIと比較しコース予測の部分やアルゴリズムの荒削りなことを考慮すると比較的良い成績がでたので結果には満足してます。(1位のtortoiseさんは機械学習でコース予測を16先まで組み立てていたみたいです)

まとめ

こうした長期間のコンテストは個人的には初心者にとって良いと感じました。有名手法に慣れ親しんでなくとも実際に実装して検討する時間があるからです。例えば、僕の場合だと今回のコンテストで一番勉強になったのは強化学習だったりします。

競技プログラマの人口も増えてきているのでマラソンマッチに手を出してみようと思う人も増えていると思います。この体験記を読んでやってみようかなと思う人が増えるとうれしいです。

問題文
http://codeforces.com/contest/851/problem/D

問題文で与えられた $a_i$ が数直線上にあることを考える

区間ごとに分けることを考えて $cost(g)$ という関数を定義する。もし、全体の最大公約数が $g$ としたいなら、答えは $g$ が $1$ より大きい時の $cost(g)$ の最小値の和。

それぞれの区間での $cost(g)$ をもとめる、ある数(例えば $c$ )が区間に含まれる時、かかるコストはそれを $x$ で消すか、 $g$ で割れるまで足していった時なので

$min(x,y\times( \lceil \frac{c}{g}\rceil)\times g-c)$
になる。
次に $\lceil \frac{c}{g}\rceil\times g$ の取る値について考える。

本題に入る前に二つの関数を定義する

$-cnt(l,r)$ : $l\leq a_i\leq r$ となる $a_i$ の個数を返す関数。この関数を計算するために配列 $b$ を定義する。 $b[x]$ は $0$ から $x$ までに含まれる $a_i$ の個数。この配列を用いると $cnt(l,r)=b[r]-b[l-1]$ と書ける
$-sum(l,r)$ : $\sum_{i\ni l\leq a_i\leq r}^{}a_i$ を返す関数。この関数を計算するために配列 $ps$ を定義する。 $ps[x]$ は $0$ から $x$ までに含まれる $a_i$ の総和。この配列を用いると $sum(l,r)=ps[r]-ps_[l-1]$ とかける。

さて、それぞれの $g$ の倍数 $k$ の時について $(k-g,k]$ でのコストを計算して足し上げていく。
つまり、その範囲を二つの区間に分割する $(k-g,k-f$ ]と $(k-f,k$ ]に分割するようなもっともよい $f$ を見つけ、一つ目の区間(図の青線部分)の数を削除し、二つ目の区間(図の赤線部分)の数を $k$ になるまで足し上げていけばよい。
求める $f$ は　もし、 $k$ との差が $x/y$ を超えるなら $x$ で消すほうがコストが安いので
$f=min(g,x/y)$
よって $cost(g)=cnt(k-g+1,k-\lceil f\rceil)\times x + (cnt(k-\lceil f\rceil + 1,k)\times k - sum(k-\lceil f\rceil +1,k))\times y$

時間計算量は $O(\max(a_i)\log \max(a_i))$
f:id:albicilla:20170908133457p:plain

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

typedef long long LL;
const int N = 2000000 + 10;
const long long INF = 1e18;

int n;
long long x, y;
long long b[N];
long long ps[N];

long long cnt(long long l,long long r){
  return b[r]-b[l-1];
}
long long sum(long long l,long long r){
  return ps[r]-ps[l-1];
}

void solve()
{
    cin >> n >> x >> y;
    for(int i = 0; i < n; ++ i) {
        int t;
        scanf("%d", &t);
        b[t] ++;
        ps[t] += t;
    }
    long long ans = INF;
    long long c = x / y;

    for(int i = 1; i < N; ++ i) {
        b[i] += b[i - 1];
        ps[i] += ps[i - 1];
    }

    for(long long g = 2; g <=1000000; g++) {
        long long tmp_ans = 0;
        long long f=min(g,(x+y-1)/y);
        for(long long k = g; k <= 1000000+g; k += g) {
          tmp_ans+=cnt(k-g+1,k-f)*x;
          tmp_ans+=(cnt(k-f+1,k)*k-sum(k-f+1,k))*y;
        }
        ans = min(ans, tmp_ans);
    }
    cout << ans << endl;

}

int main()
{
	solve();
	return 0;
}

albicilla514’s blog

SamurAI Coding 2017-18 体験記

ルール

やったこと

最終解法に至るまでの経緯

一コースごとに対戦させて勝敗をみていたのですが、あるコースで勝てるように調整しても他のコースで勝てないという事態が発生し頭を抱えました。

本番当日

まとめ

Codeforces 851 D. Arpa and a list of numbers