Billiard AI, how?

one way you could do it would be to calculate the perfect shot for any given ball configuration, then add some error depending on difficulty level. Or make the computer aware of more advanced shots and combinations depending on difficulty.

You could just pick a number of random angles and powers, simulate them and then take the one which yeilds the best result. Kinda brute-force, but it should get you started quite fast.

Hi

Thanks for your replay, well about computing the best shoot, it sounds cool but seems hard to find a best shoot for any ball config. Could you expand this method a litte?

And about "brute force method" seems really easy to implement, I will check it to get something working!

Regards,
Oscar

I take it you'd need to read/learn/ask some pro about playing billiard and finding out the small tricks and hints about what goes in there and the pros' ways of doing perfect shots, to then implement them into the game.

[edited by - M3d10n on August 10, 2003 7:35:52 PM]

Well, it depends on the rules you''re playing under, but in general:
play just like in real life
cast rays from cue to all the balls of interest, testing for intersections
find a reasonable number of shots you can do
if there are none look for a spot on the table that would be difficult for the other side to shoot from
make a tree thing, uh, graph, I forgot what it''s called, basically the same thing like in tic-tac-toe or chess or the ai for almost any board game really where you look, and look for the best sequence of possible moves, maybe a more advanced version would look at sequences of moves that if they get screwed up would place the other player in a good position
pick one
then shoot

now then, as far as the ai shooting, for realism
I''d use a different pre-trained neural net for each skill level but then again I have no idea what kind of inputs that would take, for starters you might use whatever input the player uses to shoot
so you could just use a random error with different settings for different skill levels

Hi

Thank you so much for your help, and for your replay, I have a lot to learn and a lot to do.

well I guess I will start it simple kind of brute force plus ray tests, and I hope to evole in a more advanced method like neural nets, for now I just want to get some simple CPU Oponent : )

Best Regards,
Oscar

"... make a tree thing, uh, graph, I forgot what it''s called, basically the same thing like in tic-tac-toe or chess or the ai for ..."
alpha beta prunning tree,if I can remember.

AI for a billiard game seems like a particularly tough problem -- an infinite choice of shots, the outcome of a shot is probabilistic and non-linear, and computing the outcome of a shot can be very expensive.

I suggest you repost this question in the AI forum. There are people in that forum that can give you much better answers than you've seen here.

BTW, neural nets are not likely to be useful.

Here is how I would tackle it.

1. Use a game tree.
2. Develop a set of rules to restrict the number of possible shots to a reasonable number.
3. Figure out ways to reduce the cost of determining the outcomes of a shot for AI purposes.
4. Figure out a way to evaluate the state of the game with as few simulations as possible.

[edited by - JohnBolton on August 11, 2003 12:48:22 PM]

I think some of the people here might be over complicating things. I play pool a lot, and if you ask me, theres 2 things that makes a shot easy (or hard, depending on how you look at it):

1: The angle between the object ball-cue ball line and the object ball-pocket line. the bigger the angle (up to 180 degrees - ie a straight shot), the easier the shot.

2: The distance between the cue ball and object ball + the distance betweent the object ball and the hole. the longer the shot, the harder.


You can experiment around and find a good combination of these two. Whats worse: a really long straightshot, or a really short shot at an acute angle? anyway you get the idea. For an opponent, you can make the more skilled opponent better at spotting the easy shots, and his accuracy better. For a crappy opponent, you could for example randomly pick one of the 3 easiest shots, since beginner pool players dont always attempt the easiest shot for lack of spotting them.

This is a rather simplistic way to do it, but its the way i would go, at least for starters.

One thing it doesnt take into account is something expert players do - a big factor of what is the best shot is where they think they can make the cue ball stop after the shot is over to set themselves up for a good next shot. Its easy to picture a situation where the obvious easiest shot is not the best move because making that should would leave the cue ball in a very bad spot for your next shot.

Easy to picture, but not so easy to code.

Some not coding related suggestions.

I suggest you do the AI for 9-ball first. In 9-ball, you always have to shoot the lowest numbered ball on the table so that limits your selection of shots greatly.

Visit pool sites and read instructional articles (if you haven''t). For example
http://www.8ball.org/
http://www.easypooltutor.com/

For example, this might help if you want to take cue ball position into account in your AI:
"I was told long long ago that I should position the cue ball in the center of the table, because it makes the rack easier to run. I was also told to position the cue ball in the center of the table because there are no pockets located in the center of the table. If you are always positioning the cue ball in the center of the table, you don’t figure to scratch all that often. From the center of the table, you should always have a shot. After the break, If my cue ball is correctly positioned in the center of the table, I look for the ball(s) that cannot be made from the center of the table. This ball or balls will become my key shots in the rack, requiring me to position the cue ball accordingly."

http://www.8ball.org/blackjack_running_racks.htm

Some of you guys have touched on the important points. There are two different issues to address here. First, shot selection. Second, how do you make the computer NOT be mathematically perfect?

On the first issue, some of it depends on the game. As mentioned before, in straight pool or 9-ball, your shot selection is a little more rigidly defined. However, you can always define a set of object balls that are available. Once you have that set, you can itterate through them to determine the "feasibility" of the shot. As mentioned before, this is a combination of factors including the angle of the shot and the distance from cue to object ball and object ball to pocket. There are mathematical reasons, that sharper angles are more difficult and that longer shots are hard. Each of those are a function of circular degrees, though, and can be considered with some simple formulae.

With distance, it is simply a matter of the margin of error - expressed in DEGREES - that is available on a given run of distance. Since the pocket opening is a fixed width (which will vary depending on the angle to the pocket - but that is another calculation), you can measure the angle width of the pocket using the location of the ball as the apex of the angle. When using extremes, the issue is easy to visualize. If the ball is sitting on the lip of the pocket, the available angle is almost 180 degrees. When you are diametrically opposed to the pocket, however, the angle is only a few degrees. There is less margin for error on the path of the object ball if it is to enter the pocket.

The same function can be performed between the cue ball and the object ball, but the calculation is a little more tricky. First, one would have to determine the arc on the surface of the object ball on which it can be struck that would place it''s path between the endpoints of the available angles to the pocket. For the most part, this is simply a matter of inverting the angles to the opposite side of the ball.

The difficulty on cut shots comes from how much of that target arc on the object ball is exposed to the position of the cue ball. For a relatively straight shot, most of that arc is facing the cue ball and therefore your margin for error is at it''s widest point. On a cut shot, however, what may be 10 degrees on the surface of the ball may only look like 1 or 2 degrees when viewed from an almost tangental aspect- therefore the margin for error on your cue shot goes up substantially.. Also, remember that the distance from the cue to the object cuts down that angle as expressed in degrees as well.

Since the distance and position of the object ball from the pocket determine the width of the target area on the object ball, and the "perceived" width of the target area on the ball as seen from the cue''s location, the "difficulty" of a shot is simply expressed as the angle width of the possible paths from the cue to an object ball that would yield a successful shot.

(incidentally, the strength of a shot can be dealt with in much the same way)

Therefore, shot selection could be determined by itterating through the available object balls on the table. For each ball, you would need to cast an LOS check to see if they can reach each of the 6 pockets unobstructed. For each ball-pocket combo, you would determine the available target area on the surface of the ball that would put it into each pocket. For each target area, you would then need to calculate how much of it is visible to the cue ball and what the width of that angle is from the point of view of the cue ball (giving you your difficulty level). If you are not worried about other strategy (e.g. setting up for the next shot), then simply select the widest cue angle as your easiest shot.

Of course, given the mathematical perfection of selecting the angles, the trick is now to "fuzzy up" the computer''s math so it is more "human". This can be done in two ways. The first is to fuzzy each calculation above. The second is to get the mathmatically perfect answer and then apply a +/- to the actual angle of the shot attempt. Each way has it''s own advantages and effects - and could actually be used in combination.

With the first method, you are actually affecting the decision making process of the computer - and could cause it to make (realistically) poor decisions. An example would be a tight shot around other balls on the table. If the LOS check and the desired angles are fuzzied up, the computer can be made to SEEM to think it can get the object ball past an obstacle when it really can''t. This is a legitimate failing of people playing the game.

In the second method, you are affecting the execution of the shot rather than the decision making process - and would cause the computer to make (realistically) poor shots. Using the example above of a crowded shot... the computer may know darn well that it can thread the needle and put the object ball between the others and into the pocket - but just mis-cue the ball and put it slightly off line and either strike the obstacles or miss the pocket entirely. This, of course, is also reasonable to assume that a person playing the game would do.

I would reccommend applying both to some degree. In fact, the parameters that you use to fuzzy these calculations would be prime material for the difficulty level tweaks. Likely the most realistic method for affecting these decisions and shot is to use a sine calculation. Errors in perception and excecution usually take on a bell curve form with more samples being reasonably close to the "optimum" and less samples being "completely wild-ass" ones. Applying a sine factor into the calculation does this nicely.

If you were to grab a random number from 0-359 and throw a sin() at it, you would get a number from 1 to -1 with most of the samples falling closer to 0 and only a few being out at the edges of 1 and -1. If you multiply this result by whatever coefficient you need to scale it properly for the task at hand, you would end up with a value that is occasionally correct, mostly in the neighborhoood, occasionally poor, and rarely piss-poor - on EITHER SIDE of the target value (+ or -).

When you apply this to the perceptions and decisions made by the computer, your angle calculations will widen, narrow or shift one way or the other from what is the ACTUAL value. When you apply it to your execution (the cue stroke), your computer player will strike slightly left or right of the proper angle needed for the desired path. You can see how applying the fuzzification to both the decisions and the execution looks a lot like a real pool player, in this case.

There are, of course, more advanced considerations. There would be another layer of calculations entirely if you were to include bank shots or combination shots. Also, most decent pool players are looking ahead one or more shots so they can "play position" by leaving the cue ball where they want it for subsequent plays. This is done much of the time through "English" (spin) on the ball and would require a much more advanced physics model if you were to implement it. However, this should get you started.

Remember, as always, I''m just pulling this out of my AIss, so I can''t vouch for it''s validity or accuracy.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

Nice post Dave... Not sure I agree with the use of sin(x) as a ''fuzzification'' distribution.

This problem is a good example of a planning problem in a linear domain, presumably characterised by uncertainty. Planning agents for such domains utilise a prediction model for the outcomes of their actions and then select the action, or sequence of actions, that maximises some value/utility function over the outcomes of plans.

In this situation, your value function might be very simplistic. For example, a maximum value for getting a ball into a pocket, a minimum value for getting an opponents ball into a pocket and a score in between for every other possible outcome.

However, it would be more realistic to prefer shots that set you up for a later payoff, than ones that give a poor payoff now (so long as the total payoff over that time is maximised). In that way, if you can''t sink a ball, you would select a shot that sets you up to sink a ball on your next shot. However, since the table state is affected by your opponent, you have to do one of two thing: 1) reasses your plan every time it is your turn to take a shot; or, 2) make decisions that take into account your opponents possible actions (utilise a game tree). However, the latter is not practical if there is uncertainty in the transitions of the table state (i.e., in ball movement).

There is a strict mathematical model for dealing with problems like this, based on probability theory. I''d be happy to elucidate this for you, but only if you feel you want to investigate it (since it will take a bit to type in and I''m rather sick at the moment).

Just one quick point... if you do want to incorporate uncertainty into your model, the computations can be performed as simple matrix operations (since this is a linear system), making it very fast to perform predictions and evaluate optimal shots.

Timkin

quote:

---

Original post by Timkin
Nice post Dave... Not sure I agree with the use of sin(x) as a ''fuzzification'' distribution.

---

I didn''t say that it is the BEST way, but it is certainly a way of generating a normal +/- distribution curve.



Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

quote:

---

Original post by ogracian
I am coding a billiard game and actually all works fine but it is only 1P right now, so I am trying to figure out how can I add some AI player but unfortunatly have no clue about how implement a Billiard AI.

So I really appreciate if someone could point me to some methods or docs to learn about it?

---

You might try:

http://www1.mmu.edu.my/~vckoo/p08.pdf


Good luck,
Me
http://will.dwinnell.com

quote:

---

I suggest you do the AI for 9-ball first. In 9-ball, you always have to shoot the lowest numbered ball on the table so that limits your selection of shots greatly

---

This is sort of true, but not exactly. 9-ball, you just have to 'hit' the lowest ball first, but any ball can be dropped. So if 3 is lowest, I don't have to try to sink it, just make sure i hit the 3 first before dropping others. This would mean if the 9 ball is very close to a corner pocket, the best shot is to do a 3-9 combo if possible, ending the game on that shot.

This is a very complicated problem, and has envoked alot of though in me at least as how to do it.

First step is to make a basic perfect AI that, if playing 9-ball, can always sink the 1, then the 2, then the 3, then the 4... using whatever angle/power algorithm you wish. Making it perfect will then allow you to throw in slight alteration to adjust for skill level (+/- to the angle in incidence, slight power fluctuations, etc...).

Once you get the simple down, then, depending on how you coded it, you can begin to tweak it. If you have a "shot selection" class that the AI has a member var of, then a better AI can simply just drop in a better shot selector.

Now, how to have it select the best shot is very rough indeed, as what is considered to be the "best shot" is subjective. Do I drop the easy shot and leave me no open shot? Do I take a more risky shot for better setup next shot or for worse placement for my opponent if I were to miss? Do I purposley tank my shot so my opponent has no options next time? Do I try to hit my 7-ball in front of his 13-ball to block him having an easy shot next time? All these are valid questions and you'd probably receive a different answer from every pool player. I will brainstorm in this and post any suggestions I have later. Good luck, and keep us informed of your progress.


[edited by - Stonicus on August 13, 2003 2:41:29 PM]

Simple way:

1) 0, hit.
2) (-)1 to (-)10 degrees off, miss.
Random those 2.


Dumb way:

1) Turn on your TV.
2) Watch and write down what you see.

.lick

Hi,

Thank you all people for your great responses, it give me a lot of things to try and think about, I will try to implement some of the methods presented here and come back to you when i got stuck again (: ) ), I really appreciate all your help.

Regards,
Oscar

quote:

---

Original post by ogracian
so I am trying to figure out how can I add some AI player but unfortunatly have no clue about how implement a Billiard AI.

---

It sounds like this problem has been solved (or significantly addressed) by this group. So maybe i''m too late to write a long rambling post

My few suggestions:
1. If you don''t play pool, don''t write a pool AI.
If you do play pool, you probably already know
what the AI needs to do. Personally, i don''t
consider this a very hard problem

2. As others have mentioned, you have a couple of
simple problems - shot selection, cue ball placement
and skill selection

3. There are rarely many good shots in pool and there
are often one or two good shots. So that makes things
easier. Always shoot the good shot

4. There are only a couple of types of shots. Pool
players are good at some and not at others. You
should easily be able to decide what type of shot
something is and determine if your AI player is
good at that type of thing

5. i have never understood the "AI" aiming problem.
People always talk about perfect aim and cheating
and fuzzification and all that as if these were
significant issues and as if they were AI issues.
i don''t consider them either. The reason humans
don''t have perfect aim and what not is in part
because the factors that decide where something
goes is out of there control. Randomness is built
into the environment (the gun barrel, the wind,
the ammo balance, and in pool, chalk and dust on
the felt, the shape of the cue tip, the speed of
the ball, the side spin of the ball, etc.).
Your AI should always hit the perfect angle
and hitting the perfect angle should almost never
result in the perfect shot. So in your case,
there should be two factors. One is the built
in and CONSTANT indeterminance of the environment.
The second is the variability of the player
(stroke not perfectly horizontal, cue not properly
followed through, elbow not perfectly locked,
grip not properly controlled, etc.)

People disagree on this, but my advice, don''t go near neural nets. No one should go near neural nets, especially if you don''t know what exactly they are and what they can and can''t do. If you just like them because they sound like a big topic and a cool name, get over the glamor and glitz and realize it''s probably not what you think they are

i traditionally do AI by creating models. In this case, though, you''ll go far with a handful of rules

[u]Shot Rules[/u]
1. Object balls close to a pocket are better than object
balls further from the pocket
2. Straight in shots are better than angle shots
3. Beware absolutely straight in shots. Unless you can
stop or draw, you risk a scratch. Try to cheat the
pocket
4. The harder the shot, the more likely the ball will
not go in. The ball can bounce off the back of the
pocket, the tip of the pocket or the bottom of the
pocket (or ball in the pocket). Pockets are more
lenient the softer the ball is hit
5. The softer the shot, the more it rolls. Hard shots
don''t roll, they glide. This reduces the effect of
spin. It also reduces the effect of imperfections
in the felt. Soft shots will curve/deviate from your
aim more than hard shots
6. A shot that hits only the object ball is better than
a shot that hits the object ball and other balls
7. If a ball you want to hit is frozen against another
ball in a bad way (ie, not a linear shot a short
distance into a pocket), you need to break the
balls out. Hit the object ball and then carom into
the grouping. This overrides rule #6
8. If a shot is so easy that you can''t miss it, save that
shot for a special occassion. A special occassion is
a)when you have no other shot or b)right after you have
a shot that results in a poor leave (the easy shot is
used as a leave shot)
9. If your ball blocks their ball or the 8 (in 8 ball),
don''t move your ball out of the way unless you have
nothing better to shoot at
10. Always know how your opponent is doing. Especially
in 9-ball where the 9 is near a pocket and a combo
or carom could sink it. It might be risky for you
to shoot a combo but letting your opponent shoot
it is risky too (depending on how good he is)
11. A shot close to you is better than a shot far
from you. Distance traveled is a big factor, although
distance from object to pocket is more important
(i''ll say 2-3x more) than distance from cue to object
12. If you do not have a good shot, try to find some of
your balls that will block your opponent and go for
a safety. If you can''t find a block, force the opponent
to make long shots and bank shots or, best of all
a long bank shot from behind some of your balls
13. Try not to shoot down a bank, especially if you have
to cross the side pocket (it warps things and throws
off your shot). If you do, a little right helps warp
the ball back
14. A ball frozen on a rail should never be hit directly.
Hit the railing with wide spin (left if shooting to
the left, right otherwise) and rebound into
the object ball

[u]Leave Rules[/u]
1. Center of the table is best. Unless you have a better
idea, always try to leave the ball in the center
of the table
2. Never shoot without knowing what your next shot is.
Unless you''re an idiot

[u]AI Skill Level Rules[/u]
1. Draw is a skill. Some people can do it 1 in 100 times,
others can do it always. Some can do it 2", some can
do it a table length. Make that a variable for your
agent
2. Ditto follow
3. Smart players know what they''re good at. If you have
a moderately smart player who can''t draw well, he
shouldn''t try to draw. Only an idiot attempts a
follow on a critical shot when he knows darn well
he doesn''t know how to follow
4. Few players can jump. This should also be a variable
5. English is dangerous, especially over long distances and
on slow shots. This, too, should be a skill level
variable
6. Good players plan out all their shots and attempt to
not disturb the table (one shot, one ball moves). Bad
players do not plan ahead
7. Players vary wildly in ability to do side pocket shots,
cuts, long shots, masses (sp?), banks, frozen shots,
off-angle shots, combos, caroms, planning leave,
planning ahead and, as mentioned, draw, follow, english,
jumps and keeping their cue straight. These should all
be skill variables in an agent
8. Players (well, me) hate pool AIs that suck until they''re
losing and then become magically infallible. That sucks
9. Players have shots they prefer and avoid. This gives these
people character. Character makes games fun
10. It is rude to walk in front of someone''s line of sight
if they are shooting. Ditto talking. Jerks, amateurs and
hustlers should talk to you while walking in front of
you while you shoot. Did i mention character is what
makes games fun?

OK, that''s enough to get you started i think

-b

Actually, Baylor touched on something that I hadn''t put into my shot selection algorithm... scratch potential. All it would take is to calculate the vector of the cue ball after contact and see if it intersects a pocket.

As much as I like Baylor, I think there was a major drawback to what he provided. He gave some generic "rules" to follow rather than narrowing the problem down into the specifics of what the problem REALLY is. For example,

quote:

---

1. Object balls close to a pocket are better than object
balls further from the pocket
2. Straight in shots are better than angle shots

---

While those are two great axioms for pool players, my analysis above explained and mathematically dealt with WHY those 2 statements are true. It is not enough to list criteria and then say "make is so!" in your best Patrick Stewart voice. You have to be able to boil things down to the most basic, mathematically (or logically) relevant elements. THAT is the hard part of AI.

As we look around us, we can often disect, diagram, and explain a lot of behaviors and phenomena in our native tongue - and often speaking to an audience who "gets" what we are saying when we talk about stuff. However, the computer doesn''t "get" anything that we don''t provide it.

To refer to the above, we can all see that the more "green" between the ball and the pocket, the harder it is to get it in said pocket. We have been raised on that concept since we were kids and have all internalized it. One way of approaching that would be to invent an arbitrary "distance difficulty" factor where we measured the distance from the ball to the pocket and gave it a rating of some sort. That would be effective to some degree, but highly subjective. We could invent yet another value that expressed the increased difficulty in pocketing balls where the angle to the pocket was great... such as trying to make side pockets from the ends of the table. We could combine those 2 subjective factors into one that helped us to analyze the position of the ball (cue position not being relevant yet). However, this doesn''t REALLY express what it is we are trying to solve in the simplest - and most objective - terms possible: The REASON that both of those two shots are difficult in the first place.

As people, we KNOW intuitively why those shots are hard - "the pocket looks awful damn small from here!" We KNOW intuitively that if the pocket looks small (although we know it is really the same size), it gives us less "wiggle room" on our shot. Why is that? Again, as I solved before, it is about the available ANGLE from the ball to the two corners of the pockets AS SEEN FROM THE BALL. There, without any subjective values of what is hard and what is not, we have solved both of Baylor''s first 2 points in a single value (the result angle in degrees).

Regardless of the arena - pool being the current one - THAT is the skill set that is needed to solve MOST ANY problem that AI presents us. I''m not being pompous here, but as you see in my signature - and the slogan of our company, I am always "reducing the world to mathematical equations." Only when I have achieved that does the computer really "get" what I am trying to explain.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"