評価値
ゲームの状態は評価をすることができます。強解決済みゲームの場合すべての状態で勝ち・引き分け・負けの三種類の評価値をつけることができます。その場合、一般に１・０・－１でプログラミング上で評価します。
将棋や麻雀のような強解決できない、もしくは隠れた情報がある場合、コマの損得や、リーチに近いなどの評価によって計算する必要があります。一般に評価値が高いほうが勝ちに近く、評価値が0に近いほど勝敗が拮抗している状態であると判断できます。
ミニマックス法
ゲームAIにおいて使われる基本的な探索アルゴリズムです。
次の状態に遷移するための手の中で最も評価値の高い手（最善の手）を選びます。
探索をより深く行うことで先読みをすることができます。探索の順番は次の図のように深さを優先して行います。
正しい評価値は先読みによって逆転されないことがわかる必要があります。相手の手番では最善を想定して最も評価値の低い手を選ぶ必要があります。
ミニマックス法のソースコードは以下のようになります。
//関数minimax(int depth)はdepth手先読みした場合の状態の評価値を返す。
int minimax(int depth){
if(depth==0)return value;//深さの制限のため先読みせず評価を返す
List<State>nextStates=generateNextStates();//次の手をすべて出す
if(nextStates.size()==0)return value;//次の手がないので先読みせず評価を返す
if(isFirst()){//状態が自分の番
int max = -∞;
for(nextState:nextStates){//次の全ての状態で判定
int score = nextState.minimax(depth-1);//次の状態（相手）の評価を得る
if(score>max)max=score;//評価値更新
}
return max;
}else{//状態が相手の番
int min = ∞;
for(nextState:nextStates){//次の全ての状態で判定
int score = nextState.minimax(depth-1);//次の状態（自分）の評価を得る
if(score<min)min=score;//評価値更新
}
return min;
}
}αβ法
探索の枝切りを行うアルゴリズムによってミニマックス法よりも少ない計算で最善手を探索します。
相手の手番で評価値がα以下、自分の手番で評価値がβ以上の場合に探索の枝切りを行います。
αβ法のソースコードは以下のようになります。
//関数alphabeta(int depth)はdepth手先読みした場合の状態の評価値を返す
int alphabeta(int depth,int alpha=-∞,int beta=∞){
if(depth==0)return value;//深さの制限のため先読みせず評価を返す
List<State>nextStates=generateNextStates();//次の手をすべて出す
if(nextStates.size()==0)return value;//次の手がないので先読みせず評価を返す
if(isFirst()){//状態が自分の番
for(nextState:nextStates){//次の全ての状態で判定
int score = nextState.alphabeta(depth-1,alpha,beta);//次の状態（相手）の評価を得る
if(score>alpha)alpha=score;//評価値更新
if(alpha>=beta)return alpha;//β値を上回ったので先読みせず評価を返す
}
return alpha;
}else{//状態が相手の番
for(nextState:nextStates){//次の全ての状態で判定
int score = nextState.alphabeta(depth-1,alpha,beta);//次の状態（自分）の評価を得る
if(score<beta)beta=score;//評価値更新
if(alpha>=beta)return beta;//α値を下回ったので先読みせず評価を返す
}
return beta;
}
}ネガマックス法
次の手番の状態の評価する際に符号を反転させることで手番に関係なく評価値が最も大きい手を最善とします。
ネガマックスを使ったαβ法のソースコードは以下のようになります。
//関数negaalpha(int depth)はdepth手先読みした場合の状態の評価値を返す
int alphabeta(int depth,int alpha=-∞,int beta=∞){
if(depth==0)return value;//深さの制限のため先読みせず評価を返す
List<State>nextStates=generateNextStates();//次の手をすべて出す
if(nextStates.size()==0)return value;//次の手がないので先読みせず評価を返す
for(nextState:nextStates){//次の全ての状態で判定
int score = -nextState.alphabeta(depth-1,-beta,-alpha);//次の状態（相手）の評価を得る
if(score>alpha)alpha=score;//評価値更新
if(alpha>=beta)return alpha;//β値を上回ったので先読みせず評価を返す
}
return alpha;
}最後に
三目並べのように総状態数が少ないゲームであれば先読みの深さをゲームが終わるまで深く読んだ場合でも計算しきることが可能です。しかし、多くのゲームでは先読みする状態が指数的に増えるため、浅い先読みしかできません。そのため、正しい評価値を出すプログラムやありそうな遷移のための手を探すプログラムが重要です。
参考
コメント