Marathon Match 132 BouncingBalls

問題

www.topcoder.com

方針

• 銃の位置を焼きなましで決める
• 銃の位置決定後はビームサーチで良い盤面を探す
• ボールが真ん中に集まるように盤面を作成する

銃の位置を焼きなましで決める (START ~ 1 sec)

まず最初に銃の位置を固定するために焼きなましを行って良さそうな銃の配置を決めます。

遷移としては以下の 1つだけです。

• ランダムに銃の位置を変化させる

銃の位置が決まったあとは、シミュレーションを行い貪欲にパネルを配置していってスコアを求めます。

貪欲に配置

パネル配置については以下のルールのもと行われます。

新しい空白マスに到達した際に

• ボールが上方向に進んでいる場合
  • ボールが盤面の左側に存在する場合は / のパネルを設置
  • ボールが盤面の右側に存在する場合は \ のパネルを設置
  • それ以外はランダムにパネルを配置

• ボールが右方向に進んでいる場合
  • ボールが盤面の上側に存在する場合は \ のパネルを配置
  • ボールが盤面の下側に存在する場合は / のパネルを配置
  • それ以外はランダムにパネルを配置

下方向と左方向については上方向と右方向を逆にしたものになります。

貪欲にパネルを置いていってスコアが高くなる配置を採用します。

ビームサーチで良い盤面を探す (1 sec ~ TIME_LIMIT)

銃の位置を固定したらビームサーチで盤面を探索していきます。

進め方としては以下の方法で行っていきます

• 盤面のシミュレーションを行う
• いずれかのボールがまだパネルを配置していないマスに止まるとシミュレーションを止める
• パネルを配置
• シミュレーションを再開

パネルの配置

パネルの候補として /, \, . のいずれか 1つを選択します。 配置候補が複数ある場合はすべての組み合わせを試しますが、空白パネルを 2つ以上を含む候補は除きます。

例) 配置候補が 2箇所ある場合のパネル候補一覧

• /, /
• /, \
• /, .
• \, /
• \, \
• \, .
• ., /
• ., \

盤面の評価

1つでもボールが盤面から出てしまうとゲームが終了するので、盤面から出ないように中央にボールが集まっている状態を良しとします。 また、各パネルの配置についてボーナス点を与えていきます。いくつか例をあげます

• 盤面中央に向きを変える配置

• 盤面中央へと進む配置

また特定の配置にはペナルティを与えています

• 盤面外に向きを変える配置

• 盤面外へと進む配置

他にもボールの位置についてもペナルティやボーナスを与えています

赤い部分はペナルティ、緑の部分はボーナスになっています。

他にも色々ありますが、基本的には「盤面中央に向かう変更ならボーナス、盤面外へと進む変更ならペナルティ」といった感じです。

感想

評価関数をうまく作れた人が勝てそうだと思ったので、ビジュアライザをずっと眺めてましたが最後までこれとこれといったアイデアは出てきませんでした。事前に計算した盤面を埋め込む方針も考えましたが、固定パネルとボーナスパネルがかなりノイズになっててそれが出来ない仕組みになっていた気がします。

Seed 1: 198
Seed 2: 42985
Seed 3: 28195
Seed 4: 2748
Seed 5: 285
Seed 6: 1866
Seed 7: 4445
Seed 8: 28274
Seed 9: 46363
Seed 10: 35872