Issue with MiniMax to Alpha

OK, my issue should sound pretty familiar to anyone who has played with board game programming, so here it is :

  • I've implemented a variation of the MiniMax algorithm (returning moves instead of min/max values).
  • I've also tried setting it up as an alpha-beta, although it ended up a complete failure.
  • So, here's my MiniMax code :

    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;
    }
    

    Any ideas one how the above thing could be adjusted so that it's an Alpha-Beta search?


    And here's my attempt at Alpha-Beta conversion (which fails miserably) :

    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;
    }
    

    HINTS (to avoid any misunderstanding) :

  • the this->eval() function returns a score from player A's perspective. Eg a +100 score means the position is in favour of player A, while a -100 score means the position is in favour of player B.

  • MINUS_INF and PLUS_INF have been defined as some arbitrarily small and big values, respectively.

  • This not anything like a homework or anything (if it was I'd most likely never have any interest to play with such stuff... lol)

  • Move is a simple class containing details about the move, as well as it's respective value (as assigned by the eval function.

  • HASHMAKE and UNHASHMAKE are just 2 move-(un)making and move-(un)hashing macros, that shouldn't make much difference.

  • MAXMOVE is defined like this : #define MAXMOVE(A,B) (((A)->value>=(B)->value)?(A):(B))

  • MINMOVE is defined like this : #define MINMOVE(A,B) (((A)->value<=(B)->value)?(A):(B))

  • Not sure if this is it, but I think in alphaMin

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

    should be

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

    and also a similar change in alphaMax .

    链接地址: http://www.djcxy.com/p/9632.html

    上一篇: 如何使用negamax算法

    下一篇: 问题与MiniMax到Alpha