The Computer Plays Pool
Author: Jeff Rollason and Daniel Orme
Copyright Notice: This article is Copyright AI Factory Ltd. Ideas and code belonging to AI Factory may only be used with the direct written permission of AI Factory Ltd.

This is a game project that started its history at the beginning of AI Factory and was actually the first product we ever released. However this was not a product light-weight and embodied a number of interesting design ideas that carried on to other products. This product also continued in development and featured in the later article A Tutor System For Pool, where we were addressing teaching systems.

However creation of the original product throws up AI issues that might not be immediately obvious to the developer, as follows:

Setting up the Basic Framework

Before jumping into considering AI, it is necessary to establish a core framework to play the game at all. The game is played with objects that can be assumed to be perfect spheres, so at first glance this looks like the ideal physics emulation task. However you need to examine the range of physics you will really need. In particular, pocket collisions can be quite complex, with the ball bouncing off several pocket surfaces, partly dropping into pocket and then having the momentum, on striking the pocket shelf (table edge in front of pocket), to then lift the ball back out of the pocket. Of course we had the option to have "pocket magic", so that ball that breeches the pocket boundary by a certain degree then automatically switches to a "drop-in-pocket" sequence, or even just vanishes.

However we had more ambitious plans, so jumped into considering the more general emulation, trying to get a product that really felt like Pool. Having balls rattle in pockets and potentially bounce out really is a part of the Pool experience. This product was also extended to Snooker in addition to the simpler 8-ball and 9-ball, which would also require added complexity for the AI.

Getting the Physics Right

At first glance the perfection of ball shape seems to offer the possibility of handling ball collisions by using geometry to predict the paths of balls and when they will collide. This could be a very efficient engine capable of endless predictions. However this myth rapidly evaporates when you realise that balls spin, have friction and generally can move in a complex manner. Note also what happens with a break. You now have variable speed and direction and suddenly geometry can no longer use simple math to predict where the ball will be.

Compromises

Within the scope of the project, we imposed some limitations. The key one here was predicting motion in Z plane (vertical) when the ball was travelling across the table. This is an inaccuracy as players can create shots where the ball jumps, but this greatly increases the complexity, and adds a significant speed overhead to ball collision calculations, so this was compromised.

Prediction using Time-Sliced Events

The simpler, and maybe less intellectually satisfying approach, is to divide up ball moment into very small time slices. Given that you can simply determine the very small moment that a ball makes in that time slice and move it. Friction, Spin etc. can be adjusted and a check to see whether the ball has collided or not. This obviously has a built-in inaccuracy as the point of collision will not be perfect and potentially has an error as much as the size of the time slice. It might therefore assess collision at the point that the balls already overlap.

The simple response to this issue might be to simply reduce the time slice to an extremely small value, but this imposes other issues. The emulation starts to get very slow. Note that it is not enough that the emulation can run fast enough in real time. It needs to be much faster, as it will inevitably be also needed by the AI to do predictive emulations.

Given these constraints, the adopted time slice used was 4 milliseconds. That means that a shot that takes 3 seconds to return all balls to rest will need 750 emulated steps. At first glance that seems a lot of points to have to stop and re-assess what the balls are doing, but computers are fast and this fine granularity allows the whole system to be reduced to a basically simple system.

Reducing this to a loop, the process of ball handling becomes:

Po_MoveBalls(aGameState, aMove.iMilleSecs ….)
{
//...flag that all balls are not in collision and has not hit rail yet
//...LOOP TIME : moving the balls until finished
while (aGameState.iInMotion ) {
//...LOOP BALLS: moving all the balls and apply friction
for ( movingBall=0 ; movingBall < KNumberOfBalls ; ovingBall=(movingBall+1) ) {
//...check if not in pocket and moving (see below)
}
}
}

With the expanded section below, as marked in red above:

//..check if not in pocket and moving
//...move ball in X,Y plane
//...apply orientation change, friction to linear velocity and friction to side/vertical spin as well
//...convert vertical angular momentum (side spin) to linear momentum
//...convert X-axis and Z-axis topspin/backspin to linear momentum, and vice-versa
//...BALLS/WALLS check for collisions with other balls and with rails
//...now check if we have any collision with side of table
// check left and right ends
//...check for ball hitting rail after 1st contact
//...check for near pots
//...check for ball in corner pocket zone
// check top and bottom ends
//...(as above)
//...now check if we have collisions with other balls
for ( ; other < (EIndex) KNumberOfBalls ; other=(EIndex)((TInt)other+1) ) {
if ( ball we might collide with ) {
// we may have a collision. Test actual distance
// compare sq of dist to save time
if collision possible, process collision
}
}

Collision Calculations

Much of this depends on fairly basic vector calculations, to convert speed in direction X,Y to final speed in direction X,Y. Add to this calculation about the impact of spin and also the influence of ball and cushion elasticity.

Finally, and crucially, there is rotation. This is not something you can run off easily using trigonometry, but needs matrix multiplication. We are not going to explain this here!

Determining the Point of Collision

With time slicing, as indicated above, the collision may be detected after the balls already overlap. For slow moving balls this is not a problem, but a fast moving ball might significantly overlap. To compensate for this the easiest method is to rewind time using a much smaller time slice to detect the exact point of collision. Note that this is a relatively rare event and that actually need not be calculated with the full level of calculation normally applied. The first simple approximation can be that the ball was retrospectively moving at exactly the same speed that it is currently travelling. Given that the time interval between collision overlap and collision is very small, this is a reasonable approximation.

Proving and Tuning the Physics System

For much of it, it is clear whether the system is behaving reasonably. If balls fly off in the wrong direction, you need to return to examine the code. However the whole system may appear to be reasonable, but actually the balls may be exhibiting unrealistic physics. In particular friction and elasticity needs to be tuned: there is nothing in the Pool table manual that defines these things. You have to see it live.

The only reasonable solution here is a trip down to the Pool hall with a schedule of shots to try. From this the general behaviour of the emulated system can be compared to the real thing.

still from pool hall movie

In the shot above we have a backdrop checkered strip so that exact speeds and movements can be measured. As a note of authenticity you will see that other players were around, and rather curious about what we were doing!

This required more than one trip as initial testing schedules showed up that we also needed extra shots to compare. These included shots of specific ball collision set-ups and pocket collisions and drops.

From this we gradually tuned and corrected the physics until it could reliably emulate what the movies had shown. This needed some 100 movie clips to complete our tuning.

Next Step - Pool AI

Armed with a physics engine, maybe the next step is easy. All you need to do is test what happens when you hit the ball in all possible directions and just see what happens.

First this hits a granularity problem. The shot you may need to make might be very fine. To spot it you will have to have tried a very large number of shots in order to have also tried that particular exact shot. This already becomes rapidly far too slow.

Choosing Which Way to Hit the Ball

To use the emulation efficiently the AI needs to first do some course trial shots to determine which directions are important to look into in more detail, and then return to do more detailed scans, as follows:

  1. Scan at large interval steps in a limited number of shots in all directions to check to see what happens. Note which of these resulted in legal ball collisions or best of worst fouls, where the ball was snookered.
  2. Repeat the scan, but looking at smaller intervals around the most interesting shots found in the first scan. This can also test various shot strengths.
  2. Select the best shot found in scan 2 and then try various shot trials using various strengths and spin to determine the best shot outcome.

The above arrangement is not that hard to construct, so what can go wrong?

Disaster! The program plays like a God!

The first pitfall you may overlook is that the above scheme really works very well, and actually rather too well. Unlike humans the program can find impossible shots by randomly trying anything.

Suddenly the AI can pot 4 or 5 balls all at once, each dropping after been hit by a number of other balls first and maybe none of the dropped balls were ever hit by the cue ball.

This is quite entertaining for a while as the AI shows it could demolish any player it could face, but this sadly makes a very poor opponent for the average game player.

Back to the Design Board: Emulation of Human Play

This is where it gets harder. You need to not just play Pool, but play Pool like a sentient being, not a god. Our approach to solving this was to try and make shot decisions in a manner that emulated the way a human might make such a decision.

The components of game play we needed to assess were as follows:

  1. First a human, even with fantastic foresight, will generally be unable to exactly play the shot they planned. They have to factor in errors.
  2. The AI needs to be able to assess a shot in terms of probability, so that choice of shot takes into account the consequences of missing.

The first stage here is to look at a range of missed shots around the shot that is intended in order to assess the probability of failure.

This adjustment is reasonable, but results in a player that does not succeed in every shot and actually plays quite badly, even if it successfully makes a higher percentage of pots than the human opponent. Now that the AI is missing pots it now needs to consider where the ball might be if they miss. It needs to know that if it does miss, it will not leave the opponent with an easy pot. Even if the AI makes the pot, it needs to leave the ball in a position where it can easily make a follow-on pot.

To make reasonable post-shot positions, the AI needs to evaluate the places that the ball could end up. This needs to separately assess good places for the player's cueball and good places for opponent's cue ball.

In the position below, solid is to play. If we analyse positions from where the 5-ball might be potted, we get the following map, covering a subset of the table:

table map

Linking this with the table screenshot below, the areas where the balls are located are marked in yellow. The good position to have the cue ball to strike the solid orange 5 ball are ranked starting from value 1, shown in dark blue, with increasing colour intensity to maximum value 14, shown in magenta.

pool table screenshot

From this you can see that the narrow channels A and B are visible in the evaluation map. The ideal position D shows a strong patch of magenta, indicating points where cue ball might ideally end up.

This is a simple map, as it shows only the map created for the 5 ball. In practice the AI will create a combined map that maps positions for potting any ball. To generate this the AI has to first identify balls that are candidate to be potted. It then needs to project from each of these balls to pockets to estimate whether these are likely easy pots or not. This will provide a map of where the cue ball will end up after the shot. This effectively provides an evaluation function for the shot, where potting a correct ball is a very large term and getting the cue ball on the right spot is a smaller term. Each shot projected will have this evaluation and this will contribute to the final shot selection.

Of course this evaluation needs to deal with special cases. Planning a shot that leaves the cue ball just on the edge of the pocket shelf is high risk, so needs to be weighted as such. In general leaving the cue ball close to a pocket is higher risk.

The shot evaluation also needs to factor in the nature of the shot that leads to this position. The AI is as happy to bounce off 4 cushions as it is to take a direct long pot, but humans cannot do this. Any shot that hits a cushion has to have an error factor added in, so that it has a greater chance of failing.

Limitations in this System

The above framework has one obvious limitation and that is that the other balls will still be in the same place when the cue ball comes to rest. For many balls this is a reasonable assumption, but some balls may move and other become blocked. To avoid this limitation the AI would instead need to re-examine the table afresh after each sample shot. This would require many sub scans for each shot. This would somewhat slow up the evaluation and actually would mean that the AI would not be able to examine so many shots. This compromise out-ways the benefit of instead being able to examine many shots.

Using this Evaluation for Shot Selection

To make a probability shot, the AI needs to weight the main intended shot with the shots that the player might make if they miss. A shot that depends on a fine cut may well show a single shot that succeeds and shots either side of this that fail. The valuation of the shot will be a weighted sum that averages the shots around the intended shot. If only the single fine cut has a high value then the net value will be much less.

This averaging allows the AI to more easily detect which shots are easier to make and safer. The evaluation can balance this against where the cue ball will finally end up. A safe pot may be spurned because it leaves no follow-on shot. If there are no reasonably easy pots (in general the AI will always find a pot), then the AI could elect instead to play a lower-risk safety shot, simply to either not leave either opponent a pot or even to snooker them.

Modelling different AI Players

The above model is good for allowing the creation of AI Characters as different levels of intended skills will have different levels of error and this characteristic can be directly plugged into the evaluation. Given this, a very strong player may well choose the fine cut as the number of misses they may make in that shot is small, so the high evaluation is achieved. A weaker player might rarely make the shot, in which case the high pot value is swamped by the number of times they would miss.

The general evaluation can easily factor in other characteristics, so that player that simply plays quickly have the AI only scan a limited number of possible shots. Players that favour high power shots can have the emulation bias towards trying higher power shots and adding extra evaluation weight to these. Flash players can add credits for selecting cannons and shots off cushions. Cautious players can add extra weight to the possible opponent cue ball position.

Conclusions

The above system has been out on the market for some time now. From the user perspective the view is that the AI "feels" like a human player, not a machine. Shot selection is key to whether this feels like a real opponent or not and the above AI score well in doing this. Each AI opponent has a description, which is directly mapped into the AI characteristics. This provides the user with some genuine variety, as commented on by a reviewer, as follows:

"...Generally, your artificially intelligent rivals behave in a fashion that harmonizes smartly with their descriptions and skill levels. Indeed, the game works hard to deliver distinct playing styles and diversity. In this way, Friday Night 3D Pool stays fresh when similar games have already grown stale."

Gord Goble - GameSpot 15 March 2004

Jeff Rollason and Daniel Orme - January 2010