調子に乗って４＊４のパズルAIに解いてもらおうとしたら、探索から帰ってこなくなった( ﾟДﾟ)

改良版で、速く帰って来る場合

改良版でもそこそこかかる場合

背景

前回作った正式名称良く分からないパズルですが、
３＊３を作ったなら、まあ４＊４も作るでしょう、という軽い気持ちでたった1サイズの拡張を作成し、
そして当然自力だと全然解けないのでスクリプテッドAIにお願いしたら、、
画面固まった？
リロードも効かない？
開発者ツールでコンソールログ見ると、、、動いてる。
めっちゃ探索してる。
でも、、、何分待っても帰ってこない( ﾟДﾟ)

理由と対処

探索から帰ってこないのは、何も考えずに既存のアルゴリズムで、４＊４の探索をお願いした私の落ち度でした。
画面が固まったのは、探索のループを同期処理で待っていた私の落ち度でした。
対処は、アルゴリズムの変更、非同期処理の採用です。
これでもまだ現実的な時間で帰ってこないこともありますが、一旦ここで完成とします。

デモ

どのバージョンの自動解答も、状態によっては長時間応答しなくなるので、
中止する場合は戻るボタンか、ブラウザのタブを閉じて終了してください。

ソース

前回記事

4×4スライドパズル自動解答実装変遷まとめ

① A*アルゴリズム＋同期処理版（v301→v401）

diff

diff -u v301_script.js v401_script.js
--- v301_script.js      2025-04-27 22:59:35.694709700 +0900
+++ v401_script.js      2025-04-27 23:00:13.093500100 +0900
@@ -5,9 +5,14 @@
 const timerLabel = document.getElementById("timer");
 const clearMessage = document.getElementById("clearMessage");

+// パズルサイズとタイル数を定義
+const SIZE = 4;
+const shuffleTimes = 40;
+const TILE_COUNT = SIZE * SIZE;
+
 // パズル状態管理用変数
 let tiles = [];
-let emptyIndex = 8;
+let emptyIndex = TILE_COUNT - 1;
 let tileElements = {};
 let startTime = null;
 let timerInterval = null;
@@ -17,9 +22,9 @@

 // タイルを初期化
 function createTiles() {
-  tiles = [...Array(8).keys()].map(n => n + 1);
+  tiles = [...Array(TILE_COUNT - 1).keys()].map(n => n + 1);
   tiles.push(null);
-  emptyIndex = 8;
+  emptyIndex = TILE_COUNT - 1;
   initRender();
 }

@@ -56,7 +61,8 @@

 // インデックスからCSS transform値を算出
 function getTransform(i) {
-  return `translate(${(i % 3) * 85}px, ${Math.floor(i / 3) * 85}px)`;
+  const step = 255 / SIZE;
+  return `translate(${(i % SIZE) * step}px, ${Math.floor(i / SIZE) * step}px)`;
 }

 // 指定タイルを移動
@@ -65,8 +71,8 @@
   const index = tiles.indexOf(num);
   const diff = Math.abs(index - emptyIndex);
   const valid =
-    (diff === 1 && Math.floor(index / 3) === Math.floor(emptyIndex / 3)) ||
-    diff === 3;
+    (diff === 1 && Math.floor(index / SIZE) === Math.floor(emptyIndex / SIZE)) ||
+    diff === SIZE;

   if (valid) {
     console.log(`[Move] ${num} (${index}) → empty (${emptyIndex})`);
@@ -79,7 +85,7 @@

 // クリア判定
 function checkClear() {
-  for (let i = 0; i < 8; i++) {
+  for (let i = 0; i < TILE_COUNT - 1; i++) {
     if (tiles[i] !== i + 1) return false;
   }
   console.log(`[Game] CLEAR`);
@@ -98,18 +104,18 @@
 }

 // タイルをランダムにシャッフル
-function shuffle(times = 20, onComplete = () => {}) {
+function shuffle(times = shuffleTimes, onComplete = () => {}) {
   console.log(`[Shuffle] START (${times} times)`);
   let count = 0;
   let previousEmptyIndex = -1;

   const interval = setInterval(() => {
-    const moves = [1, -1, 3, -3];
+    const moves = [1, -1, SIZE, -SIZE];
     const possible = moves
       .map(d => emptyIndex + d)
       .filter(i =>
         i >= 0 &&
-        i < 9 &&
+        i < TILE_COUNT &&
         i !== previousEmptyIndex &&
         moveAllowed(emptyIndex, i)
       );
@@ -141,7 +147,7 @@
 // 指定2インデックス間の移動可否判定
 function moveAllowed(from, to) {
   const diff = Math.abs(from - to);
-  return (diff === 1 && Math.floor(from / 3) === Math.floor(to / 3)) || diff === 3;
+  return (diff === 1 && Math.floor(from / SIZE) === Math.floor(to / SIZE)) || diff === SIZE;
 }

 // スタートボタン押下時の処理
@@ -156,7 +162,7 @@
   createTiles();

   setTimeout(() => {
-    shuffle(20, () => {
+    shuffle(shuffleTimes, () => {
       startBtn.textContent = "Trying...";
       helpBtn.disabled = false;
     });
@@ -165,16 +171,16 @@

 // A*探索
 function solvePuzzle(initialTiles) {
-  const goal = [...Array(8).keys()].map(n => n + 1).concat(null);
+  const goal = [...Array(TILE_COUNT - 1).keys()].map(n => n + 1).concat(null);

   // マンハッタン距離の計算
   function manhattan(state) {
     let dist = 0;
-    for (let i = 0; i < 9; i++) {
+    for (let i = 0; i < TILE_COUNT; i++) {
       const val = state[i];
       if (val === null) continue;
       const goalIndex = val - 1;
-      dist += Math.abs(i % 3 - goalIndex % 3) + Math.abs(Math.floor(i / 3) - Math.floor(goalIndex / 3));+      dist += Math.abs(i % SIZE - goalIndex % SIZE) + Math.abs(Math.floor(i / SIZE) - Math.floor(goalIndex / SIZE));
     }
     return dist;
   }
@@ -183,13 +189,13 @@
   function getNeighbors(state) {
     const neighbors = [];
     const empty = state.indexOf(null);
-    const directions = [1, -1, 3, -3];
+    const directions = [1, -1, SIZE, -SIZE];
     for (const d of directions) {
       const target = empty + d;
       if (
-        target < 0 || target >= 9 ||
-        (d === 1 && Math.floor(empty / 3) !== Math.floor(target / 3)) ||
-        (d === -1 && Math.floor(empty / 3) !== Math.floor(target / 3))
+        target < 0 || target >= TILE_COUNT ||
+        (d === 1 && Math.floor(empty / SIZE) !== Math.floor(target / SIZE)) ||
+        (d === -1 && Math.floor(empty / SIZE) !== Math.floor(target / SIZE))
       ) continue;
       const newState = state.slice();
       [newState[empty], newState[target]] = [newState[target], newState[empty]];

実施内容

3×3のスライドパズル実装を4×4に拡張。
盤面サイズ（SIZE）を変数化し、4に設定。
CSSではパネル1つのサイズを63px×63pxに縮小（255÷4）。

const SIZE = 4;
const TILE_COUNT = SIZE * SIZE;

その他基本構成やA*アルゴリズムはそのまま適用。

発生した問題

探索数が爆発的に増え、帰ってこないケースが多発。
探索中にブラウザ画面（タイマー含む）フリーズ。
リロード操作にも応答しないことがあった。ブラウザタブを閉じるしかなくなる。

理論背景

3×3パズルの状態数：約18万通り
4×4パズルの状態数：約10兆通り
5×5パズルの状態数：計算不能

たった1サイズの拡張（3→4）でも、探索空間は天文学的に増加するため、
既存のA*アルゴリズムでは到底現実的な探索はできなくなった。
状態数が何千倍〜何万倍になっていて、
1手1手違うだけで、指数的に候補が増えていきます。
仮に1秒間に1億探索できても、全探索は数年かかるレベル。
参考までに、サイズ５は無理っぽい。＃やろうとしてました。

盤面サイズ	状態数	パズル的にあり得る状態数
3	9!、約36万2千通り	半分の約18万通り
4	16!、約20兆通り	半分の約10兆通り

→何故半分？
パズルの初期状態と目標状態の 転倒数（inversion number） の偶奇性が一致している必要がある。
もし一致していなければ、どれだけ操作しても目標状態にたどり着くことはできない。
これにより、約半分の状態が探索対象から除外される。
ルール破ってピースを外して入れ替える、ということはしない、できない、考えない、ということ。

転倒数について

理論的な最大状態数の約半分が到達不可能になる理由：転倒数（Inversion Number）

スライドパズルの到達可能性は、転倒数（Inversion Number） という概念で説明できます。

転倒数とは: ある盤面において、空白を除いたピースの順番を見たときに、数字の大きいピースが数字の小さいピースよりも左（または上）に現れるペアの数のことです。
例えば、以下の3x3の盤面を考えます（空白を9で表します）。

1 2 3
4 5 6
8 7 9

この盤面の転倒数を数えます。

(8, 7) のペアで1つ

したがって、この盤面の転倒数は1です。

スライドパズルの重要な性質として、1回のスライド操作（上下左右にピースを動かして空白と入れ替える操作）を行うと、盤面の転倒数の偶奇性は必ず変化します。

空白が横方向に移動する場合、転倒数は変化しません。
空白が縦方向に移動する場合、飛び越えるピースの数だけ転倒数の偶奇性が変化します。

さて、目標状態（例えば、以下のような昇順に並んだ状態）の転倒数は0（偶数）です。

1 2 3
4 5 6
7 8 9

初期状態の転倒数が偶数であれば、偶数回の操作で目標状態に到達できる可能性があります。
一方、初期状態の転倒数が奇数であれば、奇数回の操作で目標状態に到達できる可能性があります。

重要な点:

初期状態の転倒数が偶数の場合、転倒数が奇数の状態には決して到達できません。
初期状態の転倒数が奇数の場合、転倒数が偶数の状態には決して到達できません。

ありうる全ての盤面の配置を考えると、その約半分は転倒数が偶数、残りの約半分は転倒数が奇数になります。
したがって、特定の初期状態から到達可能な状態は、全ての理論的な最大状態数の約半分に限定されるのです。

② IDA*アルゴリズム＋同期処理版（v401→v402）

diff

diff -u v401_script.js v402_script.js
--- v401_script.js      2025-04-27 23:00:13.093500100 +0900
+++ v402_script.js      2025-04-27 23:01:07.858020600 +0900
@@ -169,7 +169,7 @@
   }, 300);
 });

-// A*探索
+// IDA*探索
 function solvePuzzle(initialTiles) {
   const goal = [...Array(TILE_COUNT - 1).keys()].map(n => n + 1).concat(null);

@@ -204,39 +204,48 @@
     return neighbors;
   }

-  // A*メイン探索関数
-  const open = [{ state: initialTiles, path: [], cost: 0 }];
-  const visited = new Set();
-
-  while (open.length > 0) {
-    open.sort((a, b) => (a.cost + manhattan(a.state)) - (b.cost + manhattan(b.state)));
-    const current = open.shift();
-    const key = current.state.join(',');
-    if (visited.has(key)) continue;
-    visited.add(key);
-    trialCount++;
-    if (trialCount % 1000 === 0) {
-      console.log(`[HELP AI] trialCount now: ${trialCount}`);
-    }
-    if (key === goal.join(',')) {
-      console.log(`[HELP AI] trialCount: ${trialCount}`);
-      console.log(`[HELP AI] solution: ${current.path.length} sreps`);
-      return current.path;}
-
-    for (const neighbor of getNeighbors(current.state)) {
-      open.push({
-        state: neighbor.state,
-        path: [...current.path, neighbor.move],
-        cost: current.cost + 1
-      });
+  // IDA*メイン探索関数
+  let threshold = manhattan(initialTiles);
+  let solutionMoves = [];
+
+  function search(path, g) {
+    const state = path[path.length - 1];
+    const f = g + manhattan(state);
+    if (f > threshold) return f;
+    if (state.join() === goal.join()) return "FOUND";
+
+    let min = Infinity;
+    for (const neighbor of getNeighbors(state)) {
+      if (path.some(p => p.join() === neighbor.state.join())) continue;
+      const t = search([...path, neighbor.state], g + 1);
+      trialCount++;
+      if (trialCount % 1000 === 0) {
+        console.log(`[HELP AI] trialCount now: ${trialCount}`);
+      }
+      if (t === "FOUND") {
+        solutionMoves.push(neighbor.move);
+        return "FOUND";
+      }
+      if (t < min) min = t;
     }
+    return min;
+  }
+
+  // 閾値を増やしながら反復深化
+  while (true) {
+    const t = search([initialTiles], 0);
+    if (t === "FOUND") break;
+    if (t === Infinity) return [];
+    threshold = t;
   }
-  return [];
+  return solutionMoves.reverse();
 }

 // AIによる自動解答実行
 function autoSolve() {
   const solution = solvePuzzle(tiles);
+  console.log(`[HELP AI] trialCount: ${trialCount}`);
+  console.log('[HELP AI] solution steps:', solution.length);
   console.log('[HELP AI] solution:', solution);

   let index = 0;
@@ -250,6 +259,7 @@
     moveTile(solution[index]);
     index++;
   }, 300);
+  console.log(`[HELP AI] trial end at: ${timerLabel.textContent}`);
 }

 // HELPボタン押下時にAI起動

実施内容

アルゴリズムをA*からIDA*（Iterative Deepening A*）に変更。
f=g+hでしきい値（threshold）を設け、段階的に深さ優先探索する構成に。
メモリ使用を最小限に抑え、完了判定は段階的に行う。

while (true) {
  const t = search([initialTiles], 0);
  if (t === "FOUND") break;
  if (t === Infinity) return [];
  threshold = t;
}

solvePuzzle()関数をIDA*版に刷新。

改善できた点

状態によっては現実的な時間（数十秒から数分程度）で解答が得られるようになった。

理論背景（`A`と`IDA`の違い）

特徴	A*	IDA*
探索方法	open/visitedをキュー管理（幅優先＋ヒューリスティック）	深さ優先＋段階的制限
メモリ使用	非常に多い（全候補保持）	少ない（pathのみ保持）
速度	小規模なら高速	大規模ならIDA*有利

次はタイマーなどの画面更新も可能にしようとする。

③ IDA*アルゴリズム＋非同期処理版（v402→v403）

diff

diff -u v402_script.js v403_script.js
--- v402_script.js      2025-04-27 23:01:07.858020600 +0900
+++ v403_script.js      2025-04-27 23:01:30.088150300 +0900
@@ -169,8 +169,8 @@
   }, 300);
 });

-// IDA*探索
-function solvePuzzle(initialTiles) {
+// 非同期でIDA*探索
+async function solvePuzzleAsync(initialTiles) {
   const goal = [...Array(TILE_COUNT - 1).keys()].map(n => n + 1).concat(null);

   // マンハッタン距離の計算
@@ -208,20 +208,24 @@
   let threshold = manhattan(initialTiles);
   let solutionMoves = [];

-  function search(path, g) {
+  async function search(path, g) {
     const state = path[path.length - 1];
     const f = g + manhattan(state);
     if (f > threshold) return f;
     if (state.join() === goal.join()) return "FOUND";

     let min = Infinity;
-    for (const neighbor of getNeighbors(state)) {
+    const neighbors = getNeighbors(state);
+
+    for (const neighbor of neighbors) {
       if (path.some(p => p.join() === neighbor.state.join())) continue;
-      const t = search([...path, neighbor.state], g + 1);
+      await new Promise(resolve => setTimeout(resolve, 0));
       trialCount++;
       if (trialCount % 1000 === 0) {
+        helpBtn.textContent = `trial ${trialCount.toLocaleString()}`;
         console.log(`[HELP AI] trialCount now: ${trialCount}`);
       }
+      const t = await search([...path, neighbor.state], g + 1);
       if (t === "FOUND") {
         solutionMoves.push(neighbor.move);
         return "FOUND";
@@ -233,7 +237,7 @@

   // 閾値を増やしながら反復深化
   while (true) {
-    const t = search([initialTiles], 0);
+    const t = await search([initialTiles], 0);
     if (t === "FOUND") break;
     if (t === Infinity) return [];
     threshold = t;
@@ -242,11 +246,13 @@
 }

 // AIによる自動解答実行
-function autoSolve() {
-  const solution = solvePuzzle(tiles);
+async function autoSolve() {
+  const solution = await solvePuzzleAsync(tiles);
+  helpBtn.disabled = false;
+  helpBtn.textContent = `trial ${trialCount.toLocaleString()}`;
+  helpBtn.disabled = true;
   console.log(`[HELP AI] trialCount: ${trialCount}`);
-  console.log('[HELP AI] solution steps:', solution.length);
-  console.log('[HELP AI] solution:', solution);
+  console.log(`[HELP AI] trial end at: ${timerLabel.textContent}`);

   let index = 0;
   const interval = setInterval(() => {
@@ -259,7 +265,6 @@
     moveTile(solution[index]);
     index++;
   }, 300);
-  console.log(`[HELP AI] trial end at: ${timerLabel.textContent}`);
 }

 // HELPボタン押下時にAI起動

実施内容

solvePuzzle()を非同期版 solvePuzzleAsync()に置き換え。
各ノード探索ごとにawaitを挟み、タイマー・ラベル更新を可能にした。

  await new Promise(resolve => setTimeout(resolve, 0));

HELPボタンの表示もtrialCountに応じて更新。

改善できた点

探索中もタイマーが動き続けるようになった。
探索試行回数もリアルタイムで表示できるようになった。

新たに発生した問題

1手ごとにawaitしていたため、探索速度が極端に劣化。
数万試行を超えると探索時間が数分以上かかり、事実上実用に耐えなくなった。

理論背景

awaitはタスクキューに戻るため、1回ごと数msのオーバーヘッドが発生。
毎手数msの遅延×数十万手＝数分レベルの遅延。

④ IDA*アルゴリズム＋非同期バッチ処理版（v403→v404）

diff

diff -u v403_script.js v404_script.js
--- v403_script.js      2025-04-27 23:01:30.088150300 +0900
+++ v404_script.js      2025-04-27 23:02:41.177837500 +0900
@@ -207,6 +207,7 @@
   // IDA*メイン探索関数
   let threshold = manhattan(initialTiles);
   let solutionMoves = [];
+  let batchCounter = 0;

   async function search(path, g) {
     const state = path[path.length - 1];
@@ -219,12 +220,20 @@

     for (const neighbor of neighbors) {
       if (path.some(p => p.join() === neighbor.state.join())) continue;
-      await new Promise(resolve => setTimeout(resolve, 0));
+
       trialCount++;
-      if (trialCount % 1000 === 0) {
+      batchCounter++;
+
+      if (trialCount % 10000 === 0) {
         helpBtn.textContent = `trial ${trialCount.toLocaleString()}`;
         console.log(`[HELP AI] trialCount now: ${trialCount}`);
       }
+
+      if (batchCounter >= 100) {
+        await new Promise(resolve => setTimeout(resolve, 0));
+        batchCounter = 0;
+      }
+
       const t = await search([...path, neighbor.state], g + 1);
       if (t === "FOUND") {
         solutionMoves.push(neighbor.move);

実施内容

非同期探索中、一定回数(batchCounter)ごとにだけawaitする設計に改善。
バッチ単位設定：100手探索ごとにawait 1回

if (batchCounter >= 100) {
  await new Promise(resolve => setTimeout(resolve, 0));
  batchCounter = 0;
}

HELPボタンは引き続きtrialCountに応じてリアルタイム更新。
タイマーも問題なく更新。

改善できた点

探索速度が同期版とほぼ同等レベルに復帰。
タイマーもHELPラベルも滑らかに進行。
数十万試行クラスの探索でも実用的な数十秒以内で完了可能になった。

バッチ処理単位「100」の根拠

仮に1試行1msかかると仮定しても、100ms単位で一度息継ぎできる。
100ms間隔なら人間が「止まってる」と感じないレベル。
描画更新と探索速度とのバランスが良いはず。

変遷まとめ

バージョン	更新内容	問題点	改善点
v301→v401	3×3→4×4へ拡張、A*同期探索	帰ってこない、タイマー停止	-
v401→v402	IDA*導入	タイマー停止	現実的な時間で完了
v402→v403	非同期化（毎手await）	遅すぎる	タイマー動作OK
v403→v404	非同期＋バッチ処理	-	速度・描画両立達成

thresholdについて

「しきい値（threshold）」の仕組み

そもそも「しきい値（threshold）」とは？

IDA*では、「今探索していいノードの最大評価値(f=g+h)」を制限する。
この制限値を「しきい値（threshold）」と呼ぶ。
今回の実装では初回は「スタート状態のマンハッタン距離」で決める。
- つまり「今の位置からゴールまで、ざっくりこのくらいコストがかかりそう」という見積もり。
これにより、無駄な深い探索を抑えながら、現実的な範囲内で探索を進める。

具体的な流れ

まず、初期しきい値を設定する。

let threshold = manhattan(initialTiles);

ここでの manhattan(initialTiles) は、
スタート地点からゴールまでのマンハッタン距離（最も単純な推定コスト）を計算する。

例：スタート状態のマンハッタン距離が「12」なら、しきい値は「12」から開始。

次に、探索を開始するメインループ。

while (true) {
  const t = await search([initialTiles], 0);
  if (t === "FOUND") break;
  if (t === Infinity) return []; // ゴール不能な場合
  threshold = t;
}

ここで重要なポイント：

search()関数は、現在のしきい値以内でゴールに到達できるか探索する。
もし、すべてのノードがしきい値を超えてしまったら、その中で最も小さかった超過値をtとして返す。
次の探索では、そのtを新たなしきい値とする。

つまり：

ステップ	しきい値（threshold）	意味
最初	スタート地点のマンハッタン距離	「これくらいのコストで届くなら探索してOK」
1回目探索失敗	次に小さい超過f値	「もう少し深く見よう」
2回目探索失敗	さらに小さい超過f値	「さらに深く」
...	繰り返し
ゴール発見	-	探索終了

この「探索→失敗→しきい値更新→再探索」を、何回も繰り返してゴールに近づくのがIDA*の特徴です。

流れイメージ

初期状態
  ↓
マンハッタン距離計算（初期threshold決定）
  ↓
threshold以内で深さ優先探索
  ↓
ゴール見つからず → 最小超過f値を新thresholdに
  ↓
threshold更新して再探索
  ↓
ゴール発見 → 完了！

これを踏まえてコードを読むと

let threshold = manhattan(initialTiles);
while (true) {
  const t = await search([initialTiles], 0);
  if (t === "FOUND") break;
  if (t === Infinity) return [];
  threshold = t;
}

「最初は最小限の範囲だけ探索し、必要になったら段階的に探索範囲を広げていく」
という設計になっていることがわかるはず

searchについて

solvePuzzleAsync内の search(path, g) 関数詳細解説

search()関数の概要

現在のパス（path）と累積コスト（g）を元に、
しきい値(threshold)以内でゴールを探索する「1回の深さ優先探索」。
ゴールを発見したら FOUND を返し、
もし探索不能なら、次回以降必要なしきい値を計算する。

search() 関数の中身をステップごとに解説

① 現在の状態（state）を取得

const state = path[path.length - 1];

現在のパスの最後の状態（現在地）を取り出す。
これを起点に、次にどこへ進むかを考える。

② f値（g + h）を計算

const f = g + manhattan(state);

f値 = 実際にここまで来たコスト(g) + ゴールまでの推定コスト(h)。
マンハッタン距離（h）は「どれだけ遠いか」をざっくり見積もるための値。

③ しきい値オーバーチェック

if (f > threshold) return f;

f値が現在のしきい値(threshold)を超えたら、
ここではこれ以上探索しない。
代わりに、そのf値を返して「次回探索に向けた参考情報」とする。

④ ゴール判定

if (state.join() === goal.join()) return "FOUND";

現在地(state)がゴールと一致するなら、
これ以上探索は不要、FOUNDを即返す。

⑤ 最小超過f値を記録するために初期化

let min = Infinity;

子ノードたちを探索していく中で、
「しきい値を超えたけど一番小さかったf値」を覚えておくための変数。

⑥ 隣接ノードを生成

const neighbors = getNeighbors(state);

現在地から合法的に動けるすべての隣ノード（上下左右）をリスト化。
これからこの隣ノードたちを順に探索していく。

⑦ 隣ノードを順番に探索

for (const neighbor of neighbors) {

1つずつ隣ノードを取り出して、以下の手順を行う。

ステップ⑦-1: ループ検出・スキップ

if (path.some(p => p.join() === neighbor.state.join())) continue;

すでに通った状態(path)と同じなら無限ループになるのでスキップ。

ステップ⑦-2: 試行回数カウント・バッチ制御

trialCount++;
batchCounter++;

試行回数をカウント。
batchCounterも増やして、一定回数ごとにブラウザに制御を戻す準備。

if (trialCount % 10000 === 0) {
  helpBtn.textContent = `trial ${trialCount.toLocaleString()}`;
}

1万試行ごとにHELPボタンのラベルを更新し、進捗を可視化。

if (batchCounter >= 100) {
  await new Promise(resolve => setTimeout(resolve, 0));
  batchCounter = 0;
}

100試行ごとにawaitしてブラウザの応答性を確保。

ステップ⑦-3: 再帰的にsearch呼び出し

const t = await search([...path, neighbor.state], g + 1);

隣ノードに実際に移動した場合の探索を再帰的に実行。
コスト(g)を1増やして探索を進める。

ステップ⑦-4: ゴール発見チェック

if (t === "FOUND") {
  solutionMoves.push(neighbor.move);
  return "FOUND";
}

再帰探索結果がFOUNDなら、現在の移動手を記録しつつFOUNDを返す。

ステップ⑦-5: しきい値更新候補の記録

if (t < min) min = t;

隣ノード探索でしきい値を超えた場合、最小の超過値を覚えておく。
これを次回のthreshold更新に使う。

⑧ 全隣ノード探索終了後

return min;

隣ノードすべて探索してもゴールが見つからなかった場合、
今回の探索で出た「最小超過f値」を返す。

まとめ

searchは「現在地→合法な隣ノード→さらに合法な隣ノード」とどんどん探索を深く進める。
ゴールを見つけたらすぐに"FOUND"を返す。
ゴールが見つからなかったら、次に必要なしきい値(最小超過f)を返す。
深く探索しつつも、定期的にawaitしてブラウザの応答性を確保している。

イメージ

[開始]
  ↓
f値がしきい値を超えた？
   ├─ はい → f値返す
   └─ いいえ
         ↓
    ゴール到達した？
       ├─ はい → FOUND返す
       └─ いいえ
             ↓
        隣ノード探索（再帰的にsearch呼び出し）
             ↓
    最小超過f値を記録
             ↓
[全部探索し終えたら] 最小超過f値をreturn

現状到達点

4×4パズルも状態によっては 数十秒から数分で自動解答可能 。
タイマー・HELPラベル更新もリアルタイム対応。
ブラウザ応答性も維持。

現状の限界

敢えて上半分に9以上、下半分に8以下を固めてやってみると、流石に帰ってこなくなる。
可能な限り、答えの感じに近くしてから助けを呼んでください。いじわるしないでください。
一定時間経過したら、「もうちょっと答えに近くしてから呼んでね」って感じで制御を返した方が良いかも。

参考記録

CPU Xeon E3-1270v3, mem16GBで以下の結果でした。探索中のは終わったら更新します。

ver	状態	試行回数	所要時間	手数
v401	シャッフル直後自動解答開始	94,382試行	3822秒=1時間ちょっと	30手
v402	状態悪化させて自動解答開始	632,152,906試行	36988秒=10時間半くらい	61手
v403	シャッフル直後自動解答開始	323,754試行	4492秒=1時間半くらい	34手
v404	状態悪化させて自動解答開始	371,000,000試行超えてまだ探索中	11時間半くらい探索中	探索中

詰まり、端末性能次第かもですが、どの実装もそのうち帰ってくるはず。一応ちゃんと探索は継続されている。
4つの探索並行させても、CPUは50％程度だったことを考えると、試行した環境ではCPUボトルネックではなさそう。
探索速度はやはりv402が速そう。v404の二倍くらいに見える。
でも、10時間以上、というか3分以上待つ気にはなれないので、根本的にアルゴリズム見直すべきと思う。