びったんびったん

ユーザビリティ・プログラミングについて。

TCO17MMR2 AbstractWars

問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16928&pm=14599

ヒューリスティクス的なアイデアが色々考えられて今までで一番好きな問題。

本当はもっとたくさん書いたんだけど長くなったのでがんばったところだけ。
以下抜粋。

敵同士をつぶしあわせる、ビームサーチの評価関数、最小費用流のコスト

自分が攻撃される確率が低いほどよい

初期配置を↓とする。

f:id:hakomof:20170525230804p:plain

テキトーに近い敵baseを奪うと↓のようになり、これは敵自入り混じった乱戦になりpowerが不利な自分が負ける。

f:id:hakomof:20170525230818p:plain

しかし↓のように敵baseを奪うと敵は距離の近いbaseを攻撃する確率が高いため自分をあまり攻撃せず敵同士でつぶしあってくれる。その間にsizeを着々と貯めれば100の倍数ボーナスで差がつくので勝てる。

f:id:hakomof:20170525230836p:plain

このような自分が攻撃される確率が低い（相対的に敵同士でつぶしあいやすい）配置になるように敵を攻撃する。

敵の初撃に耐えるほどよい

序盤、敵baseを奪いすぎるとsizeが小さいため簡単に再奪取されることが多い。これを軽減するために奪えなかった敵base近くの自baseのsizeを大きくしたい。

f:id:hakomof:20170525230847p:plain

localityを1.1とすると敵baseが各baseを攻撃する確率は計算できてattackTも決めれば初撃ターン・初撃サイズも求まり、自baseが奪われる確率も計算できる。そこでattackTの値域から均等に3つ583,750,917を選びその平均を初撃に耐える確率としそれが高いほどよいとした。

これで奪いすぎるのを軽減したり、敵baseの近くに壁をつくる効果が期待できる。

ビームサーチの評価関数

ビームサーチの評価関数 = 奪ったbaseの数 - 自分が攻撃される確率の和 - 敵の初撃で奪われる確率の和

狙ったわけではないが、自分が攻撃される確率が長期的な評価値で、敵の初撃で奪われる確率が短期的な評価値で、バランスがよさそう。

攻撃されやすい敵baseを攻撃するのは後回し

↓のような状況のとき上真ん中を奪うと左右からぼこされて再奪取されやすい。

f:id:hakomof:20170525230857p:plain

しかし↓のように上右から奪うと真ん中の攻撃は左右に分散しやすく、左の攻撃は真ん中にいきやすい。そのため奪った後も守りやすい。

f:id:hakomof:20170525230902p:plain

このように攻撃されやすい敵baseは奪った後も攻撃にさらされやすいので後回しにする。また攻撃されて弱った後なら楽に奪えるという効果もある。

最小費用流のコスト

最小費用流のコスト = 到着時刻 + 50 * -log(その敵baseが自分を攻撃する確率) + 40 * -log(max(1e-9, 1 - その敵baseが他の敵に攻撃される確率の和))

空を飛んでいるtroopはbaseと接触してはじめて効果がでる（敵baseを奪うにしろ、自baseに合流して100の倍数ボーナスを増やすにしろ、敵baseを削って100の倍数ボーナスを減らすにしろ）ので滞空時間、到着時刻は短いほうがよい。ので到着時刻にペナルティを加算した。

Example scores

0) 1700.3533398049744
1) 1806.7049780062375
2) 1978.8025098890039
3) 1962.538169965643
4) 1983.4413356595355
5) 1663.3656903521724
6) 1829.6786713895922
7) 1486.8174209242056
8) 1690.0970680903945
9) 1810.6962420903901

GIF