Implementation

Designing the Game

There were no easily accessible APIs or libraries for Chinese Checkers, requiring us to program the game from scratch in Python. We created several Python classes and methods to program the game and used matplotlib libraries to generate an interactive UI; allowing a player to play the game independent of robot actuation. The following sections discuss the main milestones in the project.

Main Game Classes

Board Class

Peg Class

Player Class

Point Class

Interactive UI / Displaying the Game State

To allow the user to play the game against a computer player, we designed a UI using matplotlib. Not only would this allow a user to play the game, but it would also allow us to display a real-time visual representation of the board, which would be useful when playing against the sawyer arm robot. Here is an example of a user playing as red against the greedy movement algorithm (described further below) playing as gold.

Designing an AI player

Random Movement Algorithm

One of the experimental player algorithms we developed was one that picks a random movement to make based on all the possible moves. Here is a video of six players playing the game by randomly picking movements for pieces. An interesting discovery we made was that even with uniformly random choices on movement, the pieces eventually reach their corresponding endzones!

Greedy Movement Algorithm

Another experimental player algorithm we developed was one that picks a movement by prioritizing movements that travel the furthest to the endzone. Here is a video of two players playing the game, where Gold is operating under the greedy movement algorithm while Red is operating under the random movement algorithm. We discovered that the greedy movement algorithm is quite good, but some game strategies can be implemented to beat the algorithm!

Optimized AI-Based Movement Algorithm (UNDER DEVELOPMENT)

We attempted to implement a more advanced computer player by using AI and optimization strategies to find better playing strategies. The optimization strategies used are as follows:

Minimax: The Minimax algorithm is a decision-making strategy. It assumes that the opponent will also play optimally and tries to minimize the possible loss in a worst-case scenario. Here's how it works:

The AI simulates all possible moves (and counter-moves) to a certain depth in the game tree.
For each move, it calculates a score based on the game's evaluation function.
The AI then chooses the move that maximizes its minimum gain (hence, "Minimax").

Alpha-Beta Pruning: Alpha-Beta Pruning is an optimization of the Minimax algorithm. It reduces the number of nodes in the game tree that the AI needs to evaluate, improving efficiency. During the Minimax traversal, two values are maintained: alpha (the best score the maximizer can guarantee) and beta (the best score the minimizer can guarantee).

Analyzing the Board

Image Class

We needed some functions to process the image of the board after we took it using the realsense camera.

Image Processing Pipeline

1. Crop Original Image

We cropped the image according to some percentage of the original image dimensions. For example, we set the height of the image as a fraction of the original image. By cropping, color detection is less prone to misclassifying points, which is important for the next step.

2. Identify Board Corners

We found corner detection to be an immensely difficult problem. To resolve this, we used pieces of blue tape in the corners such that we could use standard color detection to detect them. Additionally, we sorted the xy positions of the pieces of blue tape to determine which corner was which.

3. Get Top Down Image

Now that we had the corners of the board, we could use a homography matrix to get the top-down view of the board. This would make detecting the color of the points easier for the neural network.

4. Detect Pieces and Positions

Using a neural network, we boxed and located the positions of every space on the board. Through training, we were able to get the network to detect the pieces by matching colors with player colors. If the color white was detected, then it was classified as an empty space.

5. Map Image to Game State

Finally, by sorting the classified points according to their xy positions, we could map the points to their corresponding positions on the checkerboard. Thus, giving us the state of the board. These game states can then be used to display the current game state or passed to the computer player to determine the next best move.

Inference and Actuation

Determining the positions of the pieces (inference)

We first determined the position of the ar tag on the board by moving the sawyer arm into a tucked position where the camera on the arm could see the board. The ar_track_alvar package was then used to locate the position of the ar_tag. The position of the remaining pieces on the board would then be calculated by assuming an even spacing between pieces as well as a constant offset between the ar_tag and the nearest hole to it (the bottom left most left). The resulting real world coordinate of the peg is then calculated as follows.

Picking and placing pieces (Actuation)

To pick and place the pieces we utilized the following loop. The actuation node would receieve a message containing the initial and final positions in internal board coordinates and that would be converted to real world coordinates using our the spacing and offset values we provide as well as the ar_tag position. The arm would first tuck into a position where it can see the ar_tag and record its position. Then the arm would tuck into a regular position to provide it a good starting off point before moving to the position of the piece it wants to pick up. This movement stops the arm just right above the piece to ensure it doesn't hit the ball before descending down to pick it up and ascending back up to a regular tuck. It will then repeat this movement to the end position to drop the ball before again returning to a final tuck position, except this time to a custom position very far up as to not block the camera from detecting the board and continuing the loop.

Page updated

Report abuse