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

7.2

 経路探索の概念

■

197

A

I

指数的に巨大な探索木を持つゲームでは、状態を可能な限りコンパクトに貯えな

ければならない。コネクト・フォー

＊

1

、オセロ、

15

パズルなどのように、状態に対

称性があるなら、回転または反転で同じになる状態を削除して、探索木を切り詰め

ることができる。チェス、チェッカー、オセロなどで、信じがたいほどに多数のゲー

ム状態を管理するためには、ビットボード（

bitboard

）と呼ばれる非常に効率が良い

がさらに複雑な構造が用いられる（

Pepicelli, 2005

）。

7.2.2

 可能な手の計算

最良の手を見つけるため、各盤面状態で、プレイヤーに許される可能な手の計算

ができなければならない。分岐数（

branching factor

）という用語を使って、ある盤

面状態で許される手の総数を示す。三目並べのようなゲームでは、分岐数が（ゲー

ム開始時の）最高

9

から、手で印がつけられるたびに、

1

つずつ減少する。

3

×

3

の

ルービックキューブは、（平均して）分岐数が

13.5

であり（

Korf, 1985

）、コネクト・

フォーは、分岐数が高々

7

である。チェッカーでは、プレイヤーが相手の駒を取

れるときには取らないといけないという規則のために、さらに複雑になる。多数の

チェッカーのデータベースを分析した結果によれば、駒を取れる位置での分岐数は

1.20

で、取れない位置での分岐数は

7.94

となる。シェーファーは、チェッカーの

平均分岐数を

6.14

と計算している（

Schaeffer, 2008

）。