Minimax theory including alpha beta pruning for R code

Question

Need help with developing an alpha beta pruning minimax algorithm in R. Currently I have implemented the minimax algorithm but it is only usable for 3x3 board. 4x4 boards do not run --> too long run time

I have copied the code from the 3x3 board but I realize I cannot provide a depth. So I assume it runs for all examples of a 4x4 board. What do I need to change to implement the alpha beta pruning in the minimax code section. Since I am fairly new to this field, I am trying to modify existing code to understand what each part is doing.

# 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

I theorize your issue might be some of the following:

1. You are not limiting your depth. You are trying to search all the way to the endgame. Minimax should only search enough turns ahead that your hardware can handle the strain.
2. Your scoring function is too inefficient. The score function is often the majority of your computation time in a Minimax search. If it is inefficient, you will pay for it.
3. Similarly, your code that generates a list of valid moves might be inefficient.
4. You might be considering invalid moves, causing your tree to branch way more than it should.
5. You are not generalizing your code enough. It doesn't work for 4x4 because you have hardcoded something to rely on a 3x3 board without realizing it.
6. Your Alpha-Beta pruning is incorrect. You are pruning nothing.

From my experience implementing MiniMax + variants, these tend to be some of the failure points.