inani_waonの日記

コンテスト覚書

Topcoder MM126 Slider 参加記録

TopcoderのMarathonMatch 126に参加しました。

問題はSlider。ブロックをスライド移動して穴に落とすパズルです。

 

www.topcoder.com

結果は登録157人、提出67人中(システスはまだ。provisional15位)でした。

 

問題

ブロックと穴がある。

ブロックは4方向に移動でき、移動数は[1]か[落ちるかぶつかるまで]。

ブロックを穴に落とすと[残ターン * ブロックの価値]の点を得られる。

 

考察

得点が高いものを早く落とすほど良さそう。しかしそのために無駄な手を打つとスコア倍率が減衰してしまい、その後得点が稼げなくなってしまう。そこのバランスが難しいということか。言い換えを使うと、「手数を最小に保つために高得点ブロックを後回しにした場合」「高得点ブロックを優先的に落とすために手数を増やした場合」はそれぞれ次のように表現できそう。

・8点のブロックを落とすのが100ターン遅れると800点の損失

・合計500点のブロックを落とすのが1ターンずつ遅れると500点の損失

seed=2などはブロックの合計点がとても高く、高得点ブロックを優先するよりも全体の手数ロスを避ける方が重要と言えそう。

 

評価関数をある程度リアルに作るなら、ブロック毎に何手で落とせるかを計算してブロック数[点][手数]みたいな配列に纏めた後に、評価が高いものから順に取る前提で何点になるか決める感じ？評価関数内でBFSするの、間に合わない気がする…。 

ルールベースかなぁ。

 

実装

まず最初に、プロトタイプの貪欲法を作った。各ブロックを4方向にMoveもしくはSlideして、全ブロックを最も近い穴との距離関係で以下のように評価。

-[ブロックの点数] * ([穴とのX差 ^ 0.5] +[穴とのY差 ^ 0.5])

seed=2で7.7秒かかり、動きもロスが多くて微妙な感じ。

これは使えそうにない。ルールベースへの移行を決意。

提出してないけど、Score84くらい？

 

次に、1手で落とせるブロックを高いものから落としていくようにした。高得点ブロックが奥に埋もれていることもあるので、直線上のブロックは纏めて落とす平均値も計算できるようにした。ルールベースというか、これは貪欲法では？　出来ることが無くなったらプロトタイプ貪欲をした。

この時点でScoreは95.7。

 

その次に、1回曲がった2手落としも出来るようにした。この時点では1手落としが終わった後に2手落としを行い、混在はできない。

この時点でScore97.1。

 

2手落としが終わった後のことを考えるが、1ブロック毎に何手も使うような手を探索するのはスコア的にも実装的にも美味しくない気がする。穴の向こう1段を全部壁に出来たら全部2手で落とせるけど、壁を構築するのは流石に実装難易度高いなー。あれ、壁は1枚あればスライドさせて使えるのでは？

で、ルールベースでシーケンス動作するようにしてこうなった。（動画は最終提出版）

 水平分割しかできないし、何処に何点があるとか全然考えてないしで、トップを狙えるような効率は出せないのだが、とりあえず全ブロックを2手+αで落とせるようにはなった。

これでScore97.3。

実装の重さの割に伸びないのは、これをやるのは既に終盤だからスコア上の重みはほとんど無いってことですかね…。

 

その後は微調整的なものが多かった。1手落としと2手落としを混在可能にしたり、シーケンス動作の効率化をしたり。2手落としの前倒しは、考察にもある損失で[前倒したことにより回避した損失]と[前倒したことにより発生した損失]を比較すれば実行すべきかが分かる。

Scoreに大きく効いたのは以下2つで、

・1手落としと2手落としを混在

・2手落としで0点ブロックは2手使って落とさずに1手で投げ捨てる

それぞれ0.5くらい効き、最終的にScore98.5でフィニッシュ。

やっぱり序盤～中盤の動きの改善の方が効くらしい。

 

やれなかったこと

・2手落としでストッパーになるブロックの扱い

高得点でも残すべきか、残すならいつまで残すのか

・2手落としで邪魔になる0点ブロックの扱い

落とす必要は無いので邪魔にならないような場所に寄せても良かったんだけど、その判定をお気持ちで行っていた

・2手落としが出来ない位置を落とすためにストッパーを作る

これを判断しなくても万能で動くのがシーケンス動作なんだけど、より効率を上げるために1～2手落としと混在させるのはきつかった。

・何らかの探索

実行時間が余りまくったので。多少ランダム要素を入れて10回回すとかでもやれば良かったかな。

 

皆の方針を見て

 この問題、ぼくのかんがえたさいきょうの方針が結構外れがちでしたね。

 

 ビームサーチ多様性の御株、完全に奪われました…。

 

よくばりセット、 お腹いっぱいになりそう。

 

こういうの出来たら強そうだけど、実装が地獄になりそう。

全体の操作が無効になる入れ替え処理もすべきか？とか考えると…。

 

TopCoderフォーラム:方針投稿スレッド

 

全体的には2手落としの(合計点/手数)による計算が鉄板で、

＋αの精度を高める何かをそれぞれやっていた感じでしょうか。

 

感想

いや、そのサイズの穴にブロックは落ちないだろ。

 

本当の感想

現実感のある評価関数を書けば応えてくれる、教養問題感がありました。ただ、それだけで到達できるのは98点(20位)くらいで、それ以上は各々の工夫が効いていたのかなと思います。私はそこで詰まってしまいましたが…。

今回は貪欲法(1手)と貪欲法(2手)を混在させて、終わったらルールベースのシーケンス作成と、手法の混在が酷かったですが、やはり終盤にメンテナンスで苦労しました。強い1つの方針で殴れるようになりたいですね…！　好き嫌いで言えばよくばりセットみたいなのも大好きなんですが。