在出货前用机器证明自动生成的全部400个关卡均可解的故事
自動生成した400面すべてを「解けること」を機械で証明してから出荷した話
自動生成したパズルを出荷するとき、いちばん怖いのは「解けない面が1つ混ざっていること」です。
レビューに「○○面がクリアできない」と書かれた時点で、それが生成器のバグなのか、プレイヤーが見落としているだけなのかを、開発者自身が判定できません。400面を手で確かめるのは現実的ではない。
なので、全部を機械に解かせることにしました。
この記事は、そのために書いたソルバーと、難易度指標を一度設計し直した話です。最後に、公開してみてどうだったかの数字も正直に置いておきます。
何を作ったか
スライドパズルです。ブロックを弾くと、何かにぶつかるまで滑る。同じ色が触れると消える。盤面を空にすればクリア。
盤面は最大8×8、ステージは400面。広告なし、トラッキングなし、オフラインで動きます。Godot 4.7.1 (mono) + C# で、Android 向けに出しました。
ルール自体は古い形式です。手を入れたのは、面の作り方と並べ方のほうです。
自動生成パズルの弱点
手で作る代わりに生成器を書くと、3つ問題が出ます。
- 解けない面が混ざる
- 「★3 = 最短手数」の最短が、設計者の勘になる
- 難易度の並びが体感とずれる
1は致命的です。2と3は、気づかれないまま品質を削ります。「★3の条件は5手」と書いておいて、実は4手で解けるなら、そのステージは一生★3が取れないか、逆にゆるすぎるかのどちらかです。
これらは全部、盤面を実際に解いてみれば分かる問題です。
だから全部解かせた
パイプラインを4本のコマンドに分けました。
gg-generate → gg-curate → gg-validate → gg-bundle
生成 選別 検証 同梱
要点は gg-validate が JSON に書かれた値を一切信用しない ことです。解けるかどうか、最短手数、解答例、難易度指標 ── 全部その場で再計算して、ファイルの中身と照合します。
/// <summary>スコア再計算との許容誤差。JSON には小数1桁で丸めて保存しているため。</summary>
private const double ScoreTolerance = 0.06;
private const double MetricTolerance = 0.006;
検証器のコメントにこう書きました。
ルールの解釈は solver 側（Rules / BfsSolver / StateSpaceAnalyzer）に委ねる。
検証器がルールを再実装してはいけない。
検証のために独立した実装を書くと「2つの実装が両方間違っている」事故が起きます。それよりも、ルールの実装は1つに保って、値だけを再計算して突き合わせるほうが安全だと判断しました。
ソルバーの実装
幅優先探索です。層ごとに進めて、ゴール（盤面が空）に到達した深さが最短手数になります。
状態をintにパックする
ブロック1個を int に詰めます。
bit 0- 5 : pos (0..63) 盤面は最大 8x8 = 64 セル
bit 6- 9 : color (1..15)
bit 10 : fixed
bit 11-18 : uid (元 blocks 配列でのインデックス)
ポイントは uid を状態の同一性判定に使わない ことです。同じ配置なら、どういう経路で来ても同一の状態として扱いたい。一方で、解答例を出力するときは「何番目のブロックを動かしたか」が要ります。
そこで、キーを取るときに uid を落とします。
/// <summary>状態の同一性判定に使う部分（uid を除いたもの）。</summary>
public static int Key(int b) => b & KeyMask; // bit 0-10
正準形
状態のキーは、全ブロックの (位置, 色, fixed) を昇順ソートしたものです。地形は不変なので状態に含めません。
public StateKey(ReadOnlySpan<int> blocks)
{
var cells = new int[blocks.Length];
for (int i = 0; i < blocks.Length; i++) cells[i] = Blk.Key(blocks[i]);
Array.Sort(cells);
...
}
ソートしているので、同じ色のブロックが入れ替わっただけの配置は同一視されます。これをやらないと状態数が階乗で膨らみます。
解の本数も数える
ついでに、最短手数での解が何通りあるかも数えています。層を進めるときに到達回数を足し込むだけです。
if (nextCounts.TryGetValue(nk, out long c))
nextCounts[nk] = SaturatingAdd(c, here);
オーバーフローで負になると「解が無い」と誤判定しかねないので、飽和加算にしてあります。
この値が後で効きます。たとえば無料51面は6×6で最短4手ですが、正解の手順は11通りしかありません。この数字は、そのまま「どれくらい狭い道を通すのか」の指標になります。
Unsolvable と Unknown を分ける
ここは意識的に分けました。
public enum SolveStatus
{
Solved,
/// <summary>全状態を探索したが解がなかった。このレベルは採用不可。</summary>
Unsolvable,
/// <summary>探索上限に達して打ち切った。**Unsolvable と混同しないこと。** このレベルは採用不可。</summary>
Unknown,
}
探索上限（200万ノード）に当たって打ち切った状態は、「解けない」ではなく「解けるかどうか分からない」です。扱いは同じ（不採用）ですが、意味が違うものを同じ名前にすると、あとで必ず誤読します。
結果として、出荷したのは「解けることを証明できた面」だけになりました。「たぶん解ける面」は1つも入っていません。
ルールの実装をクライアントと共有する
ソルバーとゲーム本体で判定が食い違ったら、検証の意味がなくなります。「ソルバーは解けると言っているのに、アプリでは消えない」という事故です。
これを構造的に起こせなくしました。Godot 側の .csproj が、ソルバーのソースを直接リンクで取り込んでいます。
<Compile Include="..\tools\solver\Board.cs" Link="Shared\Board.cs" />
<Compile Include="..\tools\solver\Blk.cs" Link="Shared\Blk.cs" />
<Compile Include="..\tools\solver\Rules.cs" Link="Shared\Rules.cs" />
<Compile Include="..\tools\solver\StateKey.cs" Link="Shared\StateKey.cs" />
<Compile Include="..\tools\solver\BfsSolver.cs" Link="Shared\BfsSolver.cs" />
コピーではなくリンクなので、2つの実装が存在しません。 ずれようがない。
そのうえで、アプリ側の疎通テストで全400面の解答例を Godot ランタイム上で実際に再生します。
// 全400面の解答例を再生する。1面でも食い違えば共有が壊れている。
foreach (var mv in level.Solution!.Example) model.TryApplySolutionMove(mv);
ビルド時に走るテストは現在59件。ここが落ちたら、何かが根本的に壊れています。
難易度指標を設計し直した話
ここがいちばん時間を使いました。
最初の設計
難易度スコアは、こういう式です。
double raw =
minMoves * 5.0
+ (1.0 - openingAccuracy) * 20.0
+ deadEndRatio * 30.0
+ branchingFactor * 0.5
+ blockCount * 0.8
+ (colorCount - 2) * 3.0;
-
openingAccuracy── 合法な初手のうち、最短クリアを維持できる手の割合 -
deadEndRatio── 詰みに入る割合 -
branchingFactor── 平均の合法手数
この deadEndRatio を、最初は素直に「深さ minMoves 以内の到達状態のうち、クリアできない状態の割合」として実装しました。
0.95 が返ってきた
6×6・8ブロックの盤面で 0.95 が出ました。expert に分類されます。でも実際に遊ぶと、そこまで難しくない。
原因は単純でした。状態数は深さに対して指数的に増えるので、最深層だけで比率が決まってしまうのです。
深さ4までの状態が 10 / 60 / 300 / 1500 と増えていくなら、合計に占める最深層の割合が圧倒的です。そして深い層ほど詰みが多い。結果として、この指標は難しさではなく分岐数を測っていました。
深さごとに測って平均する
測るものを変えました。「状態の何割が詰みか」ではなく、「まだ勝てる状態から指した手が、勝ちを失わせる確率」です。それを深さごとに出して、平均します。
bool Alive(int i) => dist[i] >= 0 && depth[i] + dist[i] <= maxDepth;
for (int v = 0; v < index.Count; v++)
{
foreach (int u in reverse[v])
{
int d = depth[u];
if (d >= minMoves) continue; // 起点が深すぎる手は数えない
if (!Alive(u)) continue; // すでに詰んでいる状態からの手は数えない
edgesFrom[d]++;
if (!Alive(v)) blunders[d]++;
}
}
深さごとに blunders[d] / edgesFrom[d] を出して、その平均を取る。深さによる重み付けが消えて、「うっかり手順を壊す確率」に対応する数字になりました。
ゴールからの距離は、前向きBFSの最中に逆辺を記録しておいて、ゴールから逆向きBFSで求めています。
探索を深さで制限する
初版は到達可能な全状態を列挙していましたが、6×6・8ブロックで500万状態を超えて破綻しました。
いまは深さを minMoves + 2 に制限しています。計算量が抑えられるだけでなく、「あと2手の余裕を残して最短クリアの目が消える」という、実際にプレイヤーが感じる難しさを測る指標になりました。制限が、結果的に定義を良くした形です。
出てきた数字
400面を通して、easy と expert ではこうなりました。
| easy | expert | |
|---|---|---|
| 最初の一手が正しい確率 | 45〜70% | 17〜20% |
| 行き止まりの割合 | 23〜27% | 46〜48% |
expert では、最初の一手の5つに4つが詰みです。
tier の閾値は推測ではなく、生成した207面のスコア分布から逆算しました。実測でのスコアの出現範囲は31〜81で、0〜100の全域は使っていません。
public static string Tier(double score) => score switch
{
< 43 => "tutorial",
< 56 => "easy",
< 67 => "normal",
< 77 => "hard",
_ => "expert",
};
余談：手数では難易度を測れなかった
集計して分かったことがあります。
| パック | 最短手数 |
|---|---|
| 無料100面 | 2〜6手 |
| 追加200面 | 4〜6手 |
| 高難易度100面 | 5〜6手 |
どのパックでも最長6手です。 難しい面が長いわけではない。長さではなく、選択肢の狭さが難易度を作っています。
この性質のおかげで、ステージの紹介動画が10秒前後で済むという副産物もありました。
実機でしか出なかったバグ
デスクトップでは全部通ったのに、実機で初めて出たものを4つ。
1. 1回のタップで入力が2回届く
emulate_mouse_from_touch が既定で有効なので、指でのタップはタッチイベントと合成マウスイベントの両方を生みます。評価ウィジェットが両方で反転して、死んでいるように見えました。タッチを1回でも見たら、以降マウスイベントを無視する形にしました。
2. クリア後に盤面が固まる
「クリア済みなら何もしない」を、離した通知の処理より前に書いていたため、_dragging が永久に true のままになりました。
// 離した通知は、何があっても先に処理する
if (@event is InputEventScreenTouch { Pressed: false } or
InputEventMouseButton { Pressed: false })
_dragging = false;
if (_model is null || _model.IsCleared || Locked) return;
3. 日本語が全部豆腐になる
ある端末（Android 16）でシステムフォントへのフォールバックが効かず、CJKが全部□になりました。端末のフォントに頼るのをやめて、UIで実際に使っている文字列から作ったサブセットを同梱しています（Noto 5書体で約200KB）。訳文にサブセット外の字が入ったらビルドを落とすテストも足しました。
4. 送信ボタンがソフトキーボードに沈む
UI全体を上にずらすと見出しが画面外に出るので、コンテナをキーボードの高さぶん縮める形にしました。VBoxが詰まって、ボタンがキーボードの真上に来ます。
なお VirtualKeyboardGetHeight() は実画面のピクセルを返します。stretch mode = canvas_items ではビューポート単位に変換が要ります（GetDisplaySafeArea() と同じ）。
バグではないもの：Android の書き出しテンプレートは net9.0 を要求します。エディタのランタイムは net8.0 なので、ビルドは通って書き出しだけ失敗します。
出してみてどうだったか
ここは正直に書きます。
- 製品版の審査に 13日（クローズドテスト＋データセーフティの申請は16分で通ったのに、です）
- 公開から2週間で、新規インストール 0件
- 過去28日のストア表示回数 158回（1日あたり約5.6回）
- 月間アクティブ端末 7
購入はゼロです。
しばらく「1日7件くらい入っている」と思っていたのですが、それは製品版トラックのカードに出ていた累計インストール数で、新規獲得ではありませんでした。カードの数字を、意味を確かめずに割り算していたわけです。
一方で、ひとつだけ良い数字があります。
ストア掲載情報のコンバージョン率 76.19%。 掲載ページまで来た人の4人に3人が入れています。
つまり、中身や掲載文の問題ではなく、そもそも表示されていない。15言語の掲載文を用意したのですが、効く場所が違いました。入口に人が来ていないのに、入口の看板を磨いていたことになります。
「作れば誰かが見つけてくれる」は、少なくとも私のアプリでは起きませんでした。
まとめ
- 自動生成したパズルは、全部解かせてから出せる。 400面を機械で検証するのは、思ったより現実的なコストでした
- 検証器にルールを再実装させない。 実装は1つに保って、値だけを再計算して突き合わせる
- ソルバーとクライアントでソースを共有すれば、判定の食い違いは起こせなくなる
- 「解けない」と「分からない」は別物として扱う
-
指標は、測りたいものを測れているか確認する。 私の最初の
deadEndRatioは、難易度ではなく分岐数を測っていました - そして、品質は露出の代わりにならない
最後の一行がいちばん高くつきました。作るほうは楽しかったのですが。
作ったものはこれです。無料で100面遊べます。
ソルバーまわりで聞きたいことがあれば、コメントで答えます。
来源：zenn · 游戏开发社区 · zenn.dev