12/9(月) 応用科学学会シンポジウムで自動運転に関する講演を担当します☆彡

9-21. 遺伝的アルゴリズム(vcopt)で氷の床パズルの難問生成

やること

遺伝的アルゴリズムで氷の床パズルの難問生成、という勉強会を開きました。どんな問題が出来上がったかご紹介します。

実行環境

Google Colaboratoryが利用可能です。

Google Colab

vcoptの使い方についてはチュートリアルをご参照ください。

vcoptの仕様については最新の仕様書をご参照ください。本記事執筆時とは仕様が異なる場合があります。

ソースコード

ソースコードは勉強会のページで配布されています。

また以下も学びました。

  • Pythonの「class」はどんなときに使うとよいのか?
  • パズルの難しさをどう定義(数値化)するか?
  • vcoptの使い方

岩5個

「こおりのぬけみち」の半分です。深さ18、状態数31、難しさスコア558。

岩11個

「こおりのぬけみち」と同じ個数です。深さ23、状態数60、難しさスコア1380。

岩22個

「こおりのぬけみち」の2倍です。深さ30、状態数71、難しさスコア2130。

※岩の座標が重複したために22個に満たない場合があります。

岩33個

「こおりのぬけみち」の3倍です。深さ46、状態数92、難しさスコア4232。

岩44個

「こおりのぬけみち」の4倍です。深さ51、状態数100、難しさスコア5100。

岩55個

「こおりのぬけみち」の5倍です。深さ48、状態数96、難しさスコア4608。

まとめ

岩が多すぎるとかえって簡単になってしまいました。難しさスコアは高くても、やってみると自由度が低くて簡単という印象です。岩22個程度がもっとも難しく感じるかもしれません

おまけ:大きなサイズの難問

大きな盤面で、岩30個、深さ47、状態数107、難しさスコア5029。

大きな盤面で、岩40個、深さ43、状態数125、難しさスコア5375。

大きな盤面で、岩40個、深さ51、状態数124、難しさスコア6324。

タイトルとURLをコピーしました