Exercise: Chess AI

ACTL3143 & ACTL5111 Deep Learning for Actuaries

Your task is to make a Chess-playing AI which uses the minimax algorithm.

Setup

!pip install chess

Requirement already satisfied: chess in /home/plaub/miniconda3/envs/ai/lib/python3.11/site-packages (1.11.2)

import chess
import math
import random
from IPython import display

Evaluating a board

STANDARD_PIECE_VALUES = {"P": 1, "N": 3, "B": 3,
                         "R": 5, "Q": 9, "K": 0}

def static_evaluation(board):
    if board.is_game_over():
        outcome = board.outcome()
        if outcome.winner == chess.WHITE:
            return 1_000_000
        elif outcome.winner == chess.BLACK:
            return -1_000_000
        else:
            return 0

    points_balance = 0
    for square in chess.SQUARES:
        piece = board.piece_at(square)
        if piece:
            piece_value = STANDARD_PIECE_VALUES[piece.symbol().upper()]
            if piece.symbol().isupper():
                points_balance += piece_value
            else:
                points_balance -= piece_value

    return points_balance

# Testing 'static_evaluation' on a board.
board = chess.Board("2r3k1/p3bp1p/2Bp1np1/4p3/1r6/B1R5/P1PP1P1P/R5K1 b - - 0 1")
board

# Expect this to be -1 (i.e. black up one pawn)
static_evaluation(board)

-1

Minimax algorithm

Pseudocode to evaluate the ‘minimax’ algorithm’s value of a chess board position.

function minimax (position, depth, maximizingPlayer)
  if depth == 0 or game over in position
    return static evaluation of position

  if maximizingPlayer
    maxEval = -infinity
    for each child of position
      eval = minimax(child, depth - 1, false)
      maxEval = max(maxEval, eval)
    return maxEval
  else
    minEval = infinity
    for each child of position
      eval = minimax(child, depth - 1, true)
      minEval = min(minEval, eval)
    return minEval

Source of the pseudocode: Around 3-4 minute mark of the following video:

# TODO: Create a 'minimax' function here, according to the pseudocode above.
def minimax(board, depth):
    pass

# TODO: Redefine the 'minimax' function to include the alpha-beta pruning extension.

Watch a game of AI versus AI

The following code will play a weaker AI (minimax with depth 2) against a stronger AI (minimax with depth 3).

def choose_move(board, depth=2):
  
    options = list(board.legal_moves)
    scores = []

    for move in options:
        board.push(move)
        scores.append(minimax(board, depth-1))
        board.pop()
        
    maximising_player = board.turn == chess.WHITE
  
    if maximising_player:
        best_score = max(scores)
    else:
        best_score = min(scores)
    
    best_options = []
    for move, score in zip(options, scores):
        if score == best_score:
            best_options.append(move)

    return random.choice(best_options)

def play_ai_vs_ai():
    random.seed(42)

    board = chess.Board()
    display.display(board)

    move_number = 1
    while not board.is_game_over():
        
        moves = list(board.legal_moves)
        if len(moves) == 0:
            print("No moves are possible!")
            break
        
        if board.turn == chess.WHITE:
            move = choose_move(board, depth=2)
        else:
            move = choose_move(board, depth=3)
            
        board.push(move)
        
        display.clear_output(wait=True)
        display.display(board)
                  
        print(f"Move #{move_number}: Score = {static_evaluation(board)}")
        move_number += 1

Uncomment and run the following after you’ve finished making your minimax function.

# play_ai_vs_ai()