inani_waonの日記

コンテスト覚書

CodinGame Spring Challenge 2022 参加記録

CodinGame Spring Challenge 2022に参加しました。(常設名:Spider Attack)

 

www.codingame.com

いつものゲームAIです。

結果はLegendリーグ156/400位で、全体156/7,705位でした。あと日本人28/445位。

 

ゲーム概要

RTSやMOBA感のある戦略ゲームでした。*1

ルールはツカモさんによる翻訳記事があるのでそちらに丸投げします。*2

簡単に要素を挙げると、

・非グリッド(厳密には巨大グリッド)

・不完全情報(戦場の霧)

・2P×3キャラ(+中立ユニット)同時着手

という探索絶対殺すマンです。

 

最終的にやったこと

ルールベース。プレイヤー番号ごとに位置を考慮するのは大変なので、入力を反転させて常に自分が左上プレイヤーだと思い込むようにする。

80ターンまでマナを稼いで、攻撃2:防御1に分かれる。

マナ稼ぎ

モンスターの出現位置は固定(出てくる角度でちょっとブレるくらい)なので、その位置に居座る。これで基本的には拠点にモンスターを近づけずに稼ぐ。倒しきれずに拠点に向かいそうなモンスターはCONTROLで出現位置に跳ね返す。敵に先に喰われることが少ないので、最高効率かはともかく安定する。

この時拠点に向かうモンスターが視野外で見逃してしまうのが痛いので、拠点に向かうモンスターのspawnerから遠い順>拠点に向かわないモンスターのspawnerから近い順で攻撃しに行くようにした。

防御

拠点に一番近いモンスターを追いかける。追いつく前は追いつくターン*3から最短ルートを計算する。追いついた後は角度と速度を適当な分解能で全探索し、後続モンスターの巻き込みや敵ヒーローからの逃げで貪欲に移動する。

間に合わない場合のWIND、操られたことがある場合のSHIELDなどもルールベースで撃つ。あとは拠点外のモンスターを画面外KBで消したり。

マナ稼ぎ時には他のヒーローが下側からの侵入を防いでくれるのでその前提で守るが、下側のヒーローが攻撃に出るとホイホイ侵入されて不安定になる。やられる前にやろう!

攻撃

複数の攻めに同時対応できない状況を目指した。

・SHIELD付きモンスターでゴールを狙い、駄目でも相手ヒーローを奥に押し込む。*4

・相手ヒーローをCONTROLで引きずり出す。*5

・2人同時WINDで4400飛ばして直接ゴールを狙う。1ターン前に1人WINDで+2200も狙う。

CONTROLとWINDは相性が悪いかも?

 

リーグ別やったこと

Wood2, Wood1

待機位置を設定して、拠点内に敵がいれば倒しに行く。いなければ待機位置に戻る。

Bronze

WINDやSHIELDのシナジーを見越して、攻2守1構成で実装スタート。攻撃担当2人を定位置に立たせてSHIELDとWINDを同時に叩き込むことで、連携攻撃実装の練習とした。防衛はWINDを使うくらいでそのまま…だけど防衛力が足りず、攻1守2にしたところで昇格。

Silver

細かい計算で最適化したり、固定位置待機でなく巡回できるようにしたり。守2は相互作用を考えて担当を割り当てたりするのが大変で(大変なためうんうん唸るだけで実装しなかったので)、やはり防衛が安定せず。ルールを読み込んだところspawnerが4つしか無いことに気づき、spawnerでマナ稼ぎしながら拠点に近づかせない方針に。これでやられる前にやれば守備は雑でもいいので、攻2守1に戻す。

Gold

後続モンスターの巻き込み、モンスターをspawnerに送り返すなど、更に最適化。2人で同時WINDするのを作る。防衛役が自己SHIELDを張るかを相手の戦術に合わせる。Legend昇格の決まり手がSHIELDをやめるってどうなん?(じゃんけんなので。)

Legend

条件チェックを厳密化など。*6マナ効率が良くなったので、攻撃開始ターンを120→80に早期化。

 

雑多考察メモ

AHC008風な同時着手の振る舞い作りの問題だが、こちらは誰かの行動を決めたことによる影響が多岐に渡り、管理しにくい。こういうケースの対処法は、手元のゲームプログラミング本によるとダブルバッファが良いらしい。State全体をダブルバッファにしてもいいが、一部だけダブルバッファにしてもいい。私が偶然していた実装はStateを変化させずに決定済の行動だけ持って判定時に考慮に入れるという方法で、この後者に近かった。多分このゲームだと前者の方が合いそう。

攻1守2と攻2守1の違い。攻2は攻め方が多彩になり、同時に何かすることによるシナジーも生み出せる。守2は、モンスターが弱く1人で対処できるうちは並列として機能するため、片方が操られたり飛ばされたり、隙間から攻められたりというのに強い。モンスターが強くなると、1人では削りきれないモンスターを共同で倒す直列の動作をするようになる。つまり、序盤から終盤にかけてどちらも安定度が増す。どちらが良いかは難しいが、10日の完璧な実装で強いのは攻1守2、10日の雑実装で強いのは攻2守1だろうか。4400砲や6600砲の有効度で決まりそう。

マナアドバンテージ。中途半端な攻撃は自分のマナを減らし、敵のマナを増やすだけ。普段は無駄遣いせず、ここぞという時に飽和攻撃するのがいい。WIND合戦は1:1くらいで双方消耗するが、SHIELDは自分だけ消耗して相手は稼ぐことになりやすい。実際に攻めるのはマナを使うが、マナを使わずに相手陣に居座り、相手に対処を空撃ちさせる(そしていざ本当のチャンスとなれば実際に叩き込む)という方法もある。

事故は起こるさ。視界2200に対してヒーロー2人がそれぞれ最高速度で近づくと1600で、視野外から一気にWIND範囲に入ってしまったり、一度CONTROLされると復帰の手が無かったり、WINDで飛ばした先でもう1回WIND出来たりと、とにかく事故は起こるさの設定。相手の認識外から行動を起こしたり、想定外の行動を起こすのは有効度が高そう。

 

感想

勝ち筋を自分で選べるゲームで、最終戦術を何にして実装リソースを注ぐかを決めるのは難しかったです。また、特定の戦術(≒特定個人)へのメタも存在する環境でした。プログラマ同士の対戦をエージェントが代理でやるみたいな感じだったのと、何かが視界に入ったときには対処困難というのがあり、それよりゲーム木探索したいはちょっとありましたね。*7

これはこれで楽しいんですが、正しい道に進んでいるか分からない、ゴールが見えない系なので半月マラソンラッシュの締めとしては重かったです。処理順が複雑なのもあって、綺麗なコードを書くのも難しかったですし。

順位的にも目標の上位2%に微妙に届かなかったのですが、去年のコンテストよりは伸びていたので爆死の傷は癒せたかなというところです。*8

あと、流石に疲れたので休みたいです。

 

余談

 

このツイートで何かに似ていることに気づいてしまったのですが、このゲームのビジュアライザをよく見ると…。

 

・1Pは青い服

・拠点回りは黄金とまでは言わないが黄色い畑

・つまり「青き衣をまといて金色の野に降り立つ」

・なんか体に悪そうな霧が出てる

・森から出てきて直進し続ける虫

・そんな虫をCONTROLで森へ帰したり相手の拠点に送り付けることができる

・WIND(風)

・去年のパクリ元はジブリ

 

…ナ●シカじゃん。

*1:MOBAやったことないです。

*2:いつもありがとうございます。

*3:二分探索で求める。

*4:Health>16に限定した。

*5:マナ消費がとんでもないのでMana≧100に限定した。

*6:WINDする前にダメージを与えてモンスターを倒してしまうケースなど。

*7:上位は頑張ってしていたようです。

*8:ラソンの傷はマラソンでしか癒せない。

Topcoder MM135 - BridgeBuilder 参加記録

TopcoderのMarathonMatch135に参加しました。

 

www.topcoder.com

 

問題はBridgeBuilder。パズル「橋をかけろ」のほぼコピーでした。

結果は提出44人中、暫定17位でした。(システスはまだ)

 

問題

パズル「橋をかけろ」を解いてね。

頂点は全部使わなくてもいいし、連結成分がいくつかに分かれてもいいよ。

でもスコア的には大きい連結成分が1つある方がいいよ。

1辺の橋の上限数(C)はケースによって2~5だよ。*1

 

考察

パズルの解法は理解。

部分解(それなりの大きさの連結成分)を求めるのがそもそも大変そう。連結成分に含む全ての島が条件を満たしていないといけないので、大きい連結成分を見つけるために「広げる」、連結成分を完成させるために「収束させる」という2つの方針を両立させないといけない。そんなボドゲあったな。

小さめのものを見つけるのも大変だし、小さい連結成分に島を付け加えて大きい連結成分を作れるかというと、そういう保証も無いように見える。そうなると、適当にガチャガチャやって上手くいくか見るしかない…のか?

連結成分同士が干渉せず、スコア計算も完全に分かれているのは日本橋ハーフマッサージチェアっぽい。うーん、解法も同じにしてみるか?

使う島を決めればパズルを解くだけになる。そうして成立する連結成分をいくつか求めたら、得点が最大になるよう組み合わせる。大きい連結成分を作れるように島たくさんでも探索したいが、それが出来なかったときのために小さめでも探索したい。うーん、島2個からランダムに1個ずつ増やして、最大まで行ったらリセットの形にするか。

連結成分の組み合わせは、スコア的にはほぼ貪欲になりそう。とりあえず貪欲で組んだ後は、焼きなましやビームサーチでも出来そうだけど、今まで使ったことの無いchokudaiサーチを使ってみようかな。

 

やったこと

島を全部連結

パズルを解く。

1方向にしか繋げない場合と、任意の方向に橋をかけないと矛盾が生じるパターンに対応。確定で橋を増やせる場所が無いなら頂点を1つ決めて、分岐で各方向に橋を1つかける。*2

seed1~1000のうち、996~997ケース程度は時間内に計算可能。

全て同一の連結成分に出来るもの、複数の連結成分に分かれるもの、解決不能なものがある。*3

そのため、全部の島を使うのが最善ではないケースがある。seed=1が分かりやすい。

上手く行かないケースではサンプルコードの解をそのまま出す。

提出結果は12点。

島2つ成分を列挙

探索出来る回数にもよるけど、小さい連結成分は全列挙して良さそう。

とりあえず島全部の連結に加えて、この成分を使って貪欲に組み合わせる。

提出結果は13点。

島N個成分を列挙

島2つから始めて、接続可能な島をランダムに1個ずつ増やす。

重複する島成分は島有無のZobristHashで排除。組み合わせることを考えると橋の有無単位でHashした方が良かったかも。まぁ、連結成分の大きさでほぼ決まるので誤差だと思うことに。

連結成分が2個以上に分かれるのは許容した。これを弾くとスコアが下がる。あと、連結成分の登録は横着して複数連結成分を1セットで登録した。(この辺の仕様が決まり切らないので作り切れなかった)

橋の数の和が奇数になる場合は成立しないのでシミュレート自体スキップ。

提出結果は47点。

組み合わせをchokudaiサーチに

各種ブログやツイートを参考に組む。

時間軸ごとの優先度付きキュー(元ツイートだとHeapというものだった)が溢れてしまい、capacityの自動拡張か、あまりに悪い状態を追い出す機能(両端キュー)のどちらかが必要そうとなる。

今回はほぼDFSで良い問題と見て、溢れるならキューに入れないという最悪な対処でなんとかする。

提出結果は49点。

前計算&枝刈り

モンテカルロ系でもそうなんだけど、シミュレーションの妥当さというのは大事。妥当でないパターンを延々計算するのは無駄なので、枝刈りするべき。

同時使用できない島を求める。

C=2でBi=7の島を使うと仮定すると、必ず4方向に橋を張らないといけない。そうすると隣接の島も使うので、その島でも同様に必ず張る橋を…と再帰的に求める。この"必ず使う橋"同士が交差する島は同時使用できないと言える。

島を増やすとき、同時使用できない島を考慮する。

提出結果は55点。

何も分からん

明らかに上位と別ゲームをしているので、方針の見直し。

6000msから既存の連結成分を拡張する方針にしてみたり、単純な拡張ではなく焼きなましにしてみたりと色々実験するも改善なし。

やっぱり既存成分の拡張はあまり意味が無いのかなぁくらいの確認に。

それなりの人数が一晩レベルで高得点を取っているので、そんなに難しい手法では無さそうだけれど…。

ランダムに橋を増やす

全く別の解法に着手。

橋を適当に置いて行って、パターンが成立か破綻するまで続ける。(もちろんゲームルールから自明な橋は置く。)

CやEが多いケース(生成ルールに対して多方向に橋を張りやすく破綻しやすい?)、島が少ないケース(従来手法の方がはまる)、あたりは苦手な様子。

これだけで提出すると54点でちょっと下がる。

Cと島の数で戦略を切り替えて59点。

駄目押しの高速化で60点。で終了。

 

他の人の解法を見て

愚直に辺ごとの橋の数を探索するだけで良かったっぽい。

枝刈りが上手く効いたりラッキーで時間内に妥当な解を見つける必要がありそうなんだけど、なんか上手く行くらしい。

実行時間が間に合いそうもない手法に突っ込んで撃沈するのはいつもやりがちで今回は避けたんだけど、よりによって今回は当たり方針だったという。試さなかったのが悪いのはそれはそうなんだけど、なんかすっきりしない。

 

感想

〇初めてchokudaiサーチを試した。

〇過去の知見を活かした。

×過去の知見を活かした。

〇今月あと2本マラソンがある。

×今月あと2本マラソンがある。

*1:元ネタはC=2。

*2:重複盤面排除は最後まで付けてないです。

*3:ケース生成時に同一の連結成分になるよう生成しておらず、交差も考慮していないため。

A.I.VOICE API利用記録

A.I.VOICEのAPIを使って色々試してみたので、その感想です。

 

A.I.VOICE is 何

有料の音声読み上げソフトです。

APIAPIを通して音声を読み上げできる、というものです。

 

感想概要

A.I.Voice Editorを遠隔操作するものという感想でした。これを使って何か公開サービスを作ろうとなるものではないです。サーバー(複数人が利用できる形)で利用することは規約で禁止されていますし…。*1

今回は常時起動ソフトとして任意の情報を垂れ流すものを作ってみましたが、不満点はありつつもとても楽しいという感想でした。

 

サンプルを触った感想(C# + WPF

f:id:inani_waon:20220415052646p:plain

サンプルプログラム

サンプルを動かすと、何が出来る、Editor側の挙動がどうなる、という辺りはかなりイメージが掴めると思います。

基本的にはEditorに文字列を送ってから再生機能を遠隔で呼び出すという流れです。サンプルではこれらを個別のイベントで行っていますが、メソッドを連続で呼ぶことでも普通に動作します。

マスターコントロールの各パラメータも弄れますが、これで調声しながら使うのは難易度が高そうです。使うとしても音量調節くらい?私はAPI専用のプリセットを作って、用途に合うものを呼ぶことにしました。

また、リスト機能は使用しないことにしました。複数の再生を管理したいなら自分のソフト側でやればいいんじゃない?と思ってしまったので。優先度や再生期限などを付けて再生管理機能がリッチになると、A.I.VOICE側のリスト機能に任せるのは心許ない気がします。*2

 

作るもの

常時起動しておいて、時報を鳴らしたり各種サービスから取得した情報を流してくれるもの。適当に雑談とかもしてくれると楽しそう。

という妄想ですが、今回は時報と天気予報、それからTwitter読み上げまでにします。UIも拘らず、サンプルの改変に留めました。

 

内部実装

複数の再生が重なることを考慮して、再生キューを作りました。

再生キューへの追加

各機能(時報機能、Twitter読み上げ機能など)からObserverで。データ内容は、ボイスプリセット名と読み上げ内容があれば最低限動かせます。

再生キューからの再生

EditorがIdle状態のときしか正常に再生出来ないので、1秒ごとに状態をチェックして、再生可能ならキューの内容を処理するようにしました。APIで再生完了を知らせたりというものは無いようです。

 

作ってみた機能

時報

一定時間ごとに時刻をお知らせしてくれるものです。今は15分毎。

これが作れたら技術的には何でも作れるだろう感があります。任意のタイミングでリクエストをキューに積んで再生出来たら、あとは何処からリクエストが発生するかの違いでしかないので。

タイマー

一定時間後にお知らせしてくれるものです。

世間一般のタイマーは手で止めるまで主張し続けるものが多くて煩わしいと感じていたので、聞き逃さない前提ならこういうのの方がいいなとなりました。ポモドーロ・テクニックなどに使うのも良さそうです。

ツイート読み上げ

自分のホームツイートを読み上げてくれるものです。ライブラリとして、NugetパッケージのCoreTweetを使いました。

ホームツイートを読むのが普通な気がしますが*3地震速報アカウントなどを対象に読み上げることで、各種通知サービスの代替としても使えそうです。余計なサービスを通す分、可用性は下がりますが。

ホームツイートはAPIの呼び出し回数上限がネックになりがち(現状1回/分)ですが、リストなら制限が緩いとか色々あるようです。

何を再生するかの選択、絵文字(サロゲートペア)の対処、リプ先やURLなどを省くかなど、調整もした方が快適に使えます。

余談ですが、読み上げ経由で「OK Google」する実験では認識しませんでした。環境によるとは思いますが、うちではツイート経由で遠隔操作されることは無さそうです。

天気予報

天気名(晴れ など)、最低・最高気温を読み上げます。

起動時に何も言わなくて寂しい&接続成功してるか不安になるので、起動時に日付と天気を言うようにしてみました。

天気の取得にはOpen-MeteoのAPIを利用しました。

 

調声

字幕付きの動画を比較対象として、時報などで聞き取りやすく話す場合では相対的に話速はやや遅め、抑揚は大きめ、という暫定調整になりました。逆にツイートなどを垂れ流す場合、抑揚を抑えた方が聞き疲れないです。

また、ツイートのような自由な書式の文章を読み上げると、区切り認識の関係で各種ポーズが大量に入ることがあります。ポーズ長はそれぞれ短めが良さそうです。文末ポーズはマスターコントロールでしか変更できません…。追記→ポーズ長で調整するより、文章を矯正した方が良さそう。

 

出来たもの

起動時に日付と天気を話すところ。

外部からデータを拾ってA.I.Voiceに流すという流れを感じていただけると。

 

気になったこと

色々ありますが、全てにおいて「これそういう用途で使うものじゃないから」というオーラを感じました。

音量が小さすぎる

音源側で音量を最大にして再生機器側で絞る、というオーディオあるある設定をしていると、マスターコントロールで5倍、ボイスプリセットで2倍にしてやっと適正~やや小さいくらいです。リアルタイムな読み上げだと他の音源との兼ね合いがあるので、単独で利用するときより調整しにくいです。

マスターコントロールへの設定が多い

上記の音量や文末ポーズなど、マスターコントロールを変更せざるを得ないことが多いです。API利用のためにマスターコントロールを弄って、別の用途で使うときには戻して…というのはかなり不便そうです。せめてボイスプリセットで完結してくれると他の用途と両立しやすいのですが。

もしくはEditor側の設定に干渉しないよう別物として動かすか。

同時再生ができない

単独起動のEditorを通して操作する都合でこうなります。そもそも同時再生したいか?というのはありますが。*4

あと、API不定期に操作する間はEditorを占拠されるので、別の用途での利用もしにくいです。

特殊文字に弱い?

何らかの絵文字に反応してか、A.I.Voice Editor側がビジー状態のままになってしまうことがありました。その文章を読んでくれないだけなら良いのですが、Editorを再起動するまで一切読み上げてくれなくなります。

読み上げ失敗するツイートの例:

朝型のジェシー on Twitter: "今、業務で使いたい(しかも全然違う2箇所で!!!)からっていう理由で、Rubyのトポロジカルソートのページを見ていて、業務中に競プロできている!?!?と幸せを感じてる🥺✨"

「!?!?」まで文単位で読んだ後に固まるので、やっぱり絵文字が原因かなーと思いました。サロゲートペアを弾くようにしてからは異常は起きていないです。

→ver1.3.1.0で修正されました。

 

総括

常時起動サービスを作ってみましたが、そもそもそういう用途を想定したAPIではないなという感想です。*5

ただ、自分で実装した通りにボイロキャラが喋ってくれるのは楽しいです。技術的な話に限っても、Alexaに枠に捕らわれないさいきょうスキルを追加しているような感覚?それを勝手知ったる開発環境で出来るのはメリットが大きいと思いました。*6

欠点としては、類似ソフトのVOICEVOXと比べるとAPI操作に制限の多さを感じます。*7A.I.VOICEはプリセットとテキストを決めて再生するだけ、Editor側で立ち絵も付けてくれると非常にお手軽ではあるんですが、Editorに縛られている感覚は強いです。

それでもA.I.VOICEを使うとしたら、キャラクター目当てか、VOICEVOX等のAPIを使いづらい場合ですかね…。私はせっかく買ったので使い倒してみようと思いますが、いずれEditorに縛られない形で使えるようになるといいなぁと思いました。

OK Kotonoha、コリドールで対戦して。みたいな未来も遠くはない?*8

*1:ローカルで自分だけが利用可能なサービスになら使っても大丈夫そうです。

*2:今回はキュー的に使うので合わないという話で、用途とマッチしていれば普通に使うと思います。

*3:そもそも読み上げるのは普通か?

*4:したい気持ちはあるけど、実際に試して聞き取れるかはまた別の問題。

*5:じゃあ何を想定しているのかと言われると…動画編集ソフトとの連動?

*6:C#使いなので。

*7:VOICEVOXはAPI仕様を少し見ただけで触れてはいません。

*8:コドゲで作り溜めたゲームAIは役に立つ。

モノグサ プログラミングコンテスト2022(AHC009) - Robust Memory of Commuting Routes 参加記録

モノグサ プログラミングコンテスト2022(AHC009)に参加しました。

atcoder.jp

問題はRobust Memory of Commuting Routes。

割合で移動する人をゴールまで移動する問題です。

提出799人中704位でした。

 

問題

割合で移動する人をゴールまで移動させてね。*1

P(0.1~0.5)の割合で移動せずにその場に留まるよ。

 

考察

余分に壁にぶつかれば移動し損ねた人が追い付いてくる。

スライド移動すれば良さそう。

 

やったこと

ビームサーチとスライド経路探索の間で反復横跳びしていました。

 

ビームサーチは初動は良さそうだけど途中から反復横跳びしてしまう。

あとは纏まらずに薄くなってしまうので、薄さにペナルティを付けたりと評価関数に調整が必要そう。

 

スライド移動はビームサーチで時間を削ってしまったので、これ時間内に仕上がらないなぁ…という感じ。

 

結局提出できるか怪しい状態なので、正の点である最短ルートの移動をちょっとだけ伸ばしたものを出して終了。*2

その後手直ししたらビームサーチは最低限動いたけど、本当に最低限なので調整はたくさんしないと駄目そう。

 

他の人の解法を見て

焼き鈍しが強そう?

ビームにしろ、スライド移動で割合を纏めることを主眼に置いて探索単位を変えるなりした方が伸びそう。

スライド移動は遠回りになることも多いので、1マス単位で探索するビームだとかなり深くする必要がありそうで、つまり多様性を上手く保つ調整と高速化が必要そう。もしくは少量を高速にゴールさせる方針か。

 

感想

確率というか割合を使う問題でありながら運要素も無く、楽しそうな問題でした。拡張ダイクストラ慣れしていない+何かにはまって大ロスしたのもあって、4時間では全然足りなかった。8時間~長期でやりたかった…。

あとは下手にレートが上がってしまったうえに非減少レーティングなので、レートが上がる見込みが無いと全然気持ちが入らないっぽい。短期は水パフォ出れば御の字だろうし、長期も1ページ目は苦しいような問題も多いだろうから、向き合い方を見直さないといけないかも。

 

*1:1人のうち0.5人が移動したりする。

*2:飛び賞位置が近かったので、それ以上位置を変えたくなかったというのもある。

MC Digital プログラミングコンテスト2022(AHC008) - Territory 参加記録

MC Digital プログラミングコンテスト2022(AHC008)に参加しました。

atcoder.jp

問題はTerritory。領域を切り分ける問題です。

暫定テストは826人中9位、システムテストでは7位でした。

問題

f:id:inani_waon:20220226214245p:plain

グリッド上に動物がたくさんいてうるさいので、300ターンで人を動かしたり壁を置かせたりして人間の領域と動物の領域を切り分けてね。

人間が5~10人いてそれぞれ動き、動物の移動もターン毎に返ってくる、マルチエージェント的*1インタラクティブな問題だよ。

人間が広い場所にいると嬉しいけど、4近傍連結セル内に動物がいると特大ペナルティがあるよ。

考察

 まず、人間が広い場所にいるとスコアが増えるので、人間の領域は出来るだけ広くしたい。人間は複数人いるので、一番広い領域に全員で入るのが最も効率的。つまり、動物を出来るだけ小さい領域に入れる問題になる。

 動き回る動物を1手で囲うのは難しいので、残り1マスを閉めるだけの部屋を用意しておいて、入り口にその1マスを閉める担当を配備すると良い。*2

 今回もSeed=0のビジュアライズ結果を共有していいルールだったが、そこでも壁含めて3x14の巨大部屋を20個作って必要な場所だけ閉じるものがあった。ただ問題になるのは犬で、犬は人間の間を移動する動きになるので、出入口が1つの部屋に入っていくことは基本無い。*3ではどうするかというと、出入口が2つある通路のような部屋にする。これなら部屋の中を通ってくれるし、むしろ入口の2人の間を通るために積極的に部屋に入ろうとする。

 入口2つの部屋を準備して閉じる、という全体方針になるが、部屋を動的に配置するというのは難しい。テンプレートを準備して、その通りに配置させることにする。ではどういうテンプレートがいいか。部屋の大きさ、部屋の数という観点から考える。まず、部屋の大きさは小さいほど理論スコア*4が高くなる。部屋の数は、理論上は(複数同時入れを考えなければ)動物と同じだけあればいいことになる。ただし、部屋が小さくて少ないほど、動物が部屋の中にいる確率が低くなる。また、猫は部屋が小さいほど部屋に入りにくい。動物が部屋にいないことには部屋を閉じられないので、小さい部屋を過剰に用意し、必要な分だけ閉じるという方針が安定しそう。

 テンプレート完成後は、人を良さそうな入口に配置して実際に閉じるという問題になる。部屋にスコアを与えて、人を配置する部屋のスコアの総和を最大化するという方針か。色々調べたところ、どうやら最大カバー問題(最大被覆問題)の亜種ということになるようだ。最大カバー問題では1人を配置すると部分集合がカバーされるが、この問題では2人を配置しないといけない。他にも3人で2段をカバー出来たりするので、ここの計算が難しそう。最悪、3-3-4人で3チームにして、各チーム単位で目標を決めれば計算しきれるだろう。

 動的に探索しながら動くタイプも一応考察してはみたけど、動物から間2マス以上離れないと間に壁を置けないという仕様上、人間が団子になると犬に粘着されてまともに動けなくなりそうなので、高度な制御が必要になりそう。

 

やったこと

初動

 開始から数日遅れで参加登録。まずはじっくり考察。重実装なのは見えているので、実装ロスが出ないよう問題の性質を考える。

 下のようなテンプレートを用意してみた。中央を空けることで、上下の分断が起きないようにしている。この通路が悪さをする予感が無いでもないが、まあ実験的にやってみるのはありかな。通路が無い場合は、部屋は行ごとにどれか1つ空けるようにしないといけない。

f:id:inani_waon:20220226212916p:plain

初期レイアウト

 テンプレートの設置は、1人目は左端から順に縦向きに設置、2人目は右から、みたいな感じで固定順にした。初期位置に応じたマッチングは後で入れるけど、ロスは今は許容する。

 テンプレート完成後は、仕事が無くなった順に人数と縦位置が固定のチームを組んで、最適な列に移動する。評価は、目的とする部屋ごとに{(0.5^動物との距離) * (0.8^チームが到達するまでのターン)}の総和とした。3チームに対して9列なので、適切に前処理してやれば9^3パターンで全探索が普通に間に合う。*5

 土日+αで完成させて、提出スコアは50.6%。*6提出720人くらいのうち14~16位くらいだったかな。

レイアウト変更

 やはりというか、極太通路部分に動物が溜まる。牛がこの辺りで反復横跳びしているとどうしようもない。通路部分が多いというだけでなく、太いということも関係していそうだ。幅1なら2方向にしか動けないが、幅2なら3方向、幅3以上なら4方向に動けることも出てくる。方向が多ければ、それだけ期待した方向に動く確率は低い。ということで、レイアウトを変更した。

f:id:inani_waon:20220226222138p:plain

 段にある10列を全て使うと上下が分断されてしまうので、9列使ったら残りの1列は使わないようにしている。

 これで提出スコアは56.4%。この時点では牛が一番の強敵。

夢の全員野球

 ある程度配置を固定して10^3パターンにしているけど、明らかに仕事をしていない人がいる。1人ずつ目的地を設定できたら強いんじゃないか?と思い、挑戦してみる。

 無理でした。作りこめば可能性はあるんだけど、目的地が変わりすぎるせいで部屋の入り口前に留まれないので、全員が実質仕事していない状態になる。これを調整しきるのは至難と思い、この方針は一旦保留。*7

細かい改善

・動物ごとに重みを付ける(牛>豚>兎=猫>>犬)

・レイアウトの事前配置の担当列決めをマッチング(一次元なのでソートするだけ)

提出スコアは55.7%。手元ケースでは上がってるのでOK。

レイアウト追加

 1位は60%強で、捕獲完遂精度を高めても到達できそうにない。もっと小さい部屋をたくさん用意する方針に変えるか、1部屋に動物をたくさん詰め込まないといけない。(そもそもテンプレートを使う方針が合っているかというのはあるが、ここは自分を信じる)

 動物をたくさん捕まえる方針は、ある程度大きく動く動物は犬猫(兎)くらいで、うちコントロールできるのは犬だけなので限界がありそう。また、使用済の部屋が多いせいで手近に入れる部屋が無くなる問題もあり、そういう意味でも部屋が多い方が良い。テンプレートを2つ増やしてみる。

f:id:inani_waon:20220226215411p:plain

 この2つのテンプレートは多少無理があって、部屋が6段のレイアウトでは、部屋の中として封鎖ができる対象位置の、チェスでいう白黒が部屋ごとに1:3となっている。ただ部屋が3マスずつずれているので、全体としてみればそこまで変わらない。7段に至っては1:1で、犬すら捕獲が難しい。ここから、豚猫犬の2マス移動動物が対処しづらくなる。また、通路の割合が増えるため、猫が特に強敵。

 ただ多少捕獲失敗ケースが増えても、一定の捕獲完遂率があれば全体のスコアは上がる。ターンを余らせても何も嬉しいことは無いので、ここからはより上位のテンプレートが使えるように捕獲完遂率を上げていくことになる。

 提出スコアは57.4%。

細かい改善

・チームの仕事が無くなったら、他のY位置まで出張する

・なるべくチーム内の横座標を合わせる(一部のメンバーが壁置きで停止したら、他も停止する)

提出スコアは57.7%。

夢のドッグラン

 犬だけを捕獲するための細長い通路を端に別途作る。

 3~4匹も捕まえれば黒字の計算だが、ドッグランまでの移動に最大30ターン近くかかり、通路に引っかかった犬を待ち、犬が中に入り切るのを待ち、と時間のロスがかなり大きい。

 どうやら、元々時間に余裕のあるケースでないと厳しいようだ。ドッグランを中央に置くとか、最初に他の壁を置くより前にやればいくらか良さそうな気もしたけど、そこまで差は出ないかな。

 また、犬は元々他の動物と一緒に捕獲しやすい性質なのもあり、何処まで効果が出るかは疑問が残った。

細かい改善

・猫の目的地を予想する。猫が入らない部屋にはスコアを加えない。

 また、動物の重みを(猫>牛>豚>兎>>犬)に変更する。

・チーム内でしか部屋を閉じれなかったのを、全員で閉じれるようにした。

 また、複数同時捕獲の部屋や、上下端の部屋を優先するようにした。

提出スコアは58.3%。

使用レイアウト調整

 動きが良くなっている分、難しいレイアウトを使いやすくなった。NとMにより振り分ける基準を再設定。

提出スコアは58.2%。下振れっぽい。

ダメージコントロール

 動物が1匹残るだけでそのケースのスコアが半減する。これが怖いばかりに部屋が大きいレイアウトを使って得点の上限が伸びなくなっているので、1匹残して被害50%のところを、広めの部屋に入れて10%などに抑えたい。それが出来ればもっと攻めに行くことができそう。

 部屋単位で数部屋x数部屋のブロックを作ってみて、それを閉じるための移動が出来るか最小カットで確認して、みたいな感じで実装してみるも、あんまりチャンスが無い。そもそも動物の方が最大速度が速いので、慎重になりすぎているのだろうか。

 そもそも動物を残すのは全体の4%程度しかないので、多少攻めたレイアウトに挑むにしても、その1~2割でしか効果が無いというのはあまりに小さい…。結果的にレイアウトを攻めるまでの効果は得られず、動物残しがさらに少し減ったくらい。

 提出スコアは57.9%で、下振れ…だといいなぁ。ここでコンテスト終了。

 

他の人の解法を見て

暫定1位~2位の方は、事前配置して部屋を閉じて、最後の1匹に特殊対応を入れたりと、細かい手法は違うけど大枠は一緒かな。*8

通路幅が3でもいいのが意外でした。あと部屋が1x4(私のは2x2)だったけど、部屋を閉じることが出来る2マスを必ず通らないと部屋の向こう側に行けない構造なので、確かに向こうの方が良さそう。2x2は1/2を引いてくれないと部屋を閉じられないので…。

1x4通路も試作パターンの中にあったけど、途中(10列レイアウトにした辺り)で捨てちゃったんですよね。掘り返してみる価値はあったかな。

 

ビジュアライズ結果公開について

今回の問題は、上位陣からするとビジュアライズ結果公開との相性は悪かったんじゃないかなぁ…と思いました。理由は以下の通りです。

・犬猫のいない結果を見て方針を真似すると実はハズレという、初心者に対する罠になる。

・犬猫あり想定の結果が共有されると真似するの考察皆無実装ゲーになる。

・Seed=0以外を想定していそうな言及も、無いとは言えなかった。

 (そもそもseed=0とそれ以外で方針が違う人は少なそう)

・閃き+重実装ゲーなので、残り1日などで良い方法が共有されると、実装速度や時間の都合で勝敗が決まる。

ただ今回は参加者層の多くが想定しないであろう振る舞い重視のコンテストなので、ビジュアライザ共有が無いとそれはそれで苦しいのかな…とも。

 

感想

段階によってネックになる動物が変わって、その対応を考えていく問題解決の連続が面白かったです。最後まで実装イヤイヤ期が来なかった。

スコア計算はペナルティが多すぎて、ケース1000件回しでは済まない限界チューニングゲーになっていたところはありそうです。時間を長くして残り時間ボーナスにするとか、20匹に対して1匹残りなら5%ダウンとか、ペナルティが軽くなれば助かるかなと思いました。

 

 

※ビジュアライザの画像にはDOTOWN様の画像が使用されています。

*1:管制できるタイプはマルチエージェントではないという考えですが、厳密なところどうなんでしょう?

*2:動物愛護的な観点から、部屋には空調や設備類が完備されているものとします。

*3:人間の誰かを犠牲にすれば可能だが、それは全体方針に反するので出来ない。

*4:ここでは部屋1つにつき1匹の動物を入れた時のスコアとする。

*5:1秒で余裕ですが、適切に処理しなかったので2.5秒かかりました。

*6:この記事では、1ケースあたり10^8点に対しての10^6点を1%とします。

*7:その後、彼の姿を見た者はいない…。

*8:つまり事前配置パターンと手法の違いで負けたということでもあり…。

Topcoder MM132 - BouncingBalls 参加記録

 TopcoderのMarathonMatch132に参加しました。

www.topcoder.com

問題はBouncingBalls。セル・オートマトンみがある最長路的な問題でした。

結果は提出43人中、暫定14位、システスも14位でした。

 

問題

グリッド外から直進するボールをB個入れるよ。

"\"や"/"のパネルを置いて直角に反射させて、ボールが1個でもグリッド外に出るまでの反射回数を多くしてね。ついでにボールを入れる位置も自分で決めてね。

ただし配置が固定のセルもあるよ。

あと自分が置いたパネルは、ボールを反射させると90度回転するよ。(最重要)

 

考察

なんも分からん。

/\

/\

こういう道の間を通すと、

\/

\/

こうなる。以後ループ。

ん-、セル・オートマトン

でも常に間を通せるわけではないし、回転しないパネルがあったり、複数のボールが同時に動き回るので、良型を探すのはかなり苦しそうに見える。ただ、2x2単位で考えるという発想はあり?

2x2は一旦置いといて、始点だけ決めてしまえば、シミュレートしながら未確定セルに着いたら中央側へ打ち返すという挙動ができる。

(ここから下はDFS実装後に気付いたこと)

角を考えたとき、例えば始点が左上の隅に無い場合に左上に"\"があると、必ず右や下から入り、画面外に弾き出されてしまう。よって固定で"/"となるが、これも一度反射してしまうと"\"に変化する。角のパネルは一度しか使えないということ。*1内側から順に"内側に跳ね返す力"を消費していく一方で、外側のセルは自身の力で内側に跳ね返しながら、内側の跳ね返す力を回復させていく。*22進数の繰り上がりみたいな感じ?ただこれは菱形に働く力なので、グリッドが矩形と考えるとどこまで有効な考えかは分からない。

ボールを外周から中央に運ぶとき、その経路は後から編集できないウィークポイントになる。実際DFSでも浅い詰みを回避するのを除けば、探索できているのは8層程度か?なので、ボールは中央に運ぶがパネルの状態は臨機応変に後から変えられるという仕組みに出来ると強そう。もしくはルールベースで良い入り方や序盤の指針を埋め込んだり。

 

実装

とりあえずDFS。

始点をランダムや全走査で決めて、シミュレートしながら未確定セルに着いたらパネルを置いたり置かなかったりする。『内側に弾く>外側に弾く>置かない』の優先順とした。*3

これで始点を400パターンで10msずつ回して、上位20件を更に時間いっぱい回した。*4始点の多さ、探索の深さがそれぞれ得点に響くケースがあり、更に10msで上位でないものが後半で伸びるケースもあるため、これをパラメータ調整しようとすると地獄の気配がした。*5

ここで期間的には半分くらいだが、他に出来る事と言えば上手く回る探索順やルール、パラメータなどを探すくらいしか思いつかない。そこで2x2で管理する方法を試してみることにした。

(結果的には上手く行かず、これが最終方針となった)

 

没実装

結果的には振るわなかったが、調整次第ではまだ可能性があったこと、使い方次第では応用が利くことから解法を晒してみる。

まず、2x2の領域に分断する。奇数の場合、間に1x2、2x1、1x1の領域を作る。

イメージとしてはこんな感じ。

f:id:inani_waon:20220120101338p:plain

①→②→⑤→④→⑦→⑧→⑤→⑥と移動しているものとする。

また、固定パネルが無い前提で説明する。*6

 

まずは①の左上から下方向に侵入し、右下から右方向に出る。

パターンとしては、

\\

?\

□?

\□

がありえる。("□"は空白、"?"は不定。)ただこの時点では決定せず、両方の可能性を残す。

このまま、破綻しないよう各ブロックの入口と出口の情報だけを残していく。

 

⑤には2回進入しているが、

□□

□/

は1回目は成立するが、2回目は成立しない。*7

//

//

ここで⑤の内容は上記パターンに確定する。

 

こんな感じで、"良い場所に移動させる"と"可能性を保つ"を両立させて探索すれば、普通のDFSなら詰んでいるところを更に粘れるので、同じくらい探索できるならば普通のDFSよりも良い結果が出そう。

 しかし問題はあって、例えば②の場所を通過するときに

??

 □\

 と

/\

/ □

では通過にかかる時間が違う。これで何が困るかというと、複数のボールが同時に動いているので時系列シミュレーションが出来なくなる。そもそも複数のボールが同じブロックに同時に侵入したら?という問題もあり、ほぼB=1専用となる。

あとはシミュレーションに時間がかかるなどの問題もあり、残念ながら1x1DFSより優秀なレベルまで漕ぎつけることはできなかった。

高速化をサボって最低限組み上げた状態でseed=126(N=6, B=1)で1x1DFSの95%程度のスコアにはなったので、調整次第では1x1DFSより良い結果が出そうな気がする。*8

とはいえ今回の問題ではやはり苦しい感じがある。序盤の悪手をリカバリーする手段としてこういう方法もあるよ、くらいの与太話として残しておく。

 

他の人の解法を見て

ビームサーチやchokudai サーチをしている人が強かった。

DFSだと悪手を打ったまま瀕死で生き繋いでしまうので、そもそも悪手を察知して良い状態を保てる複数手読みの方が優れているということだろうか。

焼き鈍しでも自分より上のスコアは出るっぽい。

パターン埋め込みが強いのは、まぁ、はい。*9セル・オートマトン感の強いパターンだけど、探索は力業っぽい。

 

感想

何か面白いことが出来そうだけど出来ずにぐぬぬ…となる問題でした。

上位は赤コーダーが固まる一方で中位程度なら色々な解法が通用するようで、問題としてはとても良い問題だったのではと思います。

最近は思考が閉塞しているせいで当たり方針が引けないので、すっきりしたいなぁ。

*1:複数同時ヒットの場合は回転しないルールがあるが、ここでは考えない。

*2:乱数にシャッフルするという方が近そう。

*3:"置かない"を上手く枝刈りしたいんだけど、刈ると弱くなる。

*4:厳密に言うと更に細かいことをしている。

*5:高速化するだけで均衡が崩れて弱くなる。

*6:固定パネルがある場合も、パターン数が減ってシミュレーション結果が変わるだけ。

*7:右下が回転して"\"になっているので。

*8:調整しようにも、組み終わったら残り1時間強だったので。

*9:自力で探し当てる必要があるだけMM130の数倍良い。

Topcoder MM131 - StopTheElves 参加記録

TopcoderのMarathonMatch131に参加しました。

www.topcoder.com

問題はStopTheElves。防衛ゲーム的な問題でした。

結果は提出51人中、暫定テスト15位、システス12位でした。

 

問題

地面にプレゼントが散らばってるよ。

外周からエルフがプレゼントを奪いに来るから、自腹で障害物の箱を置いて被害を減らしてね。

 

考察

ルールを翻訳したらエルフの産卵率とか出てきてびっくりする。*1

TDっぽさと、一発OKが出なくて改修されたルール感をひしひしと感じる。*2

サンプルは最長路っぽいことをしている。でもプレゼントを完全に囲えば箱しか奪われなくなるので、その方がいいのでは?プレゼントは100円に対して、箱は1~10円だし。

エルフが複数いるときの動き方が明文化されていないので、解析や実験してみないとよく分からない。往路エルフと復路エルフの経路をバッティングさせてデッドロックとか出来ないのか? → 出来なさそう。

となると、エルフが何かを持ち帰ること自体を食い止めるには、閉じ込めるか、目標位置を切り替えて右往左往させるしかない。ただ、これが本質かというとかなり怪しく感じる。それらをしないならエルフは何かを奪って帰るので、一時的な時間稼ぎにはあまり意味が無い。意味があるのは完全に囲うまでの時間稼ぎと、終了間際くらいか。あくまでプレゼントの代わりに箱を持ち帰らせることがメインになりそう。

これ、ポップ地点が箱で塞がってたらどうなるんだろう?湧き潰しで完全にエルフが出なくなったりする? → 外周には箱を置けない。あ、はい。問題文に書いてくれ。

elfP * Cが[箱1つ設置する時間]に対する[エルフが湧く数]なので、これが1.0以下ならエルフに箱だけを持ち帰らせることが可能。そういうケースは全体の3/4で、残り1/4は箱の供給より奪われるペースの方が速い。ただ安全寄りのケースでも壁を構築しきるまでプレゼントを奪われるのと、危険寄りのケースでも一部を食い止めながらNNターン耐えることは可能。*3

うーん、最小の囲いを作ることが前提で、それまでの被害を抑えたり、終了間際だけ頑張るゲーム…?すごくつまらなさそう。最長路的なものを頑張って作っても、結局それは最小の囲い+幅1通路だし、明らかにそれより先に囲いを作り切った方が良さそうなんだよね…。一応、elfP * Cが大きなケースでは囲い作りを放棄して外周のいくらかを割合カットする手法が取れそう。ただ箱の節約にはなるけど大事なのはプレゼントで、ランダム湧きに対して想定通り稼働するか怪しい。

ところで最小の囲いを作ると言っても、それは容易ではなさそう。途中いくつかは奪われるということは、守るべきものと捨てるべきものも決めないといけないだろうし。真ん中のものほど復路が長くなることを考えると、真ん中を残すのが良さそう。囲う方法としては、大きな矩形で全部囲うというのは思いつく。あとは角を取って八角形に出来ると嬉しそう。木を利用して動的に生成するのはきついかな…。矩形だとしてN=10で箱16個、N=30で96個が最大。あとは個別に囲う場合はP * 4個になるか。

 

実装

57点解法

とりあえず、大きく囲うか個別に囲うかしてみる。

そのまま置くだけだと余計な箱や隙間があるので、貪欲に縮小してみる。

→1マスずつ縮小しては密閉を維持できてるかの判定が間に合わない。スコアも落ちる。

余計な壁を消すだけに留める。

75点解法

早々に置き始めても、壁が完成するまでに中身が奪われてしまう。また、頑張っても結局間に合わずに全てのプレゼントが奪われてしまうことも多い。

今置き始めたらどうなるかを計算して諦めるかを判断したり、完成の目途が立ってから置き始めるようにする。*4

76点解法

複数の隣接したエルフに壁をこじ開けられたり、閉じ込めているプレゼント持ちのエルフを開放されてしまうケースが目につく。完全に壁を作って、エルフの隣に箱を置くことで安定させる。また、終盤以外も時間稼ぎに意味はないので隣に箱を出して即お帰りいただく。

80点解法

一度壁を置き始めたら場所は再考しないようにしていたが、既に無いプレゼントを守るための不要な壁を置いてしまう。プレゼントが持ち上げられた2ターン後に再考を走らせる。*5

まだ矩形と個別囲いしか出来ていないので、八角形の囲いを実装する。8方向の隅からの距離をセル毎に事前計算しておいて、プレゼントのMin - 1の位置を基準にする。全ての方向に対して基準を満たすセルを抽出すると八角形が取れる。このままだと中も塗りつぶされているので、最低1方向に対して基準をギリギリで見たしているセルに限定することで外周が取れた。*6

絶対スコアが凄く伸びたので、調子に乗って十六角形版も作る。こっちはそんなに伸びなかった。斜め部分を多くすることが重要だった?

79点解法

下がってませんか…?

1マスだけ塞げば外周7マスからの侵入を防げる、みたいな場所が存在する。*7

ここを塞ぐだけでは割合で防ぐ以外の意味が無いのだけど、メイン壁を作る前にここを塞ぐことで、壁を作る時間を稼ぐことが出来る。1マス置いて外周を1マスでも塞げるなら何も考えずに採用するという最悪な方法で手元スコアが伸びたので、何も考えず提出。

本当は外周の木2つの間をDPして最低接続コストを求めたりしたかったけど、ここで時間切れ。

他の人の解法を見て

プレゼント毎に、守るか守らないかを丁寧に決めるのが強そう?

プレゼントを持ったエルフを囲えば、時間稼ぎしつつ内側にも防壁を作れるので自然と良い形になる、みたいなのがありそう。密度の低いマップだと微妙かもだけど。

異端解法(後日談)

elfP * Cが大きなケースで、囲い作りを放棄して外周のいくらかを割合カットする手法。場所は自分が目視で決めて埋め込みました。

f:id:inani_waon:20211223213723p:plain

感想

方針がシンプルで実装が面倒、期待値計算で詰めるタイプの問題でした。

頑張って防衛を続けても、プレゼントを全て奪われると何もしない場合の1/100以下の点数になることもあるという苦行で、かつ相性で良くなったり悪くなったりも多いので、分かりやすく改善を楽しめるタイプの問題ではなかった気がします。

HTTFの疲れもあり出るか迷ったのですが、ある程度コードを書いてしまったので書いた以上は出すことにしました。

当初のコンセプトを曲げたような問題は怪しくなりがちですね…。

こういう問題だとせめて実装面で新しい知見が欲しくなるもので、その点では八角形の作成や、考察だけでしたが2つの木の接続といったものがあったので良かったです。

*1:spawn。

*2:E,eとB,bの表記ルールが逆な辺りとか。おそらく、最初は箱を動かされない設定だった?

*3:不可能なこともある。

*4:完成までN * 2ターンで動き始めることにした。

*5:直後だと、プレゼントを持ったエルフに対して閉じ込めが発生しない。

*6:自分の頭で考えて初めてやってみた方法だけど、意外に簡単だった。

*7:外周寄りに存在することが多く、無計画な縮小を裏目にする嫌なヤツだった。