🎅

Kaggle サンタコンペ2023振り返り

2024/02/04に公開

今回は、軽くkaggleのSanta Competition 2023の振り返りをしようと思います。

コンペ概要

ルービックキューブのような、複数の種類のパズルの解法を得ることを目的としたコンペティションでした。
パズルの状態は配列形式で与えられ、参加者は特定の条件の元、配列要素の場所を変更することができました。

例：
パズル初期状態[D;E;D;A;E;B;A;B;C;A;C;A;D;C;D;F;F;F;E;E;B;F;B;C]
↓操作
ゴール状態[A;A;A;A;B;B;B;B;C;C;C;C;D;D;D;D;E;E;E;E;F;F;F;F]

上位で使用されていた主な解法
・双方向幅探索(bidirectional BFS)
・ビームサーチ(simple beam search)
・焼きなまし法
・山登り法

これらに加えて、状態を3点以外変更しない3-rotという操作を発見し、これを上手く使って解いていたようです。

機械学習のコンペというよりは、Atcoderのヒューリスティックコンペような、最適化手法が中心のコンペティションでした。(サンタコンペは毎年こんな感じなのでしょうか？)
ここら辺は詳しくないのですが、興味深い分野ですのでそのうち学びたいと考えています。

ちなみにTransformerを利用して、64位を達成している手法もありました。
・アーキテクチャ

この手法では、(おそらく)
Qを理想の状態(ゴール)、
Kを現在の状態から操作を一回行った後の状態、
VをKと対応する操作
としてTransformerを利用し、現在の状態からより理想状態に似た状態に近づくような動作を選択するメカニズムを利用して、パズルを解いています。よく考えられていますね...

ほとんど解けませんでしたが自分の解法も供養しておきます。

強化学習の枠組みに当てはめて、DQNで解法を求めようとしたのですが結局はランダムサーチとほとんど同じ状態になってしまい、一番簡単な問題を解くのが限界でした。

今回は操作が一手でもずれると全く異なる状態になってしまうので、ε-greedy法を使用した探索がほとんど上手くいかなかったのだと思っています。
最初に最適解を一度通らせて、各学習プロセスでは一度だけ最適解ではないものを選択していましたが、ランダムサーチの域を出ていないような気がしています。

やはり機械学習やヒューリスティック最適化など様々な分野の知見を持っていると強いですね。今後も似たようなコンペがあれば参加してみたいと思います。

それでは、最後まで読んでいただきありがとうございました。