我目前正在与c＃中的AI进行跳棋游戏。我试图使用minimax算法实现AI。虽然我的功能有效，但它选择的动作根本不符合逻辑。我用很多游戏和算法测试它只是选择不好的动作，当有更多更好的选择时。我不认为它是由于地平线问题，因为它所造成的移动会产生直接后果，例如在没有捕获任何对手的情况下丢失一块。 Som注意到代码：
Pieces数组，它代表了跳棋板。BlackPlayer是具有函数的同一类中的bool值。MyPiece(currentPiece)函数检查currentPiece与AI的颜色是否相同。gameState是否包含任何捕获移动。如果不检查正常动作。CloneGameState(gameState)函数来复制2d数组，以便代表游戏的原始数组永远不会改变。
public int Minimax (Pieces[,] gameState, int depth, bool is_maximizing, int alpha, int beta)
{
//Base Case - Return the board value
if (depth == 3)
return HeuristicEvaluation(gameState);
Move[] possibleMoves;
int bestValue;
bool currentSide;
if (is_maximizing)
{
bestValue = int.MinValue;
currentSide = BlackPlayer;
}
else
{
bestValue = int.MaxValue;
currentSide = !BlackPlayer;
}
// check forced moves
int moveCount = rules.GetCaptureMoves(gameState,out possibleMoves, currentSide);
// if no forced moves get normal moves
if (moveCount < 1)
moveCount = rules.GetNormalMoves(gameState,out possibleMoves, currentSide);
// traverse moves
for (int i = 0; i < moveCount; i++)
{
Pieces[,] newGameState = ApplyMove(CloneGameState(gameState), possibleMoves[i]);
int newStateValue = Minimax(newGameState, depth + 1, !is_maximizing,alpha, beta);
if (is_maximizing)
{
if (newStateValue > bestValue)
{
bestValue = newStateValue;
if (depth == 0)
bestMove = possibleMoves[i];
if (newStateValue > alpha)
alpha = newStateValue;
if (alpha >= beta)
return bestValue;
}
}
//Evaluation for min
else
{
if (newStateValue < bestValue)
{
bestValue = newStateValue;
if (newStateValue < beta)
beta = newStateValue;
if (alpha >= beta)
return bestValue;
}
}
}
return bestValue;
}
启发式功能：
public int HeuristicEvaluation(Pieces[,] gameState)
{
int stateValue = 0;
//use loops to check each piece
for (int j = 0; j < 8; j++)
{
int i = 0;
if (j % 2 == 1)
i++;
for (; i < 8; i += 2)
{
Pieces currentPiece = gameState[i, j];
if (currentPiece != Pieces.empty)
{
// if the current piece is mine
if (MyPiece(currentPiece))
{
// check if my piece is a king
if (currentPiece == Pieces.whiteKing || currentPiece == Pieces.blackKing)
stateValue += 80;
// my piece is a man
else
{
stateValue += 30;
// row values, closer to king zone higher the value
if (currentPiece == Pieces.blackMan)
{
// black goes in reverse direction
int y = 7-j;
stateValue += y;
}
else
stateValue += j;
}
// pieces on the edge are safe from capture
if (i == 0 ||i == 7 || j== 0 ||j ==7)
{
stateValue += 10;
}
}
// point reduction for enemy pieces
else
{
if (currentPiece == Pieces.whiteKing || currentPiece == Pieces.blackKing)
stateValue -= 80;
else
{
stateValue -= 20;
// row values, closer to king zone higher the value
if (currentPiece == Pieces.blackMan )
{
// black goes in reverse direction
int y = 7-j;
stateValue -= y;
}
else
stateValue -= j;
}
// pieces on the edge cant be captured
if (i == 0 || i == 7 || j == 0 || j == 7)
{
stateValue -= 10;
}
}
}
}
}
return stateValue;
}
首先，我想指出你的函数Maximizer和Minimizer可以组合在一个函数Minimax(Pieces, gameState, depth, bool is_maximizing)中，因为除了几行代码之外它们的逻辑几乎相同。因此，不是调用Maximizer，而是将is_maximizing设置为true来调用Minimax。而不是调用Minimizer，只需在is_maximizing设置为false的情况下调用Minimax。这将有助于避免重复，并使您的代码更具可读性。
第一点导致我们在算法中出错。在Minimize函数中，您递归调用自身，而应调用Maximize函数。
另一点是你处理给定位置的所有有效移动的方式。您不必将捕获移动与非捕获移动分开处理。原因再一次是处理两种类型的移动的逻辑是相同的。我建议创建两个函数 - GenerateValidMoves（）和SortValidMoves（）。 GenerateValidMoves（）函数将生成给定位置中所有有效移动的列表。生成移动列表后，调用SortValidMoves（）对列表进行排序，以便捕获移动位于列表的开头，然后是非捕获移动。
这是minimax的简化伪代码：
Minimax(color, board, depth, is_max):
if ((depth == DEPTH_CUTOFF) or IsTerminalNode()):
return EvalBoard()
best_score = is_max ? -infinity : infinity
valid_moves = GenerateValidMoves(board, color)
for curr_move in valid_moves:
clone_board = board.clone()
clone_board.make_move(curr_move)
int curr_score = Minimax(opposite_color, clone_board, depth + 1, !is_max)
if (is_max) {
if (curr_score > best_score) {
best_score = curr_score
best_move = curr_move
}
} else {
if (curr_score < best_score) {
best_score = curr_score
best_move = curr_move
}
}
return best_score