ソリティアがアルゴリズムで解けるのか、AIソルバーがどう機能し戦略について何を明らかにするのかを学びましょう。
コンピューター科学の観点から、ソリティアはどのように解析されるのでしょうか？アルゴリズムとAIがソリティアを解く仕組みを解説します。
はい、そしていいえ、"解決"の意味とどのバリアントが問題かによります。計算機ソルバーは、FreeCellの標準番号セットのすべての配布を徹底的に分析し、確実に8つの勝てない配布をカタログ化し、他の32,000以上の配布がすべて勝てることを確認しました。これらのソルバーは、Klondike、Spider、Forty Thievesの配布が本質的に解決可能である割合を、高い信頼性で推定しています。これは、数百万のランダムに生成された配布を通じて自動的に徹底的な検索を行った結果です。この意味では、ソリティアはアルゴリズム的に広範囲に解決されています。どの配布が勝てるかの数学はほぼ確立されており、自動ソルバーは出会ったほとんどの勝てる配布に対して勝利の手順を見つけることができます。
別の意味では、ソリティアはアルゴリズム的に完全には解決されていません。解決されていない側面は、実際に難しい計算問題です。Klondikeの勝利可能性の分析は正確ではなく、確率範囲（約79〜91%が勝てる）であり、正確な数字ではありません。これは、Klondikeの裏向きのカードの不確実性が隠れた情報問題を引き起こし、完全な徹底分析を大規模に行うことを計算上困難にしているためです。FreeCellのような完全に可視なバリアントでも、特定の位置が勝てるかどうかを判断することは、計算の複雑性クラスPSPACE完全の問題です。これは、NP完全問題よりも難しいと考えられている問題のクラスであり、既知の多項式時間アルゴリズムは存在しません。すべてのソリティアバリアントを完璧に、かつ合理的な時間内に解決する効率的なアルゴリズムの存在は、現在の数学的結果によって保証されておらず、いくつかのバリアントはコンピュータサイエンスにおける未解決の研究問題として残っています。
実際のソリティアプレイヤーにとって、アルゴリズムとソリティア戦略の関係は、2つの方向で最も有用です。1つは、アルゴリズムソルバーが配布の勝利可能性について確立したことを理解すること（これは私たちの勝率ガイドにおける勝利期待に直接影響します）、もう1つは、どのアルゴリズム技術が人間の戦略的思考に対応するかを理解することです。なぜなら、最も効果的な人間のソリティア戦略は、自動ソルバーが使用する同じヒューリスティック検索の簡略版を適用することが判明しているからです。
アルゴリズム的な観点から見ると、ソリティアは単独プレイヤーの探索問題です。初期状態（シャッフルされた配布）から始まり、ソルバーは初期状態を勝利状態（すべてのカードが基盤に正しい順序で置かれる）に変える合法的な手のシーケンスを見つけなければなりません。状態空間、つまりゲームが通過できる異なるボード位置の総数は、天文学的に大きいです。単一のKlondikeゲームは、すべての可能な初期配布からのすべての可能な手のシーケンスを考慮すると、数十億から数兆の異なる位置の状態空間が推定されます。80枚のカードを使ったForty Thievesは、比例的に大きな状態空間を持ち、徹底的な検索を行うことが現代のハードウェアでも計算的に高価になります。
ソリティア探索に適用される主要なアルゴリズム的アプローチは、徹底的な深さ優先探索です。これは、勝利の道が見つかるまで、またはすべての道が敗北であることが確認されるまで、すべての可能な手のシーケンスを体系的に探索します。次に、ヒューリスティックな最良優先探索があります。これは、推定された位置の質スコアに基づいて手を優先し、有望な道を最初に探索します。最後に、モンテカルロシミュレーションがあります。これは、現在の位置から数千回のランダムなプレイアウトを実行し、勝利状態に到達するプレイアウトの割合をその位置の勝利可能性の確率の推定として使用します。各アプローチは、計算コストと解の質の間で異なるトレードオフがあり、それぞれが人間の戦略的思考の異なるレベルにマッピングされます。
徹底的な深さ優先探索（DFS）：正確な答え、高い計算コスト。深さ優先探索は、初期位置からのすべての可能な手の順序を探り、行き止まりに達した場合はバックトラックし、勝利の道が確認されるか、すべての道が敗北の位置に至ることが確認されるまで続けます。FreeCellでは、完全な情報により状態空間が完全に列挙可能であるため、DFSは特定の配布が勝てるかどうかを決定し、勝利の手順を見つけることができます。DFSソルバーによって特定された8つの勝てないFreeCellの配布（有名な配布11,982と146,692を含む）は、徹底的な探索によって、これらの初期位置からの合法的な手の順序が勝利に至らないことを確認しました。
Klondikeでは、DFSは隠れた情報の問題に直面します：裏向きのカードは複数の可能なカードのいずれかであり、ソルバーは特定の隠れたカードの値を仮定する必要があります（これはその仮定に基づく結論を生み出します）またはすべての可能な隠れたカードの割り当てを分岐させる必要があります（これにより、検索空間が隠れたカードの構成の数で増加し、大規模なサンプルに対して完全な徹底的検索が実行不可能になります）。これが、Klondikeの勝利率が正確な数値ではなく範囲である理由です。これは、すべての可能な配布の完全な分析ではなく、多くのランダムな配布にわたる確率的サンプリングの結果です。
ヒューリスティックな最良優先探索：迅速な準最適解、完全性の保証なし。最良優先探索は評価関数を使用します。これは、ボードの位置の質を推定するヒューリスティックスコアであり、最初に探索する状態を優先します。ソリティアの高品質なヒューリスティックは、基盤カードの数、裏向きカードの数、利用可能な合法的な手の数、テーブルのシーケンスにおけるスートの統合度に基づいて位置をスコアリングするかもしれません。良好なヒューリスティックを用いた最良優先探索は、勝てる配布においてDFSよりも劇的に早く勝利の解決策を見つけますが、最適（最短）解を見つけたことを保証することはできず、ヒューリスティックが良い位置と見なすものから一時的に離れる必要がある配布では、解決策を見つけられない可能性があります。ヒューリスティックな最良優先アプローチは、人間の専門家の戦略に最も直接的に類似しています：どちらも位置の質評価関数（ヒューリスティック）を使用して手の選択を導き、有望なパスを最初に探索し、直感に反する中間位置が必要な解決策を見逃す可能性があります。
モンテカルロシミュレーション：確率的推定、隠れた情報に適している。モンテカルロ法は、現在の位置からの多くのランダムなプレイアウトを実行します。合法的な手をランダムに行い、ゲームが勝利または敗北で終了するまで続け、すべてのプレイアウトにおける勝率をその位置の勝利可能性の確率推定として使用します。モンテカルロは、隠れた情報の変種であるKlondikeに特に適しています。なぜなら、各プレイアウトが現在知られている分布に一致する隠れたカードの値をランダムに割り当て、そこからランダムな手の順序を探索し、その結果を推定に貢献するからです。結果として得られる勝率の推定は正確な答えではなく、統計的不確実性を伴うサンプル平均ですが、計算的に扱いやすく、プレイアウトが増えるにつれて改善されるキャリブレーションされた信頼区間を生成します。モンテカルロシミュレーションは、私たちの確率戦略ガイドで説明された人間の確率的評価の計算的アナロジーです。どちらも完全な列挙からではなく、可能な結果のサンプルから位置の勝利可能性を推定します。
ヒューリスティック検索モデルは、強制スキャンシーケンスが機能する理由を説明します。強制スキャンシーケンス — 基盤？明らかにする？純粋な構築？空の列？ストック最後 — は、人間が実行可能なヒューリスティックであり、アルゴリズムのヒューリスティックがボード位置に優先スコアを割り当てるのと同じように、手のタイプに優先重みを割り当てます。基盤への移動は勝利条件を直接進めるため優先され、明らかにする移動は将来の勝利可能な位置の状態空間を拡大するため優先され、ストックの引きは有限のリソースを消費するため優先度が下がります。この優先順位の順序は任意ではなく、経験的に訓練されたソリティアのヒューリスティックが同じ手のタイプに割り当てる移動優先順位の順序に密接に対応しています。強制スキャンシーケンスは、実際には自動ソルバーが使用する最良優先ヒューリスティックの手動実行可能な近似です。
元に戻す機能は、アルゴリズムの分岐に類似した人間の仮説検証を可能にします。自動ソルバーは、移動ツリーの複数の分岐を同時に探索し、行き止まりからバックトラックして代替パスを試みます。人間のプレイヤーは分岐を同時に探索することはできませんが、オンラインソリティアの元に戻す機能は近似を提供します：プレイヤーは手を行い、その結果を数手後に観察し、最初のパスが期待外れである場合は分岐点に戻って代替手を試すことができます。この推測的な分岐 — 手を行い、それが何を可能にするかについての仮説をテストし、仮説が否定された場合は元に戻す — は、DFSにおけるバックトラックステップの人間がプレイ可能な同等物です。元に戻す機能を体系的に仮説検証に使用するプレイヤーは、複雑な位置においてDFSソルバーが効果的である理由を人間規模で適用しています。
循環依存関係の特定は、行き止まり検出の人間が実行可能なバージョンです。DFSソルバーが勝利の道が存在しない位置に達すると、すべての可能な継続を尽くして、どれも勝利に至らないことを発見することでこれを検出します — これは計算コストの高いプロセスです。人間のプレイヤーは、カードAがカードBの前に移動できず、カードBがカードAの前に移動できない構成を特定することで、行き止まりの位置のサブセットをはるかに迅速に検出できます。外部の解決策がない場合、この循環依存関係チェックは、人間が実行可能な行き止まり検出のヒューリスティックであり、ポジティブな場合は、徹底的な検索を必要とせずにアルゴリズムの行き止まり検出と同じ情報を提供します。循環依存関係の特定の習慣を発展させることは、アルゴリズムソルバーの動作を理解することの主な実用的な利点です — それは高コストの計算プロセスを迅速な人間が実行可能なチェックに変換し、同じ辞任の決定をより効率的に生み出します。
FreeCellの完全な情報は、アルゴリズムと人間の戦略が最も密接に一致する変種にします。FreeCellでは、すべてのカードが最初の手から表向きであるため、人間のプレイヤーは原則として自動ソルバーが探索するのと同じ完全な手のツリーを計算できます。実際の違いは計算能力です：ソルバーは毎秒数百万の位置を探索できますが、人間のプレイヤーはおそらく1分間に5〜10の位置を評価できます。しかし、問題の構造 — 完全な情報、決定論的な結果、完全に列挙可能な状態空間 — は人間とアルゴリズムのプレイの間で同一です。これが、FreeCellが最も深い戦略的思考を発展させるための最良の変種である理由です：その完全な情報環境は、人間のプレイヤーにヒューリスティックソルバーが使用する完全な位置の質評価にアクセスを提供し、確率戦略ガイドで専門的なレベルで説明された条件付き手のシーケンシングと完全な期待値評価を可能にします。体系的な元に戻す機能を用いたFreeCellのプレイは、人間のプレイヤーが手動でアルゴリズムソルバーを実行する最も近い方法です。
アルゴリズム的ソルバーの存在が、すべての配札が解けることを意味するという誤解があります。アルゴリズム的ソルバーは、勝てる配札に対して勝利の道筋を見つけますが、勝利の道筋が存在しない場合にはそれを作り出すことはできません。例えば、FreeCellの8つの解けない配札は、ソルバーがすべての可能な道筋を試した結果、勝利に至る道がないことが確認されたために特定されました。さらに、解けない確率が高いバリエーション（40人の盗賊では40〜60%、スパイダー4スーツでは45〜60%）では、アルゴリズム的ソルバーがランダムな配札の大部分に勝利の道筋がないことを確認しています。これは、どんなに高度なアルゴリズムでも、これらのゲームに勝つことができないことを意味します。強力なソルバーの存在は、配札の構造を変えるものではなく、その構造をより正確に分析する手段を提供するに過ぎません。
ソルバーが見つけた勝利の道筋が唯一の勝利の道筋であると仮定することも誤りです。ほとんどの解けるソリティアの配札には、複数の勝利の道筋があります。これは、勝利条件に至るための異なる手の順序が存在することを意味します。ソルバーが見つけた1つの勝利の道筋は、実際には数百または数千の道筋の中の1つに過ぎません。これは人間のプレイにとって重要です。なぜなら、ソルバーの特定の道筋は非常に直感に反する場合があり、数手先にその利点が明らかになるまで、見た目には有害に思える手を必要とすることがあるからです。一方、同じ配札に対する他の勝利の道筋は、人間のパターン認識にとってよりアクセスしやすい場合があります。ソルバーが見つけた勝利の道筋の存在は、その配札が解けることの確認であり、人間のプレイヤーが同じ配札に最も効率的にアプローチする方法を示すものではありません。
アルゴリズム的な勝率をカジュアルプレイに適用することも誤解です。ソルバーが「クロンディケのターン1の配札の35%が最適なプレイの下で解ける」と判断した場合、その数字は完璧な情報処理、各決定ポイントでの最適な手の選択、そして人間の認知的制約がないことを前提としています。カジュアルな人間のプレイでは、クロンディケでの勝率は15〜25%に達しますが、戦略的なプレイでは35〜45%に上昇します。しかし、アルゴリズム的な最適上限（約79〜91%）は、完全な状態空間にアクセスできるソルバーによってのみ達成可能です。人間プレイヤーにとってのアルゴリズム的勝率データの正しい解釈は、個人的なベンチマークとしてではなく、構造的な参照として理解することです。これは、現在の勝率と理論的な上限との間のギャップが、配札の数学によるものなのか、戦略の質によるものなのかを示しています。この構造データを使用するための完全なフレームワークについては、配札の質に関するガイドを参照してください。
FreeCellは、アルゴリズムと戦略の関連性を体験するための最適なゲームです。なぜなら、完全な情報があるため、体系的な探索と正しいプレイの関係が直接観察できるからです。FreeCellのプレイヤーが手順木を系統的に追跡し、すべての合法的な手を評価し、最も優先度の高い道筋を選択し、代替の枝をテストするために元に戻す機能を使用し、行き止まりを確認するための循環依存関係を特定することは、自動ソルバーが使用するヒューリスティックな最良優先探索の簡略版を実行していることになります。
一方、スパイダーソリティアは、完全なアルゴリズム分析を困難にする隠れた情報の次元を導入します。これには、モンテカルロ法の確率的推定アプローチが必要であり、これは人間のプレイにおいては確率加重の手の評価として表現されます。この評価は、確率戦略ガイドで説明されています。FreeCell（完全情報、決定論的、ヒューリスティック探索）とスパイダー（部分情報、確率的、モンテカルロ推定）は、ソリティアAI研究が探求する2つの主要なアルゴリズムパラダイムをカバーしており、両方で強力なプレイを発展させることは、アルゴリズムと人間のソリティア戦略の関連性を最も深く理解するための鍵となります。
人間が実行可能なアルゴリズムは、自動ソルバーが行うことに最も近いものとして、3つの要素を組み合わせています。これらは、強制スキャンシーケンスを移動優先ヒューリスティック（ファウンデーション → アンカバー → ピュアビルド → 空の列 → ストック）、アンドゥベースの仮説検証をバックトラッキングメカニズムとして、そして循環依存関係の特定をデッドエンド検出のショートカットとして使用します。これら3つの要素を組み合わせることで、バックトラッキングと部分的なデッドエンド検出を伴う簡略化されたヒューリスティックな最良優先探索が実現されます。これは、勝率を最大化するためのアルゴリズムの人間による最も近い近似を実行していることになります。
FreeCellは、アルゴリズムにとって最も簡単である理由は、人間の戦略分析にとっても最も扱いやすいからです。完全な情報は隠れたカードの分岐問題を排除し、ほぼ100%の勝利可能性は、ほとんどすべての位置に勝利の道筋があることを意味します。また、4つのフリーセルと8つの列があることで、解決の柔軟性が十分に提供され、解決パスはほとんど直感に反する逆行動を必要としません。特定のFreeCellの位置を解決する計算の複雑さは、最悪の場合にはPSPACE完全であり、つまり多項式時間のアルゴリズムが存在することは保証されていませんが、実際には、適切に実装されたヒューリスティックソルバーは、ほとんどすべてのFreeCellの取引に対して数ミリ秒以内に勝利の道筋を見つけます。
Spider 1-Suitも、単一スートの制約により同様に扱いやすいです。難易度の高い方では、Klondikeの隠れた情報が、見た目のシンプルさが示唆するよりもアルゴリズムが確定的に解決するのを難しくしています。また、Forty Thievesの大規模な2デッキ状態空間と制限されたビルドルールは、完全な情報が仮定されている場合でも計算コストが高くなります。これらのゲームの特性を理解することで、プレイヤーはより効果的な戦略を立てることができるでしょう。
いいえ。最善のAIでも約78〜80%程度の勝率です。残りは勝てない配りです。
多くのソリティアサービスのヒント機能は、単純な規則または探索アルゴリズムを使用しています。
ゲーム番号#11982が有名な解けない配りです（Microsoft Windows版フリーセルのゲーム番号）。