Game Framework

Software pic

System Framework

The Game Object, contains a representation of the board, which is a dictionary with the tuples of points being the keys and the Piece Objects as the values. We did not use any external dependencies for our gameplay code.

Our generalized framework also made it easier to insert in the functions that integrated our system together, as each phase of the gameplay loop was written out explicitly. Because of this, we were able to quickly drop in the functions we had written for viewing the board using computer vision and communicating with our arduino via its serial port into their proper locations in the gameplay loop.

Computer Vision

Raspberry Pi and OpenCV

One of the most important features of our software system was recognizing the state of the board so that the robot can process the game state and make its next move. We used openCV which is a module that is widely used for image processing. We used a camera module of the Raspberry Pi as our camera. OpenCV is used to find the contour of the images taken by the robot. Finding the contour determined the boundary of the pieces and the board in the image.

By observing the contour lines and areas, we were able to determine the position of the checker pieces and the board, as shown in the image on the right. Because the board is a big square piece in the image, it contains a large area. We can easily find the center point and the corner point of the board area and these points are used to create the virtual board in terms of image coordinates.

The pieces were also determined by the area. Since all of the checker pieces are homogeneous, we can search for a range of area to find the location of the pieces. Unfortunately, for some strange reasons the color detection did not work on pictures taken by the picamera.

We taped a triangle shape on the red piece to detect the human’s pieces by different shape compared to the robot’s checker pieces. The robot detects the human’s move by taking a picture of the board before and after the human moves and compares the change to make its next move.

Software pic

Artificial Intelligence

Software pic

Recursion Depth and Analysis

To implement a AI, we used a recursive minimax algorithm with a limit on recursion depth, at 10, and caching to make it computationally more efficient. The formal definition of the algorithm from the web is that “for every two-person, zero-sum game with finitely many strategies, there exists a value V and a mixed strategy for each player, such that

  • Given player 2's strategy, the best payoff possible for player 1 is V
  • Given player 1's strategy, the best payoff possible for player 2 is −V."

Recursion Depth and Analysis

In other words, from player 2’s perspective, the player wants to minimize the max value of the board of his or her turn, while player 1 tries to maximize the minimum value of the board. To implement this, we assign each terminal board a value, negative values for a player 2 win and positive values for a player 1 win. And with the assumption that player 2 will try to minimize the maximum value of the board, and player 1 will maximize the minimum value of the board, we can assign values to all board states above the terminal states.

Software pic

Open Source Code

code pic

Open Source Collaboration

We are advocates of open source software and we used github to host the code for our system and our project's website! We encourage you to contribute to our repositories and make the next generation of computer-interactive board games better, one commit at a time!