0

OK、私の問題はボードゲームプログラミングで遊んだことがある人なら誰でもよく知っているはずなので、ここにあります：

  • MiniMaxアルゴリズムのバリエーションを実装しました（最小/最大値の代わりに移動を返します）。
  • 完全に失敗しましたが、アルファベータとして設定しようとしました。

だから、これが私のMiniMaxコードです：

Move* Board::miniMax(int depth)
{
    return this->maxMove(1, depth);
}

Move* Board::maxMove(int ply, int depth)
{
    vector<Move*> moves = this->possibleMoves();
    int movesSize = moves.size();

    Move* maxMove = new Move(MINUS_INF);

    for (int i=0; i<movesSize; i++)
    {
        Move* move = moves[i];
        HASHMAKE(move,this);

        move->value = (ply<depth) ? (this->minMove(ply+1, depth))->value 
                                  : this->eval();

        maxMove = MAXMOVE(maxMove,move);

        UNHASHMAKE(move,this);
    }

    return maxMove;
}

Move* Board::minMove(int ply, int depth)
{
    vector<Move*> moves = this->possibleMoves();
    int movesSize = moves.size();

    Move* minMove = new Move(PLUS_INF);

    for (int i=0; i<movesSize; i++)
    {
        Move* move = moves[i];
        HASHMAKE(move,this);

        move->value = (ply<depth) ? (this->maxMove(ply+1, depth))->value 
                                  : this->eval();

        minMove = MINMOVE(minMove,move);

        UNHASHMAKE(move,this);
    }

    return minMove;
}

アルファベータ検索になるように上記のことをどのように調整できるかについてのアイデアはありますか？

そして、これがアルファ-ベータ変換の私の試みです（これは惨めに失敗します）：

Move* Board::alphaBeta(int depth)
{
    return this->alphaMax(1,depth,MINUS_INF,PLUS_INF);
}

Move* Board::alphaMax(int ply, int depth, int a, int b)
{
    vector<Move*> moves = this->possibleMoves();
    int movesSize = moves.size();

    Move* maxMove = new Move(MINUS_INF);

    for (int i=0; i<movesSize; i++)
    {
        Move* move = moves[i];
        HASHMAKE(move,this);

        move->value = (ply<depth) ? (this->alphaMin(ply+1, depth,a,b))->value 
                                  : this->eval();

        maxMove = MAXMOVE(maxMove,move);
        if (maxMove->value>=b) return maxMove;
        a = MAXVAL(a,maxMove->value);

        UNHASHMAKE(move,this);
    }

    return maxMove;
}

Move* Board::alphaMin(int ply, int depth, int a, int b)
{
    vector<Move*> moves = this->possibleMoves();
    int movesSize = moves.size();

    Move* minMove = new Move(PLUS_INF);

    for (int i=0; i<movesSize; i++)
    {
        Move* move = moves[i];
        HASHMAKE(move,this);

        move->value = (ply<depth) ? (this->alphaMax(ply+1, depth,a,b))->value 
                                  : this->eval();

        minMove = MINMOVE(minMove,move);
        if (minMove->value<=a) return minMove;
        b = MINVAL(b,minMove->value);

        UNHASHMAKE(move,this);
    }

    return minMove;
}

ヒント（誤解を避けるため）：

  • このthis->eval()関数は、プレーヤーAの観点からスコアを返します。たとえば、+ 100スコアは、ポジションがプレーヤーAに有利であることを意味し、-100スコアは、ポジションがプレーヤーBに有利であることを意味します。

  • MINUS_INFとPLUS_INFは、それぞれ任意の小さい値と大きい値として定義されています。

  • これは宿題のようなものではありません（もしそれが私がそのようなもので遊ぶことに興味を持っていなかったとしたら...笑）

  • Moveは、移動に関する詳細と、それぞれの値（関数によって割り当てられた値）を含む単純なクラスevalです。

  • HASHMAKE移動- UNHASHMAKE（非）作成と移動-（非）ハッシュの2つのマクロであり、大きな違いはありません。

  • MAXMOVEこのように定義されます：#define MAXMOVE(A,B) (((A)->value>=(B)->value)?(A):(B))

  • MINMOVEこのように定義されます：#define MINMOVE(A,B) (((A)->value<=(B)->value)?(A):(B))
4

1 に答える 1

2

いつも夢みてかどうかはわかりませんがalphaMin

if (minMove->value<=a) return minMove;
b = MINVAL(b,minMove->value);
UNHASHMAKE(move,this);

する必要があります

UNHASHMAKE(move,this);
if (minMove->value<=a) return minMove;
b = MINVAL(b,minMove->value);

また、同様の変更がありalphaMaxます。

于 2013-01-04T01:19:04.840 に答える