TSG LIVE2!の感想・反省等を適当に書いたポエム
この記事はTSG Advent Calendar 2018の13日目の記事として書かれたはずでした。書き始めたの23:45分なんですが。15分で書けるかボケ。
昨日はpizzacat83プロの『語彙力ゲーム「弓箭」であそぶ』でした。今日はkakinotaneプロの「linux sourcecode readingでやった環境構築」だそうです。
編集後記：この記事は異常に長いので読むことを推奨しないことを書いておきます。
僕がTSG LIVE2!で担当したのは「1日目CTF」「2日目競プロ（作問・実況）」「3日目AI（実況）」でした。
CTFについて
この日出たのは「Web」「Stego」等、メディア系（これは自分の中での適当な分類です）でした。前回のTSG LIVEで僕は「stego嫌い」って言った気がするんだけどなぁ…
相方はmoratorium08プロ。僕はこの方からWebを教えてもらったといっても過言ではないので、Webはmoratorium08プロに全投げして、残った問題で出来そうなものに挑戦する形に。予め「マスコットをします！」と宣言したしね！
webは全投げしたこともあり、moratorium08プロが秒で解いてくれました。僕は「W」と「3tsg0」を適当に覗いてみる。3tsg0はひたすら違いを探しますが、パッと問題は特に見当たらず(でもどこかにあるはずなので…という思考あたりで僕の才能が無いことが露見しています）。ということでWに突っ込みます。
Wは明らかにHPの画像を使用しています。じゃあdiffを取ろうってなり、pythonで2枚の画像のxorを取るスクリプトを書いていました。途中で「普通にgimpでよくね？」ってなって中断して、gimpでレイヤー間の結合方式（とても適当なことを言っている）を減算とかその辺に。でも真っ暗。うーん分からない。その後取り敢えず適当に試していて、困ったので手当たり次第に持っているstego系のソフトを試してました。
webを秒殺したmoratorium08プロは僕がサンドバッグ並みにボコボコにされている様子を見て一言。「…stegsolve」…何ですか僕それ知らないんですが。ってことでmoratorium08プロがW内のプログラムを半分見つけたところで時間切れ。文字通りのマスコットをしていました。
CTFはずっとやる時間を取りたいとは思っているのですが、（自主規制）学科のunlimited homeworkとか社会に次ぐ社会とかで時間が取れていません。夏休みになったらkaggleやろー→秋学期になったらkaggleやろー→今「やれてねぇ…」状態よりはマシですが。年末年始もマラソンがあるのでそっちに時間を持ってかれるんですよね…マラソンの休憩がてらにやろうかな…
競プロについて
今回は「マラソン形式」ということで、実は初の作問です。ある程度（といってもプロのinf分の1ですが）参加経験があるのでそれを参考に問題を生成します。「最近面白い問題出てないかなぁー」と探してみたら、画像が入出力になっている問題がありました。楽しそうですが、今回75分しか実装の時間が無いので却下。もっと簡単なのがいいです。
また、最初の段階から「いわしを出題する」ということを実は決めていました。いわしはつちからはやすんだ
ということで、最初の原案を作問担当と知らされてから1日か2日くらいで投げます。問題文を全て載せると、「異常に長い」「訳の分からない内輪ネタ（いわしの時点で…）」「部員の名前を容赦なく使っている（許可取っていない）」ので、本質部分を切り取った内容だけ。
H×Wのマス目上にN匹のいわしが同時に出現します。M個の壁（長さはLiでそれぞれ与えられます）を上手く設置し、マス目をいくつかの区画に切り分けます。各区画において、その区画内にいわしがK匹以上いるといわしは凶暴化します。凶暴化するとその区画が全壊します。なるべく多くのマスを残せるよう、いわしを隔離してください。
という感じです（画像用意したいけど時間無いので割愛！）。
まぁマラソンやろって感じの問題を出しましたが、この時点で実はサイト側がマラソンに対応しておらず、どのような感じで対応されるか分からなかったという状態でした。結局この問題でも対応は可能だったのですが、AIゲームのサイトを改変するということだったので、一応ターン制のゲームもそれっぽい案を脳内に浮かべておきます。
これを見たhakatashi総司令様「これ1時間無理やろ」とツッコミをいただきました。（そもそもマラソン1時間の時点で無理ゲーとかそんなことが脳裏をよぎります）
でも確かにこのルールは1時間だと完全に「方針ガチャ」になること間違いなしです。多分「分割」じゃなくて「隔離（なるべく大きい面積を頑張って確保して残り全部捨てる）」という感じになりそうです。
ということで頭の中にあったルールを文章化しました。そうして出来上がったのがiwashi収穫祭です。ルールその他諸々はYoutubeを見ましょう。
プレイヤーは「影響マップ」知っていたんですかね…自分は高校2年の春には知っていて、名称を忘れてずっと「ポテンシャル」って呼んでいましたが、割と色んな名前で呼ばれてたりするそうです。このレベルなら発想でも思いつきそうだし。実際はビームサーチと一緒に使ったりするんですが、1回の計算量が大きくなりがちです。その辺が計算の工夫の腕の見せ所でもあるのですが。
作問は楽しかったのですが、この時期色々と余裕が無くてhakatashi総司令様に多大な負担をおかけしてしまいました。申し訳ございません。あとプレイヤーの二人に。algorithmヘッダー忘れてました。ごめんなさい(daiプロ検索されてましたよね…)
余談ですが、現在0:20です。時間過ぎています。急ぎます。左足を攣りました。痛いです。
AIについて
という感じで、競プロ放送直前まで競プロ競プロしていて、終わってから翌日のAIのことを考えます。作問担当のmoratorium08プロ曰く「catを超えるAIを作ってほしい」とのこと。ビームサーチとか使ってちゃんとチューニングすれば勝てそうですが、移動時間食事時間その他込みで18時間切ってるんですね。無理。
ということで、最初から「ルールベースで、いくつか強力なものを組み合わせて勝ちに行こう」、という方針を取りました。帰ってイカで遊んで日が変わりました。残り12時間。さぁ、始めよう。
といっても、帰りの電車の中でスマホを使って考察を進めていました。「逃げる側は安置（ビームが単体ではたどり着けない場所の通称）に引きこもれば大体勝てる」という方針は「複数体のビームが協力して新しい場所へ移動する」というのがメチャクチャ難しいことから自明に分かります。逆に自分はビームではそのようなケースは完全に諦めています。
方針としては、「相手の進める場所を減らす（catと同じ）」というのはかなり強力です。でも「列」か「行」の両方を絞り込みするのはやや効率が悪いです。どっちかで十分ですよね（多分）。という辺りまで考察してたのですが、そもそもとして、このゲームには大きな特色があります。
- ロボットは一度動いたら壁か他のロボットに当たるまで止まらない
というルールです。これを考えると、通常のマップで考えてもいいんですが、Dancing Links(データ構造)的な思考をした方がよさそうです。
ということで、「相手ロボットの位置へたどり着くまでの最短ターン数」からなるマップを生成して、これが短くなるように進む適当な貪欲をします。結果的にこれが放送中で「追い回す」と表現される僕のプログラムのメイン部分が完成しました（実際に動作を見るまではこれがメインとなると思いませんでした）
実はこれを思い付いたのがAM 8:00頃。登校中です。これまではビーム側は「取り敢えず2ターン以内に確実に殺せるなら殺す」、逃げる側は「安置に行けるなら行く」みたいなことを適当に実装、catと戦わせては結構接戦でうーん…勝てない…ってなっていました。
登校完了（投稿は完了したいけどまだ記事の途中です）してからはひたすら（といっても大した量では無いですが）実装。ビームサーチとか高度なことはしないので、今までのデータを保存とかは一切していません。なのでデバッグは取り敢えず可能で、ローカルのサーバーに投げて様子を見ては、上手く動いていないケースでデバッグの繰り返しでした。途中で「ソースコードが10,000byteを超えて規制に引っかかる」ことが判明。不要なコードを削除・インデントやコメントを消し去ることで規制内に収めて提出します。
放送開始1時間前に実装自体は完了。あとはバグが消えれば終わり！という状態になります。ここからはゲームプログラミング担当hakatashi総司令様が圧倒的プログラミング力を発揮し、余裕でブロック崩しを完成させてしまった様子を眺めながらひたすらデバッグします。バグ…バグ…I hate bug.
終わらない。終わらない。無理。間に合わない。残り30分…残り15分…10分…5分..ここだ！！と直したのが3分前。アルゴリズム的にそこが元凶と確信したので、それ以降のデバッグを行わずに（つまりこのAIがcatに勝てる保証が全く無い状態で）投げました。結果、上手く動いてくれて本当に良かったです。
最後にAIのソースコードを公開してこの記事を終わらせたいと思います。この時点で情報量の無い4000文字という完全にポエムを書いていますが、少しだけ情報量がこれで入るかな… 今書いているPCからアクセスできるソースコードが提出されたものなので、コメントは結構消えてしまっています。また、分かりやすく書くとかそんな精神を捨ててルールベースを容赦なく書いているので、近年稀に見るクソコードが生成されております。お読みになられる際は予めご了承ください。
#define _USE_MATH_DEFINES // #define DEBUG #include <algorithm> #include <array> #include <bitset> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <iostream> #include <map> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <tuple> #include <utility> #include <vector> using namespace std; typedef long double ld; typedef long long ll; typedef vector < int > vint; typedef vector < ll > vll; typedef pair < int, int > pii; typedef pair < ll, ll > pll; typedef pair < double, double > pdd; typedef complex < ld > compd; #define rep(i, n) for (int i = 0; i < n; i++) #define srep(i, a, n) for (int i = a; i < n; i++) #define REP(i, n) for (int i = 0; i <= n; i++) #define SREP(i, a, n) for (int i = a; i <= n; i++) #define rrep(i, n) for (int i = n - 1; i >= 0; i--) #define RREP(i, n) for (int i = n; i >= 0; i--) #define all(a)(a).begin(), (a).end() #define mp(a, b) make_pair((a), (b)) #define mt make_tuple #define pb push_back #define fst first #define scn second #define bitcnt(x) __builtin_popcount(x) #define gcd(a, b) __gcd((a), (b)) const double inf = 1e18; const ll mod = 1e9 + 7; const ld eps = 1e-9; class RandomMaker { random_device rnd; mt19937 mt; uniform_real_distribution < double > rnd2; public: void setup() { mt.seed(rnd()); rnd2 = uniform_real_distribution < double > (0.0, 1.0); } double rand() { return rnd2(mt); } int rand(int a, int b) { uniform_int_distribution < > r(a, b); int ret = r(mt); return ret; } }rnd; #define ranodm rand inline void init() { rnd.setup(); } const int dx[] = {0, -1, 1, 0, 1, -1, 1, -1}; const int dy[] = {-1, 0, 0, 1, 1, 1, -1, -1}; const string dir = "ulrd"; int h, w; char T; vector < string > maps; vector < tuple < int, int, int >> beam; vector < tuple < int, int, int >> target; vector < vint > beamMap; vector < vint > targetMap; vector < vector < vector < pii >>> adjacentList; vector < vint > canBeam; bool isInside(int x, int y) { return (0 <= x && x < w && 0 <= y && y < h); } int main() { init(); map < int, int > killed; bool first = true; while (scanf("%d %d", & w, & h) != EOF) { maps = vector < string > (h); beam.clear(); target.clear(); beamMap = vector < vint > (h, vint(w, -1)); targetMap = vector < vint > (h, vint(w, -1)); scanf(" %c", & T); rep(i, h) { rep(j, w) { char s; scanf(" %c", & s); if (s == 'b') { int v; scanf("%d", & v); beam.push_back(mt(v, i, j)); beamMap[i][j] = v; maps[i] += '.'; } else if (s == 't') { int v; scanf("%d", & v); target.push_back(mt(v, i, j)); if (killed.count(v) == 0) { killed[v] = -1; } targetMap[i][j] = v; maps[i] += '.'; } else if (s == 'x') { maps[i] += 'x'; } else if (s == '*') { maps[i] += '*'; } else if (s == '.') { maps[i] += '.'; } else { cout << "error" << endl; goto TURN_END; } } } if (first) { adjacentList = vector < vector < vector < pii >>> (h, vector < vector < pii >> (w)); rep(i, w) adjacentList[0][i].push_back(mp(0, i)); srep(i, 1, h) rep(j, w) { if (maps[i][j] == '*') adjacentList[i][j].push_back(mp(i, j)); else if (maps[i - 1][j] == '*') adjacentList[i][j].push_back(mp(i, j)); else adjacentList[i][j].push_back(adjacentList[i - 1][j][0]); } rep(i, h) adjacentList[i][0].push_back(mp(i, 0)); rep(i, h) srep(j, 1, w) { if (maps[i][j] == '*') adjacentList[i][j].push_back(mp(i, j)); else if (maps[i][j - 1] == '*') adjacentList[i][j].push_back(mp(i, j)); else adjacentList[i][j].push_back(adjacentList[i][j - 1][1]); } rep(i, h) adjacentList[i][w - 1].push_back(mp(i, w - 1)); rep(i, h) for (int j = w - 2; j >= 0; j--) { if (maps[i][j] == '*') adjacentList[i][j].push_back(mp(i, j)); else if (maps[i][j + 1] == '*') adjacentList[i][j].push_back(mp(i, j)); else adjacentList[i][j].push_back(adjacentList[i][j + 1][2]); } rep(i, w) adjacentList[h - 1][i].push_back(mp(h - 1, i)); for (int i = h - 2; i >= 0; i--) rep(j, w) { if (maps[i][j] == '*') adjacentList[i][j].push_back(mp(i, j)); else if (maps[i + 1][j] == '*') adjacentList[i][j].push_back(mp(i, j)); else adjacentList[i][j].push_back(adjacentList[i][j][3]); } } rep(i, h) { cerr << maps[i] << endl; } if (T == 'A') { tuple < int, int, int > bestKill = mt(0, -1, -1); // score, id, dir rep(i, beam.size()) { rep(j, 4) { int score = 0; int px = get < 2 > (beam[i]); int py = get < 1 > (beam[i]); // first Move while (isInside(px + dx[j], py + dy[j]) && maps[py + dy[j]][px + dx[j]] != '*' && beamMap[py + dy[j]][px + dx[j]] < 0) { px += dx[j]; py += dy[j]; if (targetMap[py][px] >= 0) { score++; } } // search reach int score2 = 0; rep(k, 4) { if (j + k == 3) continue; int px2 = px; int py2 = py; int tmpScore = 0; while (isInside(px2 + dx[k], py2 + dy[j]) && maps[py2 + dy[j]][px2 + dx[j]] != '*' && beamMap[py2 + dy[j]][px2 + dx[j]] < 0) { px2 += dx[j]; py2 += dy[j]; if (targetMap[py2][px2] >= 0) { tmpScore++; } } score2 = max(score2, tmpScore); } score += max(0, score2 - 1); if (score > get < 0 > (bestKill)) { bestKill = mt(score, get < 0 > (beam[i]), j); } } } if (bestKill != mt(0, -1, -1)) { cout << get < 1 > (bestKill) << " " << dir[get < 2 > (bestKill)] << endl; goto TURN_END; } vector < vector < tuple < int, int, int >>> distMap(vector < vector < tuple < int, int, int >>> (h, vector < tuple < int, int, int >> (w, tuple < int, int, int > (h * w, -1, -1)))); queue < pii > q; rep(i, beam.size()) { q.push(mp(get < 1 > (beam[i]), get < 2 > (beam[i]))); distMap[get < 1 > (beam[i])][get < 2 > (beam[i])] = mt(0, get < 1 > (beam[i]), get < 2 > (beam[i])); } while (!q.empty()) { auto it = q.front(); q.pop(); int y = it.first, x = it.second; rep(j, 4) { int toy = y, tox = x; while (isInside(tox + dx[j], toy + dy[j]) && maps[toy + dy[j]][tox + dx[j]] != '*' && beamMap[toy + dy[j]][tox + dx[j]] < 0) { tox += dx[j]; toy += dy[j]; if (get < 0 > (distMap[toy][tox]) > get < 0 > (distMap[y][x]) + 1) { distMap[toy][tox] = mt(get < 0 > (distMap[y][x]) + 1, y, x); } } if (get < 0 > (distMap[toy][tox]) == get < 0 > (distMap[y][x]) + 1) { q.push(mp(toy, tox)); } } } rep(i, h) { rep(j, w) { cerr << get < 0 > (distMap[i][j]) << " "; } cerr << endl; } vector < pair < int, tuple < int, int, int >>> targetDist(target.size()); rep(j, target.size()) { targetDist[j] = mp(get < 0 > (distMap[get < 1 > (target[j])][get < 2 > (target[j])]), target[j]); } sort(all(targetDist)); for (int j = 0; j < targetDist.size(); j++) { if (targetDist[j].first == h * w) { continue; } tuple < int, int, int > targetMarker = targetDist[j].second; int by = get < 1 > (targetMarker), bx = get < 2 > (targetMarker); int toy = get < 1 > (distMap[by][bx]), tox = get < 2 > (distMap[by][bx]); while (get < 0 > (distMap[toy][tox]) > 0) { bx = tox; by = toy; toy = get < 1 > (distMap[by][bx]); tox = get < 2 > (distMap[by][bx]); } int id = beamMap[toy][tox]; rep(j, 4) { int tx = tox; int ty = toy; while (isInside(tx + dx[j], ty + dy[j]) && maps[ty + dy[j]][tx + dx[j]] != '*' && beamMap[ty + dy[j]][tx + dx[j]] < 0) { tx += dx[j]; ty += dy[j]; } if (tx == bx && ty == by) { cout << id << " " << dir[j] << endl; goto TURN_END; } } } int use = rnd.rand(0, beam.size() - 1); cout << get < 0 > (beam[use]) << " " << dir[rnd.rand(0, 3)] << endl; } else if (T == 'D') { vector < vint > deadMap = vector < vint > (h, vint(w, 0)); rep(i, beam.size()) { int y = get < 1 > (beam[i]), x = get < 2 > (beam[i]); deadMap[y][x] = 15; rep(j, 4) { int ny = y + dy[j]; int nx = x + dx[j]; while (isInside(nx, ny) && maps[ny][nx] != '*') { deadMap[ny][nx] |= 1 << j; ny += dy[j]; nx += dx[j]; } } } rep(i, target.size()) { int y = get < 1 > (target[i]), x = get < 2 > (target[i]); if (((deadMap[y][x] & 3) | (deadMap[y][x] >> 2)) == 3) continue; if (deadMap[y][x] > 0) { rep(j, 4) { int tox = x, toy = y; while (isInside(tox + dx[j], toy + dy[j]) && maps[toy + dy[j]][tox + dx[j]] != '*' && maps[toy + dy[j]][tox + dx[j]] != 'x' && targetMap[toy + dy[j]][tox + dx[j]] < 0 && beamMap[toy + dy[j]][tox + dx[j]] < 0) { tox += dx[j]; toy += dy[j]; } if (deadMap[toy][tox]) { continue; } cout << get < 0 > (target[i]) << " " << dir[j] << endl; goto TURN_END; } } } if (first) { canBeam = vector < vint > (h, vint(w, 0)); queue < pii > q; rep(i, beam.size()) { q.push(mp(get < 1 > (beam[i]), get < 2 > (beam[i]))); canBeam[get < 1 > (beam[i])][get < 2 > (beam[i])] = 1; } while (!q.empty()) { auto it = q.front(); q.pop(); int x = it.second, y = it.first; rep(k, 4) { auto to = adjacentList[y][x][k]; if (canBeam[to.first][to.second]) continue; canBeam[to.first][to.second] = 1; q.push(to); } } } vint lock(target.size(), 0); rep(i, target.size()) { rep(j, 4) { int toy = get < 1 > (target[i]), tox = get < 2 > (target[i]); int fromy = toy, fromx = tox; while (isInside(tox + dx[j], toy + dy[j]) && maps[toy + dy[j]][tox + dx[j]] == '.' && targetMap[toy + dy[j]][tox + dx[j]] < 0 && beamMap[toy + dy[j]][tox + dx[j]] < 0) { tox += dx[j]; toy += dy[j]; } if (canBeam[toy][tox] == 0 && deadMap[toy][tox] == 0) { if (mp(tox, toy) == mp(fromx, fromy)) { lock[i] = 1; break; } } } } rep(i, target.size()) { if (lock[i]) continue; int y = get < 1 > (target[i]), x = get < 2 > (target[i]); int currentCnt = 0; rep(j, 4) { int toy = y + dy[j], tox = x + dx[j]; if (isInside(tox, toy) && maps[toy][tox] == '.' && targetMap[toy][tox] < 0 && beamMap[toy][tox] < 0) { currentCnt++; } } int nextCnt = 0; rep(j, 4) { int toy = y, tox = x; while (isInside(tox + dx[j], toy + dy[j]) && maps[toy + dy[j]][tox + dx[j]] != ',' && targetMap[toy + dy[j]][tox + dx[j]] < 0 && beamMap[toy + dy[j]][tox + dx[j]] < 0) { tox += dx[j]; toy += dy[j]; } rep(k, 4) { int toy2 = toy + dy[k], tox2 = tox + dx[k]; if (isInside(tox2, toy2) && maps[toy2][tox2] == '.' && targetMap[toy2][tox2] < 0 && beamMap[toy2][tox2] < 0) { nextCnt++; } } if (currentCnt < nextCnt) { cout << get < 0 > (target[i]) << " " << dir[j] << endl; goto TURN_END; } } } int use = rnd.rand(0, target.size() - 1); cout << get < 0 > (target[use]) << " " << dir[rnd.rand(0, 3)] << endl; } TURN_END: ; first = false; } return 0; }
