HN 日本語サマリー

← 一覧へ戻る
AI・機械学習

世界最強の倉庫番ソルバー

The Strongest Sokoban Solver (healeycodes.com)

125 pointsby ibobev27 コメント

要約

この記事では、開発者がAI(Claude Code)を使用して作成した、世界最強を謳う倉庫番(Sokoban)パズルソルバー「Soksolv」を紹介しています。Soksolvは、既存のソルバーを大幅に上回るレベルの解決能力と速度を示し、その開発プロセス、使用されたアルゴリズム、およびAI活用の効率性について詳細に解説しています。

全文翻訳

世界最強の倉庫番ソルバーの紹介

Soksolvは、標準的なベンチマークスイートの両方で、公開されているどの倉庫番ソルバーよりも多くのレベルを解決し、24の世界初となる自動レベル解決も達成しています。また、他のソルバーが解決するレベルに対しても高速です(合計時間で約3.2倍)。

大規模テストスイート · 3,272レベル中解決率

50%70%80%90%95%98%99%1 s10 s1 min10 min+10分経過時点でのFestivalより先行

オープンテストスイート · 10,043レベル中解決率

50%70%80%90%95%98%99%1 s10 s1 min10 min+18分経過時点でのFestivalより先行

soksolv Festival Sokolution Takaken YASS BoxSearch

Festival: 同一ハードウェアで測定。その他: 公開されている結果。未解決の割合を対数スケールで表示。

この時代の一般的なことですが、私は一行のコードも手書きしませんでした。Claude CodeのOpus 5.5セッションを約430個のサブエージェント(Sonnet 5.5、Opus 5.5、Fable 5.2の混合)と共に使用しました。API相当コストは約3,500ドルです(私は100ドルのプランとリセットを使用しました)。

14日間続くClaudeセッションをMacBookから実行し、/remote-control経由でiPhoneに指示を出すことで、外出先で作業の約50%を行いました。コンピューティングに関しては、調査、検証実行、および(非常に)長いベンチマーク実行のために15,000 vCPU時間(AMD EPYC)が必要でした。

倉庫番クイックツアー

1982年に日本で初めて公開された倉庫番は、箱をゴールに押し込むパズルゲームです。1997年にPSPACE完全であることが証明され、小さな盤面でも膨大な探索空間を隠しています。人間が解けるレベルは、一般的に数百から数千の手順を必要とします。

以下はMicroban #1の解決策です。

worker: 一度に一つの箱を押す
box: 押すことはできるが、引くことはできない
goal: すべての箱は最終的にゴールに乗せられる必要がある
box on a goal: ゴールに乗っている箱

0

moves

0

pushes

レベルは敵対的

倉庫番のレベルは、移動の巡回グラフとして探索できます。分岐係数が約16(巨大な盤面では最大176!)であるため、数回の移動の後には、どのような総当たり攻撃も実行不可能になります。

プレイヤーとして、特にソルバー作者として、倉庫番のレベルは意図的に敵対的に設計されているように感じられます。明白なヒューリスティックは、ゲームのルールやレベル作成者によってすぐに罰せられます。

私が最初の倉庫番ソルバーを書いたとき(約4年前)、私は自分がどのようにゲームをプレイしているかをエンコードしようとしました。「箱をゴールに運ぶ」と、あまり深く考えずに説明できます。さて、これをプログラムでどう計算すればよいでしょうか?箱からゴールまでの距離の合計でしょうか?

これをガイドとして、可能な移動のグラフを探索し、何が起こるかを見てみましょう。

greedy: まず、最も多くの箱をゴールに乗せる

push 0

箱をゴールに乗せた後の状態

01

solution

push 0

箱をゴールに乗せた後の状態

000112

ああ、ゴールに乗っている箱を優先すると、罠にはまってしまいます。ゲームは行き詰まり、解決不可能になり、単一のルールを持つソルバーは、解決策なしで永遠に実行され続けます。

初心者プレイヤーよりも優れたパフォーマンスを発揮するために、いくつかの戦略のセットを考案する必要があります。

プロジェクトのレイアウト

私は仕事でフロンティアエージェントをしばらく使用しており、「クリエイティブな目標設定」と私が呼ぶものに(多くの利益を得て)楽しんでいます。目標、経路の一部、許容できると考えるリスク、および方法に関するいくつかの好みなどを定義します。

私が経験したのは、エージェントは非常に優れたヒルクライマーであり、ソルバープログラムは最も純粋なヒルであるということです。測定すべきことは2つあります。解決されたレベルの数と、それらの解決策の集計時間です。

プロジェクトの開始時に、Claude Codeセッションを開始し、ヒルクライミング計画を定義しました。変更不可能な既存バージョン(最初のバージョンは単なる総当たり探索でした)、実験ごとに1つの仮説、凍結された検証者(エージェントが不正行為をしないように)、および個別の昇格スイートです。

進捗を続けるにつれて、ソルバーを測定するレベルのプールを拡大し、倉庫番ソルバーコミュニティで一般的に使用されている2つのベンチマーク、大規模テストスイートとオープンテストスイートに挑戦しました。これらはますます複雑な倉庫番レベルを含んでいます。スイート間には重複するレベルがあり、ユニークなレベル数は9,756、平均16個の箱、解決には約830の手順(約160回のプッシュ)が必要です。

既存のソルバーの上に構築したくないと思った理由は2つあります。第一に、このプロジェクトは私がこのようなものを愛しているからであり、既存のプログラムに小さなパッチを適用する旅はあまり面白くありません。最初から何かの一部になり、その物語を生きる方がはるかに楽しいです。

第二の理由、プロジェクトの最終段階まで気づかなかったことですが、既存のソリューションの上に構築すると、それらの決定の知識なしに特定の設計上の決定に非常に縛られ、1桁以上の改善を行うことが不可能になります。

そこで、エージェントにいくつかの初期の基本ルールを設定しました。機械学習は使用しない(監査がはるかに難しい)、競合ソルバーのコードを読まない(非効率な設計をコピーするリスクがある)、レベルを解決するためにハードコーディングしない(それは不正行為です)。

プロジェクトの開始時、エージェントの不正行為について心配していました。初期のLLM生成が、与えられた目標を達成するためにテストをコメントアウトするだけだったことを、皆さんも覚えているでしょう!

しかし、エージェントが不正行為をした兆候は全く見つかりませんでした。この理由として最も可能性が高いのは、純粋な数字のゲームではなく、実験と学習にエージェントの動機を向けたことです。

さらに2つの基本ルールを設定しました。ソルバーはGoで書かれていること(読むのが楽しい)、そして15GBのメモリキャップで8コア/16GBのマシンに収まることです。また、公平性のためにFestival(主要な競合ソルバー)と同じコアを使用したいと考えていました。

イテレーションサイクル中、各ソリューションは凍結された検証者を使用して、元のレベルで移動ごとに再実行されました。

solver

任意のレーン、任意のトリック

Move string

dlUrrrdLullddrUl…

Verifier

すべての移動を再実行

Solved or rejected

検証済みのソリューションのみカウント

A valid solution

dlUrrrdLullddrUluRuulDrddrruLdlUU

0 / 33

moves replayed

lurd walk · LURD push a box

検証者は独自のパッケージにあり、エージェントはそれを編集できませんでした。新しいプルーニングルールを昇格させる際にも同様のチェックを行いました。2,632個の既知のソリューションを検証者で再実行し、プルーニングが1つの既知のソリューションをカットした場合、それは失敗しました(これは、導入前に2つの不正なプルーニングルールを検出しました)。

ソルバーの思考法

以前、レベルを解くことをグラフを探索することに例えましたね?そして、おそらく各ノードをワーカーのステップまたは箱の移動と数えたでしょう。しかし、歩くのは無料です!プッシュだけがパズルを変えます。そのため、プッシュを検索し、「ワーカーが到達できる場所」を flood fill として扱います。

1つの「位置」:箱のマスと、ワーカーがどの領域にいるか(正確なマスではなく)。

1

of 17 free squares reachable

?

pushes to choose from

steps from the worker possible push

このようないくつかの最適化により、移動の探索ツリーを縮小できます。例えば、箱は押すことしかできないため、箱がトンネルに詰まった場合、1つのマクロ移動に圧縮できる強制プッシュがいくつかあり、ツリーを浅くすることができます。

0 / 6

pushes

0 / 3

decisions

tunnel: the box can only go straight on

私のソルバーは謙虚な始まりでした。ベストファーストサーチから始めました。最も有望な位置を展開し、デッドスクエアを作成する位置を削除します。

start

4

0 of 14 expansions

number = pushes made + estimate of pushes left expanded waiting×n: n pushes onto dead squares, dropped

もう1つの明白な最適化は、位置の重複排除です。2つの位置は、箱が同じマスにあり、ワーカーが同じ箱に到達できる場合、同じと見なされます。

left box first

right box first

2つの順序、1つの位置:一度だけ保存。

worker here

worker here

stored

boxes

000010100000

one bit per floor squareworkersquare 0top-left square it can reach

hash

table

2つのワーカーのマス、同じビット、同じスロット:一度だけ保存。

56

sequences of 3 pushes

12

distinct positions

ワーカーは歩いて到達できるどこにでも立つことができ、それは同じ位置と見なされます。そのため、ワーカーを到達可能な領域の最初のマス(左上が優先)として保存し、それらすべてを1つのエントリにまとめます。図の右側は、これがメモリに効率的に保存できることを大まかに示しています。

デッドロック

早期に学んだ教訓の1つは、探索空間のほとんどがデッド(行き止まり)であるということです!しかし、明白なケース以外では、最初に見てもデッドであることに気づきにくいか、それがデッドであると判断するのにコスト(ノード検索)がかかります。

単純なデッドロックケースがあります。

Corner
押す側面がない。

Two boxes, one goal
両方とも壁に沿ってスライドすることしかできない。

Frozen pair
各箱がお互いをブロックしている。

Two by two
開けた床でフリーズしている。

単純なデッドロックマスがあります。例えば、Holland #68では、69個の床マスのうち19マスは決して箱を置くことができません。

dead square: a box here can never reach a goal (19 of 69 squares)

デッドロックに関連するより高度なテクニックは、PI-corral pruning(Push-In corral)と呼ばれます。ここでcorralとは、箱が邪魔をしてワーカーが到達できない領域のことです。

ここでの洞察は、これらのcorralは最終的に対処する必要があるということです。そのため、ソルバーはそれらへのプッシュを優先することができ、この作業を遅らせる他の移動をプルーニングする可能性があります。

言い換えれば、元の位置を行き詰まらせる可能性のある少数の強制移動がある場合、レベルの半分を解決するために時間を費やす意味はありません。

7

legal pushes

3

worth trying now

worker can reach corral: worker can't reach push into the corral other push

右側の3つの箱は、ワーカーが到達できない領域をフェンスで囲んでいます。それらの箱へのすべてのプッシュはその領域に入り、それらのうちの1つが動くまでボード上の他の何も助けることができません。これにより、7回のプッシュではなく3回のプッシュを試すことになります。

多くのレベルには「ゴールルーム」という概念があり、すべての箱が同じ領域に集まります。ソルバーは、探索空間を減らすために、ゴールのパッキング順序を慎重に考慮する必要があります。充填順序の数は、n個のゴールに対して約n!(10個のゴール ≈ 360万通りの順序)であり、一部のレベルでは、それらのほとんどが行き詰まりにつながります。

nearest goal first

最初の箱がゴールにぶつかると、ドアウェイに駐車してしまい、他の2つがそこを通過できなくなります。

deepest goal first

後ろから充填する。

solved

最初の箱が最も近いゴールに止まると、ドアウェイに駐車してしまい、他の2つがそこを通過できなくなります。

両端からの探索

倉庫番ソルバーに関する非常にクールな洞察は、箱を引くことによって、解決済みの位置から逆方向に探索できることです。早読みしているかもしれませんが、はっきりさせておきますが、倉庫番のゲームでは、箱を引くことは決してできません。しかし、プルをシミュレートすることで、実質的に解決策の時間を巻き戻しています。前方と後方の探索が中間で出会う場合、それぞれ単独の場合よりも大幅に少ない位置で済みます。

push from the start

試行する6回のプッシュ。ハッチングされたマスは行き止まりです。

pull backward from solved

試行する4回のプル。ここに行き止まりはありません。

前方では、角に押し込まれた箱は永久に行き止まりになるため、多くのマスが行き止まりになります。後方では箱を引くことができ、角から箱を引くことができます。したがって、この盤面では、後方探索に行き止まりはありません。

前述の約16の分岐係数を再び考えてみましょう。深さが1増えるごとに探索領域が増加します。したがって、両端から同時に開始できる場合、各探索ツリーの深さは半分になります(b^dノードは約2*b^(d/2)ノードになります)。Microban #5で見られるように、これは顕著です。

forward
0 pushes from the start

backward
0 pulls from solved

各側は到達した位置を保存します。

1012385941,89252,95116

新しい位置(深さごと)(棒グラフは対数スケール)。
Forward only: 6,019 positions. From both ends: 333.

特徴空間探索(FESS)

Feature Space Search(FESS)は、90のXSokobanレベル(かつてはコンピュータにとって到達不能だったベンチマーク)を最初に解決したソルバーによって使用されました。論文は信じられないほど興味深く、明確で、アプローチしやすいです(数学的にも重すぎません!)。直接読むことを強くお勧めしますが、主要な概念をここで要約します。

また、FESS論文の主要著者であるYaron Shohamは、非常に強力な倉庫番ソルバーFestivalの著者でもあり、私のソルバーはその手法に大いに負っています。

FESSをベストファーストサーチと比較して説明するのが最善だと思います。つまり、単一のノードスコア(いくつかの有用なメトリックから計算される)を優先して探索をガイドする代わりに、FESSは次のことを行います。

  • 進捗を記述するいくつかの特徴を選択します(例:詰められた箱の数、空きスペースの接続性、ワーカーが到達できる部屋の数など)。
  • 各位置をその小さな特徴空間のセルに投影します。
  • セルを循環し、最も探索されていないセルから展開するため、探索はさまざまな種類の進捗に広がります。
  • 特徴を1つ改善する移動を提案するアドバイザーからアドバイスを受け取ります。

これらの「特徴」をより良く説明するために、Holland #68の38回のプッシュ後の状態を見てみましょう。

Four features of one position · Holland #68 after 38 of 261 pushes

Packing · packed: 5 of 13

Connectivity · worker areas: 3

Room connectivity · blocked doorways: 4

Hotspots · boxes in the way: 3

box on a goal area the worker can't leave doorway box in the way path it blocks

次に、具体的な例として、ベストファーストとFESSで探索空間がどのように展開されるかをMicroban #35で見てみましょう。

同じレベルを2つの異なる方法で探索した結果です。グリッドの各セルは特徴の1つの組み合わせです:箱のゴールへの配置数、ワーカーエリアの数。セル内の数字は、探索がそこまでに展開した位置の数です。ベストファーストは常に最も低い推定値を持つ位置を選択します(このレベルでは、1つのセルに留まり、1259回の展開のうち405回をそこで費やします)。FESSは代わりに順番を取り、最も良いセルと交互に実行し、823回の展開で完了します。

Where the expansions go · Microban #35, 5 boxes

start

Best-first

543211012345boxes on goalsworker areas

cells reached:

1

· expansions:

1

not solved yet

FESS

543211012345boxes on goalsworker areas

cells reached:

1

· expansions:

1

not solved yet

ただし、公平を期すために言うと、この種の小さなMicrobanレベルのほとんどでは、ベストファーストの方が通常速いです。FESSは、推定値が数千の位置で連続して間違っている場合に最良の結果を出します。

私は、FESS論文から直接実装するように計画エージェントを指示しました。これは、倉庫番にとって最先端の古典的な探索戦略であり続けています。

Novelty Search

プロジェクトの2日目に、他のドメインのアイデアを探求し、実験のアイデアを提案するためにリサーチエージェントを開始しました。

この新規性のアイデアは、その探索から生まれ、ソルバーのさまざまな領域に適用され、探索領域を広げ、さまざまな種類の探索を有益な領域に導くことを期待しました。新規性は古典的な計画から来ています:width-based search / Nir LipovetzkyとHector Geffnerによる「novelty」(IW, 2012; best-first width search, 2017)。

したがって、探索ツリーの低価値領域に閉じ込められるのを避けるために、新規性は、以前に見られなかった位置(またはより抽象的な状態)に報酬を与えるために使用できます。

例えば、同様のランクの移動を選択する場合、これまで箱が置かれたことのないマスに箱を置くことは、前方探索が後方探索と出会うのを助けることができます。なぜなら、いわゆる「中間」を広げているからです。

1

expansions

3 / 14

squares a box has reached

Start.

a box has been here (darker = more often) no box here yet dead

位置は、箱がこれまでこの探索でどの箱も触れていないマスに着地した場合、新しいと見なされます。新しい位置はキューをジャンプできます。この例では、ルールありで33回の展開、ルールなしで73回の展開がかかります。

レーン

このプロジェクト全体を通して、私は計画エージェントに並行処理をうまく活用するように強く指示し、コミュニケーション、整理、および作業の再利用を強く推進しました。私がこの方向に推進した理由の1つは、並行プログラミングは人間にとって本質的に難しい(フロンティアモデルにとってはそれほどでもない)ことであり、他のすべての主要なソルバーは人間によって書かれていることです。

さらに、すべての真剣な競合ソルバーは、CやC++のように、高速でかつ正しい並行プログラムを書くのが難しい言語で書かれています。そのため、ここでの私の指示は、競合他社に対して不均衡な優位性を与えるだろうと信じていました。

したがって、私のソルバーはレーンアーキテクチャを最大限に活用しています。多くの異なる探索がすべての8コアで並列に実行され、互いに助け合います。Festivalもこの概念を使用しています。

レーンは、独自のメモリ共有を持つ、独自のコア上での1つの探索構成です。それらは位置を共有テーブルに公開し(互いに会うため)、デッドロックを共有し、進捗に応じてメモリを貸し合います。

例えば、Holland #68では、単一のレーンでは10秒以内に解決できませんが、レーン全体では3.8秒で完了します!

start positionsolved boardmacrofollows a plan for packing the goalsnoveltyprefers positions unlike any seenfa2takes turns between several planstowardaims at the best backward positionreversepulls boxes off the goalspullfeature-space search, backwardhub-pullpicks a halfway "hub" to aim forhub-genharvests many hubs, commits to a fewany forward lane can meet any backward lane

このレーンアーキテクチャは、倉庫番の敵対的なレベルの難しさと戦うための主要な戦略です。

多くの場合、単一のレーンは進歩できませんが、レーンは探索ツリーの異なる領域を優先し、それぞれが独自の決定を下すため、繰り返し協力することになります。

Holland #68

Festival 154 s, Sokolution 32 s

macro

6 s

novelty

6 s

fa2

6 s

hub-pull

6 s

hub-gen

6 s

pull

6 s

reverse

6 s

all together

3.8 s

SokHard #100

Festival 31 s

macro

6 s

novelty

6 s

fa2

6 s

hub-pull

6 s

hub-gen

6 s

pull

6 s

reverse

3.3 s

all together

1.8 s

Grigr2002 #28

Festival 4 s

macro

4.3 s

novelty

3.5 s

fa2

0.9 s

hub-pull

6 s

hub-gen

4.5 s

pull

6 s

reverse

1.7 s

all together

1.3 s

Seconds to solve. Each lane alone (6 s limit), then all together. Hatched: no solution.

テストを通じて、前方レーンと後方レーンのバランスを保つことが重要であることがわかりました。私の研究で頻繁に発生した概念は、異なる種類の作業間の接続を作成することでした。

macronoveltyfa2towardreversepullhub-pullhub-genforward tablebackward tableeach new position: write it on its side, look it up on the other (dashed)

位置のハッシュは、それがどこにテーブルに入るかを決定します。テーブルは固定サイズなので、新しいエントリが古いエントリの上に重なることがありますが、実際には問題ありません。最悪の場合、発生した可能性のあるミーティングを見逃しますが、新しいミーティングも問題ありません。例えば、Grigr2002 #17では、レーンは8つの可能なミーティングを投稿し、1つがチェックアウトし、レベルは0.65秒で解決されました。

前述したように、探索空間を移動する際の「速度制限」の1つは、デッドロックを発見するために作業を行う必要があることです。

有効な位置とともに、中間で会うことを目指し、ソリューションを接続するデッドロック位置も共有され、重複作業がスキップされます。

one lane
These three boxes can't all get home.

→

shared table

dead patterns: box squares + worker square

後で、別のレーンが同じ3つの箱の構成に遭遇し、ワーカーが同じ正規化されたマスにいる場合、パターンを(さらに検索することなく!)検索してスキップできます。なぜなら、それがデッドであることをすでに知っているからです。

ファクタリング

プロジェクトの初期段階で、既存のソルバーから直接アイデアをコピーすることなく、プランナーエージェントとそのリサーチサブエージェントがどのように進歩するかを見たかったのです。これにより、かなりの進歩があり、当時のベンチマークレベルの約93%を解決できました。

しかし、最終的には収穫逓減に達し、あらゆる可能な信号を収集する時が来ました。既存のコードベースを読み、分析のために「検索トレース」を残すように変更しました。これらのアクションを禁止していた初期の基本ルールを破棄しました。

あるリサーチエージェントは、Sokolutionが解決できたレベル(他のソルバーでは解決できなかったレベル)を分析するのに時間を費やしました。奇妙なことに、これらの他のソルバーには複雑に見えるレベルを、わずか数秒で非常に速く解決しました。リサーチエージェントが思いついた理論は、レベルのレイアウト(レベルのレイアウトのため)により、Sokolutionがレベルをファクタリングしていたというものでした。これは、レベルを効果的に独立して解決できる複数の部分に分割することを意味します。

タスクを複数の探索ツリーに分割することで、各ツリーの深さが減り、致命的な分岐係数を回避するのに役立ちます。この戦略は、他の多くのレベル(主にLife、Premysl Zika、およびSecundus gradus ad Olympoグループ)ではそれほど強力ではありません(または適用されません)。しかし、解決できるレベルでは、ソルバーが採用する他の戦略のポートフォリオの一部としてうまく機能します。

puzzle A puzzle B dead squares: no box can cross

レベルをこのように分割する方法はいくつかあります。一般的な方法の1つは、デッドボックスエリアを壁として数えることができることです(箱はそのような境界を越えることができないため)、そしてそれを複数の探索ツリーにスライスすることです。

group A group B dead for boxes

  1. Split into groups
  2. Solve each group alone
  3. Join the moves in order

UruLLdDrdLuurrrdrdrdrruUddlluRR

31

moves, 8

pushes, checked on the whole board

リレー

ここまでで気づいたかもしれませんが、ほとんどの戦略は探索空間をどんどん縮小して、解決策にまっすぐたどり着けるようにすることに関心があります。

そこでリレーの話になります。この戦略は、レーンがゴール近くで行き詰まったときに役立ちます。例えば、かなりの数の箱がすでにゴールに置かれている場合、戦略のポートフォリオ全体を、見られた最良の盤面状態で再起動できます。完成した箱は壁になります!

  1. レーンが最良の盤面を投稿します。
  2. 完成した箱が壁になります。
  3. すべてのレーンがより小さなパズルで再起動します。
  4. 2つの半分が結合され、検証されます。

これはプロジェクトの後期の実験の1つで、「ギャップ」レベル(他のソルバーは解決したが、その時点では私たちが解決できなかったレベル)を突破するために苦労していました。この発見は7つのレベル解決で報われました。

実験マシン

ソフトウェアファクトリー(と言えば)は次のように実行されました。15分ごとのハートビートチェックで実行される1つのプランナーエージェント(Opus 5.5)があり、進行中の実験とVMのヘルス/接続性をチェックしていました。このプランナーエージェントは、私たちを前進させるという任務を負っていました。それは私のセットアップ指示(ヒルクライミングの方法、基本ルール、全体的な方向性)を聞き、実験を選択し、結果を分析し、勝者を昇格させました。

次に2種類のサブエージェントがありました。

  • ビルダーサブエージェント(タスクに応じてSonnet 5.5またはOpus 5.5)は、独自のgitブランチで1つの実験アイデアを実装しました。
  • アナリストサブエージェント(Opus 5.5またはFable 5.2)は、問題を診断し、レビューと計画を行いましたが、ソルバーコードは書きませんでした(これはトークン使用量を増やさないようにするための私の個人的な指示でした)。

私が実装を依頼したもう1つの設計は、レベルごとの機能に関する単一の真実の情報源としてレベルレジャーでした。例えば、どのレベルが解決されたか、どのレベルが後退したか、どのレベルが速く遅かったかを追跡する必要がありました。特定のレベルファミリーはタグを受け取り、勝利の潜在的な影響に基づいてリサーチの方向性を知らせるのに役立ちました。

私がより積極的に活動できたとき、プランナーにアイデアを提案するように依頼し、私が検査して開発の方向性を指示できるようにしましたが、夜間はドライブしてより大きな決定を下す権限を与えました。

私が多くの価値を追加した分野の1つはリスクに関するものでした。すべてのエージェントは、わずかなリスクさえも取ることに非常に不快感を示していました(私が特にリスクを取るように求めたときでさえ)。エージェントは、回帰や分析の間違いを恐れていました。彼らは、100%正確にするためのすべてのツールを持っていたからだと思います。唯一の問題は、それに膨大な壁時計時間がかかることでした。

Planner: 私の過剰な検証傾向については、おっしゃる通りです。

2つのレベルスイートの完全な600秒実行は、VMのスライスあたり約85時間かかります!タイムアウトを設定したコマンドを強制したり、テスト実行から信号を得る方法を探すために多くのリサーチエージェントを起動したりするなど、エージェントの壁時計時間を制限するために多くのメカニズムを配置する必要がありました(例えば、ゴールに到達する前に進捗をスコアリングしたり、既知のソリューションパスにどれだけ従ったかを測定したり)。

壁時計時間に関する重い指示なしでは、このプロジェクトは実際にかかった時間の10倍長くかかったかもしれません(それは半年弱に延長されたでしょう)。

Me

goals, risk appetite, ideas and steering, permissions

↓ steering↑ health checks, questions

Planner agent

runs experiments around the clock

decides what to promote

↓ briefs↑ reports

Analyst subagents

frontier model

diagnose, review, plan

Builder subagents

cheaper models

one experiment each, on its own branch

↓ jobs↑ solve counts, timings

Laptop

builds, tests

fixed-node-count screens

Cloud machines

16 cores each

timed pairs and batch jobs

↓ every result

Experiment log and per-level ledger

792 experiments, 13,315 levels

read by the planner before each decision

もう1つの問題は、エージェントが1%の改善を何度も追求することに満足しすぎることでした。彼らは全体的な目標に向かって進歩するためなら何でも欲しがります。問題は、このドメインでははるかに積極的な思考と実験が必要だったことです(これもエージェントが弱い可能性があることです)。

私の指示の多くは、小さすぎる考え方をしている、あまり強くないアイデアを繰り返しているだけのリサーチを打ち切ることでした。

プロジェクトの初期段階では、実験が昇格を得るために証明しなければならないことに厳格なゲートを設定しました。それらは「10%のゲイン」(レベルパフォーマンス、またはトリムされたレベルスイートの解決に向けた進歩)をもたらす必要がありました。各レベルで最低+3レベルの解決と、ほとんど回帰なしという条件でした。

プロジェクトの中盤、多くの容易な成果がなくなった頃、私はプランナーエージェントに、完全な実装と部分的なベンチマーク実行の前に実行できる安価なゲートについて考える時間を使わせるように指示しました。これは非常に有益であり、プロジェクト中盤の進歩/壁時計時間を増加させるのに役立ちました。

私が重く指示したもう1つのことは、関心領域がわずかに重複していても、より多くの実験を実行するように依頼することでした。プランナーは結果を待つことを好みましたが、これもまた、壁時計時間がかかりすぎました。トークンはコンピューティングよりもはるかに安価だったので、壁時計時間とコンピューティングを無駄にするよりも、トークンを費やして無駄にする方が良いでしょう。

Brief

hypothesis tied to a measured failure

Builder subagent

own git branch, idea behind a flag

Gate, then screen

cheapest test that can kill it

Planner decides

promote: merge, tag

reject

stop at the gate

Logged

either way, with the numbers

Verdicts per day · share of decided experiments

0%50%100%Oct 31Nov 1234567891011121314Nov 2: aim for 10% winsNov 7: promote any measured gain

promoted rejected after a full test stopped at a cheap gate

11月5日に安価なゲートが登場し、それ以降、ほとんどの失敗したアイデアは、より完全なテストフェーズ(赤)に進む前にゲート(オレンジ)で却下されたことがわかります。

これらのゲートには以下が含まれます。

  • 時間ではなくノード数による決定的なスクリーン
  • 1台のマシンに2つのジョブをパックする(プランナーはデータが「不純」であるため嫌がった)
  • レベルをファミリーごとにグループ化し、それらが同様に振る舞うと仮定する
  • 最終的には、回帰を許容する(進歩がそれらを修正することを優先したため、回避するのに時間がかかりすぎた)

プロジェクトの最後の四半期では、これらの多くを解体する必要がありました。中間の容易な成果はなくなり、回帰は一般的になり、見つけるべき賭けははるかに困難になりました。また、探していたゲインもはるかに小さくなりました。追加のテストと検証が必要だったため、実験あたりの時間は約5倍になったと推測します。

ゴールに箱が配置された状態から始まる

ヒューリスティックについて少し戻ると、プロジェクト中に、箱がすでにゴールに配置された状態から始まるレベルの大きなグループで行き詰まった日がありました。「箱がゴールにある」は倉庫番のヒューリスティックの金字塔のように思えるかもしれませんが、実際にはそれよりもはるかに複雑であることが判明しました。

ベンチマークレベルの11%は、箱の75%以上がすでにゴールに配置された状態で始まります!そして、これが私たちのヒューリスティックを大いに混乱させました。すべての進捗信号(箱がゴールにある、ゴールまでの距離、パッキング順序)は、私たちがフィニッシュに非常に近いことを示していましたが、レベルの「ジグリング」が必要でした。

「アンパックファースト」やゴールへの箱の報酬を下げるなどの単純な実験はすぐに失敗しました。

最終的に、Fable 5.2のアナリストが突破口を開き、「ダイブ」レーンを提案しました。これは、解決済みの位置からゴールまでの距離を最大化し、最後にリターンフェーズを持つ貪欲な逆方向探索です。その結果、行き詰まった16レベルのクラスターのうち12レベルが解決されました。

したがって、「箱がゴールにある」という強い信号を止めさせることはできませんでした。代わりに、そのアドバイスを意図的に無視するレーンが追加されました。

starts on a goal, has to leave it

012340123456789pushboxes on goals

1,106

of

9,756

benchmark boards start with 75% or more of their boxes on goals.

ここにある4つの箱のうち3つはゴールから始まりますが、ほとんど完了しているように見えますね?しかし、他のものが実際に入る前に、そのうちの2つは離れなければなりません。したがって、カウントは3→1に減少し、その後4に戻ります。

ベンチマーク

実験はレベルスイートのサブセットで独自の数時間のベンチマーク実行を行いましたが、プロジェクトの非常に終盤になって初めて、プランナーに完全な600秒ベンチマーク実行を担当するように依頼しました。前述したように、これはVMあたり約85時間かかります!

すべてこの作業は、ただ座って進捗とプランナーエージェントの予測を監視するためでした。私のソルバーは、最初の完全ベンチマークで数レベル差で敗れました。

数百ドルを節約するために、Festivalという最も強力な競合相手のみに対してベンチマークを行うことにしましたが、他のソルバーについては、公開されているベンチマーク数値を信頼しました。しかし、私は自分のソルバーを、同じハードウェアと構成でFestivalに対して検証したいと思っていました。

数レベル足りない、あるいは数レベル多いというのは明らかに十分ではありませんでした。ノイズのしきい値内だったので、設計ボードに戻りました。

さらなる実験と昇格の後、最終ベンチマークを実行する時が来ました。8つの専用コアとそれぞれ15GBのcgroup、そして各ソリューションは検証されました。私のソルバーは、ノイズのしきい値を超えて、勝利を主張するのに十分なほど先行しました:LTSで+10、OTSで+18(完全な結果)。

Large Test Suite · solved at 10 minutes

3,1703,2083,218Nov 11Nov 12Nov 13Nov 14Nov 15Festival on our hardwarefirst run 3,217final run +10

Open Test Suite · solved at 10 minutes

9,4809,6029,620Nov 11Nov 12Nov 13Nov 14Nov 15Festival on our hardwarefirst run 9,594final run +18

Line: 開発中に得られた私たちの最高の既知の結果。ドット:2回の完全ベンチマーク実行。

同じハードウェアで両方を測定しました。短い制限時間は、各ソルバーの10分間実行での報告時間から読み取られます。注意:この投稿のチャートと数値は、Festivalを私たちのハードウェアで各制限時間で測定したものを使用しています(10分でLTS +10 / OTS +18)。チャートが競合他社を参照している場合、コンピューティング能力が不足していたため、それらの公開されている数値(他のベンチマークから)を使用しています。レベルごとの時間を含む完全なベンチマーク結果は、リポジトリにあります。

解決されたボードあたりの中央値時間は0.05秒(当方)対1.00秒(Festival)です。両方のソルバーが解決する9,223レベルでは、平均4.40秒対14.16秒であり、当方のソルバーは8,809(96%)で高速です。

0.01 s0.1 s1 s10 s100 s5 s10 s30 s100 s300 s600 ssame speedwe are fasterFestival is fasterFestival's time (same hardware)our time

1,418

boards Festival needs 5 s or more for. We are faster on

89

% of them (median

12

x).

さらに、私のソルバーは24の世界初となる自動解決(特にPremysl ZikaおよびSven Egevadファミリー)を達成しています。

コミュニティ(Festival以外の検証されていない数値)と比較しても、非常に良い成績を収めています(投稿の冒頭の図を参照)。

これをプロンプトだけで解決できますか?

このプロジェクトをプロンプトだけで一発で完了できるかどうか、興味があります。おそらくできるでしょう。「Fable、無制限のコンピューティング能力を与えるから、最高の倉庫番ソルバーを構築してくれ」のようなものです。

しかし、それは効率性の問題だと思います。人間のドライバーなしでは、壁時計時間(したがってコンピューティングコスト)は100倍の範囲になるだろうと強く信じています。792の各実験を適切に検証するには、約67,000 VMスライス時間、または市場価格で約20,000ドルかかります。あるいは、私が実行したVM構成で壁時計時間で230日かかります。

このプロジェクト中、私はICというよりテクニカルマネージャーに近い感覚でした。フォローし、指示し、導く。それは強力なエンジニアのチームを管理するようなものです。確かに、彼らは道を外れて時間を無駄にするかもしれませんが、軽い指示で修正できます。

ソルバーを書くことは、エージェントにとって非常に適しています。結果は簡単に検証でき、調整すべき人間の経験はありません。

このプロジェクトは最終的に戦略ゲーム、Tycoonファミリーのようなものだと感じました。私は熱心なコンピューターゲーマーであり、これがモチベーションの源泉の1つだったと思います。手法、実験、結果、すべてが物理的な感覚を持っていました。それは戦いのようでした。

このエージェント時代のソフトウェアでは、エージェントと同じくらい目標を望む必要があると思います。はい、誰でもソフトウェアを構築できます。しかし、それに気を配り、それを愛する必要があります。人間の焦点と努力は残ります。

最終的に、14日間でプランナーへの388通のメッセージが必要でした。

巨人の肩の上に立つ

Yaron Shoham(Festival, FESS)が信じられないほどの業績を発表し、強力なソルバーをオープンソース化して複数のリリースを行わなければ、このプロジェクトは不可能でした。

私は見つけられたあらゆるオープンソースソルバーから深いインスピレーションを受け、クローズドソースソルバーの動作も可能な限り観察しました。当初は、フィニッシュラインを越えるためにクローズドソースソルバーをリバースエンジニアリングする必要があると思っていましたが、そうはなりませんでした。

この記事のアニメーションはFable 5.2を使用して生成され、Borgar ÞorsteinssonによるLagerスキン(CC BY 3.0)を使用しています。

次は何を?

ベンチマークの100%完了を目指すことに興味がありますが、そのためにはよりコンピューティング効率の高い戦略が必要になります。

前述したように、倉庫番に適用されている既知の機械学習研究の一部からは離れました。なぜなら、監査しやすい古典的なソルバーを望んでいたからです。しかし、おそらく古典的なソルバーと学習ソルバーの興味深い戦略の組み合わせや組み合わせが存在するかもしれません。

パズル解決についてさらに学び、他者の仕事と競い合えるような、このプロジェクトに似たプロジェクトを探しています。

私のソルバーのソースコードはこちらから入手できます:https://github.com/healeycodes/soksolv