問題與極小給Alpha-Beta搜索轉換

Question

OK，我的問題應該聽起來很熟悉的人誰曾與棋盤遊戲編程出場，所以在這裏它是：

• 我已經實現了極小的變化算法（返回移動而不是最小/最大值）。
• 我也嘗試將它設置爲alpha-beta，儘管它最終導致完全失敗。

所以，這裏是我的代碼極小：

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

任何想法一個以上的事情是如何被調整，使得它是一個Alpha-Beta搜索？

---

而且這裏是我在α-β轉換嘗試（這失敗草草收場）：

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 （以避免任何誤解）：

• 的this->eval()函數從玩家A的角度返回一個分數。例如。一個100的得分手段的位置有利於玩家A的，而-100得分裝置的位置有利於玩家B的

• MINUS_INF和PLUS_INF已被分別定義爲一些任意小的和大的值，。

• 這並不像是一個功課或任何東西（如果它是我最有可能永遠不會有任何興趣與這樣的東西玩...笑）

• Move是一個包含細節的簡單類移動，以及它的相應的值（由eval功能分配。

• HASHMAKE和UNHASHMAKE僅有2 MOVE-（UN）制定和MOVE-（UN）散列宏，不應該太大的差別。

• MAXMOVE的定義是這樣的：#define MAXMOVE(A,B) (((A)->value>=(B)->value)?(A):(B))

• MINMOVE的定義是這樣的：#define MINMOVE(A,B) (((A)->value<=(B)->value)?(A):(B))

Answer 1

不知道這是它，但我認爲在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); 

也是類似的變化e在alphaMax。