The smart phone that plays Snooker

If you've ever played snooker you know that it's all really about skill, physics and geometry. How do you hit the cue ball to pocket the red and spin back to pot the black? How do you angle the cue ball to bounce of the cushion to hit the red ball snookered behind the pink? As you're playing your brain's doing lots of clever computational thinking. The best snooker players, like many athletes and sports players, have physical skill but also have a mental model of the game geometry in their heads. They can imagine how the balls will move for a given cue ball hit. But it's not just snooker players that can have a working model of the game to help them win, as Queen Mary student Zubair Mitha, supervised by Peter McOwan, set out to show using his mobile phone.

Colour Coordination

In his final year project Zubair designed a Java application to help him and others play snooker that would run on his camera phone. By taking a picture of the snooker table his computer program is able to create an accurate picture of the layout of the balls on the table. Since snooker tables are green, it's possible to find the parts that aren't green and these will be the coloured snooker balls. In an image all colours are actually made up of a mixture of red, green and blue called a colour triplet. The camera phone stores this triplet of three values for each part of the image (it actually has 3 separate images, one each for the red, the green and the blue parts). Finding red balls on a green table is easy they are only in the red image, and similarly you can look through the colour data to find the position of the other colour balls. The green snooker ball is tricky but fortunately has a different colour triplet of green to the table baize, so you can find it too. Of course snooker is played under a range of lighting conditions so you have to use some clever maths to be able to account for this as the actual values of the triplets can change, but it can be done and the ball's coordinates in the picture can be extracted as Zubair was able to show.

A new perspective on tilted tables

At this stage you have the coordinates (x and y) of the centres of the coloured balls in the image, but the ball's image coordinates aren't the same as the ball's real coordinates on the actual table. Remember you are taking the picture with your mobile from a distance and at an angle to the table. What you really need to work out angles is a birds eye view of the ball positions. Zubair used the fact that snooker tables have a fixed length and width to calculate the perspective of the image. By finding the rectangle of edges of the table in the image you can work out the slope of the table relative to you. To understand this try an experiment, take a copy of the cs4fn magazine (or some other to hand). It's a rectangle of fixed length and width. Now hold it straight up in front of your face. It's still a rectangle, but tilt it way from you and it becomes a rhombus. The further away edge looks shorter. That's the effect of perspective, and as you tilt it over further the far end gets shorter still. Knowing what the ratio of the length to the breadth of the rectangle really is and the length of the far and near edge in the image lets you calculate the amount of tilt. Once you know this tilt you can apply it to the coordinates of the balls in the image to find their actual position on the table. From that you can produce an accurate birds eye view plan. Snooker tables also have the pockets at fixed positions on their sides, so you get these coordinates for free.

Into the pocket

Once the plan view is calculated with the position of the balls and pockets, the game can begin. The physics of snooker balls can be complicated, but a first guess at how they would behave would be that they travel in straight lines, and if they bounce off a cushion the angle they come off at is related to the angle they hit at (to get technical the angel of incidence - the angle they hit at, is equal to the angle of reflection - the angle they come out at, like a light beam hitting a mirror). Zubair programmed this simple physics model of snooker balls into the mobile phone, so you can use the phone cursor to select the ball you want to try and pocket, the pocket you want to put it into and the system then shows you how to hit the cue ball to make the shot. Like all good Computer Scientists he then tested the system to see if the simplifications he had made in the physics were good enough to be able to predict how balls would move on a table, and they did. The system didn't take into consideration things like ball spin, or working out how to solve complex snookers where multiple cushion hits are needed to pot the ball you want, but for a range of real situations on real tables it worked.

Zubair went on to work for LogicaCMG, and still plays snooker in his spare time, but now he can have a computational trick or two up his sleeve if he needs it.