Time for technical details:

1) Board recognition.

We have used the camera (in android phone with IP Webcam app) to grab the photo of board and send it to the host computer. Next, the image is cropped translated to board square - then it is divided into separate fields. Algorithm tries to match circle in every field (from above pawns ale near ideal circles). If the pawn is detected the image of field is being thresholded to detect if it’s white or black. When all the fields were recognized the board is sent do game logic part of program. Image recognition was written in python with openCV library.

2) Checkers algorithm

Firstly, it detects if the human move is allowed and then computes next move. We have developed heuristic alfa-beta algorithm (http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning) to calculate next computer’s move. Depth of search tree is 5-8 depending of difficulty.

Our board to value function (we have to know which situation is better than other, but it's really heuristic):

- the closer the pawn to the end the bigger the value,

- if the pawn is a kings is much more valuable,

- if the pawn is under beat it is less valuable,

Analogically for the computer pawns.

We can set searching depth from 5 to 8. The algorithm is so good that we have never beaten it.... The slave becomes better than master...

3) Crane for moving pawns

We have to made a robot to move pawns. It was developed using two LEGO NXT’s, train tracks and many other lego parts.

Axes was made using LEGO train tracks and cars - it forces straight movement in one direction and it has enough precision. On one site of track we mounted a motor with wheel mounted to rope going to the other site of track. The NXT motors have build-in encoder which gives us an information about position where we are - this means we can move to given field. Both axes have endstops for detecting origin positions.

The holder for pawns was made using LEGO pneumatics set. One cylinder holds pawn and two other ones raise it up over other pawns to move it safely to other field.

We have build pressure controlled pump and controlled valves. The pump runs until the switch was pressed. As we have run out of touch sensor we've made a breakdown cable - NXT detects shortcut between two pins of it's cable. So we've used normal switch !

Controlled valves the easy way!

NXT's were programmed in LabVIEW with NXT for LabVIEW toolkit - they communicates with main app using TCP/IP protocol.

4) Application GUI

GUI was made using PyQT with QT Designer - It shows steam from camera, moves list, and many other options!

PyQT is very nice to write apps, especially if you use designer and generate UI code - your job is just to make an interface (slots and signals) with rest of app.

5) Putting it all together

Project Logs

Collapse

Final version!
gregg • 04/29/2014 at 01:27 • 0 comments

We've made a final version of our project.
The film show it! Enjoy!
Our workflow
gregg • 04/29/2014 at 00:37 • 0 comments

Gregory developed, wrote and implemented the software not only for computer but also for robot, which was designed and was built by Ewelina. Tests of the algorithm of checkers and the algorithm for robot were carried out together.
Work on the project proceeded during regular meetings. Meetings were held at least once a week. During the first meeting we established work plan, which we stuck to the end of the project. Some of the work we did independently between meetings. During the meetings we are doing a summary of the work and partial testing.
Software
gregg • 04/29/2014 at 00:19 • 0 comments

Gregg here.
I've developed the software for out project.
BTW. All the software is on my GitHub and it's Open Source. Maybe it'll help someone! (I hope so :) ).
I've used python with openCV and PyQT library to design main application, which consists of image recognition, gameplay and GUI:

For the hardware we've used LabVIEW (with NXT toolkit).
Python and LabVIEW communicates via TCP.
The basic dataflow:
LEGO Crane
gregg • 04/29/2014 at 00:05 • 0 comments

Rukia built out LEGO robot arm to move the pawns on the board.
It was developed using LEGO NXT's, train tracks and pneumatics.
Main skeleton:
Motors attached to ropes move the board and carriages along the axes. Both have endstops to detect zero position.
Axes was built using train tracks to assume straight moves along axes.
The carriage with mounted pneumatic actuactors:
Two of them pulls up the pawn above other and one is to hold it.
We built automatic pump with pressure switch to prevent over pressure in the installation:
Pr0 tip: we've used modeller's fuel (from airplanes models) plastic pipes and airtank (it was for fuel too!). They're much more stronger and much cheaper than lego pipes.
Checkers algorithm
gregg • 04/27/2014 at 23:15 • 0 comments

We have developed computer's brain!
We know, the checkers are solved game (Link), but we tried to do out best in time we have.
We've designed alfa-beta pruning (Link) for checkers - it creates game tree of every position under actual.

Our board to value function (we have to know which situation is better than other, but it's really heuristic):
- the closer the pawn to the end the bigger the value,
- if the pawn is a kings is much more valuable,
- if the pawn is under beat it is less valuable,
Analogically for the computer pawns.
We can set searching depth from 5 to 8. The algorithm is so good that we have never beaten it.... The slave becomes better than master...
Board recognition
gregg • 04/27/2014 at 22:13 • 0 comments

Hello, hello!
To detect pawns we decided to use android camera (with IP Webcam app - it's very good by the way). Phone was mounted over the board to have clear view of situation on it. As light source we have used built-in LED.
The board with mounted camera:
First of all, we have made a board recognition algorithm, using openCV and python (it is really faster to write code in python than in C++, especially in openCV where types names are so "strange"...).
Rukia designed the algorithm and Gregg implemented it:
- crop and transform image to square board of constant size (600x600 px),
- splits it into separate fields,
- for every field:
a) applies median blur,
b) applies Gaussian blur,
c) applies Canny edge-detector,
d) search for circle using Hough method,
e) if the circle was detected it threshold the image and then recognize color of the pawn (it depends of white pixels in threshold image)

Then build an array of field to pass it forward to game logic.
Board after transformation with marked detected pawns:
And the same board after edge detector:
Whole algorithm written in python is on GitHub
All project files
gregg • 04/27/2014 at 21:33 • 0 comments

All project files are stored at GitHub.