はじめに
トランプゲーム FreeCell に関するまとめです
参考文献
本記事は事前調査です. 調査先を記載します
-
https://fc-solve.shlomifish.org/
- オープンなFreeCellソルバのC実装, Webインターフェースもある。
- by Shlomi Fish.
-
https://www.solitairelaboratory.com/freecell.html
- 必読: 膨大で網羅的なFreeCell研究の成果をまとめたFAQを有する有名なサイト. by Michael Keller
-
http://www.solitairelaboratory.com/solutioncatalog.html
- 上記サイトの一部だけれど、ボードの符号化の要点や Standard FreeCell Notation (by Andrey Tsouladze) という標準的な表記について説明
01. 解けない問題あるの？
あります。"freecell unsolvable" で検索すると例がいくつか見つかります。
ランダムに作成すると99.99%超の問題は解けることが経験的に知られています。一方、わずかに残る解けない問題も存在します。解けないことを紙上で証明できる問題群も存在します（→外部リンク )。証明の要点は次のようなものです：カードの移動に関する不変量の存在を示し、その不変量から導き出される性質「エースは移動できない」によって、解けないことが示されます。
02. ソルバはあるの？
shlomifish氏のソルバ がデファクトスタンダードです。C実装のコンソールアプリですが、Webアプリとしても公開している ので便利です。Ubuntuなら apt でインストールできます。
アルゴリズムには深さ優先探索（DFS）をベースしているので、最短の解が得られるとは限りません。オプションを変えることでアルゴリズムやヒューリスティックスをある程度選択・調整できます。
03. 符号化の方針
前述のソルバでの符号化を例にとりましょう。まずはボード盤面です:
Foundations: H-0 C-3 D-A S-0
Freecells: TS 6D JS
: QD 9D TH KC AS 2H TC
: JD AH 4D 2D 2S
: 4C 5H 6S 7S 5S 6C TD
: JH 3S KH 8S 3H 8C KD
: QS 3D KS 9S 8H 7C
: 7D 9H 4S 6H 4H
: 7H 8D QC QH JC 5D
: 5C 9C
Foundations:はいわゆるホームセルの別名です。ゲームルール上４つのホームセルを区別しませんが、左から順番にハート・クラブ・ダイヤ・スペード用だとしても一般性は失いません。また、ホームセルの一番上のカードさえ指定すれば各ホームセルの状態を一意に指定できます。上記例ではクラブは３枚・ダイヤが１枚がホームセルに積まれている状態を表します。
Freecells: はフリーセルの状態を表します。４つのフリーセルのうち３つが占有中であることを表します。つまりスペードの１０・ダイヤの６、スペードの１１です。
８行ある: は、８つあるスタックをそれぞれ表します。それぞれのスタックにおいて一番右のカードがトップカードであることを表します。例えばスタック３のトップカードはダイヤの１０です。
以上はボード（≒ゲーム状態）の符号化でした。続いてカード移動については、標準化された方法が ここに 記載されています。移動は、移動元と移動先を表す2文字で一つの動きを表します。移動元は1～8で指定される各スタックと、a,b,c,dで指定されるフリーセルと、hで表されるホームセルとがあります。ホームセルが1つでいいのは、移動元が指定されれば移動先のホームセルは一意に決まるという事情によります。例を挙げます:
83 a3 71 7h
これは
- スタック8のトップカードをスタック3に移動させ
- フリーセルa のカードをスタック3に移動させ
- スタック7のトップカードをスタック1に移動させ
- スタック7のトップカードをホームセルに移動させる
という一連の４動作を表します。最初の２動作はフリーセルの占有数を減らす操作で、後半の２動作はホームセルへの移動するためにカバーされているカードをどかす操作です。
04. ゲームの識別子
FreeCell 愛好家は番号で盤面を指定します。例えば #11982 は解けない問題であることが知られています。採番は歴史的な経緯によります。
元々Windowsに付属されていたFreeCellには、32000個の問題がありそれらに通し番号がついていました。現在でもWindowsを含む多くの FreeCell の実装で #1～#32000 は当時の問題と同一となるようにするのが慣習です。
Windowsでの32000個の問題はある関数によって自動生成されていました。Jim Horne が solitairelaboratory.com に公開した方法 やその ポート でそれらを再現できます。実装には特にひねった部分はありません。これにより #11982 などの有名な盤面を再現できます。なお、#11982 は最初の32000ゲームの中で出てくる唯一の解なしの盤面です。
05. 難易度の定量化
プレーすると問題によってだいぶ難しさに違いがあるのがわかります。最近の FreeCell では難易度を選択できます。例えば Microsoft のアプリでは 初級・中級・上級・エキスパート・ランダム という5つの区分から選べます。難しさに関するなんらかの尺度どう定義したらよいでしょうか？統一的な見解はありませんが、いくつか候補が上がっているので紹介します
05-a. 動作数で難易度を測る
一番ナイーブには、全カードをホームセルに積み上げるのに必要な動作数を難易度の尺度にとることでしょう。ソルバが最短の解を示してくれるとは限らないので、動作数は暫定的な値になりますが定量化は簡単です。
一方、簡単な動作と難しい動作があるのも事実です。たとえば単純なスーパームーブとホームセルを一時的に使ったソーティングでは同じ動作数でも人間には後者の方が思いつきにくいです。その意味で動作数は難易度と正の相関があるのは間違いないのですが、動作数以外の要因もまた難易度に与える影響が多いと考えられます。
05-b. 試行数で難易度を測る
ソルバを使った求解では、ボード状態をノードとした木構造を巡回します。DFSであれBFSであれ、解にたどり着くまでに巡回したノード数というのが存在し、その数――試行数と呼びましょう――を難易度の尺度にすることはある意味妥当です。多くの場合、試行数は求解までの時間に比例します。
プレーヤーが解くときもまた、様々なボード状態を思い浮かべながらプレーするのである意味で試行数は「プレーヤーがどれだけ考えたか」を反映していると考えられます。一方試行数はアルゴリズムによってかなりばらつきがあるのも事実でそこは留意が必要かと思います。
05-c. 初期盤面で難易度を測る
いくつか問題を解けば初期盤面を見ただけで難しそうかどうかのアタリをつけることができます。例えば
- 4枚のエースがスタックの底の方に溜まっている
- 4枚のキングがスタックの上の方に溜まっている
- 色や順番が偏っている
などなどです。これらを何らかの形で定量化して難易度の尺度とする方針はあり得ます（例：各エースの深さつまりトップカードからの距離を総計した数）。
05-d. 解の性質で難易度を測る
同じ長さの解であっても、トリッキーな動作や特徴的な中間状態を経るなどという特徴的な尺度で測れることがあるかもしれません。例えば
- 特定のスートに関しては最後の方までホームセルに移動しない
- スタックが中途状態でかなり大きくなる
- エースが中々ホームに移動しない（ホームセルの枚数が非線形な増え方をする）
これらを何らかの形で定量化として難易度の尺度とする方針はあり得ます。
05-e. ルールに制限を加えて難易度を測る
FreeCellは驚異の99.99%という確率で解けるので、追加のルール制限を加えることである問題は解けるのに、ある問題は解けなくさせたりできます。つまり追加のルール制限を加えることで解けなくなるような問題を難しい問題としよう、という方針があり得ます。
追加のルール制限には以下のようなものが提案されており、確かになるほど問題群をいくつかのクラスタに分割できることが示されます。ルール制限を組み合わせることで（それが難易度の尺度として妥当かは置いておくとしても）さらに詳細に分割することも可能です:
- フリーセル数を3,2,1と少なくする
- 99%は3つ, 80%が2つ, 15%が1つのフリーセルで解ける
- Ephemeral: 全部もしくは一部のFreeCellが1度使ったら使えなくなる
- スタックの数を7,6,5...と少なくする
- KingOnly: 空のスタックにはキングしかおくことができない
- AutoPlayOnly: 手動でのホームセルへの移動を禁止
- KingsOnlyのみでもAutoPlayOnlyでも勝率をほんのごくわずかに下げるだけだけれど両方を制限に加えると
- FourKings: ４つのフリーセルに４枚のKingを配置し、残りは全部ホームセルに送った状態を経由して解決する
06. 次のステップ
本稿は事前調査でした。私としては「FreeCellの難易度の作成法」に関してもう少し色々研究・調査ができそうな気がしており、そのあたりを触ってみたいかな、と思いました。