How to do pool/billiard AI ?

Well actually I only need motion on XY-Plane(no rolling motion…cuz flat pieces as shown in the fig. below)

As in fig. During AI’s turn it needs to pit a piece (aka balls in pool) in hole, it only tries to pit its white/black pieces only.

Now the Final AI Function should return 3 values

1. Striker’s position on the Strip.
2. Striker’s Aim’s position (where to put cross-hair….where to hit !) and
3. Initial velocity (How hard to hit !)

Now lets assume for-now 100% hit rate….later random garbage value can then be added to these 100% Hit value to get lower difficulties of AI(missed hits !).

Now the Striker can hit a piece in a hole
1. Directly (Striker hits piece, piece falls in hole).
2. Indirectly (Striker hits a piece,……. that piece hits our intended piece then it falls in hole).
3. Rebound Shot (Striker hits a board wall and then rebounds to hit our intend piece which then falls in hole)

Now I was thinking like

Loop through all holes
{
For current hole -> Loop through all available piece to hit
{
Now if( a line passing through curr hole’s pos and curr piece’s pos also intersect Striker placing
strip and does not hit any other piece on the way)
{
Well, we got an answer for 1st case Striker Hit

Add this Shot to Available shots array along with its “Shot Weightage”.

Now How to get those other case also ?
}
}
}

Then finally shot with highest/lowest Shot weightage will be chosen as current shot.

This will be required because we will be looping for every piece on board and every piece will probably be shot to hole using 2nd case of Striker Hit(multi-level collisions)….and we don’t want our AI to pull “Super Human” or “Vulcan” or “Rajnikanth” precision shots.

So how to put weight to these selected shots ?

Now this is what I came up with. Anyone with any other brilliant idea…….And people please talk !

Some Points To Note :

1] Now there is a StackOverflow post with exact same heading...(So the NEW in the Heading)
http://stackoverflow...ool-billiard-ai
But the guys there have discussed "What needs to be done"......we want "How" so a functional code can be put together.

2] NO we cant go for "RandomShots>>genetic algo>>assessed using neural network" because we are in very limited CPU time and memory budget..Mobile platform.

3] We need to find those shots directly(without any kind of simulation) using maths,trigonometry,distance formula, etc

4] For velocity...we know final max velocity allowed to pit a piece so we just go on adding the amount of velocity reduce
due to friction and between collisions....to get initial velocity to fire the shot, which will be also in limited so if required initial
velocity is greater than "max allowed initial velocity" than assign Highest/lowest "Shot weightage" to current shot.

Thanks in advance for the patience.

This is a tricky one, unlike most of AI it's a very continuous field, so hard to explore well. My suggestions:

1. Put in specific code for direct shots. Probably as simple as looking for any ball within x degrees of a straight line to any pocket. Check for obstacles, shoot.
2. Put in specific code for rebounds. Consider targets both before and after rebound. Could get hard if you allow multiple rebounds.
3. Crap shoot at a big bunch of balls, like a break. Very hard to predict the behaviour under physics, so perhaps just try each option with a few strengths and simulate the outcome to see if it's a good idea.
4. If you want a human-like good player rather than simply a computer-like good player, try some sort of minimax 1 or 2 levels deep to allow snookering your opponent. Based on the skills of computer and human odds of success could be assigned to each branch.

I would think that spin makes everything 10 times more difficult. Probably calculable with the right equations, but creates many more situations to explore.

well thank you jefferytitan for your input.

the 3 point in your suggestion point to "running simulation to check how it looks", well as i already said that is out of question as pointed
out in my "Some Points To Note :" section point no 3.

although your suggestion 1 & 2 looks good but i need "Striker Hit" type 2 shots(Indirectly aka Multi-level collision) also....without running simulation

Similar to step 1 you could check all the other balls and see if they could hit the ball you want to go in a pocket. Then just see if you can make the second ball hit into the first ball with the striker.

well thank you jefferytitan for your input.

the 3 point in your suggestion point to "running simulation to check how it looks", well as i already said that is out of question as pointed
out in my "Some Points To Note :" section point no 3.

although your suggestion 1 & 2 looks good but i need "Striker Hit" type 2 shots(Indirectly aka Multi-level collision) also....without running simulation

I will have a think about how one would do type 2 shots analytically. Regarding type 3 shots... it is my opinion from reading a lot of literature that this is impossible without running a simulation. The traditional approach for physics engines AFAIK is iterative solvers. If there were an analytical solution the physics guys would be all over it. My suggestion is to accept the simulation and think outside the box. For example, run the simulation with increased velocities and reduced iterations. Add a "talking smack" component to cover while you calculate, e.g. "oh man, you really snookered me here!", "can I get the 7... no...", etc. A human-like delay could be turned into a feature rather than a bug.

I think that doing a simulation of many randomized shots and then picking the best one would work pretty well. If you calculated where the balls would all end up before starting the animation of the players shot you would have the entire graphical animation period to do some calculations along with the normal computer move making time. With 100 shots you would probably end up with something decent especially if you have parameters like minimum of 50% power which would prevent 0 power options from taking up computing time.

I think that doing a simulation of many randomized shots and then picking the best one would work pretty well. If you calculated where the balls would all end up before starting the animation of the players shot you would have the entire graphical animation period to do some calculations along with the normal computer move making time. With 100 shots you would probably end up with something decent especially if you have parameters like minimum of 50% power which would prevent 0 power options from taking up computing time.

I think that randomized is a waste of CPU. You should at least analytically determine that you'll hit at least one ball before running a simulation. Good point, you could do some calculations during animation of the player's turn (assuming you can determine the outcome of their turn quickly). You'd end up in trouble if the normal speed physics for their turn gave different results than your estimate that you based your turn on. You could run the physics high speed, record the positions, then perform a simple animation of their turn with no physics.

Standard pool AI doesn't work from the cue forwards but rather from the pockets backwards. For each pocket, check the apparent angle to each "ball" to see if it is feasible, then check to see if that unblocked, then check to see what the angle to the cue is (feasibility again). Rate each shot based on difficulty and pick the easiest (or use a weighted random to mix it up a bit).

For actual performance, there are plenty of places you can fuzzy things up so that the AI doesn't look perfect and can even miss. Mostly, you just need to put some noise in the cue angle and the rest cascades through the shot process.

Standard pool AI doesn't work from the cue forwards but rather from the pockets backwards. For each pocket, check the apparent angle to each "ball" to see if it is feasible, then check to see if that unblocked, then check to see what the angle to the cue is (feasibility again). Rate each shot based on difficulty and pick the easiest (or use a weighted random to mix it up a bit).

For actual performance, there are plenty of places you can fuzzy things up so that the AI doesn't look perfect and can even miss. Mostly, you just need to put some noise in the cue angle and the rest cascades through the shot process.

I can see how that might work for a simple situation like cue ball + x rebounds + target. I still doubt that a perfect pool player is possible when multiple collisions are involved. The extreme would be a pool break, where I think only shoot-and-pray or hardcoding targets/strengths would work.

I also think that the probe shot method is the simplest and the most flexible.

Sure, it takes time for the AI to calculate, but so does thinking about a shot in real life. I wouldn't be worried if it took say 5 seconds for the AI to think.

I once made an AI for a scorched earth clone. It took some 20000 probe shots in the worst case (with no early exit). Probe shooting included actual simulation of the bullet, checking with collision with the ground, and a lot of additional checks to rank each shot. collision detection was pretty much pixel color checks all along the trajectory (it was a DOS game). Getting the pixel color was dead slow on DOS and 640x480 resolution (because there has to be memory paging, since 640x480 cannot fit in the 16 bit VRAM address space).
Even with this dead slow method, it took at most 6 seconds for the AI to think.

Probe shooting even solves the complex shoot problem, in my game, AI could take pretty badass shots on bouncing border games with multiple bounces and nukes or lasers.

If you optimize the collision and simulation a bit, and use a bigger virtual delta time for the physics, or even a bit simplified physics (this also adds some error), probe shooting is feasible.


So again, for a turn based game, where the AI doesn't have to be anything real-time, I wouldn't be concerned if it took seconds for the AI to make a decision.


EDIT: maybe I'm wrong and you are using complex physics. Even so, I'd do some measurements. Probably calculating the positions after shots with the same starting conditions (same positions of balls, same angles etc), but with radically different delta times, and see how delta time affects the resulting positions of the balls.