ゲーム木

Game tree

ある状態から、取り得る次の手を打った状態を繰り返し繋ぐと樹状になる。これがゲーム木と呼ばれるもの。

(Wikipedia ではゲームの木とゲーム木を分けているが本質的には違いはないはず)

節が局面、

単純な組み合わせ問題ではなく、プレイヤーが手を順番に打つという条件が加わったもの。

プレイヤーがすべての情報が得られる完全情報のものと、得られない不完全情報のものとがある。

ゲームでは、勝利となる最適な手順を求めることが要求される。

すべての組み合わせを試すことができるのであれば、厳密解が得られるが、組み合わせ爆発が起こるために現実にはそこまで試すことができない。

このため、より有効と考えられる手のみを試すことになる。

明らかに不利となる手はそれ以上試す必要はない。

基本的には評価関数を作り、その評価点が高い物を選別するような動作となる。

常に最善手を取ることを前提に進めていくが、深く手を読まなければ逆転するかどうかは実はわからない。

局面は再利用可能な場合があるが、たいていの場合、同じ局面は現れず、再利用できない。

ミニマックス法

想定される最大の損失が最小となる手を選択する。

マクシミン法

想定される最小の利益が最大となる手を選択する。

α-β刈り

2手先(あるいはそれ以上)手を読んで、それ以上評価を続けてもよい評価が得られない枝を刈る。

手番によって利得が多い方と少ない方とが入れ替わる状況なので以下のαとβが現れる。

利得最大を求めたい節で、評価済みの枝のうち、利得最大の枝をαとし、新たに評価した枝がαを超えないことが判明した時点でカットする。α刈り。

利得最小を求めたい節で、評価済みの枝のうち、利得最小の枝をβとし、新たに評価した枝がβを超えることが判明した時点でカットする。β刈り。