はじめに
🎄🎄🎄🎄🎄｡∠(ﾟ∇ﾟ)☆ﾒﾘｰｸﾘｽﾏｽ☆(･ｪ･)＞｡🎄🎄🎄🎄🎄！
フューチャー Advent Calendar 2022の25日目(The last of this year!)です。
今年で入社7年目になりますが、趣味は相変わらずパズルとそれらを解くためのアルゴリズムです。
今回もルービックキューブのような「コンビネーションパズル」あるいは「ツイスティパズル」とアルゴリズム話を続けたいと思います。
パズルをたくさん持っている方には、こんな悩みがありませんか。
難易度が簡単から中ぐらいのパズルには、説明書やインターネットからのアルゴリズム（いわゆる手順）を応用したら、そのパズルをマスタできたと言えますが、ただそれらのアルゴリズムはどうやって作られたかまではよく分からないでしょうね。
そして、超難しいレベルのパズルに遭遇したら、説明書ももちろんついてこないし、インターネット上に関連情報もなかなか見つからないし、長い間に苦戦してもわけが分からないので、そのまま放置してしまうケースが多いでしょうね。
私は自力で解けないパズルをたくさん持っています。その場合は、プログラミングでコンピューターの力を借りてブルートフォース的に解決していきます。それについて、去年のフューチャー Advent Calendar 2021のクリスマス番では以下の記事を書いたのでご参考ください。
ただし、複雑のパズルがほとんど状態爆発の問題であり、バカ正直にコンピューターに任せられないケースが多いです。一方、パズルのプレーヤーに取って、それが完全なネタバレになってしまい、解ける過程の面白さがまったくなくなるのが残念ですね。
しかも、コンピューターでパズルの今回の特定状態から初期状態に戻せたとしても、魚がくれましたが、漁の仕方を教えられませんので、次回からまた同じパズルでも、別の特定状態からスタートとしたら、依然として自力で解けないですね。
一般的なパズルの解け方
どんなに難しいパズルでも、少し経験がある人は最初の一部は直感的になんとかできるケースが多いです。例えば3x3x3のルービックキューブの最初の一面または第一層を揃うことはそれほど難しくないですね。
ただし、後半にいくほど難しくなり、特に最後のレーヤの数個のピースは、前に揃った部分を崩さないように配慮しつつ、揃えていくことが本格的に難しいですね。その時にいろんなアルゴリズムの出番ですね。（例：3x3x3 PLL T-Permのアルゴリズムの一つは「R U R' U' R' F R2 U' R' U' R U R' F'」）
上のような特定ケースのアルゴリズムもあれば、もっと一般的なアルゴリズムもあります。ぜひ以前のフューチャー2 Advent Calendar 2019のクリスマス番の記事も合わせてご確認いただければ嬉しいです。
さて、そもそも、マジックのようなアルゴリズムは、どうやって開発されたんでしょうか。我々一般人でも新しいパズルに対して手頃なアルゴリズムを発見することが可能でしょうか。今回もまたITエンジニアの力でやってみましょう。
アルゴリズムの発見エンジンの問題定義
前述のパズルの一番難しい最後の段階では、他のペースに影響しない前提で、特定の少ないペースのみ移動するアルゴリズムさえ把握すれば、人間でもそれらの組み合わせで最終にゴールにたどり着くことが可能になるので、今回のアルゴリズム発見のエンジンのターゲットは下記です。
- 汎用性を失わないように、アルゴリズム実行後に影響するペースの数は最小にする
- 人間に覚えやすいように手順数をなるべき少なくする
それを実現するために、方便上一番ベーシックな広さ優先探索を例として採用します。本当はメモリ節約や実行効率を配慮したら、反復深化深さ優先探索Iterative Deepening Depth First Search(IDDFS)のほうがもっと適切でしょう。
やり方は単純で、パズルの完成状態からスタートし、探索の途中になる状態が最初の状態から何個のピースが入れ替わたかを注目し、入れ替わるピースの少ないアルゴリズムを記録すればよいことです。
広さ優先、または、反復深化、どちらもで少ない手順のほうが先に到達することは探索の順番で保証できることなので、「手順数はなるべく少なくする」条件に満たしています。探索の結果に、実施のアルゴリズム（操作手順）とそれを実施後で変化したピースの数を記録し、ピースの変化の少ないほうは欲しいアルゴリズムのオプションになります。
具体例
今回は見た目シンプルのパズル「パンケーキパズル」を例にします。
全体は円柱になり、上下2つのレーヤに分かれて、パンケーキのように6分割の切れ目のところに180度ひっくり返すことができるパズルです。
簡単そうに見えますが、実際に触ってみれば、単純ではない所感です。
パズルの定義
操作の定義などは、以前汎用的にパズルのソルバーを実装してみたの記事での表現と同じように、群論の置換(permutation)の一次元配列の表現を使っています。例えば(1,2)(3,4,5)なら[1,2,1,3,4,5,3]の[]int (type Permutation)で表現しています。他の定義の方式もそのまま流用していますので、ここでは割愛します。
ナンバリングは緑の面が上（時計回り順番にwhite,purple,orange,yellow,grey,redの頭文字の小文字で色を表す）、青の面が下（反時計回り順番にGrey,Red,White,Purple,Orange,Yellow,の頭文字の大文字で色を表す）、地図展開のように上下の灰色と黄色が隣接するようにしています。
操作は上の層を時計回り、反時計回り、下の層の時計回り、反時計回りはそれぞれ(U, U', D, D')で表しています。
/は、右半分(場所番号1,3,5,7,9,11の部分)を180度反転する操作です。操作の方便上、パズル全体を(上から目線で)時計回りで回す記号はz(=U D')、それの逆はz'(=U' D)です。
下記のyaml定義をご参考ください。
# ⓪①
# ② ③
# ④⑤
# ⑥⑦
# ⑧ ⑨
# ⑩⑪
# ⚪🟣
# 🔴 🟠
# ⚫🟡
# ⬛🟨
# 🟥 🟧
# ⬜🟪
turnSet:
baseTurns:
- name: "U"
value: [0, 1, 3, 5, 4, 2, 0]
- name: "D"
value: [6, 7, 9, 11, 10, 8, 6]
- name: "/"
value: [1, 7, 1, 3, 9, 3, 5, 11, 5]
extenders:
- name: U'
function: REVERSE
params: [U]
- name: D'
function: REVERSE
params: [D]
- name: z
function: COMBINE
params: [U, D']
- name: z'
function: REVERSE
params: [z]
colorSetName: pancake_2layer
representationName: pancake_2layer
goalState:
colors: ["w", "p", "r", "o", "g", "y", "G", "Y", "R", "O", "W", "P"]
データ構造
広さ優先探索のOpenキューは、処理予備のpermutationのノードを格納する用です。
現在アクセスするpermutationのノードはキューの頭から引き出すし、処理終わったら1ステップの操作を加えてキューの末尾に加えます。
type openQueue []turn.Permutation
func (q *openQueue) enqueue(element turn.Permutation) {
*q = append(*q, element)
}
func (q *openQueue) len() int {
return len(*q)
}
func (q *openQueue) dequeue() turn.Permutation {
result := (*q)[0]
*q = (*q)[1:]
return result
}
アクセスしたノードを記録する用のcloseMapは以下です。(重複アクセス排除の機能もあり)
Permutationのstringをキーにして、初期状態から適用した一連の操作の操作名をバリューとして格納します。
type closeMap map[string][]string
func (s closeMap) put(e turn.Permutation, val []string) {
s[e.String()] = val
}
func (s closeMap) get(e turn.Permutation) []string {
return s[string(e.String())]
}
func (s closeMap) contains(e turn.Permutation) bool {
if _, ok := s[string(e.String())]; ok {
return true
}
return false
}
最後に、結果を格納する優先キューの定義です。heapの実装を流用したいのでheap.Interfaceを実現します。
要素のPermutationのSliceの長さを使って優先キューの優先度にしています。（置換要素少ないほうが優先）
最終的にこの優先キューの一番最初の部分を取れば良いので、メモリ節約のために、実行の途中で頭一定サイズの部分を保持しても問題ないです。
※2つの要素の交換(1,2)の1次元配列表現には[1,2,1]になるので、それの優先度が3、(1,2,3)は[1,2,3,1]になるので優先度が4、(1,2)(3,4,5)は[1,2,1,3,4,5,3]になるので優先度は7です。つまり、優先度が「置換のループの数＋置換された要素数」になり、それを最小のものを探しています。
type resultHeap []turn.Permutation
func (h resultHeap) Len() int {
return len(h)
}
func (h resultHeap) Less(i, j int) bool {
return len(h[i]) < len(h[j])
}
func (h resultHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *resultHeap) Push(i interface{}) {
*h = append(*h, i.(turn.Permutation))
}
func (h *resultHeap) Pop() interface{} {
old := *h
n := len(old)
item := old[n-1]
old[n-1] = nil // avoid memory leak
*h = old[0 : n-1]
return item
}
BFSのアルゴリズム
パズル状態の全空間を探索しきれない（メモリがパンクするから）ので、contextをパラメータとして、Timeoutの制御も可能にします。resultは先頭の100個を保持するようにします。
func doBFS(ctx context.Context, ts turn.TurnSet, goal state.State) (resultHeap, closeMap) {
open := openQueue{turn.Permutation{}} // put a "no-op" into open
close := closeMap{}
close.put(turn.Permutation{}, []string{})
result := resultHeap{}
heap.Init(&result)
for open.len() != 0 {
select {
case <-ctx.Done():
return result, close
default:
}
curPerm := open.dequeue()
turnNames := close.get(curPerm)
iter := ts.GetPermIterator(ts.GetAllTurnNames(), false)
for iter.HasNext() {
tn, perm := iter.GetNext()
nextPerm := curPerm.Concat(perm)
if close.contains(nextPerm) {
continue
}
newTurnNames := make([]string, len(turnNames))
copy(newTurnNames, turnNames)
close.put(nextPerm, append(newTurnNames, tn))
open.enqueue(nextPerm)
heap.Push(&result, nextPerm)
if result.Len() > 100 { //we just care about the shortest results
result = result[:100]
}
}
}
return result, close
}
定義yamlを読む部分などを省略しますが、mainからdoBFSを呼んで、ある程度探索(例えば30秒)したら、結果の優先度数値の小さいほうから出力します。
func loadPuzzle(puzzleMetaName string) (
*local.ColorSet,
*local.Representation,
turn.TurnSet,
state.State,
) {
pm, cs, r := local.LoadPuzzleMeta(puzzleMetaName)
ts, err := helper.NewTurnSet(pm.TurnSet)
local.Check(err)
goal, err := helper.NewState(pm.GoalState)
local.Check(err)
return cs, r, ts, goal
}
func main() {
cs, r, ts, goal := loadPuzzle("pancake_2layer")
// print initial state
stateStr, err := r.StateToString(goal, cs)
local.Check(err)
fmt.Printf("puzzle instance:\n%s\n%s\n", goal, stateStr)
fmt.Printf("puzzle rep:\n%s\n", r)
ctx, cancel := context.WithTimeout(context.Background(), time.Second*30)
defer cancel()
result, close := doBFS(ctx, ts, goal)
for result.Len() > 0 {
res := heap.Pop(&result)
fmt.Println(res, ":", close.get(res.(turn.Permutation)))
}
}
実施結果
go run cmd/alg-discover/main.go
puzzle instance:
wprogyGYROWP
⚪🟣
🔴 🟠
⚫🟡
⬛🟨
🟥 🟧
⬜🟪
puzzle rep:
⓪①
② ③
④⑤
⑥⑦
⑧ ⑨
⑩⑪
[0 6 7 0] : [U / U' / D / D' /]
[5 11 10 5] : [U / D' / D / U' /]
[4 11 5 4] : [D / U' / U / D' /]
[0 1 6 0] : [D / D' / U / U' /]
[0 6 1 0] : [/ U / U' / D / D']
[5 10 11 5] : [/ U / D' / D / U']
[6 7 9 11 10 8 6] : [D]
[0 2 4 5 3 1 0] : [U']
[0 2 4 11 9 7 0] : [/ U' /]
[1 6 8 10 5 3 1] : [/ D' /]
...
いい感じでした。特に一番目の[0,6,7,0]は覚えやすく、とても使えそうな3ピース入れ替えのアルゴリズムが発見できて嬉しかったです。
以下はその手順[U / U' / D / D' /]のデモ動画です。その結果、0->6->7->0の順番に入れ替わりました。
ちなみに、前回の汎用的パズルソルバーを使って、隣接の2つピースを交換するケースを解けた手順は「z / U' z' / U U / z / U' / U / z' / U / U」です。長すぎるから今回のBFSではまだそこまで至っていないですが、逆にそんなに長いアルゴリズムを覚える気もしないですね。今回の「人間に覚えやすいように手順数をなるべき少なくする」原則なので、それを勘弁して、一旦気にしないほうがいいでしょう。
まとめ
今回は、シンプルでも単純ではない「パンケーキパズル」の例を使って、一般的にパズルの少数ピースを入れ替わるアルゴリズムの発見エンジンをデモしました。使ったテクニックは普通のBFS探索でした。改良として、反復深化深さ優先探索を使ったら、よりよい性能と広い対応範囲はできるでしょう。そして、ある程度の良さの結果だけ求められるので、遺伝子アルゴリズムを適用し、並列処理に拡張することも考えられます。
私は今後行き詰まったパズルにあったら、このアルゴリズム発見エンジンからヒントをもらい、独自の美しいアルゴリズムを効率的に開発できるかもしれません。
余談ですが、私の理解では、難しい問題を解ける、いわゆる発見過程の本質は「探索」です。
パズルの解決も、数学定理の自動証明も、科学の新突破も、地球外生命の新発見も、使うテクニックが違うかもしれませんが、どちらも仮設や既知の論理の空間上で組み合わせてみて、何か生み出せるかを検証するプロセスです。
ぜひ自分にとって新しい世界へどんどん探索し続けていきましょう。
メリー・クリスマス！