在 R 中开发 alpha beta 修剪 minimax 算法时需要帮助。目前我已经实现了 minimax 算法，但它仅适用于 3x3 板。4x4 板不运行 --> 长时间运行
我已经从 3x3 板上复制了代码，但我意识到我无法提供深度。所以我假设它适用于 4x4 板的所有示例。我需要更改什么才能在 minimax 代码部分中实现 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")
}