GDD 2011 Dev Quizに挑戦してみた

Google Developer Quiz 2011に挑戦してみたのでそのまとめをしてみたいと思います。 書いたコードはgithubにアップロードしてあります。 最終結果はこんな感じになりました。

GDDの成績

苦戦するとすればチャレンジクイズだと思うので、その方針を簡単に。

チャレンジクイズの内容はいわゆる15パズルを解くという問題です。 ある盤面が与えられた時に、できるだけ短い手数で解くのがポイントになります。 基本的に、次の方針で考えました。サーチに近いかもしれない。

まず、実際に単純な幅優先探索で実装してみました。これが全く答えが出ない・・・・。 結果的に、だいたい10〜100手程度で答えが得られるのですが、最小の10手でも膨大な数になります。 上下左右の移動ができるので、10手の場合だととなり、あっというまに500万盤面の1/5です。これでは全く話になりません。

そこでコスト関数を設定して、ゴールまでのコストが低くなる手を優先する様に変更しました。コスト関数をソースから抜粋。

int estimate_cost(const node &n1, const node &n2, int w, int h) {
    int cost = 0;
    
    // (1) マンハッタン距離に基づく、答えとの距離の差
    for (int i=0; i<w*h; i++) {
        if (n1.board[i] == '=' || n1.board[i] == '0') continue;

        for (int j=0; j<w*h; j++) {
            if (n1.board[i] == n2.board[j]) {
                cost += abs((i%w) - (j%w)) + abs(i/w - j/w);
                break;
            }
        }
    }
    // (2) 答えとの距離と、現在の手数/2を合算してコストとする
    return cost + n1.operation.size() / 2;
}

簡単に説明すると、(1)でマンハッタン距離の要領で答えの盤面と現在の盤面との距離を擬似的に求めて、(2)でそこまでの手数の1/2と合算して、コストとしています。 盤面間の距離は、単純に答えからの遠さを表していて、これが小さい盤面を優先することで効率的に答えに近づけることができます。 実際に、手数の長ささえ気にしなければ盤面間の距離のみをコストとした方が早く解けます。

そのまま手数の長さを足すと、手数の長さが聞きすぎてこれもウマく答えを出すことができません。 実際1/2したり1/3したりするとわかりますが、盤面間距離と手数の長さの割合をかえると、幅優先よりになったりコスト優先(深さ優先的)になったりします。 言い換えると、メモリを犠牲にして最短手を求めるかメモリを節約する代わりに長めの手を求めるか、というようなトレードオフになっています。 色々とやってみたけっか、1/2するのが私にとっては折り合いが良かったです。

これでも、割りと4x4程度ならサクサク解けていたんですが、大きいのだとうまくいきません。 そこで、ザクッと長い手を切ってしまうことにしました。

    if (n1.operation.size() > w1*h1*4) continue;

盤面の幅w1と盤面の高さh1を乗じて4倍した値よりも長ければ、打ち切りです。 幅と高さを考慮に入れてるのは、「大きさに合わせて打ち切りの値かえた方が自然かなぁ」と思った程度で特に根拠はありません。 4も実行経過をみて消費メモリが1GBにおさまる程度のところに設定しているだけで根拠ありません。

こんな感じで、ちょこちょこ改善改善とやって行った結果、macbookでだいたい8時間計算して9割程度が解ける様になりました。 で、結果が冒頭の通りです。

nokunoさんのまとめによると、どうやら反復深化法で解いている人が多かったらしいです。 反復深化法って初めて聞いた・・・・ 結果的にはコストに深さ(手順の長さ)を含めているので、完全に同じではないにしても似たような結果が出るのではないかなぁという気がします。

今回は、コスト関数の係数を数種類試すのと、打ち切りの値をちょっといじる程度の工夫しかしていないのですが、それだけでも劇的に改善することが見て取れてちょっと面白かったです。 たぶん、コスト関数の設計をもう少し検討して行けば早く短く解ける様になるんじゃないかなーという気がします。

最後に、今回の点数分布について載せておきます。ほとんどの人はチャレンジ問題やらずにすませてるみたいですね・・・・

スコア分布

追記メモ:参加者達