Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

2017-07-02

[][] TCO17 Marathon Round2 20:55 はてなブックマーク -  TCO17 Marathon Round2 - TopCoderの学習のお時間

https://community.topcoder.com/longcontest/?&sc=5&sd=desc&module=ViewStandings&rd=16928


準備フェーズ


とりあえず、感覚をつかむために次の2つの自明解を作った。

  • 毎ターン一番近い敵に攻撃
  • 990人まで貯まったら一番近い敵に攻撃

これだけでもそこそこ勝てている。前者が強い場合と後者が強い場合がだいぶはっきり分かれていて、勝ちやすいケースは前者が強くて、最終的に負けてしまうケースでは後者の方が強い。

これらをうまく組み合わせていく感じかなー、と考える。

スコアが順位ベースで決まるので、何もしない解に負けてしまうと大ダメージだからそれだけは無いようにしないといけない。


敵の方がPowerが高いことから、基本的には不利なんだけど、この不利を緩和したい。端数がたくさん切り捨てられるような攻撃をするといい、とかそういうのがありそう

…と考えていたら、6人以下で攻撃すると1:1でロスなし対消滅できて最もおトクであることに気づいた。速攻で連打するとそこそこ勝てるのは最初実装したやつで分かっているので、簡単に勝てるケースはこれをどこまで最適化できるかのゲームになるんだと理解する。

…で、そこではそんなに差がつかなさそうだからやっぱり難しいケースをどう賢くするかだなあ、という雰囲気になる。


モンテカルロシミュレーションやったりするのかなあと思いつつ、何やるにしても敵のパラメータ(power・attackT・locality)やTroopの行き先推定は必要なのでそいつらを実装していく。


実装フェーズ


そして実装していたら1週間経ってしまったので絶望する https://twitter.com/tomerun/status/864889052826288128

ついで、速攻ケースのシミュレーション+倒すbaseの順番での山登りを書き上げて、ある程度の高速化・パラメタ調整をやる。

この時点でまだ本丸(勝ちにくいケース)に手がついていないのに、もう2回目の週末が終わっていて絶望する https://twitter.com/tomerun/status/866298649680027648


とにかく、速攻で勝てないケースの戦略を作っていく。

とりあえず、全滅させられてしまう直前の逃避戦略を実装する。これはまあやるだけ

最序盤ですぐ倒せるところだけは速攻で倒しておくとして、基本は980まで貯めてから攻撃する。攻撃先をどこにするのかが考えるところ。

単純に一番近いところを攻撃するのは、すでに倒せるのが確定しているところに集まりすぎで損、というのはこれまでの結果から分かっている。

すでに倒せることが確定したbaseへは攻撃せず、他を狙うようにするとそれなりに良くなった。

あと、980貯まっていても、敵の攻撃が向かってきていて、攻撃で人数が半分になった状態では全滅させられてしまう場合は、攻撃せず待つようにしたり。

ここまででもう終了前日になってしまったので、全然細かい調整できてないんだけど観念して提出したら93万点とか出てびっくりした。

最後に、他の敵から攻撃されづらい位置にあるbaseを優先的に攻撃する、というのを入れようとしてみるが、良くならなくて終了


ビジュアライザ

f:id:tomerun:20170702204626p:image


カスタマイズした点は以下の通り。

  • 早送り・巻き戻し可能に
  • growRateに応じてbaseの形を変える
  • baseのindexも表示できるように(デバッグ用、普段はoff)
  • playerごとの合計人数を表示

そのほか


  • 今回は実装が難しそうで、そこまで高速化勝負にはならなさそうだったのでJavaを使った。結果的に、やっぱり実装がボトルネックだったのでこれは正解だった
  • 仲間同士で人数を1箇所に集中させて成長速度を増やすのはちょっとやってみようとしたが、あまり効果が感じられなくてやめた
  • 敵のlocalityも推定した(離散化してベイズ推定)けど結局使わなかった

結果

2017-05-11

[][] TCO17 Marathon Round1 01:11 はてなブックマーク -  TCO17 Marathon Round1 - TopCoderの学習のお時間

https://community.topcoder.com/longcontest/?&sc=5&sd=desc&module=ViewStandings&rd=16903


やったこと


3段階で焼きなましをした。

  1. 35*35のグリッド上で、ランダムな頂点をランダムな位置に動かす遷移。評価値は、各辺について目的の長さと実際の長さの差の絶対値
    • 点の位置の重複は許す
    • 終わったら、各頂点をグリッド内の20*20のどこかにばらまいて700*700にする
  2. ランダムな頂点をランダムな近傍に動かす遷移。現在の辺の比の最大/最小の少し内側を目標にして、そこから外れた辺にペナルティがつく評価値
    • ペナルティは、(外れ量+0.5)^8 とか外れ具合に応じて大きく傾斜をつける
    • 頂点の移動距離は時間に伴って徐々に小さくしていく
  3. 比が最大/最小の辺に属した頂点をランダムな近傍に動かす遷移。真のスコアが評価値
    • 頂点の移動距離は時間に伴って徐々に小さくしていく
    • どの辺の比が最大/最小かを管理するのに、辺を比の値でバケットに入れて扱った
      • 各辺が自分のバケット内で何番目かを覚えておくと更新がO(1)でできる

最後の仕上げとして山登りをした。遷移は、比が最大/最小の辺に属した頂点を微少に動かして、他の辺が最大/最小を超えたら再帰的にその辺の頂点を動かす、というのを一定深さまでやる。

一応無意味ではないかな…くらいの効果はあった(結果のBestsが多かったのはこれのおかげだと思っている)


焼きなましの3フェーズの時間配分は 0.39:0.16:0.45 だった。これと別に最後の山登りに50ms使う。

焼きなましのイテレーション回数は合計6000万回くらい。SSEも使った(高速化の恩恵は1割程度)


時系列で


とりあえず真っ先に思いつくのは比が最大/最小の辺をいじることだけど、最大/最小だけ見てたら評価がハードすぎて一瞬で局所最適にハマりそう。もっとソフトな感じに評価したい。

一瞬バネ物理シミュレーションが浮かんだのだけど、その手の問題は以前ぼろ負けした(TCO13R3)のでひとまず考えないことにする。

というわけでまず焼きなましPhase2だけを作った。これが初日の48万点。


で、いろいろなケースの結果を出力して眺めていたら、長い辺がボトルネックになりがちなことが分かる。

長い辺は後から微調整が効きづらいので、最初の方でだいたい良い感じにしておかないといけない、と考える。

そこで焼きなましPhase1を作った。比で評価すると短い辺の重みが強くなってしまうので、差で評価。これで70万点超え。


ちょこちょこ調整した結果が3submit目の76万点。


ここで満を持してPhase3を追加すると4submit目の78.5万点。

https://twitter.com/tomerun/status/855468636860891136 ここで言っていた「伸びしろ」はこれのこと)


このあとはほとんど焼きなましの調整と高速化だけだったと言ってよい。

最終日の1日前の段階でアルゴリズム的な改善は打ち止めにして、ここで有給休暇を取って細かい高速化をまとめてやり、最終日に会社行っている間にクラウド使ってパラメタ調整、というのが最近の試合運びのトレンドになっている。

EC2のc4.8xlargeを24時間ほど動かして$17くらい使った。35スレッドだと1000ケースのテストが3分で終わるので良い。


もうちょっと探っておくべきだったかなーというところは、

  • 多スタート
    • 難しいケースでスコアが0.1くらいぶれることがあるので、その安定性のため
  • 辺の目標長を最初から短めに設定しておく
    • ちょっとやってみたら良くならなかったので捨てたのだけど、実際最終状態が短い方に寄るケースが多いし、Psyhoさんはこれ入れるとめっちゃ伸びる(余裕で1位超えるくらい)らしいし、もっと時間をかけて見ておくべきだったかも
  • 頂点の移動先はランダムじゃなくて辺の向きを考えて選ぶ
    • 1位2位はそれをやっているみたいなので

結果

2014-06-15

[][] TCO14 Marathon Round2 18:45 はてなブックマーク -  TCO14 Marathon Round2 - TopCoderの学習のお時間

http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15982&pm=13189


問題


ランダムな大きさの長方形がN個与えられる。長方形の各辺の長さは[1,1000]、Nの範囲は[100,1000]の一様分布。

こいつらを平面内に配置して穴を作る。

(穴の個数)^2 * (穴の面積合計) を最大化せよ。


やったこと


大きな穴を1つ作る+小さな穴をたくさん作る が最適になるのはまあ直感的にわかる。

colunさんに倣ってBigHoleとManyHolesと呼ぶ。


ManyHolesに何個の長方形を回すかは、実験してみたらN*0.54くらいが良さそうだった。

ManyHolesを作るときは、BigHoleで使われている長方形も利用した方がManyHolesに寄与する長方形の数を稼げる(その結果穴の数が増える)ので、BigHoleにくっつけて作る。


ManyHolesの領域はできるだけ表面積を小さくした方が良い(N個の長方形から作れる穴の数の最大値はNが大きいとほぼN個なんだけど、領域の外側に出ている長方形の個数分その限界から遠ざかっていく)ので、ManyHolesの部分は丸い感じになるようにする。

そのため、BigHoleの作り方を工夫して一部を外側に張り出すようにした。それでできた空間に小さい長方形を詰めていく。



小さい穴をたくさん作る方法なんだけど、賢い配置を考えて決めるのは泥沼っぽい気がして探索することにした。

長方形を小さい順に取って、既存の長方形の右側か左側に接するところを試す。他の長方形に接する一番端の箇所を見つけて、隙間ができていたらそれを穴ができたと見なす。

      |               |   |
      |               |   |
      |               +---+
 -+   |                 +---+
  |   +----             |   |
  |+----+      や     -+|   |
  ||    |              |+---+
  ||    |              |
  |+----+              |
  |                    |
 -+                   -+

こんな感じだと良い配置。


時間制限いっぱいまで、使う長方形の順序をちょっと変えながらこれを繰り返す。本当はビームサーチしたほうが良いのだと思うけど、実装時間が足りなくて断念してしまった。


あと、BigHoleの内側にManyHolesを作るのではなく外側に作ったら、面積が2%くらい増えるなーと思ってたけど、どうやっても穴の個数が減ってしまってうまくいかなかった。


画像


seed=1の例。


全体:

f:id:tomerun:20140615183106p:image


上部:

f:id:tomerun:20140615183105p:image


ビジュアライザには次の変更を加えた。

  • 穴になった部分が赤く塗られていたけど気持ち悪かったので消した
  • スクロールやズームを可能にした
  • 縮尺を表示するようにした
  • ビジュアライズ部分をテスタと分離して別プログラムにして、テスタ実行時に表示するのではなくスタンドアローンで起動できるようにした
    • テスタではログに出力しておいて、ビジュアライザにはそれを読み込ませる

結果

  • provisional score : 954551.54(各ケースで1位を100万点とした相対スコアの平均)
  • provisional rank : 9 / 170
  • final score : 954969.99
  • final rank : 10 / 170
  • レーティング : 2188->2250

意味のあるスコアを出すまでの実装が大変なのでやっぱり参加者少なかったですね。

2014-05-04

[][] TCO14 Marathon Round1 21:23 はてなブックマーク -  TCO14 Marathon Round1 - TopCoderの学習のお時間

http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15938&pm=13132


問題


yowaさんのスライドを参照。

http://topcoder.g.hatena.ne.jp/yowa/20140424


やったこと


問題読む→はい、いつものビームサーチのパターンですね

2次元グリッド上でなんかゲームやって、1手ごとならビームサーチ、全体を構成するのなら焼きなまし、というパターン最近多すぎて飽きてきた…


ターン数が10000と多くて、評価関数で色々やろうとするとビーム幅小さくなってどうやってもスコア下がってしまうので、評価関数はごく簡単にしてひたすら高速化を頑張った


探索空間


C=4の場合は1手で消せるところ、C=5,6の場合は1手か2手で消せるところを全探索

始めは高速化のため、前回動かしたところの周辺だけ探す、ということをやっていたけれど意味なかった


ビーム幅は、時間をいっぱいまで使えるよう実行中に残り時間を見ながら動的に変える


評価関数の要素


  • 累計の得点
    • 連鎖を全部シミュレートしてしまうのはあまり意味がなく、得点が0か1か2以上か、だけ判定した
  • 2×2のブロック中に3つ同色がそろった箇所・2つ同色がそろった箇所が、盤面内に何個あるか

データ構造と探索方法


struct Board{
    uint64_t f[20];   // 各セルがどの色か。最高6色、番兵として使う無効分も入れて7色なので1セル3bitで収まる。周囲2マスずつ番兵にするので20*20分確保
    uint64_t v[15];   // 各2×2の領域がどのような状態か。15×15個分確保。
                      // 3つ同色のパターン:4個、2つ同色*2のパターン:3個、2つ同色*1のパターン:6個、同色無しのパターン:1個 で合計14個なので1つ4bit
    uint64_t v2[15];  // 高速化用。基本的にはvと同じだけど、一度探索してみた結果1手や2手では消せないとわかった箇所は、
                      // 0(無効を意味する)で上書きして再度調べないようにする
};

探索するときは、たとえばv2が「3箇所そろっていて右下だけ違う色」を示しているときは、次のような状態になっている。

 AA
 AB

下の図のXの箇所を調べ、そこの色がAだった場合、それをBの箇所に持ってくる動きを候補として採用する。

 AA_
 ABX
 _X_

C=5,6でXの箇所が候補にならなかった場合は、次に、2手で揃えられる箇所として、下の図のYの位置も調べる。

 __Y__
 _AAY_
 YABXY
 _YXY_
 __Y__

v2が「2箇所そろっている」の場合も、同じように2手で揃えられるパターンを全列挙してそこに揃えたい色が入っているかを調べる。


反省


  • 同一盤面の除去をやらなかった
  • 評価関数のパラメタ調整をやらなかった

同一盤面の除去を軽く入れてみたら2%くらい上がったので、もっとこの辺をちゃんとやっていたら通過ラインくらいまで行けていた可能性もある。

詰めが甘いです


結果

  • provisional score : 950346.80(各ケースで1位を100万点とした相対スコアの平均)
  • provisional rank : 10 / 333
  • final score : 952155.96
  • final rank : 10 / 333
  • レーティング : 2334->2371 highest更新

2013-06-02

[][] TCO13 Marathon Round2 20:26 はてなブックマーク -  TCO13 Marathon Round2 - TopCoderの学習のお時間

http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15648


問題


yowaさんのスライドを参照。

http://topcoder.g.hatena.ne.jp/yowa/20130516


やったこと


まず問題読んで、これ去年のRound1と似てるなあ、はいはいビームサーチでしょ、と書いてみたらなぜか50点くらいしか出なくて涙目


評価関数みたいなので探索順序を決めるDFSを書いてみる→73点くらい

それから探索順序をいろいろ工夫してみるけど全然スコア上がらなくて早くも心が折れそうになる


ランキングを見ると64点くらいの人が多数現れていて、この人たちは一手ごとに一番たくさん鏡が壊れるところを選ぶGreedyをやってるのだろうと推測される


ビームサーチでそれより低いスコアしか取れないのはありえないので、なんかおかしいのだろうと書き直してみる→85点くらい出た。どこかでバグってたらしい

同一盤面除去をやるとあっさり90点越えた

ちょこちょこ評価関数を調整して97点くらいになったので提出

DFSで悩んでたのも、その間に偶奇性とか評価関数の要素を考えられたから無駄ではなかったと思うが


あとはC++で書き直しての高速化と、Nの偶奇で係数を分けたりの細かい調整で103点くらいまではチマチマ伸ばしたけど最後の方は全然改善しなくなってしまった


評価関数、探索順序について


  • 評価関数の要素にはこれらを使った
    • 残った鏡の数(少ない方が良い)
    • 行・列ごとの鏡の数の偶奇(偶数の方が良い)
    • 空になった行・列の数(多い方が良い)
  • 同じ盤面から分岐する数は一定以下になるよう制限を付けた
  • 評価関数の高い順に残すのではなく、いくつか下の方からもランダムにとってくる
    • これが効くのって評価関数がいまいちだからだよね…

評価関数の要素に、鏡が固まって残っていること、例えば16個残っていたら2*8よりも4*4の方が良い、ということを含ませようとしたけどうまくいかなかった。

評価の計算方法があまりうまくなかった。参照:https://twitter.com/tomerun/status/334719466153848832

二乗和は、数が大きい方を大きく評価しすぎてしまう。小さいところがあるのが悪い、というのを評価したいのだから不適切だった

このあたりの数式的な考察がテキトー過ぎてよくない


高速化について


  • 盤面の持ち方は、各マスが上下左右の隣接する鏡までの距離を持つ2Dリンクリスト的なので
    • 各マスの情報は、鏡の状態がLかRか破壊済みかで2bit、4方向の隣接する鏡までの距離が7bit*4で、1つの32bit整数に押し込められる
    • 別の方針として、空になった行が発生したら随時詰めていくのもやってみたけどこっちの方が速かった
  • 盤面の同一性判定はZobrist Hashingで
    • 使用済みのハッシュ値は全体で1つのsetに入れるのではなく、残っている鏡の個数で区別してN*N個のsetに分けて入れる(setは重い)
  • 盤面のメモリは最初に全部確保しておいて使い回す
  • 評価のためのビームのシミュレートは、壊す→戻す のではなく、「何回目のシミュレートで壊されたか」情報を盤面と別にマスごとに持っておくことで、元に戻すフェーズを無くした
  • 鏡を壊した数が4個以下のビームについては、それが出てきたところから入れるビームは同じ経路を逆に辿るだけなので省略する
  • ある盤面から1手進めるとき、盤面をコピーしてビームをシミュレートして新しい盤面を作るのだけど、同じ親から別れる盤面のうち1つだけは、盤面をコピーするのではなくswapで済んでコピーコストを減らせる
  • 盤面の中に、同じ行・列に他の鏡がない孤立した鏡がある場合は、適用する遷移はその孤立した鏡を壊すビームだけにする

結果


  • provisional score : 103.88(100ケースの合計)
  • provisional rank : 7
  • final score : 2094.61(2000ケースの合計)
  • final rank : 7 / 247
  • レーティング : 2326->2354 highestを2だけ更新