当玩家可以连续移动两次时，Negamax搜索实现不起作用

我试图在Java中实现一个名为Nine Men's Morris的Negamax搜索。当玩家可以连续移动两次时，Negamax搜索实现不起作用

如果玩家连续有三件（这里称为磨坊），他在切换转向之前移除对手的棋子（'额外'移动）。

此外，还有一个组片相和移动片阶段，所有初始片已放置后。

我的实现看起来是这样的：

public int[] negamaxSet(int depth, int alpha, int beta, int color) { 
    if (depth == 0 || board.isGameOver()) { 
     return new int[] { color * evaluateBoard(color}; 
    } 

    int stonesSet = color == -1 ? board.blackStonesSet : board.whiteStonesSet; 
    // set piece phase 
    if (stonesSet < Game.initialPieces) { 
     List<Piece> moves = board.getEmpty(); 

     int bestValue = Integer.MIN_VALUE; 
     int bestMoveX = -1; 
     int bestMoveY = -1; 

     for (Piece piece : moves) { 
      Piece move = new Piece(color, piece.x, piece.y); 
      board.setPiece(move); 

      int value[] = null; 

      //Player made Mill, move again 
      if(board.checkMill(move)){ 
       value = negamaxRemove(depth - 1, alpha, beta, color);    
      } 
      //normal move, switch turn 
      else { 
       value = negamaxSet(depth - 1, -beta, -alpha, -color); 
       value[0] = -value[0]; 
      } 
      if (value[0] > bestValue) { 
       bestValue = value[0]; 
       bestMoveX = move.x; 
       bestMoveY = move.y; 
      } 
      if (value[0] > alpha) { 
       alpha = value[0]; 
      } 

      board.revertLastMove(); 

    //  if (alpha >= beta) 
    //   break; 
     } 
     return new int[] { bestValue, bestMoveX, bestMoveY }; 
    } else { 

     //move phase 

     List<Piece> moves = board.getPiecesByColor(color); 

     int bestValue = Integer.MIN_VALUE; 
     int bestMoveX = -1; 
     int bestMoveY = -1; 
     int bestMoveX2 = -1; 
     int bestMoveY2 = -1; 

     for (Piece piece : moves) { 

      List<Piece> adjPieces = board.getAdjacentEmtpy(piece); 
      for(Piece adjPiece : adjPieces){ 

       Piece newFrom = new Piece(color, piece.x, piece.y); 
       Piece newTo = new Piece(color, adjPiece.x, adjPiece.y); 

       board.movePiece(newFrom, newTo); 

       int[] value = null; 

       //Player made Mill, move again 

       if(board.checkMill(newTo, false)){ 
        value = negamaxRemove(depth - 1, alpha, beta, color); 

       } else { 
        value = negamaxSet(depth - 1, -beta, -alpha, -color); 
        value[0] = -value[0]; 
       } 

       if (value[0] > bestValue) { 
        bestValue = value[0]; 
        bestMoveX = newFrom.x; 
        bestMoveY = newFrom.y; 
        bestMoveX2 = newTo.x; 
        bestMoveY2 = newTo.y; 
       } 
       if (value[0] > alpha) { 
        alpha = value[0]; 
       } 

       board.revertLastMove(); 

    //   if (alpha >= beta) 
    //    break; 

      } 


     } 
     return new int[] { bestValue, bestMoveX, bestMoveY, bestMoveX2, bestMoveY2 };  
    } 
}

这可能是最好不改变基本Negamax算法和封装设置一块石头，在一个操作中移动的石头在算法本身在这两者之间没有区别，但从我的理解来看应该仍然是这样工作的。

函数negamaxRemove与negamaxSet基本相同，但没有检查磨机（不可能）并寻找要移除的部分。

使用与调用函数相同的参数调用negamaxRemove并且不切换符号（从而再次最大化）是否正确？不知何故，AI玩家不会阻止对手形成磨坊（如果可能的话，他自己组成一个磨坊）。

算法是否正确，我应该在代码的其他地方查找错误？还是我误解了Negamax应该如何工作？（我注意到alpha-beta修剪，所以错误地设置alpha或beta在这里不会有所作为）

我真的很感激一些指针！

来源

2016-08-18 Jamest

'evaluateBoard'如何工作？你不应该乘以颜色 - 分数应该总是相对于当前玩家。你应该把双重举动当作一个动作，这会为你节省很多不必要的麻烦。 –

你可能是对的。我把维基百科的伪代码作为参考，它被乘以颜色，但也许它只是为了得到相对于当前玩家的分数而已，并且没有更多......这已经在我的evaluateBoard方法中用参数完成了。我会在一分钟内测试它。你会如何处理设置/移动一块，然后（有条件地）删除一块石头而不用调用递归函数来选择最好的块去掉？ – Jamest

只需添加另一个循环。 I.e .:如果移动完成行，则也对对象片断进行迭代以选择要删除的对象。或者直接将它添加到可能的移动列表中：0，3，（4，删除1），（4，删除2）...它将允许您使用通用搜索算法。 –

I've implemented this game。将您的移动定义从“执行操作，授予另一个操作”更改为“执行多部分操作”。然后，您不必进行2次“移动”，而只需完成类似from: 3, to: 0, remove: 17,from: 3, to: 0, remove 19等的移动。对于不移除棋子的移动，只需将移除设置为-1即可。

来源

2016-08-19 14:36:16

当玩家可以连续移动两次时，Negamax搜索实现不起作用

回答

相关问题