hama_duのブログ

ノンジャンル記事置き場

マラソンマッチで最初の12時間にすべきこと

競技プログラミング

Competitive Programming Advent Calendar 2015 14日目の記事です。

マラソンマッチ関連の記事を書くに当たって、マラソンしてる時の感覚を思い出すため一昨日 マラソンマッチの過去問 を12時間やってみました。 その結果改めて気づいたことと、普段マラソンマッチに取り組む際に気をつけていることをまとめたのが以下の文章です。読者に何かしらの気付きが与えられれば幸いです。

また、偶然にも TCO15 Marathon Finalist である takapt氏 の記事も本日発表(Topcoderマラソンマッチの探索問題で重要なこと) なので、合わせてご覧ください（多少のネタ被りがあるかもしれませんが、ご容赦ください。）

問題文を読み、ビジュアライザを改造する

問題文を読んで、ルールを理解します。合わせてビジュアライザのコードも斜め読みします。

そして、早速ビジュアライザ改造です。 後述するテストを実行するスクリプトでの処理が楽になるよう、ビジュアライザの出力フォーマットをいじります。 加えて、統計的に有用であるかもしれない情報も追加します。

今回、ビジュアライザの出力は以下のようになりました。

シード値,N(盤面の縦のサイズ),M(盤面の横のサイズ),K(パーツのサイズ),P(初期状態で利用不可能なセル数の割合),OrderCnt(オーダー数),スコア

また、ビジュアライザのオプションを追加します。

-n : 盤面の縦サイズを指定
-m : 盤面の横サイズを指定
-k : パーツのサイズを指定
-p : 初期状態で利用不可能なセル数の割合を指定
-o : オーダー数を指定

このあたりは後々の調査で効いてくるので、サボらずにやるべきでしょう。

環境の整備

環境を準備します。私の場合はこんな感じです。 ちなみに、IDE は IntelliJ IDEA を使っていて、今まで不自由したことはないです。

├── src
│   ├── CuttingFigures.java　# (普段はこのファイルを編集する)
│   └── CuttingFiguresVis.java　# (ビジュアライザのソースコードを置く)
└── vis
    ├── Visualizer.jar　# (ビジュアライザ)
    ├── novis.sh　# (ビジュアライズ無しで単発テスト)
    ├── out # (一括テスト結果置き場)
    │   ├── 0-10
    │   └── 0-100
    ├── test.sh # (一括テスト)
    └── vis.sh # (ビジュアライズ有りで単発テスト)

ソースコードは IDE で編集する一方、別窓でコンソールを vis 直下で開いておき、

sh vis.sh 1

ですぐにテストが実行できるようにしておきます。

正のスコアを得る

テストが回せる環境が整ったら早速実装開始です。まずはどんな方法でもいいので、正のスコアを得てみましょう。

また、この時点で結果に付随する何かしらのメタ情報も出力しておくと後で便利です。今回の問題の場合は、

  • 使ったピースの平均スコア
  • 利用頻度が多かったピース
  • 余っているフィールドのセル数

あたりになるかと思います。

初回提出

本番であれば、この段階で一度提出します。コンテスト開始後間もないなら1位が狙えるかもしれません。

イテレーション

以降は

  • 次のアクションを決める
  • 実装する
  • テストする
  • テスト結果を考察する

を繰り返します。この時に役立つのは、考えを逐次メモできるツールです。 数年前までは BitBucket に付属するWikiを使っていたのですが、最近だと自分専用の Slack を立てて体裁を気にせずダラダラと書いてます。 しゃべった時間が自動でメモされるので参加記を起こすときに便利です。また、発言のお気に入り機能を TODOリストとして使っています。

f:id:hama_DU:20151213115522p:plain

次のアクションを決める

ビジュアライザを眺めてふむふむします。もしくは、実行結果とメタ情報を眺めてふむふむします。 コツは「スコアを阻害している原因を考える」「理想状態との差を考える」でしょうか。 または、TODOリストからやるべきこと／有望そうなのをピックアップしてもいいと思います。

アクションは「点数の改善を目指す」だけでなく、「特定のパラメータの範囲で結果がどうなるか調べる」等の、何かしらの気づきを得るための調査でも構いません。

実装する

決めたアクションを実現するため、実装します。ただ闇雲に書きなぐるのではなく、素早く実装できる方法を考えましょう。このときにかかる時間は 30〜60分程度が目安です。 私の場合、新しいアイデアを実装するときは計算量が悪い方法でも、すばやくミス無く実装できる方法を選んでます。 このときに、実装は大変だが計算量が良い方法がありそうなら、TODOリストにあげておきます。

テストする

実装が終わったらテストします。 たくさんのテストケースで走らせるのもよいですが、特に序盤はサンプルのseed1〜seed10でもよいと思います。 このとき、シェルスクリプトを利用すると便利でしょう。(以下は ↑ で紹介した test.sh の中身です)

#!/bin/sh

from=$1
to=$2
program=$3
limit=$4
if [ $# -lt 2 ]; then
  from=0
  to=10
  program="CuttingFigures"
  limit=20000
fi

cp ../src/$program.java .
javac $program.java
mkdir -p out/"$from"-"$to"/"$turn"
datafile=out/"$from"-"$to"/"$turn"/"`date +"%Y%m%d%H%M_$1.txt"`"
if [ $# -gt 0 ] && [ $1 != "none" ] ; then
  touch $datafile
fi

i=$from
while [ $i -lt $to ]; do
    i=`expr $i + 1`
    result=`java -jar Visualizer.jar -exec "java -Xms512m -Xmx512m $program $limit" -novis -seed $i 2>/dev/null`
    if [ $# -lt 1 ] || [ $1 = "none" ]; then
        echo "$result"
    else
        echo "$result" >> $datafile
    fi
done;

また、私はやっていないですが テスト結果をSlackの専用部屋に送りつけると記録と完了通知が同時にできてお得だと思います。(今思いついた)

テスト結果を考察する

本来は結果が悪かったらその原因を考察・・・となるのですが、 私の場合はそのままTODOリストに突っ込んで放置、思い出した時に改めて考えることが多いです。

12時間マラソンの結果

イテレーションを6回ほど繰り返したら、12時間が経過していました。 全体2位Java1位(wleite)のスコア、今回のスコア、5年前の当時の私のスコアを並べてみました。（全て手元のマシンで実行した結果です。）

seed 5年前wleite 今回のスコア 5年前hama_du
1 50456 48811 39405
2 13874 13226 12478
3 24014 19723 18967
4 48781 47111 38030
5 33384 31817 26312
6 7672 7597 6259
7 103751 103187 94408
8 7287 7300 5913
9 33107 31487 25415
10 30602 29758 23283

さすがに5年前には圧勝しましたが、トップに至るまでは遠そうです。当時の順位に換算すると40位程度でしょうか。 ですが、スタートダッシュの結果としては申し分ないでしょう！

まとめ

マラソンマッチではじめの12時間にすべきことをまとめました。

本当はマラソンマッチのジャッジシステムを作りドヤる発表する予定だったのですがあまりうまくいかなかったので別の記事を用意することになりました。構築のアイデアが 同日のAWS Advent Calendar から読めるので、もし興味があればどうぞ。