概要

ソシャゲ「ステラソラ」の Web ミニゲームとして公開されたパズル「もぐもぐマジックボックス」が面白い仕様だったため、最高スコアを探索するプログラムを作成してみました。

自分用の備忘録を兼ねて、探索のアプローチや結果を残しておきます。

検証に使用したリソースは Github にて公開しています。

もぐもぐマジックボックスとは

縦 5 マス、横 6 マスの計 30 マスの盤面にアイテムを敷き詰めてスコアを稼ぐゲームです。

アイテムは90度、180度、270度回転して設置可能
アイテムは形状、ベーススコア、効果、効果範囲が異なる全16種類
ステージごとに配置可能なアイテムとその個数が指定されている

アイテム仕様

アイテム名

形状
■ : アイテムブロック
□ : 効果範囲

ベーススコア: アイテム自体の基礎点
効果: 周囲に及ぼす、または周囲から受ける効果

1. 至高の一杯

■
■ □
■

ベーススコア: 2
効果: 効果範囲内に他のアイテムがある時、そのアイテムのスコア +3

2. いつでもいっしょ

  □ 
□ ■ □
□ ■ ■

ベーススコア: 2
効果: 効果範囲内にスコアが 5 以上の他のアイテムが 1 つあるごとに、このアイテムのスコア +5

3. 危機一髪

      □
    ■
□ ■
□ ■ □

ベーススコア: 2
効果: 効果範囲内に他のアイテムが 1 つあるごとに、このアイテムのスコア +4

4. 家計簿

  □ □
□ ■ ■ □
□ ■ ■ □

ベーススコア: 0
効果: 効果範囲内に他のアイテムが 1 つあるごとに、このアイテムのスコア +4

5. 労働の喜び

□ ■
□ ■ ■ □
    ■ □

ベーススコア: 3
効果: 効果範囲内にスコアが 3 未満のアイテムがある時、そのアイテムのスコアを 3 まで引き上げる

6. 差し入れ

  □
  ■ □
■ ■ □
□ ■
  □

ベーススコア: 3
効果: 効果範囲内に他のアイテムが 1 つあるごとに、このアイテムのスコア +5

7. おすわりシャロ

  ■ □
□ ■ □
  □

ベーススコア: 0
効果: このアイテムのスコアは効果範囲内にあるすべてのアイテムの合計値になる

8. 十字型の宝石

□ ■ □
■ ■ ■
□ ■ □

ベーススコア: 5
効果: 効果範囲内に他のアイテムがある時、そのアイテムのスコア +5

9. 路上に咲く花

  □
■ □ □
■ □ □ □
■ ■

ベーススコア: 2
効果: 効果範囲内に他のアイテムがある時、そのアイテムのスコア +3

10. 栄養満点の種

  □ □
□ ■ ■ □
□ ■ ■ □
  □ □

ベーススコア: 0
効果: 効果範囲内にスコアが 5 未満のアイテムがある時、そのアイテムのスコアを 5 まで引き上げる

11. スヤスヤウッドモッド

  □ □
□ ■ ■
□ ■   □
□ ■ ■

ベーススコア: 3
効果: 効果範囲内にスコアが 8 以上の他のアイテムが 1 つあるごとに、このアイテムのスコア +10

12. 誰かのヘソクリ

■

ベーススコア: 2
効果: 効果なし

13. 麗しの証明写真

  □
□ ■ □
  □

ベーススコア: 1
効果: 効果範囲内に他のアイテムがある時、そのアイテムのスコア +1

14. たまご型の琥珀

■
■

ベーススコア: 2
効果: このアイテムが効果を受けている場合、このアイテムのスコア +3

15. 特大まぜまぜ棒

■ □
■ □

ベーススコア: 1
効果: 自効果範囲内に他のアイテムがある時、そのアイテムのスコア +2

16. キンキンに冷えたシュワシュワラムネ

  □
□ ■ □
□ ■ □
  □

ベーススコア: 0
効果: このアイテムのスコアは効果範囲内で最もスコアが高いアイテムと同じになる

探索の課題とアプローチ

全探索の難しさ

最高スコアを求めるためには、理論上はアイテムの配置パターンを全探索する必要があります。しかし、「配置可能なアイテム数」「設置場所の組み合わせ」「回転パターン」などを加味すると総パターン数は膨大になり、通常のPCスペックでは処理しきれません。

さらに、この手のパズル（配置問題）でよく使われる「途中で盤面を評価して見込みのないルートを切り捨てる（枝切り）」という手法が、本作では困難です。なぜなら、アイテム同士が相互に効果を及ぼし合うため、すべてのアイテムを配置し終えるまでそのルートの真の価値が確定しないからです。

そのため、今回は全探索を諦め、ランダム配置を繰り返して最適解の近似値を求めるアプローチをとることにしました。

アイテム効果の分析と最適化方針

アイテムの効果を観察すると、高スコアを求める上で重要なアイテムが2つ存在することが分かります。

おすわりシャロ: 効果範囲内のアイテムの「合計値」を自身のスコアにする
キンキンに冷えたシュワシュワラムネ: 効果範囲内の「最高スコアをコピー」して自身のスコアにする

幸いにも、ゲーム内における効果の解決順は以下のようになっていました。

他者へのスコア加算系の処理
自身へのスコア加算系の処理
合計値系（おすわりシャロ）の処理
コピー系（シュワシュワラムネ）の処理

この解決順から、「コピー系（ラムネ）の範囲内に合計値系（シャロ）を配置する」ことで、最大の相乗効果を得られることが分かります。

そこで、完全なランダム配置ではなく、以下のような制約を持たせた「狙い撃ちのランダム配置」を実装しました。

最初にコピー系アイテム（ラムネ）をランダムに配置する
その効果範囲内に合計値系アイテム（シャロ）を配置する
残りの空きスペースに、他のアイテムをランダムに配置する

論理的には、さらに「合計値アイテムの範囲内に自身のスコア加算系を配置し、その加算系の範囲内に小型アイテムを敷き詰める」というところまで固定できれば最善ですが、今回のプログラムでは実装していません。

実行結果

プログラムを実行した際の、最大スコア更新のログ（一部抜粋）です。

[エリートもぐもぐ] New Max Score Found (Random): 95 (Iter: 2)
誰麗キたた特
おおキ麗十特
路路路十十十
路た家家十誰
麗た家家特特

[エリートもぐもぐ] New Max Score Found (Random): 218 (Iter: 11513)
特誰差たた麗
特差差差麗キ
誰たいおおキ
たたいい麗路
た特特路路路

[エリートもぐもぐ] New Max Score Found (Random): 256 (Iter: 4453021)
麗十いい麗誰
十十十い家家
誰十おお家家
特特キいいた
特特キい麗た

[エリートもぐもぐ] New Max Score Found (Random): 269 (Iter: 47450560)
誰家家キ路路
た家家キ麗路
た差おお十路
差差い十十十
麗差いい十誰

ベストスコア

プログラムによる探索では最終的にスコア 271 の盤面が出力されました。
そこからさらに手動で微調整を加えた結果、スコア 293 が今回の最高記録となりました。

6/27 追記
スコア 324 達成しました。

感想

ベストスコアの盤面を振り返ると、以下のような綺麗なシナジーが形成されていました。

コピーアイテムの隣に合計値アイテムを配置
合計値アイテムの効果範囲内を、すべて自身のスコア加算アイテムで埋める
そのスコア加算アイテムの周囲を、他者へのスコア加算アイテムでブーストする

相乗効果により、合計値アイテムの効果を最大限に活かせる構成となっています。

ただ、前述の通りあくまで近似解を狙ったアプローチであり、完全な全探索を行ったわけではありません。そのため、まだ見ぬ未知の高スコア配置が存在する可能性は十分にあります。