Chess Engine

I started playing Chess as a small kid with my uncle. When I started playing online chess, even though I was very bad, I was fascinated by how the computer could show you your legal moves and even analyze your game. I had no idea how it worked but I wanted to learn. Since I also had a Data Structures and Algorithms class in my university, I decided to try to build a Chess game myself.

I was completely clueless. First, I had to figure out how to even represent the board and the pieces. After that, I had to come up with a way to only allow legal moves and enforce correct player turns. Then I had to add the ability to capture pieces and do special moves like castling (moving 2 pieces in one move) and en passant. I thought that was enough but my Algorithms professor told me to implement an AI player, so I had to figure that out too. And finally, I had to figure out how to make a nice Graphical User Interface with React to plug into the logic I had written in Python.

I learned a lot in the couple months of working on this project so I wanted to write about that journey here and show some of the cool things I had to make.

Representing the Board

Board State

I decided to represent the board state using a dictionary where the keys are coordinate tuples (x,y) and the values are the pieces at those coordinates e.g. “white_rook”.

When I first built this, I didn’t know much about data structures. Now I’ve learned that systems like Stockfish represent the board as a bit array which makes a lot of sense and is way more efficient. For this project, though, this representation is fine.

I could have also used a 2d array to represent the board without a change in performance, but I personally prefer working with a dictionary. It is also more convenient because I can represent moves using a tuple of tuples ((start),(end)) like ((0,0), (0, 6)). It also makes dealing with the coordinate base logic more intuitive:

• if (row, col) in self.board: do this

I downloaded svg of the pieces from Wikipedia and mapped them to their string representations :

• “white_rook” → “white-rook.svg”

Making a Move

With this representation, making a move is simply setting the starting position of the piece to null and setting the new position to the piece. e.g. Moving the white knight would look like this:

chess_board[(0,1)] = None
chess_board[(2,2)] = "white_knight"

Voila! We have a chess game! But, we can make any move we want at any time. We can capture our own pieces. We can move the king 6 squares. We can move the bishop like the knight. There is no validation. We have to add all that logic.

Building a Valid Chess Game

There are two main ways for validating moves:

1. validate each move as it is made based on rules.
2. create a list of all legal moves and check if the made move is in that list.

The second way is usually much more efficient and easier to manage.

Generating Legal Moves

To create a list of all legal moves, I basically iterated through each move a piece can make.

For example, the Rook can go up/down/left/right. So for each square in any of those directions until reaching the end of the board, we create a legal move:

If there is a piece on the board before reaching the end of the board, you have to stop before if it’s your own piece, or stop at the piece if it’s the opponent’s piece and mark it as a target for capture.

if piece.endswith('rook'):
            # Implement rook movement logic
            for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:  # Right, Left, Up, Down
                for step in range(1, 8):
                    new_row, new_col = row + step * direction[0], col + step * direction[1]
                    if 0 <= new_row < 8 and 0 <= new_col < 8:
                        target_piece = self.board.get((new_row, new_col))
                        if target_piece is None:
                            moves.add((pos, (new_row, new_col)))
                        elif not target_piece.startswith(piece.split('_')[0]):
                            moves.add((pos, (new_row, new_col)))
                            break
                        else:
                            break
                    else:
                        break

Now only legal moves are permitted and player turns are respected:

Captures

A capture is when the ending position in the move (start, end) is the same as an opponent’s piece’s position.

For that, we append the captured piece to the list of captured pieces of the current player and make the move.

if end in self.board:
            captured_piece = self.board[end]
            self.captured_pieces[self.current_player].insert(captured_piece)
        # Make the move
        self.board.pop(start)
        self.board[end] = moving_piece

Castling

Castling was interesting to handle. There are two ways you can castle: long and short. To be able to castle, you have to make sure neither the king or the rook has moved before, there are no pieces between the king and the rook, and none of the squares in the king’s castling path are under attack.

I used a hashset to track moved pieces to be able to check if the pieces have been moved or not. After each move, I append the starting position of the move to this set.

Here’s the logic of castling:

and represented in code:

# Kingside castling
                if (row, 7) not in self.moved_pieces:  # Rook hasn't moved
                    if all(self.board.get((row, col + i)) is None for i in [1, 2]):  # Path is clear
                        if not any(self.is_square_attacked((row, col + i), piece.split('_')[0]) for i in [0, 1, 2]):
                            moves.add((pos, (row, col + 2)))

                # Queenside castling
                if (row, 0) not in self.moved_pieces:  # Rook hasn't moved
                    if all(self.board.get((row, col - i)) is None for i in [1, 2, 3]):  # Path is clear
                        if not any(self.is_square_attacked((row, col - i), piece.split('_')[0]) for i in [0, 1, 2]):
                            moves.add((pos, (row, col - 2)))

En Passant

En passant was also another interesting move to handle. For that, you have to check if the previous move was a 2-move pawn move in an adjacent file to your pawn that ended on the same rank as you pawn. Then, the logic of applying the en passant is simple:

# En passant captures
            if self.last_move:
                last_start, last_end, last_piece = self.last_move
                if (last_piece.endswith('pawn') and
                    abs(last_start[0] - last_end[0]) == 2 and  # Last move was a two-square pawn advance
                    last_end[1] in [col - 1, col + 1] and  # Adjacent file
                    last_end[0] == row):  # Same rank
                    moves.add((pos, (row + direction, last_end[1])))

Checking Conditions

Of course, this would be an incomplete game of chess if it didn’t include checks, checkmates, and stalemates. I created them as helper functions since they often need to be checked for making moves or evaluating the strength of a position or move.

Check

def is_in_check(self, player: str) -> bool:
        # O(n^2) where n is the number of pieces, due to checking all opponent moves
        king_pos = self.find_king(player)
        opponent = 'black' if player == 'white' else 'white'
        #print(f"Checking if {player} king at {king_pos} is in check")
        #print("Current board state:")

        #print(f"Checking king at {king_pos}")
        opponent_moves = self.generate_player_moves(opponent, ignore_turn=True)
        for start, end in opponent_moves:
            if end == king_pos:
                piece = self.board[start]
                #print(f"Check detected by {piece} at {start}")
                return True

        #print("No check detected")
        return False

Checkmate

def is_checkmate(self) -> bool:
        # O(n^2) where n is the number of pieces, due to checking all legal moves
        if not self.is_in_check(self.current_player):
            return False

        for start, end in self.legal_moves:
            if self.try_move(start, end): # check if there is a legal move
                return False
        return True

Stalemate

def is_stalemate(self) -> bool:
        # O(n) where n is the number of legal moves
        if self.is_in_check(self.current_player):
            return False

        # Check if there are any legal moves available
        return len(self.legal_moves) == 0

Using React and Flask to make a Web UI

I wrote all the logic of the game in Python because it’s the language I was most comfortable at. But, I didn’t want to also make the UI in python. I had more experience making user interfaces with React and I wanted to ultimately make the game to be played on the web.

So, I exposed the python logic and state using Flask and used React with React Query to communicate the moves and positions via a REST API.

Flask Endpoint for making a move

@app.route('/move/player', methods=['POST'])
def make_player_move():
    """Handle player move request
    """
    data = request.json
    start = tuple(data['start'])
    end = tuple(data['end'])

    # Make player's move
    player_success = chess_board.make_move(start, end, data.get('promotion'))

    # Print sorted captured pieces from BST instead
    sorted_captured = {
        'white': chess_board.captured_pieces['white'].get_pieces_by_value(),
        'black': chess_board.captured_pieces['black'].get_pieces_by_value()
    }
    print(sorted_captured)

    return jsonify({
        'success': player_success,
        'message': 'Invalid move' if not player_success else None,
        'gameState': get_game_state()
    })

React Query for handling player moves

const playerMoveMutation = useMutation({
    mutationFn: (movePayload: MovePayload) => {
      return axios.post('/api/move/player', movePayload)
    },
    onSuccess: (response) => {
      if (response.data.success) {
        // Update game state with player's move
        queryClient.setQueryData(['gameState'], response.data.gameState)

        // Trigger CPU move
        cpuMoveMutation.mutate()
      } else {
        setLastMove(null)
        console.error('Player move was not valid:', response.data.message)
      }
    },
    onError: (error) => {
      console.error('Error making move:', error)
      setLastMove(null)
    }
  })