NTL Robot Challenge

Topcoder方面でWeekend Algorithm Contestなるものが開催され，少し時間を作って参加してみました。コンテスト形態はマラソンマッチですが，期間が2週間ではなく金～日の3日間という短いもの。

NASAスポンサーでRoom内上位5位に入れば賞金Getという形式でした。幸いなことに私の割り当てられたRoomはエライ過疎りようで，最終的には参加者4名でした。0点でもSubmitすれば5位に入れるという状況なのに誰も参加してこない。

私自身は(金)は仕事，(土)は家の雑用，(日)はHaskell勉強会に参加してたので，トータル5,6時間程度しか時間をかけられず，あまり練ることができませんでした。しかしながら，上述の状況なので暫定順位は2位。少しばかり賞金を頂けそうです。

問題は「複数のロボットと複数の出口があって，ロボットは全体同時にしか制御(右ターン，左ターン，前進)できないけど，なくべく短い手数で全ロボットを脱出させてね」というもの。

初めの考えは，DevQuizのスライドパズルのようなグラフ探索だったのだけど，TLEまで2秒なので早々に断念。次の考えは，それぞれのロボットが最適手を考えて投票するのってカッコイイねとか思いながら，それってタダの評価関数の線形結合だよねとか･･･結局ローカルミニマムに嵌まってグルグルと回る。

とりあえずゴールできる版として「一機ずつ脱出させる」版を作ったところで，モチベーションが切れる。前述の評価関数をチューニングするところまでは気持ちが届きませんでした。後はどれから脱出させるかを探索するようにして少しスコアを上げたところで終了でした。