オセロでNegaAlpha法
Posted: 2009年2月22日(日) 21:52
オセロを組んでいて今までNegaMax法を使っていたのですが、
アルファベータ法の方が効率的ということで、[url]"" target="_blank"[/url]を参考にアルファベータ法+ネガマックス法を組んでみたのですが
うまく行きません。
というのも、コンパイルはうまく行くのですが、NegaMax法の時と全然違う手を打ってきます。(深さ及び評価関数は同じ)
悪い点を教えてください。
環境はWinXP+VC++2008EEです。
アルファベータ法の方が効率的ということで、[url]"" target="_blank"[/url]を参考にアルファベータ法+ネガマックス法を組んでみたのですが
うまく行きません。
というのも、コンパイルはうまく行くのですが、NegaMax法の時と全然違う手を打ってきます。(深さ及び評価関数は同じ)
悪い点を教えてください。
環境はWinXP+VC++2008EEです。
#define SEARCH_DEPTH 6
bool CanPutAnyWhere(void); //どこかに打てるのか
bool CanPut(x,y); //そこに打てるのか
int Put(int x,int y); //駒を打つ
int UndoPut(int x,y); //打った駒を戻す
bool IsEnd(int *result); //終わっていたらtrueを返す。resultは勝ち負けの格納用
int Eval(void); //その時の評価値を返す
void PutCPU(void); //NegaAlphaの使用例
int NegaAlpha(int depth=0,int a=-10000,int b=10000); //問題の関数
typedef struct{
int x,y;
} Place_t; //場所用の構造体
int Board[8][8]; //オセロの盤
Place_t Next; //次の手の格納用
int NegaAlpha(int depth,int a,int b){
int x,y,val,result;
if(depth==0){ //最初に呼び出された時
for(x=0;x<8;x++){
for(y=0;y<8;y++){
if(CanPut(x,y)){
Put(x,y);
val =-NegaAlpha(depth+1,-b,-a);
UndoPut();
if(val>=a){
Next.x=x;
Next.y=y;
a=val;
}
if(a>=b){
Next.x=x;
Next.y=y;
return a;
}
}
}
}
return a;
}
else if(depth!=SEARCH_DEPTH){
if(IsEnd(&result)==false){
if(CanPutAnyWhere()){
for(x=0;x<8;x++){
for(y=0;y<8;y++){
if(CanPut(x,y)){
Put(x,y);
val =-NegaAlpha(depth+1,-b,-a);
UndoPut();
if(val>=a)
a=val;
if(a>=b)
return a;
}
}
}
return a;
}
else{
Pass();
val = -NegaAlpha(depth+1,-b,-a);
UndoPut();
return (a>val)?a:val;
}
}
else{ //既に終了
if(result==turn)
return 1000; //勝ってたら最高の評価
else if(result==DRAW)
return 0; //引き分けは・・・どうなんだろう?
else
return -1000; //負けは出来れば避けたい
}
}
else //葉の時は
return Eval();
}
void PutCPU(void){
NegaAlpha();
Put(Next.x,Next.y);
}