CV Chess

This is the page for the CV Chess project.

Project Overview

This project aims to use a camera, a raspberry pi, and computer vision software to recognize the movements of chess pieces in a game of chess. The final product will be able to recognize individual pieces, as well as determine the change in positions (squares) they occupy. This will ultimately yield a project that can verify valid moves, transcribe games, and perhaps implement an AI to act as an opponent of a lone player.

Powerpoint: https://drive.google.com/open?id=1YedAReM6O2aCmyuhbexrzyZo2OzDirnc

Demo day powerpoint(rough draft): https://drive.google.com/file/d/1Bia1HT9QYs1-1q9sQBzvP3-1uzONgBiM/view?usp=sharing

Team Members

Robert Goodloe
Nhut Dang
TA: Ethan Shry
Instructor: Prof. Jim Feher

Objectives

Use OpenCV software to recognize chess board.
Use OpenCV software to recognize the chess pieces.
Use OpenCV software to recognize the movement of the pieces.
Transcribe game of chess and present in user-friendly fashion.
Add an AI component that responds to a users movements. It would display a move which the user must execute on behalf of the AI.

Challenges

Limited knowledge of Raspberry Pi
Zero knowledge using OpenCV or any computer vision software
Have been told that nobody has gotten OpenCV compiled and running in ESE 205 despite several attempts
Using object recognition to differentiate between similar pieces i.e. bishop versus pawn
testing

Gantt Chart

Budget

Item needed	Unit	Price	Total(max)	Description	Link
Chessboard	1	9.76	9.76	wood	https://www.amazon.com/Yellow-Mountain-Imports-Magnetic-Travel/dp/B0019FATKG/ref=sr_1_10?s=toys-and-games&ie=UTF8&qid=1538161920&sr=1-10&keywords=chess+set
color dot(optional)	1	9.99	9.99	may needed if we are going to color code the chessboard's pieces.	https://www.amazon.com/gp/aw/d/B06X6LT9G9/ref=sspa_mw_detail_4?ie=UTF8&psc=1
Pi touchscreen (optional)	1	79.95+tax+ship	79.95+tax+ship	may needed if we are going to color code the chessboard's pieces.	https://www.amazon.com/gp/aw/d/B06X6LT9G9/ref=sspa_mw_detail_4?ie=UTF8&psc=1
tripod	1	free	free	for mounting	https://www.thingiverse.com/thing:2348881
Plexiglass(optional)	1	12	12	clear board	https://www.amazon.com/MIFFLIN-Plexiglass-Transparent-Acrylic-Plastic/dp/B076VR7D9C/ref=sr_1_28?s=office-products&ie=UTF8&qid=1538162741&sr=1-28&keywords=clear%2Bglass&th=1
			111.7

Design Solutions

Hardware

The project used a Raspberry Pi model 2b and an accompanying Raspberry Pi camera module. The camera was connected to the Pi using a 24-inch cable and mounted to the bottom of a tripod. The original design was intended to have a 3D printed tripod to mount the Pi camera, but this was changed. The tripod was able to stand directly above the chessboard and the camera directed straight down at the board managed to capture it in its entirety.

Software

The program was written in python and implemented using Object-oriented programming. The program had a graphical user interface created using the tkinter library. The GUI allowed the user to start a new game, choose the difficulty of the CPU opponent, and choose which color they would like to play.

Board Recognition Algorithm

At the start of the program the GUI prompts the user to clear the board so that it may initialize the board. This process took a picture of the empty board and performed an analysis of the image in which it could properly map the chessboard. In doing so, the photo was first turned into a grayscale copy of itself. Using the OpenCV library's built in algorithm Adaptive Thresholding, pixels above a threshold rgb color value were turned white and those below turned black. This binarization of the image allowed for contours (shapes) within the image to be more easily found. The largest of these contours found was the edge of the chessboard. Given the edge of the chessboard, a black copy of the image was created and the original image within the edge of the chessboard was written onto the black image. This effectively created a new image with the chessboard surround by black. This is important because it excludes any noise that may interfere with the following OpenCV algorithms. Next, using the OpenCV Canny Edge Detection, the edges of the chessboard squares were inferred from the sharpest gradient of the color values in the image. Given these edges, the Hough Line Transform was able to infer the lines in the image, mapping a grid onto the image. The corners of the squares were determined by the intersection of the vertical and horizontal lines. After removing duplicates and sorting the corners by both row and column, the squares were created. Using these squares, the program was able to initialize a board that would hold much of the information about the game. before explaining the piece movement detection algorithm, it is best to describe the objects used by the program and the information that they stored.

Objects

Camera: The camera takes pictures.

Line: Line objects held the lines endpoint x and y values as well as the orientation of the line (vertical or horizontal).

Square: These Square objects held much of the information used throughout the entirety of a program during a game of chess. The Squares stored their standard algebraic notation (i.e. a1, a2,...) as a variable called position. A square object also stored the piece located within in it or empty if it was empty. This variable called the state held a character representing the piece. Capital letters for white (R N B Q K B N R/ P P P P P P P P), lower case for black (r n b q k b n r/ p p p p p p p p) and and period (.) for an empty square. The Squares had a circle of radius 7 at their center, in which the color value of the square was found. This circle is called the region of interest or ROI. The Squares stored the empty color value, found when the board was cleared for initialization, and their current color values throughout the game.

Board: The Board objects stored all of the squares in the board. It assigned the squares' states. It is also where the piece movement detection algorithm was written.

Chess Engine: The chess engine class imports the chess module from the python-chess library which can be found at https://pypi.org/project/python-chess/. The Chess Engine class instantiates a local chess engine using the open source chess engine Stockfish. The class communicates with the chess engine using an open communication protocol that allows chess engines to interact with user interfaces. It is called the Universal Chess Interface (UCI). The Chess Engine class holds an instance of the chess board that can be updated when pieces are moved. The methods in this class include updating the board after a player move and getting a move from the CPU. It also notifies the user when they make an invalid move or they are in check/checkmate/stalemate...

Game: The Game class is the main bridge between the user interface and the underlying image/game analysis. It contains the Board, the Camera, the Chess Engine, and two images for image analysis (before a move, and after). This class calls the Board initialization. It houses the Player Move method and the CPU method, handling image updating and calling other classes for image analysis as needed.

Piece Movement Detection Algorithm

This algorithm requires two photos: one before a move and one after. So, after a move is made, the user hits 'Done', telling the Camera to take a picture which is passed to the algorithm. Next, the program iterates through all of the squares on the board, determining the change in color value from the previous photo to the current photo. It does so using the distance formula for each color value. In a typical move, two squares have the largest change in color, the square from which a piece moved and the square to which it moved. A similar color differencing is done on these two squares, however this time their color value is compared to their empty color value. Whichever square has a color value closer to its empty square color is now empty. Consequently, the move can be determined to be the position of the now empty square to the other square ('a1a2'). The states of these squares are updated appropriately, the occupied square is given the previous state of the now empty square and the empty square is now set to empty. There are a few special cases for piece movements. The first is castling. In castling, both the king and the rook move. This leads the algorithm to find more than two squres changing, in fact four squares change. In this case, the algorithm ensures that it is the king and rook moving, rather than two other pieces, for which it would throw an error. It then determines whether the castling takes place on the short side (king side) or long side (queen side). The move returned for castling as per the UCI protocol is the movement of the King so an example might be 'e1g1' (white short side castling). Another special case is pawn promotion. I n the game of chess, when a pawn reaches the other end of the board, the player is offered to promote that pawn to any piece of their liking. While it is common to simply promote it to a queen, one should have the ability to choose any piece. So, when detected a GUI window pops up asking the user to choose which piece to which they would like to promote. As per UCI protocol, the character associated with their choice is appended to the end of the move. For example, a move 'e7e8' with the choice of promoting to a queen becomes 'e7e8q'.