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

7.1

 ゲーム木

■

195

A

I

有効な手を生成する

validMoves(IGameState)

は、与えられたゲーム状態で可能な手の集まり

を返す。

インタフェース

IGameMove

は、手がゲーム状態をどのように変更するかを定義す

る。このクラスは、問題ごとに決まるもので、探索アルゴリズムはそれらの具体的

実装を考慮する必要はない。

IGameScore

は、状態の点数計算のインタフェースを定

義する。

プログラミングする際のゲーム木での経路発見アルゴリズムの核心となるのは、

インタフェース

IEvaluation

の実装である。例7-1に示す。

例

7-1

 ゲーム木経路探索の共通インタフェース

/**

*

与えられたゲーム状態、プレイヤー、相手に対して、プレイヤーに最良の手を返す。

*

可能な手がないなら、

null

を返す。

*/

public interface IEvaluation {

IGameMove bestMove(IGameState

state, IPlayer player, IPlayer opponent);

}

現在のゲーム状態を表現する節点が与えられると、このアルゴリズムは、相手も

最善手を指すものと仮定して、プレイヤーの最善手を計算する。

7.1.1

 静的評価関数

探索には、工夫する方法がいくつかある（

Barr and Feigenbaum, 1981

）。

適用可能な手の順序と個数を選ぶ

ゲーム状態で可能な手を考慮するときに、成功しそうな手をまず評価す

べきである。さらに、成功しそうにない手は取り除く方がよい。 ...