アルゴリズムクイックリファレンス 第2版

216

■

7

章 

AI

における経路探索

しかし、このような大幅な削減を達成するには、取りうる手が並んだうちの先頭

に最良の手が来る必要がある。本書での三目並べの解は、そのように手を並べてい

ないので、おかしなことも起こる。例えば、盤面を

180

度回転した同じゲーム状態

（図7-12）では、

アルファベータ法

が、

960

個のゲーム状態を調べる（

88.3

％の削減）。

理由は、正しい手の順序が異なっているからである。このような理由から、探索ア

ルゴリズムが静的評価関数を用いて手の順序を変更することにより、ゲーム木のサ

イズが減ることがよくある。

図7-12　2 手後の三目並べの盤面を回転した例

7.6

 探索木

プレイヤーが

1

人だけのゲームは、ゲーム木と似ていて、初期状態（探索木の最

上節点）があり、一連の手により、目標状態に到達するまで盤面状態が変更される。

探索木（

search tree

）は、経路探索アルゴリズムが進行する過程で生成される中間

的な盤面状態の集合を表現する。計算構造が木なのは、アルゴリズムが盤面状態を

二度とは訪問しないことを保証しているからである。アルゴリズムは、目標への到

達を試みる際に盤面状態がどの順番で訪問されるかを決める。

8

パズルに対する探索木を検討する。

8

パズルは、

3

×

3

の盤面で、

1

から

8

までの

番号がついた正方形の駒と

1

か所の空白からなる。空白の隣（水平または垂直方向）

の駒は、空白の個所にずらすことができる。ゲームの目的は、適当に混ぜた駒によ

る初期状態から出発して、駒を動かして目標状態 ...