极小极大理论，包括 R 代码的 alpha beta 剪枝

Question

需要帮助在 R 中开发 alpha beta 剪枝 minimax 算法。目前我已经实现了 minimax 算法，但它仅适用于 3x3 板。 4x4 板无法运行 --> 运行时间较长

我已经从 3x3 板上复制了代码，但我意识到我无法提供深度。所以我假设它适用于 4x4 板的所有示例。我需要更改什么才能在极小极大代码部分中实现 alpha beta 剪枝。由于我对这个领域相当陌生，因此我尝试修改现有代码以了解每个部分的作用。

# draw the board for tic tac toe
draw_board <- function(board) {
  xo <- c("X", " ", "O") # symbols
  par(mar = rep(0, 4))
  plot.new()
  plot.window(xlim = c(0, 40), ylim = c(0, 40))
  abline(h = c(10, 20, 30), col = "darkgrey", lwd = 4)
  abline(v = c(10, 20, 30), col = "darkgrey", lwd = 4)
  pieces <- xo[board + 2]
  text(rep(c(5, 15, 25, 35), 4), c(rep(35, 4), rep(25, 4), rep(15, 4), rep(5, 4)), pieces, cex = 6)
  # identify location of any three in a row
  square <- t(matrix(board, nrow = 4))
  hor <- abs(rowSums(square))
  if(any(hor == 4))
    hor <- (5 - which(hor == 4)) * 10 - 5
  else
    hor <- 0
  ver <- abs(colSums(square))
  if(any(ver == 4))
    ver <- which(ver == 4) * 10 - 5
  else
    ver <- 0
  diag1 <- sum(diag(square))
  diag2 <- sum(diag(t(apply(square, 2, rev))))
  # draw winning lines
  if(hor > 0) lines(c(0, 40), rep(hor, 2), lwd = 10, col = "red")
  if(ver > 0) lines(rep(ver, 2), c(0, 40), lwd = 10, col = "red")
  if(abs(diag1) == 4) lines(c(2, 38), c(38, 2), lwd = 10, col = "red")
  if(abs(diag2) == 4) lines(c(2, 38), c(2, 38), lwd = 10, col = "red")
}



# Human player enters a move
move_human <- function(game) {
  text(4, 0, "Click on screen to move", col = "grey", cex=.7)
  empty <- which(game == 0)
  move <- 0
  while (!move %in% empty) {
    coords <- locator(n = 1) # add lines
    coords$x <- floor(abs(coords$x) / 10) + 1
    coords$y <- floor(abs(coords$y) / 10) + 1
    move <- coords$x + 4 * (4 - coords$y) # 4 is the number of rows/columns --> needs to be a square
  }
  return (move)
}



# Evaluate winner function
eval_winner <- function(game_1, player) {
  game <- matrix(game_1, nrow = 3, byrow = T)
  hor <- rowSums(game)
  ver <- colSums(game)
  diag <- c(sum(diag(game)), sum(diag(apply(game, 1, rev))))
  if (-4 %in% c(hor, ver, diag))
    return(-10)
  if (4 %in% c(hor, ver, diag))
    return(10)
  else
    return(0)
}



# Minimax AI function
minimax <- function(game_1, player) {
  free <- which(game_1 == 0)
  if(length(free) == 1) {
    game_1[free] <- player
    return(list(move = free, U = eval_winner(game_1, player)))
  }
  poss.results <- rep(0, 16)
  for(i in free) {
    game <- game_1
    game[i] <- player
    poss.results[i] <- eval_winner(game, player)
  }
  mm <- ifelse(player == -1, "which.min", "which.max")
  if(any(poss.results == (player * 10))) {
    move <- do.call(mm, list(poss.results))
    return(list(move = move, U = poss.results[move]))
  }
  for(i in free) {
    game <- game_1
    game[i] <- player
    poss.results[i] <- minimax(game, -player)$U
  }
  random <- runif(16, 0, 0.1)
  poss.results[-free] <- 100 * -player
  poss.results <- poss.results + (player * random)
  move <- do.call(mm, list(poss.results))
  return(list(move = move, U = poss.results[move]))
}



# Main game engine human versus randomly choosing computer!
tic_tac_toe <- function(player1 = "human", player2 = "computer") {
  game <- rep(0, 16) # Empty board
  winner <- FALSE # Define winner
  player <- 1 # First player
  #players <- c(player1, player2)
  players <- c("human", "computer")
  draw_board(game)
  while (0 %in% game & winner == 0) { # Keep playing until win or full board
    if (players[(player + 3) %% 3] == "human") # Human player
      move <- move_human(game)
    else { # Computer player
      move <- minimax(game, player)
      move <- move$move
    }
    game[move] <- player # Change board
    draw_board(game)
    winner <- max(eval_winner(game, 1), abs(eval_winner(game, -1))) == 6 # Winner, winner, chicken dinner?
    player <- -player # Change player
  }
  if (winner == 1)
    print("Human has won")
  else if (winner == 2)
    print("Computer has won")
  else
    print("Play ended in a draw")
}

Answer 1

我推测您的问题可能是以下一些：

1. 你并没有限制你的深度。您正在尝试一路搜索直至游戏结束。 Minimax 应该只向前搜索足够多的转弯，以便您的硬件可以处理压力。
2. 你的评分功能太低效了。在极小极大搜索中，得分函数通常占据大部分计算时间。如果效率低下，你就要付出代价。
3. 同样，生成有效动作列表的代码可能效率低下。
4. 您可能正在考虑无效的移动，导致您的树的分支比应有的多。
5. 您对代码的概括不够。它不适用于 4x4，因为您已经硬编码了某些东西以依赖 3x3 板而没有意识到。
6. 你的 Alpha-Beta 修剪不正确。你什么也没修剪。

根据我实施 MiniMax + 变体的经验，这些往往是一些失败点。