オセロでNegaAlpha法

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
lbfuvab

オセロでNegaAlpha法

#1

投稿記事 by lbfuvab » 16年前

オセロを組んでいて今までNegaMax法を使っていたのですが、
アルファベータ法の方が効率的ということで、[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);
}

box

Re:オセロでNegaAlpha法

#2

投稿記事 by box » 16年前

>int NegaAlpha(int depth=0,int a=-10000,int b=10000); //問題の関数

この関数の引数の意味を説明してくださると、
回答しようとしている方々の助けとなるかもしれません。

lbfuvab

Re:オセロでNegaAlpha法

#3

投稿記事 by lbfuvab » 16年前

あ、すいません。
depthは深度です。
ですから最初呼び出す時0です。
aはアルファ値です。
ですから最初は十分に小さくないといけないので-10000にしています。(どんなに悪い状況でも-10000を割る事はないので)
bはベータ値です。
ですから最初は十分に大きくないといけないので10000にしています。

デフォルト引数を付けたのはこっちのほうが呼び出す時に
NegaAlpha(0,-10000,10000);とするより
NegaAlpha();の方がすっきりすると思ったからです。

lbfuvab

Re:オセロでNegaAlpha法

#4

投稿記事 by lbfuvab » 16年前

自己解決しました。
ありがとうございました。

閉鎖

“C言語何でも質問掲示板” へ戻る