Pool Billiard AI

Im implementing a pool billiard game in Java and it al开发者_如何学Cl works fine. It is a multiplayer game, but nevertheless, it should also be possible to play it alone. For this purpose I'm trying to implement a simple KI. At the moment, the KI choose just randomly a direction and a random intensity of the impulse (don't know the correct english word for that). Of course this AI is very poor and unlikely to ever challenge a player.

So i thought about improving the KI, but there are several hard to solve problems. First I thought of just choosing the nearest ball and to try to put it directly into the nearest hole. This isn't that bad, but if there other balls in the line between, it isn't really working anymore. Additionally this dosn't solve te problem of calculating the intensity of the impulse.

So are there any general advice? Or any ideas? Best practices?

---

How much CPU time and memory does it take to calculate the results of one "move" of the game? Can you afford to analyze more than one move? If it's relatively cheap to do, just pick N random directions/impulses, calculate the results and pick the best one. You may eliminate some "tricky" cases, when ball goes to pocket after too many collisions. Also, to simplify, you can limit the simulation time for each move (i.e. don't wait until all the balls stop, just calulate the first T seconds).

This way, you can have computer players of different level - the higher N (and T) correspond to higher play level.

---

Depending on the game of the billiards you usually have two tasks

Assess the situation on the table (get possible shots)

• In perfect scenario (perfect aim, perfect shot) all possible shots are equally hard and if you consider only direct shots to one ball there will be only maximum of 6 holes x n balls situations that you need to analyse (analysing simple canons - hitting two balls requires only extra n^2 balls x 6 holes situations). For each of these situations establishing if they are possible requires simple analysis (unless you are doing very realistic collision simulations). So in very simple simulations you might want to try to construct all possible situations and rank them. To analyse shots off the bank you might want to mirror the balls and holes.

• Alternatively in enumerating the possible situations you might simply do a line scan of the table, marking the areas which are illegal for shots and enumerating and building potential shots like...

angle1, ball1, pocket2
angle2, ball1, pocket3
angle3, ball1, ball2, pocket1
angle4, cushion2, ball2, pocket1

• For nicer AI you want to simulate imperfections, for example the shot is played by hitting a ball at some point x (maybe defined as an angle away from direct hit), let's assume that there will be an error (due to bad aim, or bad hit, or anything) of dx - this in turn will cause the ball to have an error in direction which will increase with the distance to the pocket. This gives one way to rank the shots by difficulty - the sensitivity of the shot in terms of error in aim/shot (some shots are easier then others). This will depend on the length of the path from white to the ball and from the ball to the hole.

• One more thing to look at is the risk of white ball going in the hole, or other illegal shots

Choosing the shot (not only based on difficulty, but also on potential gain)

• you will need to look at the strategy as well (an easy shot might leave you with nothing in the next round)
• it is not only how easy is it to make a first shot, but also how hard will be the second shot (for this you could run the assessment of that simulated situation again, and here you could make the player stronger or weaker depending on how many shots he is able too look ahead; you can also give your player personality - looking for solutions depth first or breadth first)
• in choosing strategy you should look for the combination of shots whose sum of difficulty is minimal (you might need to assess importance of the later shots taking into account probability that you will miss)
• depending on the game you might consider introducing safety shots which are purely positional game and the aim is not to pocket the ball immediately but to either force the opponent to make a mistake or to ease a situation for yourself (there are other situations when playing such shots would be beneficial - for example when you can not hit anything but would need to split few balls or move them away from cushion). in this case you will need to start from the end.
• all this gets much more complicated with realistic physics: spins, realistic collision, bounces, realistic cushions, cue slips, etc..

---

I can think of two broad approaches.

1. Make a list of all possible cue positions surrounding the cue ball and force levels, and then search the list to find the first one that lets you sink a ball. That's a fairly large list, you can trim it by using a small number of force levels and by excluding any "obviously" bad shots.

2. Work backwards -- look at each ball on the table, and see if the cue ball can be made to contact it. Then work out the correct cue position and force level to make it go in the hole. You can expand this to search a tree for multiple-ball shots.

I like solution 1 the best; it lets you find situations where you would be able to sink two or more balls at one time.

---

You might consider as displaying the balls as a weighted graph maybe. You could put in the pockets as special nodes. You then chose which ball to put, or hit, depending on the weight of the path from the cue ball, to the specific ball and to the pocket. The intensity of the impulse can also be set by using the value of this weight. You can then use a physics engine to determine if the shot is at all possible. I have never tried such thing, so everything is theoretical and I do not know if it is at all practical. Also, such method does not include having the cue or the other balls bouncing around, so basically it will cater only for straight shots.

---

I would think it's hardly random. You'd want a physics engine to model the interactions of cue, balls, bumpers, and pockets. It feels less like AI and more like physics to me.