Hatena::Grouptopcoder

hasiの日記

2014-12-15ICFPC2014参加記(今更)

Competitive Programming Advent Calendar 2014の記事です。

\DiamondPrincess!/

@mecha_g3, @shohei909, @hasi_t, @___Johniel の4人でチーム DiamondPrincess として、

ICFP Programming Contest 2014 に参加しました。

もう5ヶ月ほど前ですね。。

問題概要

(省略)

gcc++作成

宿泊しようかという案もあったが結局 @hasi_t 宅に集まることに。

問題文長いと言いつつ4人で問題文を読む。

@hasi_t はひたすらThe Lambda-Man CPU simulatorを触る。


とりあえずラベルを行番号に変換するやつがないと困るので、雑にPerlスクリプトを書く。

(ちなみに、業務でPerlはほとんど書かない)

次に、関数定義と呼び出しを作る。

ここらへんから「if文の書き方がわからん」とぐちりながら、なんとかif文を書けるようにする。

いろいろ動かしてみると、ループがないと使いづらいので、ループを作成。

ここらへんで朝になり、一旦解散。仮眠をとる。

仮眠から起きて、ローカル変数を作る。

そうしてできたgcc拡張 :

関数定義 :
  FUNC funcname [argname ...]
  VAR [varname ...]
    [関数内容]
  RTN ; これは元からある命令

関数呼び出し :
  [引数push]
  CALL funcname

引数をpush :
  PUSH argname

ローカル変数をpush :
  GET varname

ローカル変数にset :
  値push
  SET varname

IF文 :
  条件push
  IF
    [処理]
  ELSE
    [処理]
  ENDIF

ループ :
  DO
    [処理]
    条件push
  BREAK
    [処理]
  LOOP

演算は基本的にgccに元からあるものを使う。

なので書くコードはほとんどgccを直接書く感じに。

でも、こんだけあればとりあえず書けるやろということでAI作成に移行。

AI作成 (lightning round)

とりあえず貪欲にpillを食べるやつを作る。あと逆方向に進まないように。

同じ所をぐるぐる回り続けてしまうので、評価値同じならランダムに選ぶようにする。

ghostに殺されるのでマンハッタン距離でghostを避けるのを実装したところで提出。


提出後は夕食に行き方針を話し合う。

@hasi_tは引き続き Lamda-Man AI を作り、ghost は他の3人に任せることに。

gcc++修正

lightning roundは人力コンパイルつらい、型が欲しい、とぼやきながらのAI実装だった。

しかし、やっぱり人力コンパイルでがんばることに。

ただ、push命令が、引数はPUSH、ローカル変数はGET、定数はLDC

と分かれている状態だけはなんとかしようと思い、汎用push命令 P を追加。

AI作成 (full round)

ひたすらThe Game mechanicsで動かして挙動を見ながらAIを修正する。

タブレットPCではThe Game mechanicsの動作も遅いなあってなった。


クリアボーナス欲しいので、pillを全部取れるように、そして死なないようにしたい。

敵の動きも読みやすいのでいい感じにしたい。

そこで、敵の動きをDFSして進路を避けるのと、BFSでpill探すのを作ることにした。


Hall of Fameが追加。Wow!

fruitの重要性に気づき、fruitが出現したら取りに行くやつを作る。


結局できたロジック :

  1. 必ず動く
  2. 敵の進路から逃げる(power pill状態では評価値反転)
  3. fruit出現時はfruitに近づく
  4. pillに近づく

power pill残り700tickで評価値反転をやめるつもりが、

; if (pow > 700)
P pow
P 0 ; 正しくは P 700
CGT

こんなバグが含まれているのに土壇場で気付き、

classicの点数が8000点台だったのが17200になったところで提出。

ghost は @shohei909 さんのを提出。結局どういうのかよくわかっていない。。

まとめ

コンパイラは作れず、シミュレータも全く書かなかったので、

ひたすら泥臭くアセンブラを書き続けるコンテストでした。

ちょっとしたコードを書くにも時間かかるので、

最終日は時間無いーとひぃひぃ言っていました。

高級言語ってすばらしい。。


提出したコード : https://github.com/hasipon/DiamondPrincess

結果

Third prize!

Perl が not too shabby になってしまった。わははは

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/hasi_t/20141215