Round3 毒ワインが混じったワイン群から安全ワインを取り出す問題

自分の中ではスタートダッシュがいい方だっただけに，もう少し伸ばしたかった感．問題自体は結構楽しめた．

結果

30th/120 (Provisional: 57th/120)

概要

7/6: 問題理解
7/7-8: DPで期待値
7/9: 大きいケースは重回帰分析でDPの結果推定
7/10: インフラ整備と提出
7/11-16: 手動関数近似
7/17: 迷走
7/18-19: 係数等最適化～最終提出

実際の動き

7/6

問題文を読む．

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16944&compid=56483

ワインW本の中に毒ワインがP本紛れている．
毒を検出するための試験紙をS枚与えられる．
 - 試験紙は毒に反応(検出)するともう使えない
 - 毒に反応してない試験紙は使いまわせる

以下の検出ステップをR回繰り返す
 - 各試験紙について，試験するワインを決める
   - 1枚の試験紙に複数ワイン同時にテスト可能
   - 1枚で複数ワインをテストした場合，毒があってもどのワインかはわからない
 - 各試験紙について，どの試験紙が反応したかの結果を受け取る

このとき，できるだけ多くの安全ワインを発見せよ．

W: 50～10000
P: 1～W/50
S: 5～20
R: 1～10

読んですぐ，なんかどっかで聞いたことがあるなと思って調べたらこれだった． http://stabucky.com/wp/archives/6319

人(今回は試験紙)を2進数に見立てて，2ⁿのワインから1本の毒入りを見つける方法らしい．

毒1本ならこれでなんとかなるが，今回はワイン50～10000，毒1～200なのでほとんどの場合これだけでは無理そう．

考察

試験紙はできるだけ毒ワインに当てないべき
- 毒に反応しない試験紙に使っていたワインは全部安全
- 毒に反応しなかった試験紙は使いまわせる
試験紙1枚当たりのワインが少なすぎてもだめ
- 試験を行える回数に限りがある中で，多くのワインに毒がないと判定したい

なんか確率ゲーっぽい雰囲気を感じて，式をいじったりするうちに，DPとかモンテカルロとかできそうだなという気持ちになった．割といけそうではという気分になる．

7/7

いろいろ考えているうちに，以下の問題がDP(メモ化再帰)で解けそうとなった．

ワイン数W，毒数P，試験紙S，試験回数Rが与えられる．
各試験ごとに，試験紙1枚に対するワインの数Nを最適に定めたときに，救出可能なワインの数の期待値を求めよ．
(毎試験時全部の試験紙を使う，常に毒はランダムに分布)

dp(W, P, S, R, N)とおいて，これを最大化するNを求める．

dp(W, P, S, R, N): N[ワイン/試験紙]のときの期待値
Prob(W, P, S, N, M): 毒に反応しない試験紙がMである確率

$dp(W, P, S, R, N) = \sum_{M=0}^{min(S, P)}Prob(W, P, S, N, M) * max_{N'=1}^{\frac{W - NM}{M}}dp(W - NM, P, M, R - 1, N')$

Probの前計算でO(P² S² W)
dpは最悪O(W² S² R)

ただ探索空間はそんなに大きくならなさそうだしケース絞ればまあいけるやろとなって実装開始．

追記

他の人の解法見てると上よりずいぶん計算量が落ちてるように見えるので，ここの筋はよくなかったっぽい．

7/8

実行してみた感じ期待値より救っているワインの数が少ない場合が圧倒的に多くて悲しくなる．

よく検証してみると，DPの結果をもとに安全ワインを除外するまではいいが，残ったワインを前から順に詰めているので，先頭の方に毒ワインが集まってしまっていることが判明．先頭から順に試験紙に割り当てているのでよくない感じに．

o: 毒なしワイン
x: 毒ありワイン

とすると，

「oooxooxoxooooo」に対して5枚の試験紙を使い，先頭から2本ずつ割り当てると，

「oxxoxooooo」となり次回先頭から割り当てる戦法での期待値が下がる．

ここで，毒が検出されたワインを後ろに回すと，

「oooooxxoxo」

となるので，先頭から順に割り当てる戦法に有利な形になる．この結果，dpの期待値より多めにワインが救えるようになった．

7/9

出力を検証していると，dp計算時の

$max_{N'=1}^{\frac{W - NM}{M}}dp(W - NM, P, M, R - 1, N')$

の箇所が凸関数っぽくなっていた．直感的にも，ある最適なNに向かって救出ワインの期待値は単調増加しそうな気がするので，三分探索に書き換え． (凸でない箇所もあったが，点数を落とさず高速化できたのでOKとした)

ただ，現状だと W < 1000, P < 10 などパラメータが小さい場合しかDPができないので，何かしら手を打たなくてはとなる．

パラメータの種類が少ないので，パラメータから最適なNを推定できないかと考えて，とりあえずExcelにデータを突っ込んでみる．

候補として上がったのが，

機械学習
重回帰分析
手動関数近似

まず実行できる形にしたかったので，手っ取り早くできそうな重回帰分析をしてみる．

参考: http://www.ipc.shimane-u.ac.jp/food/kobayasi/multipleregression_excel.htm

「重決定R2」「有意F」の値がよさげになるように説明変数と目的変数を選んだ(よくわかってない)．

最初適当にやると決定係数が55%くらいだったが，今回回帰が必要な，パラメータが大きいケースに絞ると77%くらいまで上がったので採用．

f:id:threepipes:20170721061746p:plain

説明変数: X値上からW, P, R, S (ただしP > 10)
目的変数: 試験紙が毒に反応する確率(これからNは逆算)

ここまでで，ローカルテストseed1～500の点数が198kだったので勝ちを確信する(これは罠)．

7/10

初期に考えていた「毒が1本の特殊ケース」解法を実装し，いくつかバグを潰す．

点数seed1～500: 198k -> 221k

当時のトップ層が200k手前くらいだったので，これはいけるのではと思いながら提出するも，「160924.42」と出て「は？」となる．

順位表をよく見ると，「79789.78」が4つくらい並んでおり，サンプルコードの点数だということが分かった．手元のサンプルが144kだったので，pretestに点数が出にくいケースが集まっていることに気付く．バグとかではないとわかってつらい．

起きてから試しに，最初にワインをシャッフルして実行するコードを投げてみたら181kが出て一気に10位くらいになってテンション上がる．あと，順位表が全く信頼できないことに気付く．

(本来なら，ここでいろいろなseedでシャッフル提出してみて，適性順位を知っておくべきだった気がする)

7/11～16

重回帰分析部分が流石に適当すぎたので，そこを手動近似することに． (非線形関数の回帰をうまくやる方法が探したが見つからず)

とりあえず，ワイン数W <= 2000，毒数P <= 100 のほぼすべて(Wは100ごと)のケースでDPを実行して，最適なNのデータを収集した．

横軸に試験紙の数S，縦軸に最適Nを取ってプロットしてみると予想以上になだらかになっていることに驚く．

f:id:threepipes:20170721062632p:plain (W=2000, P=8, 線の色はR=1なら黒，R=10なら青)

さらに，グラフの形はWにほとんど影響を受けないということに気付いた．

f:id:threepipes:20170721062851p:plain (W=1000以外上に同じ)

横軸にPを取ってみたところ以下のようなグラフに．

f:id:threepipes:20170721064339p:plain f:id:threepipes:20170721064357p:plain (W=2000, 左はS=1, 右はS=20)

S=20の上は $\frac{W}{S}$ で抑えられている．

反比例らしい形をしていたので，手動で関数近似をしてみたところ，

$N=\frac{2W}{(P-log(R)(S-3))(R+1)}$

がかなり近い近似となった．

下は近似曲線(赤)を上から乗っけた図．

f:id:threepipes:20170721064410p:plain f:id:threepipes:20170721064417p:plain

実際に実装してみたところ，ローカル500ケースで224kが出たのでこれをもとに調整していくことに．

7/17

(この時の順位表上だと)上位陣に追いつくのも現実的に見えたので，戦略はあってるだろうと思ってパラメータ調整をしていくことに．

なぜか，DPの割合を下げて関数近似の割合を上げたら点数が上がったので提出．あと「反応試験紙数=Pとなったときは未テスト区間には毒が無い」「毒分布が均一化したらシャッフル」などのアドホックをいくつか追加して提出．

181k -> 183k -> 184k

さらに，試しにDPを使わない方法に切り替えたらなぜか点数が上がったので，結果的にDPを使わない方針に．(いろいろ検証不足)

この時点でローカル500ケースで235～240kくらい(シャッフル用seedで変動)

7/18～19

手動パラメータ調整が非人間的だったので，焼き鈍しでのパラメータ調整を試してみることに．

wikipediaの焼き鈍しをコピペするも，温度管理などミスして5時間ぐらいただの乱択をしていた．

ただ，ちゃんと動くとしっかりパラメータ調整してくれて，ローカル240kだったseedで244kまで上昇した．

7/20

結構遅くまでパラメータ調整していたため，寝る時間も考えると案外残り時間が少ないことに気付く．

最終確認として，焼き鈍し結果上位100種で20000ケースずつで試して，その上位3種でもう一度検証し，最終パラメータ決定で提出．

184k -> 178k

ある程度落ちる可能性も考慮していたものの，流石に最終提出で下がっているのは気分が悪いので，2時間後にもう一度シャッフルseedを変えて投げることにした(この時点で午前0時)．

で2時間後に再提出．

178k -> 172k

ん～～～～．

ここで，ようやく今までのseed運が良すぎたという考えに至り，力尽きて寝る．

感想

まあ終わりはアレだったけど，plotしたりパラメータ自動調整したりと，いつもと違う動きができ，それなりに楽しめたのでよかった．

その他今回新しく取り入れたこと

提出スクリプト作成
- (Javaなので)開発時はtesterとくっついてるのでその切り離し
- デバッグコード消去など
自動並列テスト実行システム作成
- 外出先から投げれるように
Gradleによるプロジェクト管理
- 環境移行コストの削減

リポジトリ

github.com

最終提出ソースコード

期間中は割と書いたけど，ほとんど没になったのでかなり短くなった．

gist.github.com

　ゲーム作りは毎回完成せずに挫折しているので、短時間で簡単なゲームを作ろうと思い、1時間を目標にブロック崩しを作った。実際はコーディングだけで2時間半かかったが。タイトル詐欺。あくまで目標だったということで。

作業環境：eclipse

言語：Java (swing)

概観 (vine消滅により消失)

ボールやブロックなどは円・矩形描画で済ませ、効果音はなし。

バー操作を十字キーの左右で行い、ボールに当てるとボールが上に跳ね返る。ボールが下に落ちるとゲームオーバー。

スタート画面やクリア画面もないため少し寂しいが、とりあえずブロック崩しとしてプレイできるようにした。

ソースコード

<a href="https://github.com/threepipes/breakout/tree/master/Breakout/src/breakout" data-mce-href="https://github.com/threepipes/breakout/tree/master/Breakout/src/breakout">threepipes/breakout</a>
breakout/Breakout/src/breakout at master · threepipes/breakout · GitHub

クラス設計

JFrameとスレッドを用いたアニメーション
ボール等は抽象クラスSpriteを継承する形の、申し訳程度のオブジェクト指向

　JPanelを継承したクラスMainFrameで、ゲーム状態・キー受付・オブジェクトの管理といったシステム関連のことはすべて受け持っている。

　個別オブジェクトの描画や更新・衝突判定などは、オブジェクト自身に任せている。

考察

キー受付

　現在の実装では、1回のキー受付で1つのキーしか取得していないので、キーの同時押しの際にバーの挙動がおかしくなる。

　これを回避するためには、現在押されてるキーをすべて取得し、押されている方向にx座標を動かすようにする必要がある。たとえばこの場合には、同時押しを行うと左右方向にx座標の加算が行われ、打ち消しあって止まる、などといった動作を実現できる。

衝突判定

　一応の完成に至った際、バーの横からボールにぶつかると、ボールがバーに刺さるバグが残っていた*1。一般的なブロック崩しではどのような対応をしているのだろうと気になって探したところ、対応の種類がいくつかあった。

ボールがどこからぶつかっても、y座標を強制的にバーの上に変更
当たった角度によって反射角度を変える、物理挙動に近い動作
バーが球
バーにボールが当たるとくっついて、再発射できる

　下2つは別物という感じだが、考え方として面白かった。上2つはだいたい半々の割合で見つかり、実装が楽な1つ目を採用した。

感想

　作成直前になって「これ矩形と円の衝突判定いるじゃん！やったことないって！」と慌てて調べたものだから、衝突判定がベクトルを使った大仰な実装になってしまった。よく考えてみれば、矩形の縦横はxy座標に平行なのだから、xy座標の比較だけで済む話だった。

　そもそも形にするだけならボールを矩形として扱ってもよかった。

　ゲーム作成、特に2Dゲームは数学的・物理的に"厳密な動作"というよりも、"納得できる動作"が求められることが多いので、次回短時間で作るときは、うまくごまかせる簡潔な実装をしたい。

*1:これは衝突判定の順番や衝突後の処理の簡素化に起因していたもので、求めていた挙動(横からぶつかったボールは横に反射する)にするためにはボールが1フレーム前にどこにいたか、という情報が必要だった

threepipes_s blog

制作物や参加記など

TCO17 MM Round3 参加記

結果

概要