Knightr0's Gambit
A UCF AI/UCF IEEE Collaboration
Home Github Hardware Software Play Members
Software



Mock System Diagram
Hardware Interface Software
Our plan is to implement a software system using two processing units, a Raspberry Pi and an ESP32 microcontroller. The Raspberry Pi will run a game loop to keep track of game state (whose turn it is, past moves, etc.), compute moves using our custom AI, and process images taken of the board to compute board state after the player moves a piece. The AI move is then converted to a standardized message format (see OpCode) and sent to the ESP32 microcontroller using UART serial communication. The microcontroller then actuates the physical board mechanism (motors and electromagnet) and sends back status messages indicating current state of the board/microcontroller (see ArduinoStatus). UART serial communication is used as it allows us to easily send data in both directions.
Piece recentering capability
The centerPiece() function is used after a player makes a move to ensure that the player's chess piece placement is aligned properly and does not interfere with the board's piece movement. The function is composed of concentric circle approximations and shifts between the circles, with calls to makeCircle() and moveToNextCircle() respectively.

The makeCircle() function receives two parameters, int circle and int firstQuarter. The function moves the electromagnet along the given circle size, starting from the given quarter (where 0=top, 1=left, 2=bottom, 3=right). The movements are restricted to slopes that can be generated through combinations of the EasyDriver MS1 and MS2. Each direction can be set to 1/8, 1/4, 1/2, or full step size. This allows for slope settings of 0, 1/8, 1/4, 1/2, 1, 2, 4, 8, and vertical. Moving the x and y motors in paired steps prevents the magnet from making a stair-step style movement, and increases movement speed by reducing the amount of logic required to make the movements. During the movement, a previously computed number of moves is made at each slope. Several of the slopes have two different scales in order to further accelerate the movement. A slope of 1, for example , moves as far as possible with full steps in the x and y directions, and switches to ⅛ scale steps in both directions for the last 1-7 movements.




The number of steps at each slope is computed by the calculatePulsesPerSlope() function, which is only called once in the setup() initialization function. It calculates the instantaneous slope of a circle at the current point, approximates it to one of the available slopes, then increments the x and y position for that slope. It repeats this process until the first quarter of the circle is complete. The remaining three quarters of the circle use the same pulses per slope counts with different x and y directions and/or reversed order.

Figure 1: Example of circular motion composed of multiple tangent line approximations


An example of the slope calculation process is shown (Figure 2). The initial point is at the topmost part of the ideal circle. Movement begins with horizontal steps to the left. After each step, the slope is recalculated using a tangent line to the concentric circle that passes through the point. The slope of the tangent line is then approximated to one of the nine slopes that can be generated by the EasyDrivers, and is used for the next step. Note that the difference between the path and goal circle is greatly exaggerated for visualization purposes.



Figure 2: Visualization of tangent line computation to obtain instantaneous slope


The getInstantaneousSlope() function calculates the instantaneous slope, dy/dx, of a circle at the provided point. The calculation is derived from the parametric equations for a circle.The current x and y coordinates are calculated using the number of steps remaining in each direction and the radius of the circle.





The moveToNextCircle() function moves the electromagnet from the current circle to a smaller concentric circle in two motions (see Figure 3). The first motion has a slope of ±1 and aligns the magnet with the side of the next circle. The second motion is a vertical or horizontal movement to reach the starting point for the next circle. This is much easier to calculate than a direct movement, given our slope constraints. Additionally, it allows the magnet to cover more area than a direct movement. The final call to moveToNextCircle() implicitly resets the electromagnet to the center of the square.

Figure 3: Path from outer to inner concentric circle composed of diagonal + straight line
Game State Managment
The game state management code is comprised of a few fundamental components:
Game
After setting up the connection to the board and doing startup tasks (such as determining who moves first), the general structure of the game loop is as follows
  1. Get the board status from the arduino (see ArduinoStatus)
  2. If the status is EXECUTING_MOVE or MESSAGE_IN_PROGRESS, continue
  3. If the status is ERROR, handle the error
  4. If it is the human's turn
    1. Wait for the END_TURN_BUTTON_PRESSED signal from the Arduino
  5. If it is the AI's turn
    1. Get move from the neural network
    2. If move is valid, send it to the board, else, get the next best move
  6. While not checkmate/stalemate, repeat
We plan to set up an architecture for a queue of moves: Each loop, we try to dispatch one move from the queue. If the queue is non-empty, we dispatch moves until it is. In order to pop the front of the queue, the Arduino needs to send back the move count of the previously dispatched move and idle status. Only then do we pop that move from the queue and start sending the next move to be processed. Once the queue is empty, we proceed to the rest of the loop.
BoardInterface


Diagram showing indexing scheme, graveyard, capture squares, and promotion area
Board

The Board class is the interface point between the Arduino and the Raspberry Pi. Board is used to send and receive messages through the Board interface (see ArduinoStatus and OpCode), validate moves, and handle captures/promotions.
Engine

We construct a simple wrapper around python-chess and add some helper functions to keep track of board state.

We formulate the Graveyard to avoid the need to use computer vision to keep track of captures and promotions. By having a capture square, we can determine from the state of the board which piece was captured, and automatically move it to a specified position in the graveyard. When the user wants to promote their pawn to a new piece, they select the replacement piece from the designated promotion area. When the board state determines a promotion happens, the promotion area is backfilled from the other pieces in the graveyard (as long as there are spare pieces available).
Player
We eventually plan to allow users to play the board through
  1. Physical interface: User moves physical pieces on the chessboard
  2. Command line interface (CLI): User specifies pieces to move in grid algebraic notation (GAN) format (e.g. e2e4)
  3. Web graphical user interface (GUI): User specifies pieces to move by dragging and dropping (similar to Lichess or chess.com)
  4. Voice interface: User specifies pieces to move using voice commands (see Speech Recognition)
OpCode
This is an enum of operation codes used to provide information about the type of move the Arduino should make.
  1. MOVE_PIECE_IN_STRAIGHT_LINE: A code to indicate that the Arduino should use a straight-line path (diagonals allowed)
  2. MOVE_PIECE_ALONG_SQUARE_EDGES: A code to indicate that the Arduino should move the piece along square edges instead of through the center of squares. This is used for knights if adjacent pieces are in the way, and for moving pieces to and from the Graveyard, and for castling.
  3. ALIGN_PIECE_ON_SQUARE: A code to indicate that the Arduino should use the electromagnet to center piece on square (used after human moves).
Note that queenside and kingside castling are composed of two moves; one move of type 1 (king moving in straight line) and one move of type 2 (rook moving around king). Messages sent from Pi to Arduino have the following format:
"~<OpCode><StartPosition><EndPosition><MoveCount>"
~ is a delimiter; OpCode is as described above; StartPosition and EndPosition are 2-character strings of the form <A-L><A-L> to index the 12x12 array (they are converted on the Arduino to two integers in the range of [0, 11]; MoveCount is an integer that serves as a handshake between the Arduino and Pi. Move number <MoveCount> is sent until the Arduino responds with the same <MoveCount> and an IDLE status (see ArduinoStatus), after which move number <MoveCount + 1> is sent if it is available. Note that we send `MoveCount % 255` since a byte only allows sending 256 0-indexed values. ExtraByte is used whenever there is an error and is used to pass along additional information about the type of error.
ArduinoStatus
This is an enum of status codes used to provide information about the current operational state of the Arduino.
  1. IDLE: A status to indicate that the Arduino is waiting for the next move.
  2. MESSAGE_IN_PROGRESS: A status to indicate that the Arduino is currently processing a message from the Pi.
  3. EXECUTING_MOVE: A status to indicate that the Arduino is currently executing a move.
  4. END_TURN_BUTTON_PRESSED: A status to indicate that the human player pressed the end turn button. Pi should then take a picture and compute the difference in board state.
  5. ERROR: A status to indicate that an error occurred.
Messages sent from Arduino to Pi have the following format:
"~<ArduinoStatus><MoveCount><ExtraByte>"
~ is a delimiter; ArduinoStatus is as described above; MoveCount is as described in OpCode. From the Arduino side, MoveCount serves as a handshake between the Arduino and Pi to confirm that move number <MoveCount> is either being executed (EXECUTING_MOVE), was the last move executed (IDLE), or is the move currently being sent (MESSAGE_IN_PROGRESS). When the Pi receives an IDLE status from the Arduino along with move number <MoveCount>, the Pi sends the move corresponding to <MoveCount + 1> if it is available. ExtraByte is used whenever there is an error and is used to pass along additional information about the type of error.
Chess AI
For the AI and computer vision side of the project, our plan is to utilize a variety of techniques from AI and combine them into the most efficient algorithm, parallel to the algorithm implemented by AlphaZero.
The chess AI will be trained using the Actor Critic algorithm for reinforcement learning, parameterized by a neural network (a network of equations that takes in input(s) and returns output(s)). We may initialize the network parameterization using supervised learning over a training set of existing chess games played by humans to allow learning to get off to a faster and more efficient start. We will decide this by comparing its efficiency to an AI that learns exclusively through self play.
To test the efficiency and utility of different machine learning approaches to chess AI, we will compare the convergence rate and style of play of our AI to other state-of-the-art methods. We will then find which approach is the most suited for learning in as little time as possible and compare which approaches lead to contrasting playing styles. This will include testing against other chess AIs such as Stockfish, Maia, and Leela Chess Zero, and also human players. When testing against people, we plan to ask them about their experience playing against our AI and to rate how it plays.
Computer Vision
Our plan involves utilizing computer vision to both detect where pieces are on the board initially and where the pieces get moved by the player. Our system will determine the location of each piece based on the difference in the board state after each move. Since only a fixed number of pieces can be moved at once, we can cross reference the board state changes with the rules of chess to keep track of the locations of each piece throughout the game. This will be used to determine where the AI is allowed to move a specific piece on the board, if a human player makes an error, or where to find a new piece if a pawn promotion is necessary. In summary, our problem statement is to use the state of the board at time t-1 and an image of the board at time t to get the board state at time t.
Preliminary Ideas

Outline of ideas about computer vision
Approach
Our approach given the above problem statement is as follows:
  1. Take a picture of the board from a fixed angle (top down or skew? TBD)
  2. Perform edge detection with OpenCV (possibly using Canny edge detection)
  3. Perform line detection with OpenCV (possibly using Hough edge detection)
  4. Compute intersection points with OpenCV (possibly using findContours)
  5. Find corners of the chess board
  6. Compute transformation matrix to constant image dimension (e.g. 800x800)
  7. Transform/crop/resize image based on transformation matrix and computed corners
  8. Segment board into 64 squares
  9. For each square
    1. Check if square is occupied
    2. If occupied, determine piece color
    3. Determine difference between B[t-1] and B[t] to compute delta_matrix[i][j]
    Using pixel difference to compute change in board state. If a square is either empty in both or occupied in both images, we assign a 0 to the corresponding cell (to indicate no difference in board state for that cell); if a square is occupied at time t and is empty at t-1, we assign a -1; lastly, if a square was empty at time t and is occupied at t-1, we assign a 1.
  10. If needed, handle piece promotion
    1. Approach 1: Use a neural network based classifier to determine which piece was chosen for promotion
    2. Approach 2: Ask user to specify (via GUI or CLI) which piece they chose for promotion
Steps 2-6 are done a single time at program startup; we can then reuse the computed values to segment the board and isolate each square.
To avoid using computer vision to keep track of the Graveyard state (see Graveyard), we have a capture square and designated promotion spaces in the graveyard so that we only need computer vision for the main part of the board.



Speech Recognition
The Harry Potter scene where Harry and Ron give commands to move pieces using their voice alone while playing Wizard's Chess inspired us to implement something similar for this project. We use a python wrapper of Google's speech recognition API to convert audio input to a representation that is compatible with our chess engine.
Web Application
Our web application will consist of a front end web app built using Javascript that uses the chess.js and chessboard.js libraries. To communicate with the chessboard, we need two way communication. One option we are considering is to use a flask backend that updates a database when moves are made; this can then be polled by the frontend and game loop to get the most recent move. Another option is to use web sockets to allow direct two way communication without the need to poll a database. In either case, we need to set up authentication of some sort to ensure that only authorized users are sending moves to the chess board, but we want to publish the current state of the board to a non-auth-protected page for anyone to follow along with the current game. We also want to make user profiles to track statistics like win-loss record, games played, and elo, among other attributes. Lastly, we aim to set up a live-stream of the physical chess board and host that alongside the other components of the web app.