このサイトでは、C言語でのオセロ(リバーシ)のプログラム開発方法を解りやすく説明しています。初級者、初心者でも作れるオセロ実装のコツが満載です。
αβ法はMINIMAX法を改良した素晴らしい探索アルゴリズムです。改良次第でより高速なプログラムを生み出すことも可能です。
最初に「オセロ(リバーシ)の作り方 ~Minimax 探索法~」を読むことをオススメします。
最善手を見つけるとき、相手が最善を打ったと仮定したときの、自分の最善手を検索する必要があります。これは最善手を見つけるときの基本であり、min-max法と言われます。
すなわち自分は評価関数が最大になる手を探し、相手は負に最大になる手を探すというわけです。
図1 minimax法 実行例
図2 minimax法 実行例
すべての手を検索すると、莫大な時間がかかってしまいます。そこで、考え出された方法が、a-b法と呼ばれるものがあります。
a-b法はゼロ和ゲームをプログラミングする上で非常に基本的かつ重要で、その適用範囲は広いです。
図で説明します。
図3 アルファベータ法 を適用する評価木
最小値を求めるAでは「5」なので、Dは「7」が見つかった時点で残りの「3」「5」の探索は行いません。
図4 アルファベータ法 実行例
また、最大値を求めるSでは「5」なので、Bは「4」が見つかった時点で「3」「2」「6」「4」「1」の探索は行いません。
なぜなら、Eで最大値が「4」の場合、「B=4」以下となります。このため「S=5」以上の値がBの枝には存在しないことが分かるためです。
まとめると、Aでは「最小値5より大きな値が見つかった時点」、Sでは「最大値5より小さな値が見つかった時点」で枝の探索を打ち切ります。
より具体的な動作が分かるようにシミュレーションを用意しました。
/******** αβ法による評価値の検出関数 *************/ int alphabeta(局面 node, 縦 row, 横 col, 手順 turn, 先読みの深さ depth, α, β) { copy(局面 node, コピー局面 node); /* コピーを行う */ コピー row = 縦 row; コピー col = 横 col; /* 盤面の状態を送る(パスや終局等の判定を行う) */ state = board_state(コピー局面 node, コピー row, コピー col, turn); if(state == END){ /* 終局の場合 */ return(終局評価関数(コピー局面 node, turn)); }else if(state == PASS){ /* パスの場合 */ turn = turn*(-1); }else if(depth <= 0){ /* 最下ノード時処理 */ return(局面の評価関数(コピー局面 node); } /* 現在の局面から1手進めた状態をa[1],a[2],a[3]とする */ expand_node(コピー局面 node, 配列 row, 配列 col, turn, 打てる個所の数 child_count); select = 0; /* 初期設定 */ /* α < β && i < child_countの時は繰り返す */ for(i = 0; (α < β) && (i < child_count); ++i){ inc_row = 配列 row[i]; inc_col = 配列 col[i]; val = alphabeta(コピー局面 node, inc_row, inc_col, turn*(-1), depth-1, α, β); if(turn == 先手 && val > α){ α = val; /* αカット */ select = i; }else if(turn == 後手 && val < β){ β = val; /* βカット */ select = i; } } 縦 row = 配列 row[select]; 横 col = 配列 col[select]; if(turn == 先手) return(α); else return(β); }
次に打った手を送る必要が無いのであれば、プログラムの下の方は簡略化され、綺麗な形にまとまります。
Negamax探索法は、基本的な考え方はαβ探索法と同じです。
違うのは、相手はこちらの利益を最小にするように打つのではなく、自分自身の利益を最大にするように打つというところです。これはMinimax探索法と同じになります。
Negamax探索法では、自分も相手も常に最大値を選ぶようになるので、プログラムが簡潔になるという利点があります。
int NegaMax(int a,int b){ /* 葉の場合、評価値を返す */ if(leaf()) return eval(); else{ int t,i; for(i=0;i<n && a<b;i++){ t=-child[i]->NegaMax(-b,-a); if(a<t) a=t; } return a; } }
αβ探索においては、その局面での良い手を先に探索することが重要となります。
良い手を先に検索すれば、α-βのカット量が増しより速く効率の良い探索となる為です。
このために、いくつかの手法が使用できます。
考慮した結果、初段程度のプログラムを作成するなら、「開放度」によるノードの並び替えが、最も効率的でした。
オセロに強くなりたい人は下記を読むことをお勧めします。
オセロ(将棋等)のプログラムを開発したい人・ゲームプログラマーになりたい人は下記は持っていて損はないでしょう。
Copyright ©2024 pl_kyo.(since 2001/11/18)