11 min read

Programming a simple minimax chess engine in R

Why write a chess engine in R?

Chess has always fascinated me. This is a game with simple rules that takes a lot of practice to master. No information is hidden from the players: the game state is clearly visible on the board, but strategies can be complex and subtle. This combination of simple rules and complex strategy becomes very relevant when attempting to write a chess engine. As we will see, a single line of R code is sufficient to implement a program that returns random legal moves. Creating a chess engine that actually plays well is another story.

Powerful chess engines have been developed that can currently defeat most human players. These are highly optimized pieces of software that:

  • search through the space of available moves very quickly to query positions many moves ahead
  • often use expert knowledge of the game or pre-computed results to evaluate positions accurately (examples include opening books, endgame databases and evaluation heuristics)
  • rely on vast amounts of computer resources for training and leverage advanced machine learning models such as neural networks for position evaluation

My goal is not to recreate any of these advanced efforts. This would be unrealistic and, as a casual chess player and avid R programmer, I am more interested to discover the opportunities that R offers around chess. For example, multiple packages are available to plot game positions or to generate lists of legal moves. I am also curious to explore some of the standard algorithms used in chess engines (starting with minimax) and see how simple R implementations of these approaches translate into enjoyable chess games.

In essence, my simple R chess engine should be fun and informative to write and also entertaining to play against as a casual player. It serves as an opportunity to explore an uncommon but fun application of R.

With this introduction let’s dive into the world of R chess!

Getting started: basic chess functions in R and first ‘chess engine’

Before we start implementing any game logic it is important to ensure that some basic chess functionality is available. This includes:

  • plotting the game board
  • listing all legal moves for a given position
  • recognizing when a game is won or drawn

The rchess package provides excellent functions that address these points.

Let’s start a new chess game and plot the board:

# Load the rchess package:
library(rchess)
# Create a new game:
chess_game <- Chess$new()
# Plot the current position:
plot(chess_game)

What moves are available for white? We can get a list of all legal moves via the moves function:

chess_game$moves()
##  [1] "a3"  "a4"  "b3"  "b4"  "c3"  "c4"  "d3"  "d4" 
##  [9] "e3"  "e4"  "f3"  "f4"  "g3"  "g4"  "h3"  "h4" 
## [17] "Na3" "Nc3" "Nf3" "Nh3"

We can pick a move and update the game accordingly:

chess_game$move("e4")
plot(chess_game)

The next player to move is black:

chess_game$turn()
## [1] "b"

and the available moves are:

chess_game$moves()
##  [1] "Nc6" "Na6" "Nh6" "Nf6" "a6"  "a5"  "b6"  "b5" 
##  [9] "c6"  "c5"  "d6"  "d5"  "e6"  "e5"  "f6"  "f5" 
## [17] "g6"  "g5"  "h6"  "h5"

Using the moves function we can already write a first chess engine that returns a random legal move:

# Random move generator for a given position:
get_random_move <- function(chess_game) {
  return(sample(chess_game$moves(), size = 1))
}

We can use this simple function to generate full chess games with both sides played by the computer:

# Set up a new game
chess_game <- Chess$new()

# Perform random legal moves until the game ends in mate or draw
while (!chess_game$game_over()) {
  chess_game$move(get_random_move(chess_game))
}

# Plot the final position
plot(chess_game)

This game ended in a win for white and took only a few seconds to run. We can also get a summary of the board in FEN notation by using the fen function:

chess_game$fen()
## [1] "7N/r1nb4/4kQ2/1p1pP1p1/p1p3p1/1P5P/P1P3P1/R2K1B1R b - - 0 43"

This FEN representation of the game state allows us to easily determine which pieces are still available for each player.

We can also confirm that the game is over, that checkmate occurred and that black is in check:

chess_game$game_over()
## [1] TRUE
chess_game$in_checkmate()
## [1] TRUE
chess_game$in_check()
## [1] TRUE

Improving our chess logic: heuristic position evaluation function

While playing a full random game is surprisingly simple with the help of the rchess package, we would like to start improving our engine in two ways:

  • Evaluation function: implement a simple heuristic to evaluate individual positions based on the pieces on the board and the safety of the king
  • Search function: implement an algorithm that allows our engine to search through positions multiple moves ahead

Let’s first work on the position evaluation function, which is usually performed from the perspective of white. More precisely, scores greater than zero indicate an advantage for white and scores less than zero point to an advantage for black. Our scores are based on three aspects of the position being evaluated:

  • Is this position a win for one of the players or a draw? If white won the score is 1000. If black won the score is -1000. In case of a draw the score in 0.
  • What is the material advantage for white? Each piece receives a value (9 points for queens, 5 points for rooks, 3 points for bishops and knights and 1 point for pawns) and the total piece value for black is subtracted from the total piece value for white.
  • If the white king is in check subtract one point from the position score. If the black king is in check add one point to the position score.

This is a fairly standard (although highly simplified) way to define an evaluation function: white will choose moves with high scores and black will prefer moves with low scores. Both players can thus use the same position evaluation function, which simplifies our program.

Let’s implement these simple heuristics in R:

# Position evaluation function
evaluate_position <- function(position) {
  # Test if black won
  if (position$in_checkmate() & (position$turn() == "w")) {
    return(-1000)
  }
  # Test if white won
  if (position$in_checkmate() & (position$turn() == "b")) {
    return(1000)
  }
  # Test if game ended in a draw
  if (position$game_over()) {
    return(0)
  }

  # Compute material advantage
  position_fen <- strsplit(strsplit(position$fen(), split = " ")[[1]][1], split = "")[[1]]
  white_score <- length(which(position_fen == "Q")) * 9 + length(which(position_fen == "R")) * 5 + length(which(position_fen == "B")) * 3 + length(which(position_fen == "N")) * 3 + length(which(position_fen == "P"))
  black_score <- length(which(position_fen == "q")) * 9 + length(which(position_fen == "r")) * 5 + length(which(position_fen == "b")) * 3 + length(which(position_fen == "n")) * 3 + length(which(position_fen == "p"))

  # Evaluate king safety
  check_score <- 0
  if (position$in_check() & (position$turn() == "w")) check_score <- -1
  if (position$in_check() & (position$turn() == "b")) check_score <- 1

  # Return final position score
  return(white_score - black_score + check_score)
}

Applying this function to our previous game we see that it correctly recognizes a win by white by returning a score of 1000:

evaluate_position(chess_game)
## [1] 1000

Testing our R minimax chess engine

Let’s first test the performance of our minimax-based chess engine by letting it play 10 games as white and 10 games as black against the random move generator we defined at the beginning of this article. If everything works as expected then our engine should win every time:

# Function that takes a side as input ("w" or "b") and plays 10 games
# The selected side will choose moves based on the minimax algorithm
# The opponent will use the random move generator
play_10_games <- function(minimax_player) {
  game_results <- vector(length = 10)
  for (i in 1:10) {
    chess_game <- Chess$new()
    while (!chess_game$game_over()) {
      if (chess_game$turn() == minimax_player) {
        # Selected player uses the minimax strategy
        chess_game$move(get_minimax_move(chess_game))
      } else {
        # Opponent uses the random move generator
        chess_game$move(get_random_move(chess_game))
      }
    }
    # Record the result of the current finished game
    # If mate: the losing player is recorded
    # If draw: record a 0
    if (chess_game$in_checkmate()) {
      game_results[i] <- chess_game$turn()
    } else {
      game_results[i] <- "0"
    }
  }

  # Print the outcome of the 10 games
  print(table(game_results))
}

White wins every game by playing the minimax strategy against the random move generator:

play_10_games("w")
## game_results
##  b 
## 10

Black also wins every game as the minimax player against random white moves:

play_10_games("b")
## game_results
##  w 
## 10

This simple experiment shows that our minimax chess engine is indeed more powerful than a random move generator, but this is a fairly low bar. I have also tested this program against multiple chess apps and it was able to win games against opponents playing at a casual difficulty level. Increasing the minimax depth leads to stronger play, but evaluating more than four moves in advance was not feasible on my computer due to long runtimes.

Conclusion and next steps

Overall this simple R chess engine is fun to play against for a beginner or casual player, and writing it was a great way to practice the minimax algorithm. Numerous improvements can still be made.

Some updates that I plan to discuss in future posts are:

  • Implement alpha-beta pruning to decrease the number of positions evaluated by minimax.
  • Use negamax to further simplify the code.
  • Leverage neural networks to define a better position evaluation function. The tensorflow and keras R packages make it possible to build very flexible neural networks within R.

Programming a simple chess engine is an exciting journey through the many machine learning capabilities offered by R. Looking forward to the next steps!

For a full collection of R programming tutorials and exercises visit my website at codeRtime.org and the codeRtime YouTube channel.