TCO19 Marathon Match Round 1 参加記

TCO19 Marathon Match Round 1に参加しました。

順位表:http://cmap-leaders.topcoder.com/challenges/30092483?reviewTypeId=0d5b13d6-7562-4045-af35-d6a5cf62de31

問題設定

概要

N人の人がいる。人は0からN-1までの整数で番号付けられ、i番目の人の高さはH[i]である。最初、左からi番目にはi番目の人が立っている。この状態から並び順を変える操作をX回行う。このとき、できるだけ移動距離の総和を小さくしつつ、i回目の並び替えの直後に左からj番目に並ぶ人の高さをarrangement[i][j]に近づけたい。

スコアリング

i回目並び替えの直後に左からj番目に並ぶ人の番号をord[i][j]とし、i回目並び替えの直後のj番目の人の位置をpos[i][j]とする(pos[i][ord[i][j]] = j)。distをabs(pos[i][j] - pos[i-1][j])の総和とし、errを(H[ord[i][j]] - arrangement[i][j])^2の総和とするとき、スコアはdist+sqrt(err)と計算される。

テストケース生成

以下の範囲から一様ランダムに選ばれる。

 10 \le N \le 100

 2 \le X \le 20

 10 \le M \le 1000

 1 \le arrangement[i][j], H[i] \le M

Mは高さの上限を表す変数。Mが選ばれた後に  arrangement[i][j], H[i] が選ばれる。

解法

焼きなましました。

近傍設定

近傍は、「i番目の人とj番目の人の、a回目からb回目までの並び替えでの位置をそれぞれ入れ替える」と設定しました。i回目の並び替えでj番目にいる人が、i回目の並び替え以降でとおる場所のarrangementの合計値をsum[i][j]と書くと、errの更新は、

err +=  2 * (H[i] - H[j]) * (sum[a][pos[a][i]] - sum[b + 1][pos[b+1][i]]);

err +=  2 * (H[j] - H[i]) * (sum[a][pos[a][j]] - sum[b + 1][pos[b+1][j]]);

とO(1)で計算できます。実際に遷移が起きるとき、O(X)かけてsumの値を更新すれば、O(1)でスコア差分が求まり、O(1)で遷移判定を行うことができます。

distに関して、i番目とj番目の人の、「(a-1)回目からa回目」及び「b回目から(b+1)回目」の移動が変化しています。ただし、b=Xの時は「b回目から(b+1)回目」の移動が存在せず、この場合は変化する箇所が少なくなり、特別扱いします。

遷移提案

50%の確率でb=Xとする。b=Xは状態の変化量が小さく、焼きなましの遷移としてよい性質を持っているといえるので、確率を大きくしておく。

a,iをランダムに選ぶ。a番目の順列の前後でi番目の人の近くにいる人をjの候補とする。候補の中でiから遠い位置にいる人から順に見ていき、遷移が受理される時点でイテレーションを終了する。

温度管理

温度そのものをスケジューリングするのではなく、最良スコアと現在の状態におけるスコアとの比が線形に減衰するように温度を調整するようにした。具体的には、線形に1から0に減る量をrとし、W=1+0.03rとしたときに、(それまでに見つかった最良スコア)×W>(現在のスコア)なら温度を上げ、そうでなければ温度を下げる、とした。

再スタート

時間を4分割してそれぞれで焼きなましを行った。Wの初期値は減衰させるようにした。

感想

久しぶりにまともに参加(といっても3日だけ)できて楽しかった。

COVE VS Reborn 参加記録

ゲームAIコンテスト「CODE VS Reborn」に参加し、予選6位、決勝3位でした。

https://codevs.jp/

決勝提出版アルゴリズム概要

カウンターを狙うため発火点を高めに構えた状態を維持しながら連鎖を延ばす。連鎖の探索はビームサーチ。左から2列目にお邪魔4つと1から9の数字ブロックをそれぞれ落としたとき発生する連鎖数を評価関数に含めた。

18ターン目まで考える。最初はビーム幅4000くらい。最後の数ターンはビーム幅100くらいまで減らす。こうすることで、早い段階でのつぶしに強くなる。なぜなら、ビーム幅が広いと、「一時的に連鎖数が伸びていないが最終的に連鎖数を最大化できる」ような手を選んでしまい、連鎖数が伸びていないタイミングで相手に発火されるたときカウンターで返せる連鎖を作れなくなってしまうから。ビーム幅をあえて狭めることで、常にそこそこの連鎖数を維持しながら伸ばせるルートを見つける。

18ターン目に近づいたら、「2ターン先まで全探索、3ターン先からビーム幅100で5ターン先まで読む」に切り替える。相手が自分に合わせて連鎖をどんどん伸ばしてきたときにも対応できるようにした。

自分の解答にオリジナリティーがあるとしたら、ビーム幅をわざと狭めることでカウンタ―成功率を上げている点だと思う。相手の盤面を見る手を変えるなど、調整に時間がかかりそうなことをせずに決勝に行けたのは良かった。

経緯

最初と最後で5日ずつくらいしか時間がとれなかったので、いかにコスパの良い戦略を取るかが重要でした。最初の5日間で探索部分をほぼ完成させて、最後の5日間で戦略的な部分を頑張るという方針にしました。

残り5日の時点で上位陣の対戦記録を見ると、keraさんが明確なカウンター戦術を成功させており、僕も真似することにしました。すでに作ってある評価関数は、各位置に数字ブロックを落としたときの連鎖数を見ていたのですが、落ちる位置をnつ上にずらすだけでそれなりにカウンターの動作をするようになりました。

この時点で30位くらいまで落ちていたのですが、上記の変更を加えるだけで一気に13位あたりまで戻りました。

その後はひたすら自己対戦でパラメータ調整を行い、運よく予選6位に滑り込みました。

時間がなかったこともあり、ビット演算や並列化による高速化、相手の盤面を見て手を変えるなど、実装や調整のコストが大きそうなことには全く手を付けられませんでした。それでも予選通過できたのは、カウンター戦術を取り入れることができたことが多いと思います。

決勝では初撃の連鎖数をみんな大きくしてくるだろうという読みから、より大きな連鎖に対してもカウンターをできるよう、より受け身になりました。それ以外は特に変更してません。

決勝で学んだこと

評価関数にも人ごとに少しずつ差異があって面白かった。評価関数として8近傍に空白があるブロックを消してみたときの連鎖数を見ている人が多かったなか、tanzakuさんはすべてのブロックを消してみたときの連鎖数を見るということをしたらしい。これで一度発火点を埋めてから連鎖を延ばすみたいなパターンを検知できるらしい。また、ケイマ、大ゲイマの位置関係に消滅するブロックの対があるかパターンマッチを評価関数に入れている人が多かったが、keraさんは縦の段差をすべて見ている。

どのように連鎖力を評価するかという点も話に挙がった。僕は時間がなくて自己対戦でしか評価していなかったが、これは良くない。例えばビーム幅を増やすと連鎖力は上がるかもしれないが、カウンター発火の成功率は低くなる。連鎖力は連鎖力として量るべきだろう。ターン数固定でできる連鎖数を評価基準にしている人が多かった。また、y.sさんなどは、ツモを実際の試合からサンプリングしたようだ。公式の記述とは異なる分布から生成されているらしく、割と性能評価に影響があるらしい。

予選でサーバーを借りてやっている人、どうやってクライアントを動かしているんだと思っていたけど、ローカルでクライアントを立ち上げて、実行コマンドのところでsshすればよいというのをnyashikiさんに教わった。言われてみれば当たり前だけど全然気づかなかった。

 

 

TCO18 MM Lightning 2 KnightsAndPawns 参加記録

問題文:

http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17225&compid=66697

順位表:

http://community.topcoder.com/longcontest/?module=ViewStandings&rd=17225

 

大学のテスト・レポートとかぶっていてだいぶつらい

 

問題概要

H*Wのボードにいくつかのポーンが置かれている。ここにいくつかのナイトを置いていく。このとき、すべてのナイトについて、攻撃できる駒の数がちょうど2でなくてはならない。置くコマ数を最大化せよ。

解法

 とにかく時間がないので実装が簡単でパラメータ調整でゴリおせそうなものを目指しました(パラメータ調整は大学のレポートなどと並行してできるので)。

一般的な考察

・ナイトのattack数が2ということは、attackしているナイト同士を結ぶとパスができて、パスは閉路であるかポーンを端点としていると言えます。

・3つ以上のポーンを攻撃するマスはそもそも考慮に入れる必要がありません。

validと準valid

 validな状態とは、非負スコアが得られる状態、すなわちすべてのナイトのattack数が2である状態です。これに対しすべてのナイトのattack数が2以下である状態を準validと呼ぶことにします。

焼きなまし

僕の解法が全体としてやっていることは焼きなましです。以下に示す状態遷移を繰り返して準validな状態を得た後、validな状態に直すところまでを一遷移として、焼きなましをします。

状態遷移

 状態が準validであるとします。基本的な考え方は、「新たにナイトを置いていきたいが、準validな状態を保持したい」です。

 attack数が1であるナイトを一つ選び、その近傍にナイトを一つ置きます。選んだナイトをA、Aの近傍に置いたナイトをB、さらにBの近傍にあってAでないもの(ナイトorポーン)をCとします。AとBを設定すると、

  1. そもそもCが存在しない。
  2. Cとして考えられるものがちょうど1つ存在する。
  3. Cとして考えられるものが2つ以上存在する。

のどれかが成り立ちます。

 1の場合は簡単で、Aのattack数が2、Bのattack数が1、それ以外は影響なしなので準validな状態は保たれています。

 2の場合は、Aのattack数=2、Bのattack数=2、Cのattack数+=1、となります。Cのattack数が1増えるということは、attack数が3になる可能性があります。その場合、Cがナイトであれば準validでなくなってしまいます。そこでCの近傍であってBでないもの2つのうち一つを消します。もし両方ともポーンであるならば、Cを消してしまいます。

  3の場合は、そもそもBの候補として除外しておくことにします。 

 以上の挙動は、以下のように説明できます。

・ナイトが作るパスの端を伸ばしていって、ほかのパスにぶつかったらそのパスを切って切り口につなぐ。ほかのパスの端点とぶつかったら2つのパスをつないで一つのパスになる。

 この操作において、ナイトの数が減ることはありません。

 そもそもAの候補がない場合ですが、適当な空きマスを選んでナイトを置き、上述の2の場合と同様な処理を施すことで、状態を変化させることができます。

準validからvalidを得る

準validな状態からattack数が1以下のものを消していくと、最終的にvalidになります。これは不完全なパスをすべて消すことに対応し、得られたvalidな状態は、消す順番などに依らず準validな状態に対して一意に定まります。

焼きなましの一遷移

焼きなましの一遷移は、「準valid保持の状態遷移を20回程度繰り返したのち、上述した方法でvalid解を得る」です。遷移回数は100万回ほどになりました。

 

細かい工夫

大学レポートと並行しながらやっていた関係で、なんでうまくいくか考察できていない部分が工夫点のほとんどになってしまいました。すべて挙げるときりがないので一部だけ書きます。

・一定期間ベストを更新しないときロールバック処理を行いました。ロールバック直後、ランダムなナイトの消去操作を何回か行いました。また、ロールバック直後の状態遷移の回数をマスの大きさぐらいまで増やしました。

・状態遷移において、低確率でattack数1のナイトを消去するようにしました。

example test

Example scores:
0) 15.0
1) 1335.0
2) 3457.0
3) 1426.0
4) 2001.0
5) 173.0
6) 1389.0
7) 258.0
8) 230.0
9) 1528.0

seed2

f:id:ats5515:20180801005942j:plain

 

TCO18 MM R3 InvestmentAdvice 参加記録

問題文:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17203&compid=65421

順位表:

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=17203

 

最終日のみの参加になってしまった

 

問題内容

概要

N個のファンドがあり、それぞれ異なるexpertにより運用されている。毎round、各expertは次roundまでにリターン可能であると予測される利益の投資額に対する比を提示する。どれにいくら投資するかを決めて、利益を最大化せよ。

制約、条件

1roundで1つのexpertに投資できる額の上限は400000である。また、投資額の合計が所持金額を超えてはならない。これらの条件を満たせば、投資額は毎roundごと自由に決められる。投資したお金は必ず次のroundには清算される。利益は、各ファンドごとに投資額×真の利益比(小数点以下切り下げ)によって計算される。この値は次のroundにおいて知ることができる。

・最初から持ってるお金=1000000

・ファンド数 N=nextInt(10,50)

・全round数 R=nextInt(10,100)

・各ファンドの真の利益の比=平均0、標準偏差0.1の正規分布に従う。

・expertの提示する値:

確率Aで平均が真の利益、標準偏差Sの正規分布に従う。

確率1-Aで平均0、標準偏差0.1の正規分布に従う。

ここでA,Sはexpertごとに持つパラメータで、

A=nextDouble()

S=nextDouble()*0.2

として決定される。これはroundごとに変化しない。

やったこと

平均a、標準偏差s、の正規分布確率密度関数をf(x,a,s)と書くことにします。

基本方針

まず、毎roundの利益の期待値を最大化するには、各ファンドごとに利益率の期待値を求め、大きいところから順に、期待値が正である間、また所持金が残っている間、上限額(400000)ずつ投資していけばよいです。

もし全く投資しない場合、そのファンドの真の利益率についての情報が得られません。よって、情報を得るために期待値が低いところに投資することも考える必要があります。情報を得たいファンドについては一定の額を投資することとし、それ以外についてはそのroundの利益の期待値を最大化することを考えることにします。

期待値の計算

ベイズの定理とかで確率計算します。以降一つのファンドに注目して考えることにします。

あるroundにおいて、真の利益率がactual、提示された値がreportであったとします。

expertのパラメータの確率分布は、

p(A,S | actual,report) ∝ p(A,S)×p(report | actual,A,S)×p(actual | A,S)

です。p(report | actual,A,S)は、問題の制約において、真の値から提示する値を決定する部分がそのまま使えます。

p(actual | A,S)はそもそもA,Sに依らないので無くて良いです。したがって、

p(A,S | actual,report) ∝ p(A,S)×{A×f(report,actual,S)+(1-A)×f(report,0,0.1)}

投資したファンドについては前roundのactualの情報が分かるので、これを用いて確率計算します。投資しなかったファンドについては、

p(A,S | report) ∝ p(A,S)×p(report | A,S)

=p(A,S)×{A×f(report,0,sqrt(0.01 + S*S))+(1-A)×f(report,0,0.1)}と計算できると思いましたが、やるとスコアが悪くなるのでやってません。なんで

続いて、利益の期待値を計算します。さっきまでのactual,reportは直前roundの情報でしたが、これからは現roundのactual,reportです。actualに関しては予測値ですので、区別するためにXと書きます。

p(X | report) ∝ p(report | X)×p(X)

=∬p(report | X,A,S)×p(X,A,S) dAdS

=p(X)×∬p(report | X,A,S) dAdS

=f(X,0,0.1)×∬{A×f(report,X,S)+(1-A)×f(report,0,0.1)}dAdS

後は期待値ですが、

∫X×p(X | report)dXを計算すればよいです。

これらの計算は解析的にはできそうにありません。A,S,予測actualに関して標本化して計算しました。

情報を得るための投資

投資した回数が一定回数以下のexpertには、必ず40だけ投資するようにしました。この値は大きすぎるとそのroundに得られる利益の期待値が低くなる損が大きくなり、小さすぎると得られる情報の正確さが落ちます。

「一定回数」の決め方ですが、全ファンド数と全round数のみに依るものとして考えました。あらかじめいくつかの{全ファンド数、全round数}に対して「一定回数」として最善の値を求めておき、間の値は補完することでテストケースごとの「一定回数」を求めました。

この辺は改善の余地が大いにあると思うのですが、時間がなくてやってません。

 

TCO18 MM R2 CrystalLighting 参加記録

問題文:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17179&compid=64279

 

 順位表:

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=17179

 provisional8位でした。

記事にするようなことをしていないので一般的な話も含めて書きます。

やったこと

焼きなまし。

近傍

遷移は各アイテムを置くor消す、ランタンを自分の発する光が通るマスへ移動。

 

焼きなましの近傍の選び方の基本は、高速に動作すること、解空間が滑らかになること(遷移によるスコアの変化量が小さい、任意の状態から別の状態への遷移回数が少ない)。そもそも焼きなましが有用かはそういう近傍が存在するかで判断できると思う。

各アイテムを置くor消すは自然で思いつきやすい。移動が有用なことも焼きなましに慣れていれば割と思いつくと思う。光線に沿った移動は、基本的に変化が4方向(2光線の削除+2光線の追加)になるので、設置、削除の近傍に劣る理由がほぼない。

評価関数

 

各アイテムのコストを0から真値に線形に変化させた。

一般に、焼きなましの評価値が真のスコアであるという保証はない。だから、設計の最初の段階でそれを意識した方が良い。意識しないと、「真のスコアで焼きなましてベストスコアを保持してロールバックしたりする」みたいな工夫をした後で、真のスコアでない値で焼きなましをしようと思った時に無駄に実装コストがかかるようになってしまう。

僕はこれが原因で、上位陣がやっていた、2色のうち一方のみで照らされるクリスタルのコストを変化させるということを試さなかった。正確には、試したけどスコアが改善しないと勘違いした。試したとき、実装上の都合でイテレーション回数の増加という副作用が起きていて、スコアが改善しなかった。この副作用は時間をかけて実装をやり直せば起こらないものだった。

遷移の実装

実装は、各マスを通る光線を愚直に(差分計算はするが)シミュレートするというもの。ランタンが置ける位置のリストなどを保持することができる。遷移回数は6千万程度になった。

反省

遷移の実装に関して、一本の光線が通るマスでグループ化し、各マスからある方向へ行ったらどこでぶつかるかを保持しておけばもっと高速に同じ遷移を達成できた。ランタンが置ける位置のリストを保持などはできないが、アイテムの移動が遷移として有用なので、遷移提案のオーバーヘッドはほとんどなくなると思う。

とりあえずのつもりで愚直な実装をしたら費やせる時間の9割を消費してしまい、これを試す余裕がなかった。最初、実装が思いとは思わなくて両方試せば良いと考えた(やってみるとややこしい要素が多い)。もっと最初に構想を練っておけば良かった。

使わないコードをほとんど書かなかった割に2000行とかになったので、今まで参加したMMの中で一番実装重かったかもしれない。

最初に思いついたことをコンテスト中に消化できなかった。コンテスト開始直後の自分に、実装する前に紙に書いて整理することと、めんどくさがらず考えたことを試すことをアドバイスしたい。

 

TCO18 MM R1 RoadsAndJunctions 参加記録

問題文:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17153&pm=14907

順位表:

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=17153

問題概要

平面上にN個の点が与えられる。一点当たりコストCで最大2N個の点を加えることができる(位置を重複させてはならない)。新たに加えた点は、それぞれ確率Pで消滅する。(最終的に得られる点群の最小全域木のコスト)+C×(追加した点の数)をraw scoreとし、(best/your)^2を最大化する。

やったこと

点をばらまき最小全域木をもとめる。次数が2以下のものを取り除き、木構造を固定した状態で山登りをする。ないほうがよさそうな点を削除し、評価値を求める。

以上までを1遷移として焼きなました。

同じ位置に点を重複させた方がいいこともあるので1つずらすなどして配置した。

評価関数は、

(すべての点を使った時の最小全域木のコスト)+  各点ごとの、(C×(その位置に置く点の数)+(P^(その位置に置く点の数))×(消滅したときの最小全域木のコストの増量))の和  

とした(各点ごとに独立に考えても真の期待値とそんなにずれないという仮定を置いた)。

ローカルでの評価は、モンテカルロ法によってE(1/rawscore^2)を求めた。

感想、反省

ローカルの評価がずっとバグっていて期間のほとんどを無駄にした。それ以外にもいろいろバグが多かった。そもそも順位表があまり信用できないこともあってスコアが落ちても致命的なバグがあることに気づけなかった。最終結果はともかく全期間通じて動きが過去最悪だった。結局最初に書いたものを少し改善したものを最終提出とした。

 

やはりコードはきれいに書くべきだ。

 

 

TCO18 MM Lightning Round Map Recoloring 参加記録

問題文:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17149&pm=14893

順位表:

https://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=17149

終結果3位でした。

問題概要

2次元グリッドがNR個の領域に分けられている。領域には飛び地もあり得る。また、各マスには色が塗られている。同じ領域に属するマスが同じ色で塗られ、隣り合う領域に異なる色が塗られるように色を塗り替えるとき、(使った色の数)×(色を塗り替えたマスの数)を最小化せよ。

考えたこと

色を最初に固定した。validな解を見つけるため同色隣接領域のペアの数を目的関数とする焼きなましを書いた。ほとんどのケースで6色解が見つかったが、7色使った方がいいケースもあった。解が得られたら、ランダムに一部の色の割り当てを変え、再度解を見つけるための焼きなましをした。得られた解は塗り替えマス数で評価し、もし解が悪くなるなら、前に得られた解に戻した。この部分にも焼きなましの遷移式を用いた。

反省

6色か7色かの判断を適当にやりすぎた。ちゃんと探索してやるべきだった。forumの統計によると、1位、2位に比べて6色でやりすぎらしい。

色を変えるたびに隣接する同色の領域の色を消し、色のついてない領域の数で焼きなます様な方法もあった。その方がよさそうに思える。

validな解を探す焼きなましの遷移において、塗り替えコストの情報を使っていないの点が良くなかった。

invalidな状態を許し、同色隣接領域を禁止する条件をペナルティで表現する方法もあった。コンテスト中考えたがとてもうまく気がしなかったので試してもいなかった。