2024sp-quoridor

Project overview

This project aims to create a modified version of the physical board game called Quoridor, a strategic maze-building game, where a player competes against a computer opponent on the board.
Quoridor is a 2 player game where each player’s piece start on opposite sides of the board, each turn the player chooses to either move their piece in any cardinal direction (up, down, left, right) or place a wall to block the other player’s path (walls cannot be moved once placed), the first player to get to the other side wins.

Project Proposal link:

https://docs.google.com/document/d/114cAhuUHxiCxB0LIXvpHFLx6ZjFtf0oyKlaDsvuiIQ8/edit?usp=sharing

Project instructions

These instructions are structured in 2 sub-assemblies:

• The Gripper

• The machine

  • Main part
  • Y axis rail

As well as a set of instructions for the Computer Vision:

• Players and walls detection
• Game board and coordinates building

The two sub assemblies can be built in parallel and assembled at the end. The design is such that only two screws hold the gripper to the rest of the assembly, so it's quite easy to modify the gripper seperately.

Gripper

Overview:

Here is the design of the gripper for the Quoridor game board. The gripper's movements include rotation (±280°), translation (10 cm), and gripping (4 cm wide). The gripper is powered by two DMS15 motors and one Servo 9G, with a power supply of 5V from an external source, drawing a maximum of 3A.

Required Components:

Motors:

• 2x DMS15 Servo
• 1x 9G Servo

Bearings:

• 2 dry bearings (outer diameter: 10mm, inner diameter: 8mm)
• 1 standard bearing (outer diameter: 24mm, inner diameter: 15mm)
• 2 Metal Shafts 100x8mm

Tools: File, lubricant, screwdriver

Equipment: 3D printer, laser cutter (for plates of 5mm and 3mm thickness, or alternatively, these parts can be 3D printed)

Assembly Instructions:

Gripper Assembly:

1. Clean the gear and the two racks with the file.
2. Attach the claws to the claw racks using screws (two screws per claw). Ensure the screws are tightened sufficiently to prevent any movement.
3. Mount the gear onto the servo. Apply a bit of force to fit it securely and then screw it in place (Note: This servo is trash).
4. Slide the two claws onto the rack holder, positioning them close together.
5. Use an Arduino to run the servo, setting it to its maximum position (180° = closed).
6. Slide the servo on top of the rack holder. Adjust the claws slightly to ensure the teeth align correctly (this step may require some patience, precision and despair).
7. Optional: you can stick pieces of rubber on the gripper clamp to increase adhesion (I used pieces of rubber glove).

Moving Part:

1. Clean the bearing holder and the main linear part.
2. Insert the bearing and nuts into the bearing holder.
3. Mount the servo on top of the bearing holder.

5. Insert the two dry bearings and nuts into the main linear part.
6. Position the servo with the bearing holder underneath the main linear part.
7. Secure the assembly by adding screws to the top of the main linear part. Use a small screwdriver to access the holes.
8. Slide the rack under the rack holder.
9. Attach the rack holder to the back of the main linear part, ensuring the rack holder protrudes upwards.

Main Part:

1. Try to pass the 2 metal axes through the two laser-cut 5mm parts. If necessary, use a file to clean the holes, but do not over-file as the axes need to stay securely in place.
2. Place the left and right pillar supports on the 5mm main plate. You can add screws for additional stability, but this is not mandatory.
3. Position the two upper pillar fix on top of the pillar spacers and screw them in place.
4. Place nuts on the right pillar support and the linear servo support, then screw them onto the main plate.
5. Attach the servo circular extender (I dont know how to call that) to the main gear and secure it using the screws provided with the servo.
6. Insert the two metal axes, slide the moving part onto them, and add the two spacers at the top.

8. Position the servo motor and the two pillars, then add screws at the top and base to secure them.
9. Run the two servos with an Arduino, ensuring the rotation is set to 0 and the linear position is also at 0.
10. Attach the main lower plate to the main plate using spacers.
11. Slide the moving part to the top and fix the gear onto the servo motor. The goal is to have the last teeth of the rack engaged by the gear. (Optional: It is recommended to screw it only when everything is installed).
12. Return to the claw assembly. Fix the gripper support servo to the bearing, applying a bit of force to secure it, and add the screws provided with the servo.
13. Insert the servo from the claw into the gripper support servo, ensuring the cables are passed through before positioning the servo.
14. Add two screws to secure everything. (Optional: It is recommended to do this only when everything is installed and tested to avoid damaging the claw).

Wiring:

Due to their high power consumption, all 3 servos must be powered by an external power source of at least 5v/3amp. Here is the electrical diagram to connect them to a Ramps 1.6

1 is the gripper servo, 2 is the rotation servo and 3 is the servo of the linear actuator.

Improvements:

• The 9G servos are unreliable and prone to malfunction. Consider using higher-quality or bigger servos to improve the performance and longevity of the gripper.

Machine sub-assembly

3D printed parts

Camera mount

• 1x main part
• 1x camera clamp

Walls

• 10x in red

• 10x in blue

  Print in this direction to get the best results (no supports necessary)

Player pawns

• 1x in red
• 1x in blue

Board

• 2x "long"

• 1x "square"

• 1x "little square"

Angle brackets

• 15x

Corner brackets

Warning, these are symetrical pieces ! One of each

End pulley

• 2x

Optionnal : 3D printed T-nuts

The metallic openbuilds t-nuts are recommended. We 3d printed those because we forgot to order them. We ended up doing a slightly modified version of the original openbuilds CAD model with a bigger diameter, that works better when 3d printing

Laser cutting

In MDF

Main board

• 1x Main board, 10mm

Walls holder

• 2x, 3mm

In acrylic

Camera arms

• 2x, 5mm

Wheel plate

-3x 3mm

Stepper mount plate

-2x 3mm

End pulley bracket

• 4x 3mm (Two are used per axis)

What needs improvements

3mm thick acrylic is not strong enough. We had a failure for an end pulley bracket, the 3d printed part ended up stronger.

We also a noticed a crack developing on one of the wheel plate

Assembly instructions

With all the parts cut and printed, we are ready for assembly (note that you can also 3d print as you go, since the three pieces for the board for example take quite long to print)

First, screw in the wall holders pieces to the board. These parts add thickness to the board, so doing this first helps stabilizing it a bit more (MDF tends to bend with time).

Next, screw in the 8 angle brackets to the board (4 on each side).

Attach the V slot aluminium profiles, screwing them in place with the t-nuts

Screw in the corner brackets. These help stabilizing the profiles, and at the end to mount the camera arms.

Now flip the board upside down, with the top side of the profile resting on your workspace. We will use the profile as spacer. Slide in the 3d printed boards part. Glue them. gravity will hold them in place. We used fast super-glue, but with this setup you can use a glue that takes a while to set.

X axis assembly (built this seperately)

Warning : follow precisely this order, so you don't need to dissassemble sub-assemblies down the line

Mount the wheels to the wheel plate (this is the plate we will later mount the gripper to) Slide the wheels+plate assembly to the middle of the profile.

Mount the end pulley plates on both side on end of the profile

Mount the stepper mounting plate on the other side

Mount the angle bracket to the v-slot. The placement is simple : on each end, they are next to each other, sarting at the end of the profile.

Do this two times, for both sides:

Mount the wheels to the plate and then slide the assembled carriage.

Combine x axis assembly with the rest

Now we can mount the stepper on the x axis with the belt. Attach the belt to the plate going above the profile like this:

Slide in the end switch mount. Tighten it so it does not move, but don't try to be precise with regards to the adjustments. Adjustements are done when everything is in place.

Attach the Y stepper to the stepper motor plate, setup the belt but don't attach it to the gripper plate yet.

Put the gripper assembly on top of the plate, screw it in place

Screw in the electronic box. Put the arduino+ramps+motor driver sandwich inside of it. Do the wiring according to the diagram. Pass the cables via the side holes (otherwise you won't be able to close the lid at the end).

Camera arms

1. Screw in the arms to the angle brackets

2. Connect bot arms together

3. Mount the camera using the clamp

Button

1. Screw in the button housing to the board
2. screw the button itself to the housing from below

The end

Congratulation ! At this point, you should have the full machine assembled like this:

You can now proceed with adjustements regarding the end switch positioning, as well as the camera angle for the webcam.

Arduino code

The arduino code is separated in 2 parts, one is for all movements on the board (the X, Y axis stepper motors and 3 servo motors for the gripper) and the part is for communication and interpreter which will send, receive and decode message from the computer which it will translate to valid moves on the board.

The arduino will be managing communication with itself and the computer with a serial connection. This diagram shows the communication between all of our components:

The arduino will send a "end turn" message through the serial once the button pressed, then the computer will communicate with the camera to detect the current board state (placement of the player pieces and the walls), with that it will compute the best move for the bot. Finally it will send the move information as the board position of the piece we want to grab, the new board position where we want to place the piece, the piece type, and optionally the orientation of the piece if it is a wall.

To accomplish the first part the arduino will stay idle, but once the player presses the end turn button it will trigger an interrupt. This will cause the arduino to print the message "get next move", which will be sent by the serial port.

Then the arduino will remain idle until it receives the move information from the computer.
There are 2 types of moves, moving a player piece or a wall piece. If the move is to move a player piece, then the move information will be under this form: <old_position><new_position> where old_position and new_position are board position for player pieces which are shown here:
If the move is to move a wall piece, then the move information will be under this form: <old_position><new_position><old_orientation><new_orientation> where old_orientation new_orientation are either horizontal or vertical, and old_position and new_position are board position for wall pieces which are shown here: With all of this information the arduino knows what it has to do.

Now for actually placing the piece where it needs to go.
First we must move to the piece we desire to move, which we use the 2 X and Y stepper motors. Since the board was made with cells that are 4 times bigger than the gap between cells, it just takes knowing the distance in steps from the position 0 0 of the grabber to board position 00 for a player piece, and the distance in steps from a board position to a neighboring one board position to know how to move any board position for player pieces and wall pieces.
That is the hard part done, then the gripper drops down, grabs the piece, pulls it back up, rotates it if it is needed (for instance if we had to place a vertical wall), moves to the new position, drops down, releases the piece, goes back up and moves back to its origin.

Here are some videos that process working flawlessly:

VideoEditor_20240531_21-32-51.mp4

VideoEditor_20240531_21-34-08.mp4

Quoridor Solver

We implemented a greedy version of a Quoridor solver. The solver sees the game as a graph where:

• each board cell is vertex (with a board position attached to it).
• each possibility of movement from one cell to another is represented by an edge from that vertex to the other.
• each wall is represented by missing edges from 2 cells to 2 other cells.

The solver works as follows:

• computes the shortest path to get to the other side for both players, it uses a breadth first search algorithm to do this, as it guarantees that it will find the shortest path first.
• if the path of the robot is shorter than or equal to the one for the real player
  • then the robot is in an "advantaged" position, thus moves his player piece one step forward on its shortest path
• otherwise it means the path of the robot is longer than the one for the real player
• the robot is in a "disadvantaged" position, thus it will need to place a wall on the board if it wants to win
• if the robot has 0 free walls to move:
  • there is nothing it can do to win, thus moves his player piece one step forward on its shortest path
• else
  • for each wall position that goes on the real player's previously calculated shortest path:
    • checks that there is no colision with other walls on that board position
    • calculates the shortest path for both players on that new board with that wall placed
    • checks that there is a path to a winning cell for both players
    • keeps state of the best "winning move" and the best "losing move"
    • the best "winning move" is defined as the move that maximizes the distance difference between the robot's and player's new path where the robot's new path is the shorter one.
    • the best "losing move" is defined as the move that minimizes the distance difference between the robot's and the player's new path where the robot's new path is the longer one.
  • if a "winning move" exists:
    • it moves a free wall to the position in the best winning move
  • else
    • it moves a free wall to the position in the best losing move

The solver seems quite robust and plays really well, but it still has some weaknesses due to the fact that it uses a greedy algorithm which means that it only considers the best move for itself on this turn.
So no future planning or strategy is going on and it won't consider what the real player can do in their future moves.

Computer Vision

Pieces detection

The playing pieces (players and walls) are recognized through color detection.

Using colorimetry software, we first get the BGR (Blue Green Red) color of each of the playing pieces we need to detect. This value, along with the camera feed, is then converted into the HSV (Hue, Saturation, Value) format. We now create a color mask based on the detected color with a range on the hue based on a sensitivity chosen to be 50 to account for the shadows and slight color variations.

Once we obtain this mask, we use OpenCV's minAreaRect function to obtain all the possible rectangles containing objects of the same color. We then apply filters to only keep the rectangles for which the height and width would correspond to our playing pieces. This is also how we distinguish between walls and player pieces since their enclosing rectangles would have different sizes.

Once we filter the rectangles of the correct sizes, we extract the centers of these rectangles which we then use to detect their coordinates on the grid. This part will be explained on the next section.

Finally, for the walls, we also need to detect their orientation. We do that using the "angle" value returned by the minAreaRect function and by comparing the width and height of the rectangle. Just the angle is not enough in our case since the openCV function returns a value between 0° and 90°,it is very error-prone when thresholding between Horizontal and Vertical values (if the value is slightly above 90°, it goes back again to 1°).

Game board

The board, its cells, and wall gaps are not detected as is, but rather re-created after detecting the board's corners. Each corner is uniquely identified by ArUco markers: they are a sort of QR code that can be generated and identified through its corresponding library. Given the corners and the cells' number and dimensions, a grid is recreated:


You can see in the picture that the grid is purposefully offset near the top. Because the camera is not directly centered on top of the board, walls near the top will tend to look like they are higher on the board than they truly are. You will find more detail on aruco detection and perspective wrapping in the code /computer_vision/create_grid.py
When creating the grid, the set of intersections between all perpendicular grid lines is stored for future use. For each intersection, we store the absolute coordinates as well as the game-system coordinates (9 units on each side, origin is bottom left)
Then, given the absolute coordinates for the pieces' centers, the code uses the set of intersection coordinates to output, for the solver to use, the game-system coordinates of each piece.

When sticking the ArUco markers on the board, you should be mindful that the outer corners should be well-aligned with the board's corners (PS: the markers don't need to have the same size, they should just be well-aligned).
Be careful however that they can be seen entirely from the camera (black square included). Here are corner-case examples:

On the image above, the top markers should be small enough that the walls placed at the top don't block them
On the image above, the markers are too far down: the black square isn't showing entirely.

Final Project

And that's it!
You have successfully built a Quoridor playing robot.
Now take seat and try to beat your new creation!

Here you can check out some videos showing our project's successes (and failures)