simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

競技プログラミング獲得賞金額(2022年度)

一覧

コンテスト名 順位 金額 備考
Hitachi Hokudai Lab. & Hokkaido University Contest 2021 B問題 2位 100,000円
MC Digital プログラミングコンテスト2022 4位 30,000円 賞金対象外者が 1名いたので繰り上げ
第8回 Asprova プログラミングコンテスト 9位 10,000円
第9回 Asprova プログラミングコンテスト 2位 80,000円
TCO22 Regional Events Marathon 東アジア地区 3位 50$ コンテストというよりイベント的なやつ

合計 220,000円 + 50$

MM143 TreeMaker 参加記

問題

www.topcoder.com

戦略

  • 完成図の作成を行う
    • 色の配置を決める
    • タイルの配置を決める
      • 初期解の作成
      • 枝の追加・削除による木の変形
  • 完成図に対してもとのタイルとのどのタイルが対応するのかを割り当てる
  • 盤面を操作してタイルを揃える
    • y軸を揃える
    • x軸を揃える

完成図の作成

ただ闇雲に盤面をスライドさせても最小全域木の完成は難しいので、先に完成図を作成するところから始めました。

色の配置を決める

色の配置については各色について領域の4隅 [0, 0], [N - 1, 0], [N - 1, N - 1], [0, N - 1] を起点としてそこから dy, dx の最大値が小さい順にセルを彩色していきました。(なるべく正方形になるような配色になります)

もう 1つのパターンとしてシンプルに順番通りに彩色していくパターンも用意います。

タイルの配置を決める

初期解法の作成

まずは最初にベースとなる最小全域木の作成を行います。幸いテスターに木の作成方法は書かれていたので今回はそれを利用しました。

最初に対象の色の領域に空のタイルを設置します。

その後、ランダムにタイルとランダムな方向を選択して、その方向にまだタイルが設置されていない場合は枝を伸ばします。

この処理を未完了の領域が無くなるまで繰り返します。

木が完成したら他の色に対しても同様の処理を行っていきます。

枝の追加・削除による変形

木の性質として「辺を 1本追加すると必ず閉路が出来る」というものがあります。そしてまたその閉路の中の 1本を辺を消すことで再度木になるので、この特徴を利用して木の変形処理を行っていきます。

辺を追加して閉路の検出を行う(計算量は N * N)

見つけた閉路の中から辺を 1つ削除する。

この処理を行うことで木を維持しつつ使用するタイルの種類を変更することが可能となります。今回はこの処理を繰り返しつつ元の盤面のタイルの種類の数との差分が小さくなるように変更を行いました。

タイルの割当を行う

完成した盤面に対して元の盤面のタイルをどの位置に割り当てるのかを決定します。AHC011 の時は最小費用流を用いて割当を行いましたが、今回は速度重視で貪欲に割当を行いました。割当の評価としてはこの後に「y軸を揃える」-> 「x軸を揃える」という作業を行うので y軸が等しいものが多くなるように評価を行うようにしています。

盤面を操作してタイルを揃える

盤面を揃えるパートについては「y軸を揃える」 -> 「x軸を揃える」の順番で行っていきます。

y軸を揃える

現在持っている余剰パネルを正しい y軸の方向に入れます。余剰パネルが完成版で使用しないパネルの場合はまだ完成していない y軸で適当な箇所に入れます。

x軸を揃える

x軸を揃えて行きますがその際に「余剰タイルを含めた行の連結成分が 1になるように盤面の操作」を行っていきます。

例として下記の画像を使用します。

まず、本来そのタイルがいるべき x座標に対して有向辺を張ります。現状では連結成分数は 3となります。

この数が 1になるように行を横にスライドさせたりタイルの形が一緒の場合は値のスワップ等を行います。

あとは元の場所にタイルを押し出すことで x軸を揃えることが出来るようになります。

ソート後

このように x軸をそろえつつ行を1つ上に押し上げることが出来ます。この作業を N 回繰り返すことで盤面を完成させます。

まとめ

AHC011 と似たような問題ではあり実際に完成図を作るところは完全に AHC011 の方針と一緒だったが、盤面を完成させるパートが完全に別物でそこをどうやって手数を短くするのかを考えるのは楽しかった。横軸を揃える -> 縦軸を揃える方法だと多くの手数を使ってしまうのでそこをなんとか改善したかったが最後まで何も出来なかった。(上位勢と近い考察はしていたがうまく動か無さそうだなと案を捨ててしまったのが良くなかった)

MM142 HelpTheElves 参加記

問題

www.topcoder.com

戦略

主に以下の 2つになります。

  • 各エルフについてルールベースによる行動の選択
  • どの AI が使用されているかの検出 & メタ戦略

今回の問題では各AIの弱点を上手く攻める必要があったので、序盤の箱の配置でどの AI が使用されているかを検知し各AIに対して特化した戦略を使用しました。個人的な攻略難易度としては「AI3 > AI2 > AI1 > AI4 > AI5」の順となっています。

AI のタイプ推定

自分は C++ を使っていたので Java で書かれた AI のコードを C++ で書き直して、各 AI がどの位置に箱を置くのかをシミュレーションしてその一致率が高いものを採用しました。正直 AI のタイプについては入力で渡しても良かったと思います。(特に AI2 と AI3 の判別が難しかったので)

AI5 対策

今回のAIの中で一番攻略が容易となっています。AI5 の特徴としては以下の 2つになります。

  • ターン毎に指定された座標に箱を置く
  • プレゼントを守る行動は一切行わない

そのため「プレゼントに向かって移動、プレゼントを回収したら戻る」というコードを書くだけでもプレゼントの回収率 100% を達成することがほぼ可能です。(無理なパターンとしては プレゼントの数 > エルフの数 の時ぐらいです)

あとは全ての AI 攻略に共通する対策ですが、プレゼントの回収は画面外から遠いもの(中央付近)を優先するようにしています。これは終盤に出現したエルフが何も回収出来ずにゲームが終了してしまう可能性をなるべく排除するのと、後半になればなるほど中央の守りが堅くなり到達が困難になるため序盤のうちに回収したいからです。

余計なお金を使わせる

AI5 はプレゼントが全て回収されたあとも箱を設置してくれるので、最後の 1個のプレゼントに関しては回収したあとに画面外から出ず待機させ、他のエルフに箱を回収させるようにしています。そうすることでマネーを消費させてスコアアップを狙うことが出来ます。

この「あえてゲームを終了させずに箱を設置させることでマネーを消費する」という戦略も全ての AI 共通の戦略となっています。

AI4 対策

特徴としては「プレゼントが危なくなったらブロックを行う」プレゼント防衛型の AI となっています。そのため、単純に接近するだけでは箱でブロックされてプレゼントの回収が行なえません。そのためいくつか工夫が必要になります。

AI4 の弱点として以下の 3つがあります。

  • プレゼントの周辺マス以外については特に警戒されない
  • 箱かプレゼントを保持しているエルフは警戒されない
  • プレゼントを回収しているエルフに対するブロックは行われない

そのため自分の戦略としては「箱 or プレゼントを持っているエルフを利用して警戒されずにプレゼントに近づく」というものを採用しました。

具体的には下記の画像のような プレゼントの周辺 4マスのいずれかを箱 or プレゼント持ちのエルフに待機させる 状態を維持するようにします。

この状態を維持することで安定してプレゼントの回収を行うことが出来ます。

具体的には プレゼントに近づいても箱でブロックされる ということが無くなります。

近づくと箱でブロックされる。

箱でブロックするのをプレゼント持ちのエルフで回避して、位置を入れ替えることでプレゼントの回収を行う。

AI1 対策

特徴としては「プレゼントの集合を効率よく囲んでブロックする」エリア防衛型の AI となっています。各プレゼント毎にブロックを行うのではなくエリアに対してブロックを行うので箱を効率よく利用できマネーの消費を抑えることが出来ます。

MM131 においては一番優秀だった AI1 ですが 1つ弱点が存在しております。

  • プレゼントを囲む経路上に箱が置けない場合は箱を置かない。

また、この経路を作成する際には木以外のマスについては同じコストで計算されているので画像のような箱で囲まれている状態と

経路の一部にエルフが入り込んでいる状態は経路のコストとしては同じになります。(エルフがいる位置に箱を置きたいが、エルフがいるので箱を置くことが出来ない。また、コストが一緒なので箱持ちエルフを回避した経路を作ることもない)

攻略としては以下の段階を踏みます

  • 囲まれている部分の箱を回収する
  • 箱を回収したエルフは「ゲート役」として他のエルフが囲いの中に入る手助けを行う

ゲート役について

ゲート役のエルフは他のエルフがエリア内に入る手助けを行います。具体的には近くにエルフが来たらマスを開けて通り過ぎたら元の位置に戻るという行動を行います。

この行動は相手の AI が箱を置きたい場所を常にエルフがいる状態にして箱を置くのを防ぎつつエリア内の出入りを自由に出来るというメリットがあります。

AI2, 3 対策

この 2つの AI が今回の攻略で一番難しかったタイプになります。

AI2, 3 は基本的な方針は一緒で「箱が置ける場所に置いてみて、一番プレゼントが回収しにくくなる場所に箱を置く」というものです、評価値の算出方法の点が異なります。

少ししか改善されない場合でもマネーがある限りどんどん箱を設置していくので、MM131 的にはあまり良くない解法でも今回の問題に関してはかなり攻略が難しい AI となりました。(箱の物量作戦で押し切られるのが一番つらい)

基本的な攻略は AI1 の時と一緒でゲート役のエルフを上手く使いながらエリア内に侵入しプレゼントを回収していきます。

閉じ込められるのを回避する

箱を回収する際に場所によっては閉じ込められて再度箱の回収が必要になってしまうので、それをなるべく避けるために相手の箱の設置場所を先読みしてなるべく閉じ込められないように行動するようにしています。

次のターンで再度閉じ込められてしまう。

相手の行動を先読みで閉じ込められないように行動。

これで大体 1% の改善です(AI は 5つあるので 0.2% の改善)

正直この 2つのタイプについては特に特化した戦略を思いつかなかったのであまりスコアは良くありませんでした。(複数のエルフを使って攻略する案はあるのですが、実装が複雑になりそうなので止めました)

まとめ

いつもの問題だとジャッジ内部の AI のコードを読んでそれに対応するコードを実装するみたいな感じだと思うので、AI のタイプが複数あってそれぞれに対応する必要があったのは斬新だなと思いました。 ただ高いスコアを得るためにはジャッジコード + AIのコードを読む必要があり、AI のコードが Java で書かれていたため C++ で再実装する必要があったのでいつもよりコード量が多くなってしまったのは少し面倒だなと感じました。(AI のタイプを推定するためにも移植は必要)

ルールベースのコードを書くと毎回最後の方で条件が複雑になってしまって、最後の方はデバッグに時間が取られてしまったのは戦い方としてはあまり良くなかったなと思った。まだ実装したい案はいくつかあったけどバグの埋め込みの可能性のほうが高いので結局手が出せなかったのは残念。

TCO22 Final 参加記

問題

今年のお題はパズルゲームでした。(インタラクティブ問題)

入力として N * N のサイズのグリッドと 3 * 3 の固定サイズの手持ちパネルの情報が与えられ、1ターン毎以下の操作を行うことが出来ます。

  • 手持ちのパネルを 1枚選択しフィールド上のフルーツと重ならないように配置する(パネルの回転は出来ない)
  • 手持ちのパネルを 1枚選択し破棄する

また、行動後はパネルが新たに 1枚手持ちに追加されます。(追加されるパネルの内容はランダム)

配置後にフィールドをチェックして横か縦にフルーツが 1列並ぶと消えます。ラインを消した場合はスコアが与えられ、その得点は各ライン毎に 消したラインの数 * 消したラインに含まれるフルーツの最頻出値 ** 2 で計算されます。

例えば以下の画像ではスコアはこのように計算されます。

消したラインの数 : 1

ラインのフルーツの最頻出値 : 4

1 * 4 * 4 = 16点

また、次の画像では以下のようになります。

消したラインの数 : 2

縦のラインのフルーツの最頻出値 : 6

2 * 6 * 6 = 72点

横のラインのフルーツの最頻出値 : 6

2 * 6 * 6 = 72点

合計 144 点。

以下は実際に動作している様子です。

この操作を 1000ターン繰り返しなるべく多くのスコアを獲得することが目的となります。

可変なパラメータとしては以下の通りになります。

  • フルーツの種類 : C (1 - 5)
  • 手持ちのパネルの枚数 : T (1 - 5)
  • グリッドサイズ : N (6 - 20)

方針

ビームサーチによる探索を行いました。ただ、探索の深さは手持ちのパネル枚数の T の値を上限にしていたので T が 1のケースでは実質貪欲法になっています。

操作としては以下の 2つです。

  • 任意のパネルを 1枚選択し、任意の場所に配置する
  • 任意のパネルを 1枚選択し、破棄する

多くのスコアを獲得するには「多くのラインを同時に消す + なるべく同種類のフルーツでラインを作る」ことが必要でしたので、評価関数として以下の要素を主に評価しました。

  • ライン毎の フルーツの最頻出値
  • ライン毎の フルーツの最頻出値 / ラインに配置されているフルーツの数 (ラインの何割を同じフルーツで占めているのかをチェック)
  • 連続した空白地帯の数 (独立した空白地帯が多いとパネルが置きにくくなるため)
  • 単発消しに対するペナルティ

ライン毎のフルーツの最頻出値

最頻出値は 2乗でスコアに影響しているのでなるべくこの値を大きくなるように評価を行いました。

ラインごとのフルーツの割合

同じ最頻出値でも N の値が 15 だとして 5 / 105 / 6 では後者のほうが同じフルーツが配置されている割合が高く、より得点が伸びる可能性があるので、割合を計算して評価に加えました。

連続した空白地帯の数

今回の問題では、なるべくパネルを破棄するような自体を起こしたくないため パネルを配置しやすい状態 というのを維持したいです。そのため連続した空白地帯の数を調べてその数が少ない状態の盤面を評価するようにしました。

空白地帯が連続しており、色々なパネルが置きやすい状態。

空白地帯がまばらでパネルが起きにくい状態になっているため良くない。

盤面全体を評価するこの処理はちょっと重かったので T = 1 のケースでしか利用していません。

代わりに、他のケースではライン毎の連続した空白地帯の数を評価しました。

下の画像のほうが他のパネルが置きやすいため良い状態と評価しています。

単発消しに対するペナルティ

なるべく同時消しを行ったほうがスコアが高くなるため単発消しに対してペナルティを与えました。ただ、盤面が埋まってくると単発消しを行って盤面整理を行う必要があるので空白率を調べてその割合が 10% を切ったらペナルティを与えないようにしています。

まとめ

シンプルに 24h でどこまで評価関数の精度を上げることが出来るのかの勝負でしたが上位勢のスコアに追いつくことが出来なかった。provisional のスコアの解析を見た感じ C = 1 のケースでは勝っていて、C の値が大きくなるにつれてスコア差をつけられていたので同一のフルーツを集めて消す処理があまり上手くいってなかったのかなと思われる。去年よりは戦えたがまだまだ実力が足りないと感じた。今年は寝ようと思っていたが、なんだかんだ順位が気になって結局ずっと起きていた。(それでも途中イスの上で 1-2h 寝た)

総括

今年の TCO はオンサイト(ボストン)で開催予定だったが、オンサイト参加者が少ないのでオンライン開催となりました。パスポートの取得とESTAの申請は終わっていたけど無駄になってしまった。それはそれとして、去年の初参加から絶対に改善しようと思っていたのが以下の 2つ

  • 作業マシンの変更
  • 与えられた EC2 環境を利用する

作業マシンの変更

去年は外付けの web カメラが無かったので、メインとは別のノートPC のほうで作業を行っていたのだが「全画面共有」にかなりマシンパワーを取られてローカルでテストを回すのが遅くなってしまったので、今年は外付けの web カメラを購入してメインのほうのマシンで作業できるようにした。

EC2 環境を利用する

去年は競技が終わったあとに EC2 環境に関するメールが届いていたことに気づき「これを利用できなかったのはかなりもったいない」と思ったので今年は利用することにした。今年は c5.9xlarge を与えられていたので手元のマシンよりかなりスペックが高くて便利だった。

スペックが高いとローカルでテストを回すスピードが格段に速くなる。元々テスト自体はマルチプロセスで並列処理出来るようにしているので並列数を 3 -> 30 にパラメータ変更するだけでテストのスピードが 10倍になった。

あとは事前に安いインスタンを使って EC2 上での環境構築の手順を確認して本番のときに手間取らないようにした。

試合の流れ

「問題を読む」-> 「ビームサーチ系の問題だな」→「それっぽい評価関数を書く」 (ここまでで大体 6h ぐらい)

「暫定 2位! ただ、全員提出していないので(仮)だな」

評価関数をどんどん変更する(ビジュアライザを見て色々調査しながら 6h ぐらい)

「暫定 1位!キター」

この後 6h ぐらい何も思いつかず順位が 8位ぐらいまで落ちる。

「タイルを破棄する評価が割と高かったので、ギリギリまでタイルを破棄しないように評価値を調整したらスコアがかなり上がった」

けどまだ上位には全然届かない。そのまま試合終了。

システムテストで最終的に 2人に抜かれて 5位で今年の TCO は終了しました。 provisional テストの解析結果から 4位には確実に落ちることはわかっていたけど、5位まで落ちてしまった。

感想

去年 8位で今年 5位だったので当初の目標「去年より高い順位を取る」は達成出来てよかった。来年もし参加出来たら 4位以上を狙いたい。2度海外オンサイトの機会があってコロナで全部フイになってしまっているのは少しもったいない感じがする (HTTF もそうだけど)。(飛行機代とか調べたら 30万とかしたので海外行けるだけでもお得感ある)

MM141 TrafficController 参加記

問題

www.topcoder.com

方針

  • 毎ターンごとに5ターン先までの信号機の方向を焼きなましで求める

焼きなましで信号機の方向を決める

  • 遷移としては任意のターン、任意の信号機をランダムに 1箇所選択して変える
  • 実際にシミュレーションを行い評価を行う
    • 前進 +1pt
    • 停止 -1pt
    • スポーン地点での停止 -2pt
    • グリッドロックが発生しうる箇所での停止 -5pt

グリッドロックの回避

グリッドロックは下の画像のように渋滞が連続すると全く前進できなくなる状態のことを指す。

これを回避するために閉路を検出して、閉路の角に対して停止した場合のペナルティを大きくした。(赤色の部分で停止するとペナルティが大)

ただこれだけだと不十分なので他にもっと良い回避方法があったかもしれない。(1方向を完全に止めるとかもやってみたけど回避率が上がっても全体のスコアが下がってしまったのでバランスが難しい)

感想

最後までグリッドロックを効率的に回避する方法がわからなかった。車両にそれぞれポイントが付与されていたが結局どれだけ車両を捌けるかが大事なのであまりスコアに影響なかったように思える(終盤で緊急車両を優先するみたいなことはあるとは思うけど)

最近はわからない問題が多くて何もわからない。

第9回 Asprova プログラミングコンテスト 参加記

問題

atcoder.jp

方針

各設備の稼働パターンを以下の流れで調整しました。

  • 二分探索で基本となる稼働パターンを決める
  • 調整案をいくつか作成しその中からランダムで選択した案を採用する
  • 終盤に稼働が必要なさそうな設備の稼働を止める

二分探索による稼働パターンの探索

稼働パターンを下限値 4 上限値 9で二分探索を行います。この探索で必要な試行回数は最低 2回、最高でも 3回となります。

変更する時はすべての週に対して操作を行います。

下限値を 4 にしているのは、今回は山登り的にスケジュールを改善しているので序盤からキツめに調整してしまうと後の調整の自由度がなくなってしまうのである程度余裕をもたせるようにしているためです。

調整案の作成

基本となる稼働パターンを決めた後は調整案を作成していきます。調整案はいくつかのパターンがありそれに基づいて作成されます。

調整案1

今回の問題では各注文に「納期」が存在するため、合計の稼働時間が同じでも「日程の前半に多く稼働させる」 or 「日程の後半に多く稼働させる」では前者の変更のほうが依頼の達成率が高くなります。

稼働時間が単調減少するパターン

稼働時間が単調増加するパターン

そのため、調整案 1 では稼働スケジュールの 1週目のパターンを「基本パターン」として「2 ~ X - 1」の中からランダムな値を選択し「選択した値 ~ X週」までの稼働パターンを基本パターンからいくつか下げた値に変更します。(この下げ幅もランダムに選択されます)

この変更は「平日のみ適用」「休日のみ適用」「両方に適用」の 3つからランダムに選択され実行されます。

調整案2

調整案 1 が採用され続けると 2週目以降の稼働パターンが完全に下がりきった状態になるので、それを解消するために 1週目の稼働パターンを下げます。

スケジュール変更の流れ

各設備では「二分探索による基本稼働パターンの探索」→「細かい調整」を行っていきます。まず変更を行う設備をランダムに選択し、基本稼働パターンの探索が完了していない場合はその続きを、完了している場合は調整案を作成します。この処理を何回か行いその中で一番コストが削減されるものを採用し、その後は変更後のスケジュールを計画プログラムに渡して評価を受け取ります。

変更が成功したか失敗したかによってその後の処理が変わります。

成功時

成功したスケジュールを採用し、変更を行った設備の「最低設備コスト」の値を 0 にリセットします。ここでの「最低設備コスト」とは「その設備における最低限必要なコスト」を指し、この値を下回る変更を行わないようにします。(このコストを下回ると必ず依頼に失敗するというしきい値

失敗時

変更を行った設備のスケジュールを元に戻し、「最低設備コスト」の値を更新します。

最低設備のコストの計算は (a * updated_cost + b * cur_cost) / (a + b) で行っており、a: 4, b: 1 を基本として失敗した注文の数が多い場合は a: 2, b: 1 に設定して計算を行いました。(例 - 現在のコストが 100、更新後のコストが 0の場合 (4 * 0 + 1 * 100) / 5 = 20 となる

序盤はまとめてスケジュールを変更する

序盤はほとんどのクエリが成功するので複数まとめてスケジュールの変更を行いました。まとめる件数は最初 M件からはじめて成功失敗に関わらず半分にしていきます。(例: M が 8 の場合は 1ターン目: 8件まとめて変更、 2ターン目: 4件まとめて変更, 3ターン目: 2件まとめて変更 といった感じです)

終盤のスケジュール作成

終盤では今まで送ったスケジュールの中で一番スコアが良かったものをベースに稼働が必要なさそうな部分を「稼働させない」パターンに変更する作業を行いました。稼働が必要かどうかについてはクエリを送ったときの返り値の 負荷率 を調べてその値が 0 の部分を「稼働させない」に変更します。

休日のみ稼働を停止させる

負荷率が 0 でない場合でも「休日」は停止できる可能性が残っています。というのも 1週間の構成は「day1 ~ day5 が平日で day6, day7 が休日」となっているので、画像のように day1 ~ day5 の間だけ稼働していて day6, day7 は何もしていないという可能性があるからです。

「負荷率 Y を下回った場合は休日の稼働を停止させる」という処理を行いますが、この Y の値については二分探索で求めました。今回は ok: 0, ng: 80 を初期値として設定しています。(例: 1回目は 40% が基準となる。2回目の値は失敗した場合は 20%、成功した場合は 60%) もし、最後のターンまで 1回も成功しなかった場合は Y = 0 にして処理を行います。

この処理は E = 50 のケースでは終盤の 2ターン、それ以外では終盤の 4ターンで行っています。

感想

問題文が複雑そうだから理解するのに時間かかるかなと思ったけど、やってみたら思ったよりやることが少なかった印象。テストケース生成のコードと調整プログラムのコードを調べようかと思ったけど 1週間コンテストだし気合が足りなかったので結局ふわふわした感じの理解で問題を解いていた。時間があれば TPE とか調べて参考にしていたかもしれない。

雑感

ジャッジプログラムの日本語が文字化けしていたので英語のコメントを読んでいた。

クエリの結果から得られる情報がほぼないのでクエリを工夫して注文の内訳を調べるとかそういう感じの問題ではなかった。(ブラックボックスなものをいい感じにパラメータ調整する問題なのでそれはそう)

工程自体は複数に分けられていたけど注文が特定の設備に依存している感じだったので工程がM個あるのとあまり変わらない感じがした。(工程 a を行う設備 b が今使えないから代わりに工程 a を行う設備 c を使おうみたいな処理があると思っていた - ちゃんと把握しているわけではないので違う可能性もある)

最終日付近でジャッジプログラムに最適化オプションつけるのを忘れていたことに気づいて直したら 4倍ぐらい速くなって感動した。C++ 使っていたから気づけたけどそうでない人はハマってそう。

インタラクティブ問題ではクエリの結果に「今このぐらい時間を使用していますよ」というのを含めたほうが良いと思っている。

後いろいろ細かい調整は入っているけどスコアにクリティカルに影響あったのは書いたつもり。

Marathon Match 137 StoneSeries 参加記

問題

www.topcoder.com

方針

2種類のビームサーチによる探索

  • 通常のビームサーチ
  • 最長パスを見つけるためのビームサーチ

ビーム幅がある程度確保出来る場合は通常のビームサーチをそうでない場合は最長パスを見つけるためのビームサーチを使用しました。

最長パスの探索

今回の問題ではなるべく大きな値の石を置くことで獲得出来るスコアが増えるので、大きな値の石を置くために最長パスを探索しました。

パスの伸ばし方

パスを伸ばすのは 1の石を使うことで可能となります。

任意の石の周辺の空きマスに対して +1 した石を置きます。

このままでは「2以上の石を設置する場合は周辺に 2個以上の石が必要」という条件に反するので、さらに周辺のマスを探索して 1が置けるマスを探して設置します。

条件に反していない場合はそのまま +1 した石を置き続けることが出来ます。

このように 1の石の周辺は +1 した石が置きやすくパスを伸ばすのに非常に役に立つので、この動作を続けることで長いパスを作成することが可能になります。

ビームサーチによるパスの探索

パスの伸ばし方はわかりましたが適当に探索してもいい感じのパスを見つけてはくれないので 2つほど大きな指標を与えてなるべく大きなパスを見つけてくれるようにしました。

  • 石を置く際にはなるべく斜め置きを避けるようにする
  • なるべく外側からマスを埋めるようにする

探索については以下の通りです

  • 画面端の任意の位置を選択してそこから開始
  • 周辺 8マスの空きマスを探索し「現在の値 + 1」の石を置く
    • 周辺に 1の石がない場合は 1の石を置ける場所を探して置く

斜め置きを避ける

石の影響範囲の関係上、斜めに移動するよりは縦 or 横に移動するほうが 1の石をより効率的に利用出来るので斜め移動に対してペナルティを与えています。

斜め移動と横移動を比べると横移動のほうが効率よく 1の石を利用できている。

外側のマスを埋めるようにする

長いパスを作ってもらうためになるべく端を詰めながら移動して欲しかったので、グリッドの中央からどれだけ離れているのかを各セルに対してスコア化してその合計値を評価しました。

こうすることでなるべく端のマスを通りながら移動する経路を評価することが出来たと思います。

この探索で見つける経路は以下のようなイメージになります

パスの反転

この探索で見つけたパスは基本的に「外側 -> 内側」へと向かうのですが、この状態だと値の大きな石が中央付近に来ることになります。値の大きい石の周辺は周辺の合計値が大きくなってしまうので利用が難しく空きマスを多く無駄にしてしまう可能性があります。そのため、なるべくブロックの多いマスに追いやって影響を弱くしたいです。

幸い、見つけたパスは始点と終点をちょっと変更すれば逆向きに出来ます。逆向きにすることで「内側 -> 外側」に向かう経路となり大きい値の石を画面端に追いやることが可能となり影響力を弱めることが出来ます。

逆向きにした経路

最初から「内側 -> 外側」に向かう経路を探索すればよいのではと思うのですが、自分の評価関数だと「内側 -> 外側」の経路を作ろうとするとうまく画面端にピッタリくっつくような経路が出来なかったのでこのような反転処理を入れています。

残った空きマスを探索して石を置く

経路を作り終わった後は残りのマスをビームサーチで探索して得点が大きくなるように石を置きます。

時間制限まで処理を繰り返す

ここまでの処理が 1セットで、後は制限時間の間「経路の初期位置」「斜め移動のペナルティの値」「画面端ボーナスの値」をランダムに変えながら繰り返して一番高いスコアが得られたものを採用します。

通常のビームサーチ

「グリッドのサイズが小さい」 or 「ブロックの比率が高くて最長経路の探索が困難」な場合は普通のビームサーチで探索を行いました。

こちらに関しては特筆することも無く。評価としては主に以下の通り

  • 盤面の石の値の合計値
  • 画面端に値の大きい石が存在しているかどうか

後は zobrist hash による重複排除を行っています。

感想

問題自体はシンプルだったが、シンプルが故に評価が難しかったです。小さいサイズでのビームサーチの結果を見るに最長経路を作るよりかはいかにして空きマスを少なくするのかが重要っぽい感じではあるのだが、いい感じの評価関数を見つけれられずに終わった。最長経路を作らずにビームサーチをしたほうが得点は高くなるのでなるべくビームサーチに置き換えたかったがどうしてもグリッドサイズが大きくなるとビーム幅が十分に確保できなくなってしまうので諦めた。

そのビームサーチも評価関数があまり良くなさそうなので改善する余地はいくらでもありそう。「評価関数を良くする」->「ビーム幅が少なくても高スコアが取れる」->「ビームサーチ出来るグリッドのサイズが増える」->「得点がUP」という感じになるはずなので後半は評価関数の改善に主に力を入れてたけどダメだった。

Seed 1: 263.0
Seed 2: 289489.0
Seed 3: 154934.0
Seed 4: 174324.0
Seed 5: 154501.0
Seed 6: 10181.0
Seed 7: 1289.0
Seed 8: 5684.0
Seed 9: 11545.0
Seed 10: 97828.0