Meet the mobile phone that can play checkers

Most of us have played the popular board game of draughts or checkers at some time in our lives. It's a game of strategy as you move your pieces forward, and try to jump over your opponents pieces to remove them from the board to win, but what if you need a little help to complete that victory? Faisal Adam, a final year Computer Science student at Queen Mary decided to give a helping hand using some clever artificial intelligence and his mobile phone. He wrote a program that allowed him to photograph the draughts board with his phone, and then use cunning programming to suggest the best move.

Looking at it from a different angle

The project involved having to build a program that would recognise the checkers board and pieces from any angle. After all you can't be sure when you can take that sneaky picture. The task was made easier by using a trick often used in computer vision; prior knowledge, make use of the thing you can be sure about in the world to help the computer understand what its looking at. We know here that there will be a square board with dark and light squares in an 8 by 8 grid, so we can look for the edges of the squares, and the places where they come together to form a cross. The pieces used to play will be a different colour, light or dark. Light pieces will be on dark squares and vice versa, so when you know where the board squares are you can test inside them to see if there is something of a different colour. This way you know which square contains which piece, and using some clever geometry you can create a computer graphic image of the board showing the current state of play.

Leafing through artificial trees

The mobile phone now has information on the set up on the board, the state of the game, and you've told it what colour you're playing with, so now the program has to suggest the best move. It does this using a game play tree; to make the tree you take the current set up on the board as the starting point and from this calculate all possible next states of the board by applying the rules of the game. For example the program calculates what the game board looks like if you were to move piece A. It also calculates what the board would look like moving piece B and so on. Starting from the beginning the program branches out into all possible next stages. Of course you can look further into the future. You can look two steps ahead. What happens if you move piece A, your opponent moves piece X then you move piece B and so on? Each step forward and the branches of the tree become more numerous as the possible look ahead to future states of the board increase.

The search is on

How does this collection of possible future board positions help? For each board position we can calculate a score: how good is the move, does it take an opponents piece for example? Now all we need to do is find the move that gives us the best score, and we can do this by searching through the tree branches to find it. There are lots of clever ways to search through the trees. One popular but simple method is called MiniMax search. The best move is to make your opponent lose and make yourself win. At the end of the branches are the possible final board positions we can get to by following all the legal moves possible from the starting position. We can start at the end and work back through each of the branches. So, the computer would look through all possible sets of moves, and from all of these select the route to get you to your MAX score and force your opponent to get the MIN score. This can take a lot of time to compute, particularly if you want to look a few steps ahead, you need to compute all the possible scores in each long branch. You can speed things up a bit by using a method called alpha beta pruning. The program keeps a note of the best score so far, and if it starts to evaluate another branch, and finds it to be worse than a previously examined move, the program ignores it and tries another.

Making a phone smart

The further you can look ahead the more intelligent your algorithm looks to the outside world. After all it's making predictions about what the players will do. However on a mobile phone like Faisal's there's a limit to the amount of computation you can do, and also a limit on the time you can take to calculate a move. Your opponent may get suspicious if you're sitting waiting for too long. But after doing some experiments with different algorithms and examining how quickly they worked with different number of look ahead steps, the application was completed. It worked. It suggested moves that were sensible, and better still it was able to function with a whole range of different chequers sets sneakily photographed from different positions. So, anyone fancy a game?