アルゴリズムクイックリファレンス 7.4 A*探索での GoodEvaluator

8パズルの評価関数の例として挙げられている GoodEvaluator。

P(n)+3*S(n)、P(n)は、各駒の「ホーム」からのマンハッタン距離の和。
S(n)は、升目を順に調べて付けた点数。正しい次の駒が後に続いていなかったら2、その他の駒は、0。ただし、中央に位置する駒には1を与える。

P(n)はいいとして、S(n)がどういう計算かわからなかった人はいるんじゃないだろうか。
原文は以下の通り(S(n)のところだけ)。

...
S(n) is a sequence score that checks the noncentral squares in turn, allotting 2 for every tile not followed by its proper successor and 0 for every other tile, except that a piece in the center scores 1.

ためしに訳すと、

S(n)は順序スコア。中央以外の升目を順に調べていって、正しい次の駒が次の位置にない駒についてそれぞれ2点を割り当て、それ以外は 0 点とする。ただし、中央の駒は 1 点とする。

正しい配置が

┌─┬─┬─┐
│1│2│3│
├─┼─┼─┤
│8│ │4│
├─┼─┼─┤
│7│6│5│
└─┴─┴─┘

であることを考えると、「正しい次の駒(proper successor)」というのは、1 に対しては 2、2 に対しては 3、…、8 に対しては 1 である ことがわかる。そして、「次の位置にある(follow)」というのは、時計回りに回った次の位置にあるということ。

例として挙げられている

┌─┬─┬─┐
│1│4│8│
├─┼─┼─┤
│7│3│ │
├─┼─┼─┤
│6│5│2│
└─┴─┴─┘

では、1 と 4 と 8 と 2 と 7 が「正しい次の駒」(それぞれ 2, 5, 1, 3, 8)が次の位置にないため、それぞれ 2点で合計10点。

5 と 6 は「正しい次の駒」(それぞれ 6, 7)が次の位置にある。

3 は中心なので 1点。

というわけで、この配置に対する S(n) は 11。


アルゴリズムを勉強するのには実際に手順に従ってやってみるのが一番だが、その手順がどういうことかわからないと苦労するので、誰かがハマった時用に書いておく。