February 20, 2015 at 09:43Billiard bot: the history of creation
Hi, habrahabr! This article is devoted to a detailed description of the process of creating a billiard bot, which, without human intervention, plays the game pool billiard and makes decisions, earning points. The article will be useful and interesting to people who are fond of creating bots and programming.
We all have favorite games and sports. It’s great when the first coincides with the second. In addition to my hobbies for sports and sports projects, I also love some computer games. One of my favorite games, both live and virtually, is, of course, billiards. Billiards, pool, snooker ... whatever you like - I love them all! I share the opinion of many that, for example, snooker is “non-discrete” chess. It’s not enough just to hammer a sequence of certain balls into the pockets, there is also an incredible strategic struggle. The fight for snookers, for positions ... and what fantastic equipment professional billiard players possess - I just keep quiet in a rag.
The advantages of this undoubtedly aristocratic game can be listed for a very long time. But let's get to the essence of the article. My favorite game of billiards for five years now and to this day is Pool Pooliard on Facebook. It is famously made not only aesthetically, but also technically. With the naked eye you can see a cool written physics engine, thoughtful gameplay, client-server validation of actions, error handling, design, statistics system, store, chat in the end. The game was clearly made by the pros, and it is in the tops. It is very nice to play it ... and win!
For a long time I played it, until the thought came to my mind: “ Bah! Yes, it’s perfect for creating a game bot for it!. It's nice to win, but to win with your robot is automatically double! Winning against paid players who have acquired a navigation system and tightening the cue ball, demonstrating blows that are fantastic in technique and beauty, leaving them with saggy jaws is triple pleasant! Plus an automatic set of experience points and coins: left the robot for the night, in the morning you are the best! In addition, I, as a spectator, love to watch billiards for hours. In general, yes, I decided!
Before starting the creation, I, having at that time already quite a lot of experience in playing Pool Billiard, carefully thought out everything with a pencil and a piece of paper in my hands. Of course, it is impossible to predict everything, but the "skeleton" was created. Bring in the skeleton! To create the bot, I used C ++.
Writing and debugging the code in the optional mode in the evenings took me almost four months. Agree, it is difficult to debug something on a closed system, especially when you need to test some rare or exceptional case that happens in one of a hundred parties. I can’t frivolously arrange the balls and simulate this or that situation on the table.
I realized that the bot will interact with the browser through a complete simulation of a person: pattern recognition and imitation of human input: mouse, keyboard. Thank God, you don’t have to enter captcha before each hit :) So I did: I like systems simulating human behavior, from which browsers are so defenseless!
This means that you need to be able to find the region with the game on the screen, be able to interact with it, receive certain signals from the game and process them, and, most difficult, be able to correctly execute strikes. I made a list of necessary actions that the bot should be able to carry out (for example, enter a certain game, send a certain message to the chat, put a ball at a certain point, check the number of points, strike a certain force at a certain angle, break a pyramid and so on) and a list of certain signals that the bot must be able to recognize (for example, our turn began, the round suddenly ended, the enemy gave up, there is little money, and so on). In total, about forty situations turned out; some were asynchronous, some were not. I programmed and, as far as possible, carefully tested each of them (about this separately),
I decided that the general logic of work would, of course, be a state machine. First, the bot is calibrated for the game, then it calculates the amount of money available, then it decides which bet to make. The following is the gameplay itself, after which the bot again decides how best to enter a new game. The simpler the logic, the more reliable and predictable the system works. And it’s easier to catch bugs.
The detailed logic is harsh and bearded, it contains a whole bunch of branches and possible situations. It all starts with the fact that the game starts and the bot itself. The game (browser window with the start screen of the game) is on the screen. Its coordinates are recorded and this serves as a starting point for all subsequent mouse input and recognition of the situation.
Further, the bot determines the amount of my money in order to understand what bets can be made. After choosing the size of the bet, the bot enters the corresponding room and the game begins. It can end at any moment, since already from that second the opponent can close the browser, and, after a certain timeout, our round is invalidated. An opponent can also leave the round at any time: in this case, the victory will be awarded to me. Recognition of all these situations begins right here.
Further, the server randomly determines who will start the game: me or the opponent. The bot is waiting for the start of its turn. For the entire course, only 20 seconds are given. During this time, you need to have time to determine that the move is already mine, count balls, glasses from the table, correctly recognize them, find the right blow and have time to take it.
The bot itself determines whether it will break the pyramid, and for this case it has a couple of simply awesome options. If you don’t need to break the pyramid, the bot will recognize the coordinates of the balls on the table, which balls it can score (colored or striped or any_ except black or only black (judging by the situation in the game), the number of points and the whole-all-other gimmick. After that, the bot calculates and strikes.
The bot, in addition to basic activities and not to the detriment of the game, also likes to chat with opponents. Usually, such a temporary window occurs immediately after the strike. This is where the bot writes some chat message to the opponent. After the blow, either the move goes to the opponent, or we continue to play, or we won, or we lost. The bot is waiting for a sign of one of these situations. In case of defeat or victory, the bot closes the current window of the game and the summary window of results and proceeds again to the recognition of the amount of money.
A state machine is generally something like this.
I read the entire screen context in C ++. The game is on the screen is very simple. Since the design of the game is not "rubber" (it does not stretch), but fixed, then all the elements are constantly at the same distance from each other. So, you need to find on the screen with the game a certain static element that never visually (graphically) changes, and calculate the coordinates of the beginning and end of the window relative to it. Having made a couple of screenshots and processed everything in Photoshop, I did so. I made a simple and reliable table recognition marker. I decided to abandon the idea of recognizing the coordinates of the window before each hit. This is stressful and takes away the precious moments of calculating the perfect blow. Therefore, the bot determines the position of the game only once - at startup. After the bot has found the game window, it is strictly forbidden to move the browser window even by one pixel: in the process of playing on the pool table, an inaccuracy of even one pixel with long strokes accumulates a monstrously huge error. From here all blows will be incorrect.
A game marker is an immutable part of the image of the game window:
Here I was just lucky. I didn’t have to put a sniffer on my browser and listen to the broadcast of the game to determine the amount of money or recognize characters from the screen. Everything is prosaic: the fact is that in the game not everything is done on a flash. The element with the sum of my coins is a simple text field that is easily highlighted with the mouse. I just imitate the following: I bring the mouse to the beginning of the field, hold down LMB, move right to the end of the field, release LMB. As a result, the bot simply allocates a field with money. Then I copy it to the clipboard, delete special characters such as spaces, commas and periods ... and that’s it! The amount of coins in my pocket.
Game coins are just a highlighted field:
There are several rooms for the game, each of which contains a certain rate (entrance fee). Two opponents enter the room, placing each, for example, 100 coins. The winner receives a prize of 140 coins (not 200, as you might expect (this was done by game designers in order to constantly lose a lot of money from the game, and people were forced to use the store and buy coins for real money and play, or wait until the daily wheel of fortune brings them coins for the game)). The loser leaves with nothing. The logic is simple.
In cheap rooms every rabble hangs forever: beginners, losers, and so on. For the sake of fun, sometimes pros go there. The probability of winning there is very high.
In more expensive rooms, you can meet middle-hand players, sometimes newcomers go there stupidly, sometimes superprofiles go down there (apparently to tear someone to shreds). The probability of winning there is approximately 50%.
In expensive rooms, the elite hang out: either superprofiles, or payers with a purchased navigation system, tips and so on. Most likely, there is a loss there.
The bot has several modes for choosing a bet: forced modes (when the bot always puts the amount that I indicated to it) and auto mode. Auto mode is made in a very interesting way. I collected the statistics of winning by the bot in the rooms of different bets and based on it I wrote a very interesting program. It only gives out several numbers, but very important numbers. These are the so-called threshold amounts of coins. For example, if we have 300 coins, the bot has the right to play only in the first room, but after overcoming the threshold amount of 740 coins, the bot has the right to play in the first and second rooms. Of course, the bot seeks to play in the most expensive room.
So, the program is interesting in that it automatically selects these same threshold values according to some algorithm, which it itself further uses to predict the risks of a subsequent loss. It simulates millions of parties and decisions about playing in a particular room (shelling of Monte Carlo) and issues the correct border quantities of coins. Moreover, I noticed that the algorithm is convergent!
Directly entering the room is done by clicking on a specific part of the screen where the button for entering and making a certain bet is located.
After choosing a room, click on the appropriate button:
Here again, markers come to the rescue. On the game screen, everything is just as static as on the main one, and all the elements are always in the same places. This is a panacea. My opponent’s avatar, as well as statistics, a message box and other items, are always on the left. Mine is on the right. I also created a simple and reliable marker for determining my course. As soon as the bot reads it, it proceeds to the next phase.
Here is a whole saga in three acts. I will not describe all my two-month suffering on this issue, I will describe what is happening only briefly. From the table image taken at the time of recognition of the balls, the image of a clean table, carefully prepared by me in Photoshop, is subtracted. Further, there are high-contrast zones, on which there are spots of balls. For certain specific light markers, taking into account the inadmissibility of overlap, the centers of the balls are located. Then they are sorted by the contrast of their brightness to prevent debris from entering the screen (cue, inscriptions on the table). After that, the position of the balls is verified by checking the shadows around them. Finally, we got a list of the required number of ball centers in the image.
As soon as I tried to look for balls differently! And with the help of defining shadows, and with the help of the Canny border method, and with the help of ingenious classifiers: all these and many other methods were very ineffective and inaccurate compared to the method written by me personally. I even set Wolfram Mathematica on statistics, but this did not give me a particularly clear answer. Maybe bad set.
But it’s not enough to know the centers of the balls, you still need to determine where the stripes are, where is solid, where is white (cue ball), and where is black (eight) balls. There was no limit to unlimited fantasy, because it was necessary to unify a whole bunch of problems. For example, a green ball merges very strongly with cloth, and if the striped yellow ball stops so that its white pole is directed strictly towards the camera, then it will be almost as white as the cue ball is. The subtleties surfaced a whole billion, and with all of them I had to fight.
I went over a whole sea of solutions, discarding them due to lack of accuracy, and finally I wrote the most accurate of them. I got a decisive tree, in each node of which there is a self-written classifier. For each ball found, I determine the color characteristics: average {R, G, B}, average {H, S, B}, the brightest and darkest color without taking into account color spots. Then I definitely find the cue ball as the whitest ball. Next, I try to determine the eight as the darkest ball. After all, you need to separate the colored from the striped. But the casket was not easy to open: I compiled three-dimensional tables of samples, photographed balls a thousand times in attempts to train the network, but still I was not able to build a hyperplane uniquely separating the clusters of solid and striped balls. Anyway, there are errors. For this case, I made a small error-correction-on-the-fly. More about this below.
Here, various orthonormal basis bases of turns, cluster statistics with predefined color of balls, and other mathematical basis were used, but it was not that ... and not that ... I went through a lot of options. In the end, our bot has a certain set of balls with their fairly accurate characteristics: there are always white and black balls, and sets of solid / striped. Believe me, not a little work has been done.
Here I was relaxed: we create a simple classifier of the position of the pyramid (each ball is at the point of the pyramid) and if our move and our move is the first, then we break it. But it was not there! Something didn’t work! It turns out that cunning programmers added some noise to the initial positions of the balls in the pyramid. Clever! Otherwise, it would be possible to record an “ideal game” - an unmistakable series of punches leading to victory, and, constantly reproducing it, win. But they provided such protection here. Having slightly adjusted the classifier, I achieved success in recognizing the moment of breaking the pyramid.
When it is necessary to break the pyramid, the bot selects one of several luxurious options for breaking tightly programmed into it and implements it. Almost all of the above options make one or two balls immediately fly into the pockets. Well, or nakraynyak very much scatter balls on the table, which is only to my algorithm.
Near my avatar and opponent's avatar there is a stack of clogged balls. It is a strip with clogged balls placed there with a slightly smaller radius than on the table. However, what to do? Recognizing the balls on the table alone is not enough to understand which series I play - striped or solid. So, it is necessary to recognize not only the number of balls in the stacks, but also the balls themselves! Pffff ... the algorithm of "subtracting the table" does not fit here, and the sizes are not the same.
... by
an incredible effort of will, I forced myself to write another recognizer
...
and the second incredible effort is to combine both of these recognizers into one universal recognition function. In fact, I had to write everything from scratch. This is the problem of insufficient planning. But now I indicate the region and size of the balls, and at the output I get the coordinates and characteristics of each ball! The victory of the mind!
Having determined the number and type of balls clogged by me and the opponent, the situation on the table becomes completely deterministic. Now the bot knows what and how he needs to score:
A strictly deterministic algorithm is programmed here. If we break the pyramid at the beginning of the game, then we can hit any ball (anyway, we won’t get into the black one - it’s hidden inside the pyramid). If the first move has already been completed, we look at the number of balls scored. If there are none, you can beat anyone except black. If only the enemy has it, take the opposite type and hit. If I have (and not only mine) - beat the same type. Finally, if I have clogged all the balls in my series except black - score black. All! ;)
Sometimes the opponent mows. In this case, the rules of the game oblige me to free kick: I have to put the cue ball anywhere on the table and strike. So, there are two problems: recognizing the opponent's foul and correctly setting the ball under attack.
The first problem is solved relatively simply. In a separate thread, a certain tracker is trying to find such a situation: now the opponent’s move and the “Fault!” Marker has appeared on the table. In this case, he informs the main stream that the next blow must be done with the production.
The second problem - the formulation problem - is solved a little more complicated. Although, I confess to you, friends, here I faked. I'm not trying to put a cue ball on some line of clogging one of the balls in my series. Not. I'm just trying to put the ball universally - as close as possible to the center of the table, where there are no obstacles. First, I recognize the situation on the table, then I calculate the nearest point, not closed to the center of the table, and put the ball there. While staging is in progress, I’ll almost certainly calculate the perfect shot.
So, before me there was a task for a given time with a given configuration of balls on the table and a given rule of striking, to calculate all possible effective punches and choose the best one among them. Possible values of the set time: {20 seconds}. Possible configurations of balls: them? .. Possible rules for striking: {any except black, only solid, only striped, only black}.
Before you get into the jungle of billiards, you must first understand the physics of what is happening. What do you need to score a ball?
To do this, draw an imaginary segment from the center of the pocket to the center of the ball and slightly extend it further to the intersection with the border of the ball. The intersection point is the point of impact. If you hit the ball on it, it will fly into a pocket.
In order for the cue ball to hit this point, it must not be directed to it, but to the point that is located from the point of impact by the radius of the cue ball further along the same imaginary line.
Well, then, I think you have already caught. In order for the cue ball to fly where it is necessary, you also need to build a line from the target point through the center of the cue ball and cross it with the far edge of the cue ball circumference.
So, from here a general rule is born: in order to direct any ball to a given point A , it is necessary to connect the point A and the center of this ball with an imaginary line and extend it to the intersection with the far boundary of the circle of the ball. This is where you hit the ball. I decided to make the bot’s game strategy the same as for people: the bot selects one ball under attack and hammer it. All. The simpler the system, the more reliable and easier it is to debug it.
The pockets are different. And getting into them is subject to different laws. For example, you can get into the corner pocket in different ways:
But for each pocket I managed to find a universal point, rolling the ball to which from any place entails getting into the pocket:
I programmed the bot just to aim at these points. The only limitation that the pockets of long sides impose on themselves: the flying of balls into them is possible only in the casement of 70 degrees. It is also embedded in the code.
I decided to abandon the rebounds. No no, don’t be scared, not in the sense, of course;) To build such a simulated space in order to forget about rebounds altogether. They are in the game and remain, but they will not be in space. I only worked on the solution to this problem in the evening. I realized: the collision of a ball of radius R with a side of thickness 0 is the same as the collision of a material point of radius 0 with a side of thickness R :
This means that the calculation of physics can be significantly simplified: in terms of trajectories, we will work not with balls, but with material points. Further: according to the laws of the genre, the angle of incidence of the ball on board is equal to the angle of reflection. As in the case of light rays and a mirror surface. You ask: what does it have to do with it? I will answer. The collision of a material point with the side (ricocheting against the side) is the same as the continuation of the movement of the material point through the side into the space mirrored from this side. That is, if the ball could “see” forward in the direction of its movement, and the sides were mirrors, then this would result in:
In such a “mirror-board” space, I no longer need to think about ricochets. They flow by themselves. Plus, we connect the rule of motion of the material point, and it turns out generally luxurious.
In the simulated space, all strokes are straight lines, no rebounds. But on the table they already are.
Great, a lot of work done! But there is still an extremely important question, which we did not touch at all: what is the maximum way a cue ball can go? What is the energy in it? I do not want to hit balls every time with all my might; this will put the cue ball at risk of accidentally rolling into a pocket. I want to very accurately and accurately calculate the impact force. To do this, I need to know at what length of the cue from the cue ball in pixels the minimum impact occurs and how long it is, and at what length of the cue from the cue ball in pixels the maximum impact occurs and how long it takes. I also need to know what energy is taken from the ball when it hits the side. Now it remains to find out all this. With minimal strokes, everything is prosaic: it is measured at any moment. With maximums it is much, much more complicated. The diagonal of the table is not enough even for an average hit, so I clearly can not measure the length of its path.
I came up with this in two cases: horizontal and vertical. After making the appropriate measurements and equating the equations together, I would get the full length of the maximum trajectory of the ball and the coefficient of energy quenching on board. So I did. I waited for the moments when the opponent got a foul to gently put the cue ball right to the edges of the sides, so that nothing prevented the horizontal and vertical movement of the cue ball. And twice he struck with all his might: once horizontally, the other vertically. He took off his indicators: in a vertical impact, the cue ball bounced off the long sides 8 times and, having reached the rest of the energy for some other way, he stopped. With a horizontal impact, the number of rebounds was 5 with a tail. From here, knowing the dimensions of the table, it is easy to obtain equations, numerically solving which we obtain the full length of the maximum path,
Let x be the maximum length of the ball’s rolling path without collisions with the sides in pixels, and p <1 the coefficient of energy loss when hitting the side at right angles. The width w and height h of the table in pixels are known. Consider the horizontal case:
We equate the last equation to zero. Similarly, we obtain the equation for the vertical case. Solving this nonlinear system of two equations with two unknowns numerically, I got the desired x and p.
Of course, the depth of impact can be any, if only enough energy. But due to the accumulation of errors, I decided to stop at number 4, that is, the maximum number of objects involved (including pockets) is 4. My cue ball can hit ball A , which will hit ball B , which will fall into the pocket. And then (!) The accuracy is lost so much that I introduced a number of restrictions on such attacks. They should be without ricochets about the sides, the distances between the balls and the pocket should be approximately equal and the angles of attack are close to elastic impacts. But such a fantasy does not shine for me yet:
All suffering and calculations will be in vain if even after an enchantingly masterpiece hit our cue ball rolls back and falls into a pocket. Even through a rebound. Therefore, I immediately discard such blows from consideration, after which the bot may fail. To calculate the rollback of the cue ball, the strength and direction of the rollback after hitting the cue ball against the target ball are calculated. I thought everything would be simple: we calculate the remaining energy after an elastic / inelastic impact, how far and in which direction the cue ball will roll back, the direction using the cosine of the relative angle of attack, and see if the trajectory passes through the pockets. But no, a pitfall awaited me here too. After conducting a series of tests, I noticed that the actual rollback is significantly different from the simulated one.
Both the game’s navigation system (yellow) and common sense with calculations show that the cue ball will roll back along the green line. However, after a hit, he rolls on red:
This is a trap. It turns out that the game also takes into account the inertia of the torsion of the ball and its direction. I had to write and test the nonlinear function of calculating the rollback trajectory for almost four evenings. Such trifles infuriate, but in the end it turns out that these are not trifles at all. I was able to determine a less accurate function only by trial and error. But I did it! Now I can safely throw out the blows that lead the cue ball through the pockets as a result of the rollback.
As a result of analyzing the table configuration, I received a collection of a large number of possible strokes. But how to choose the best of them? It is necessary to turn on the brain and evaluate each impact parameter. Logically, what would we like? It would be desirable to minimize the number of rebounds from the cue ball to the target ball: each rebound introduces a small, but an error. The distance from the cue ball to the target ball should be as small as possible, but not quite small, in order to be able to accurately aim. Oddly enough, these are two different conditions. Think about it. Further. The distance from the target ball to the pocket into which it should fall should be as small as possible. Of course. And this path should contain a minimum of rebounds, preferably zero. A strike is desirable medium strength, not too strong (errors of torsion and the physical engine of the game) and not too weak (errors of my bot already). The cue ball strike on the target ball should be as “direct” and elastic as possible: tangents are evil! The minimum rollback length automatically follows from here. Additional conditions came out of my lengthy scuba diving and pitfall analysis (not so important, but still significant): it is necessary that the target ball fly into the corner pockets at an angle as close as possible to 45 degrees, and into the pockets of long sides - at an angle no more than 35 degrees. There are some additional conditions, but I’ll keep silent about them. Additional conditions came out of my lengthy scuba diving and pitfall analysis (not so important, but still significant): it is necessary that the target ball fly into the corner pockets at an angle as close as possible to 45 degrees, and into the pockets of long sides - at an angle no more than 35 degrees. There are some additional conditions, but I’ll keep silent about them. Additional conditions came out of my lengthy scuba diving and pitfall analysis (not so important, but still significant): it is necessary that the target ball fly into the corner pockets at an angle as close as possible to 45 degrees, and into the pockets of long sides - at an angle no more than 35 degrees. There are some additional conditions, but I’ll keep silent about them.
But in essence, all these things are far from perfectly comparable with each other and with each other. For example, if the angle of attack (elasticity of impact) is somehow comparable with another angle of attack (say, 0 degrees is better than 50), then such a characteristic as the force of impact ...? For different trajectory lengths, different forces are needed, because there the distance is different and the cutting is different. If we translate the impact force into some relative indicator, then what to do with cutting? Indeed, for different strokes she is her own! And how to compare incomparable categories, such as, for example, the number of rebounds (a number from 0 to, say, 10) and the angle of entry of a ball into a pocket of a long side? What is more important?
Pffff ... Another significant problem arose in front of me. It was necessary to bring all these characteristics to some consistency. Say, to a numerical range from 0 to 1, where 0 is monstrously bad or impossible, and 1 is absolutely perfectly good. This was the next huge step in the work; search and selection of such functions that would reflect (and adequately reflect) all the presented characteristics in the corridor [0, 1]. And this is a huge job. Take the number of rebounds. Yes, it can be from 0 to 10, but on average 1 or 2 rebounds are considered the norm. 8 - this is an exceptional situation, which is extremely rare in the game. Therefore, linearly translating the range [0, 10] into the segment [0, 1] is stupid and unjustified. I had to look for “inverse” distribution functions for all characteristics, fit, dig them out, suck out of the finger.
Well, the next step is to find weights for these characteristics. Weight is the importance of performance. And here again the dilemma. What is more important than what? At first I tried to put all the characteristics the same weight, but the bot played disgusting. Then another stage of work began - a long and tedious one. Fitting and searching for the necessary coefficients. This phase also took me a couple of weeks, but I was lucky. I already felt all the situations so much that the adaptive method reached a very good selection. So far I have not found anything better;)
So, the main function being defined was ready! I recall, it consists of the sum of the products of the weighting coefficients and the fitting functions. As a result, for each stroke, I get the number of "good" hits from 0 to 1 (normalizing). Well, then it’s a matter of technology: we choose the best strike and hit.
Over the months of testing, I found an interesting glitch. Either because of inaccuracies in the engine, or because of some of my jambs, the shock balls standing near the side are not always amenable to the general laws of striking. A must. Here's what happens: in a situation where I perfectly direct the shock ball standing near the long side into the pocket, instead of flying strictly parallel to the board and falling into the pocket, for some reason it hits the side and bounces, flying in the wrong direction . It feels like I'm undercutting. I introduced a special corrective function to bring cutting to the ideal. It is again taken from the ceiling and is a pure fit. But it works.
For everything about everything, we have only 20 seconds, and the bot may not have time to find a hit. Therefore, with a high priority stream, I am looking for so-called emergency strikes. These are blows with the goal of not hitting a ball, but at least touching their ball. If within 15 seconds of the search the bot did not find a single blow to block, it immediately implements an emergency hit on touch to avoid a foul. And I made the search for the impact adaptive. First, the table itself is taken as the simulated (the same mirror) space. If no blows were found, then the simulated space is increased three times horizontally and vertically: the vertical reflection along with balls and pockets “is attached” to the table to the left and right, and horizontal reflection above and below. If the blow is not found here - there is another completion of the simulated space. And so on until either 15 seconds have passed, or the number of “blocks” of the table does not exceed the maximum allowable number of rebounds; a ride on the ball simply does not have enough energy.
It’s necessary to score a green ball:
It would seem that he has achieved everything: there is both an aiming point and a strike force. It remains only to implement it. But even here I came across difficulties, or rather, either inaccuracy of programming, or hidden protection from fellow programmers of the game Pool Billiard. But first things first. Between the aiming point and the cue ball is the angle of impact. Let's say it is 27 degrees:
The bot should find such a pixel on the table so that, having put the mouse there, the line of impact was exactly 27 degrees. Since the pixels are discrete, but not continuous, in the special search area, a search is made for the pixel that best suits the given angle.
Well, that would seem to be all! We put the mouse in the desired pixel, do a guy by the specified number of pixels to the cue ball and release. But no. Wrong balloon flies! What a curse !? In some cases, the ball hits perfectly, in part it is somehow doubtful, and sometimes not at all! I spent 4 days to find this floating error. Shoveled the entire code. It turned out that the matter was not on my side at all: the physical mouse (screen) did not coincide with the gaming mouse. It’s done on a flash. Either this is a bug, or a feature, but their coordinates differ by 4 pixels horizontally and by 1 vertically. By some miracle, I accidentally noticed this; introducing the appropriate amendments, I got an excellent result.
Yes, ball recognition is not perfect for me. Sometimes a bot mistakenly classifies a striped ball as solid, and vice versa. The easiest way to correct this situation is when the incorrectly recognized ball is on the table. The most difficult thing is when there are clogged balls in the stack.
Suppose the bot incorrectly recognized the ball on the table. Let, for definiteness, the bot think that the ball is striped, when in fact it is solid. Bot scores striped. By chance, this particular ball was chosen under attack. What happens next? If the bot doesn’t strike its ball, it will receive a Fault and a miss pass. And this is not good. I did this: if at the time of aiming on a ball (if there are no bounces) in the game interface near the ball a green arrow lights up, then you can beat.
If it is red, then the bot immediately reclassifies it to the opposite type (now it is solid for the bot), discards all the hits found on it and takes the next best hit, not touching this particular ball. The bot is trying to hit another ball. If it is also incorrectly classified, the story repeats itself. And so on until the bot either has a timeout or ...
... the logic is much trickier. After all, such a situation is also possible: the beginning of the party; the bot scores the first and only ball. In fact, it is solid, while the bot thinks it is clogged with striped. This is just the second situation described at the beginning of the section.
What will happen next? The bot will be absolutely sure that it needs to score striped, when in fact - solid. The bot will aim at the first striped ball - the red arrow, the second striped ball - again the red arrow, the third - the same thing. In fact, this process will not last until the timeout. I programmed it this way: if more than half of the balls on the table give a red arrow, it means that the type of ball in the stack of clogged balls is simply incorrectly recognized. Then the bot immediately reclassifies the type of balls to be clogged from irregular striped to regular solid ones and is already looking for solid punches, taking itself out of a steep peak. And that’s all - if time is left.
In war, any means are good. And, therefore, it is possible and necessary to seek such funds. For example, means of influence on the enemy. The game essentially completely closes opponents from each other. They interact only through the gaming table. Game table and ... chat! Yes, the game has a chat. And this is the maximum available channel of verbal communication. And that means exposure. What can be done through chat with the enemy? Calling him to surrender, of course, will not work, but you can coolly divert his attention and even pat his nerves! Ah yes method!
I decided not to bother with the coherence of the broadcast text. After all, chat is a secondary task. Let it be just some short messages.
As a separate case, I programmed several options for greetings. They are spoken by the bot at the beginning of the game in order to a) attract the opponent to the chat function and b) immediately set him up so that I will speak with him. And good breeding forces me to answer, I tell you. To answer is to connect to the brain an additional distraction from the game functionality of talk and reaction to messages. I note that the vast majority of players respond to the greeting with a greeting. Excellent! Let them think that with them playing man (they even thought can not come, that there may be a robot)!
Well, then - the sausage shop! Here, jokes and jokes, and jokes, and teasers, and incoherent nonsense, and demotivating phrases come into play ... Out of ten people, about two seriously communicate with the bot. Many answer obscenities. Furious. The bot forces them. It's great!
Well, the chat functionality itself is implemented after the bot has hit and waiting for the physics to trigger; great place to "talk". I simply put the selected phrase on the clipboard and, through the on-screen baloon, send a message to the opponent. The tricks here are zero.
On this, my long and painstaking work on the bot was completed. It remains only to enjoy the fruits of labor.
I am posting for you a presentation video of a very old version of the bot:
And the video of the new version of the hours-long game in automatic mode:
Thanks for attention!
Foreword
We all have favorite games and sports. It’s great when the first coincides with the second. In addition to my hobbies for sports and sports projects, I also love some computer games. One of my favorite games, both live and virtually, is, of course, billiards. Billiards, pool, snooker ... whatever you like - I love them all! I share the opinion of many that, for example, snooker is “non-discrete” chess. It’s not enough just to hammer a sequence of certain balls into the pockets, there is also an incredible strategic struggle. The fight for snookers, for positions ... and what fantastic equipment professional billiard players possess - I just keep quiet in a rag.The advantages of this undoubtedly aristocratic game can be listed for a very long time. But let's get to the essence of the article. My favorite game of billiards for five years now and to this day is Pool Pooliard on Facebook. It is famously made not only aesthetically, but also technically. With the naked eye you can see a cool written physics engine, thoughtful gameplay, client-server validation of actions, error handling, design, statistics system, store, chat in the end. The game was clearly made by the pros, and it is in the tops. It is very nice to play it ... and win!
For a long time I played it, until the thought came to my mind: “ Bah! Yes, it’s perfect for creating a game bot for it!. It's nice to win, but to win with your robot is automatically double! Winning against paid players who have acquired a navigation system and tightening the cue ball, demonstrating blows that are fantastic in technique and beauty, leaving them with saggy jaws is triple pleasant! Plus an automatic set of experience points and coins: left the robot for the night, in the morning you are the best! In addition, I, as a spectator, love to watch billiards for hours. In general, yes, I decided!
Creature
Before starting the creation, I, having at that time already quite a lot of experience in playing Pool Billiard, carefully thought out everything with a pencil and a piece of paper in my hands. Of course, it is impossible to predict everything, but the "skeleton" was created. Bring in the skeleton! To create the bot, I used C ++. Writing and debugging the code in the optional mode in the evenings took me almost four months. Agree, it is difficult to debug something on a closed system, especially when you need to test some rare or exceptional case that happens in one of a hundred parties. I can’t frivolously arrange the balls and simulate this or that situation on the table.
How does the robot interact with the game?
I realized that the bot will interact with the browser through a complete simulation of a person: pattern recognition and imitation of human input: mouse, keyboard. Thank God, you don’t have to enter captcha before each hit :) So I did: I like systems simulating human behavior, from which browsers are so defenseless!
This means that you need to be able to find the region with the game on the screen, be able to interact with it, receive certain signals from the game and process them, and, most difficult, be able to correctly execute strikes. I made a list of necessary actions that the bot should be able to carry out (for example, enter a certain game, send a certain message to the chat, put a ball at a certain point, check the number of points, strike a certain force at a certain angle, break a pyramid and so on) and a list of certain signals that the bot must be able to recognize (for example, our turn began, the round suddenly ended, the enemy gave up, there is little money, and so on). In total, about forty situations turned out; some were asynchronous, some were not. I programmed and, as far as possible, carefully tested each of them (about this separately),
What is the general logic of work?
I decided that the general logic of work would, of course, be a state machine. First, the bot is calibrated for the game, then it calculates the amount of money available, then it decides which bet to make. The following is the gameplay itself, after which the bot again decides how best to enter a new game. The simpler the logic, the more reliable and predictable the system works. And it’s easier to catch bugs.
What is the detailed logic of work?
The detailed logic is harsh and bearded, it contains a whole bunch of branches and possible situations. It all starts with the fact that the game starts and the bot itself. The game (browser window with the start screen of the game) is on the screen. Its coordinates are recorded and this serves as a starting point for all subsequent mouse input and recognition of the situation.
Further, the bot determines the amount of my money in order to understand what bets can be made. After choosing the size of the bet, the bot enters the corresponding room and the game begins. It can end at any moment, since already from that second the opponent can close the browser, and, after a certain timeout, our round is invalidated. An opponent can also leave the round at any time: in this case, the victory will be awarded to me. Recognition of all these situations begins right here.Further, the server randomly determines who will start the game: me or the opponent. The bot is waiting for the start of its turn. For the entire course, only 20 seconds are given. During this time, you need to have time to determine that the move is already mine, count balls, glasses from the table, correctly recognize them, find the right blow and have time to take it.
The bot itself determines whether it will break the pyramid, and for this case it has a couple of simply awesome options. If you don’t need to break the pyramid, the bot will recognize the coordinates of the balls on the table, which balls it can score (colored or striped or any_ except black or only black (judging by the situation in the game), the number of points and the whole-all-other gimmick. After that, the bot calculates and strikes.
The bot, in addition to basic activities and not to the detriment of the game, also likes to chat with opponents. Usually, such a temporary window occurs immediately after the strike. This is where the bot writes some chat message to the opponent. After the blow, either the move goes to the opponent, or we continue to play, or we won, or we lost. The bot is waiting for a sign of one of these situations. In case of defeat or victory, the bot closes the current window of the game and the summary window of results and proceeds again to the recognition of the amount of money.
A state machine is generally something like this.
How is the game on the screen?
I read the entire screen context in C ++. The game is on the screen is very simple. Since the design of the game is not "rubber" (it does not stretch), but fixed, then all the elements are constantly at the same distance from each other. So, you need to find on the screen with the game a certain static element that never visually (graphically) changes, and calculate the coordinates of the beginning and end of the window relative to it. Having made a couple of screenshots and processed everything in Photoshop, I did so. I made a simple and reliable table recognition marker. I decided to abandon the idea of recognizing the coordinates of the window before each hit. This is stressful and takes away the precious moments of calculating the perfect blow. Therefore, the bot determines the position of the game only once - at startup. After the bot has found the game window, it is strictly forbidden to move the browser window even by one pixel: in the process of playing on the pool table, an inaccuracy of even one pixel with long strokes accumulates a monstrously huge error. From here all blows will be incorrect.
A game marker is an immutable part of the image of the game window:
How is the amount of money determined?
Here I was just lucky. I didn’t have to put a sniffer on my browser and listen to the broadcast of the game to determine the amount of money or recognize characters from the screen. Everything is prosaic: the fact is that in the game not everything is done on a flash. The element with the sum of my coins is a simple text field that is easily highlighted with the mouse. I just imitate the following: I bring the mouse to the beginning of the field, hold down LMB, move right to the end of the field, release LMB. As a result, the bot simply allocates a field with money. Then I copy it to the clipboard, delete special characters such as spaces, commas and periods ... and that’s it! The amount of coins in my pocket.
Game coins are just a highlighted field:
How to choose a room for the game?
There are several rooms for the game, each of which contains a certain rate (entrance fee). Two opponents enter the room, placing each, for example, 100 coins. The winner receives a prize of 140 coins (not 200, as you might expect (this was done by game designers in order to constantly lose a lot of money from the game, and people were forced to use the store and buy coins for real money and play, or wait until the daily wheel of fortune brings them coins for the game)). The loser leaves with nothing. The logic is simple.
In cheap rooms every rabble hangs forever: beginners, losers, and so on. For the sake of fun, sometimes pros go there. The probability of winning there is very high.In more expensive rooms, you can meet middle-hand players, sometimes newcomers go there stupidly, sometimes superprofiles go down there (apparently to tear someone to shreds). The probability of winning there is approximately 50%.
In expensive rooms, the elite hang out: either superprofiles, or payers with a purchased navigation system, tips and so on. Most likely, there is a loss there.
The bot has several modes for choosing a bet: forced modes (when the bot always puts the amount that I indicated to it) and auto mode. Auto mode is made in a very interesting way. I collected the statistics of winning by the bot in the rooms of different bets and based on it I wrote a very interesting program. It only gives out several numbers, but very important numbers. These are the so-called threshold amounts of coins. For example, if we have 300 coins, the bot has the right to play only in the first room, but after overcoming the threshold amount of 740 coins, the bot has the right to play in the first and second rooms. Of course, the bot seeks to play in the most expensive room.
So, the program is interesting in that it automatically selects these same threshold values according to some algorithm, which it itself further uses to predict the risks of a subsequent loss. It simulates millions of parties and decisions about playing in a particular room (shelling of Monte Carlo) and issues the correct border quantities of coins. Moreover, I noticed that the algorithm is convergent!
Directly entering the room is done by clicking on a specific part of the screen where the button for entering and making a certain bet is located.
After choosing a room, click on the appropriate button:
How is a move determined?
Here again, markers come to the rescue. On the game screen, everything is just as static as on the main one, and all the elements are always in the same places. This is a panacea. My opponent’s avatar, as well as statistics, a message box and other items, are always on the left. Mine is on the right. I also created a simple and reliable marker for determining my course. As soon as the bot reads it, it proceeds to the next phase.
How are balls recognized?
Here is a whole saga in three acts. I will not describe all my two-month suffering on this issue, I will describe what is happening only briefly. From the table image taken at the time of recognition of the balls, the image of a clean table, carefully prepared by me in Photoshop, is subtracted. Further, there are high-contrast zones, on which there are spots of balls. For certain specific light markers, taking into account the inadmissibility of overlap, the centers of the balls are located. Then they are sorted by the contrast of their brightness to prevent debris from entering the screen (cue, inscriptions on the table). After that, the position of the balls is verified by checking the shadows around them. Finally, we got a list of the required number of ball centers in the image.
As soon as I tried to look for balls differently! And with the help of defining shadows, and with the help of the Canny border method, and with the help of ingenious classifiers: all these and many other methods were very ineffective and inaccurate compared to the method written by me personally. I even set Wolfram Mathematica on statistics, but this did not give me a particularly clear answer. Maybe bad set.But it’s not enough to know the centers of the balls, you still need to determine where the stripes are, where is solid, where is white (cue ball), and where is black (eight) balls. There was no limit to unlimited fantasy, because it was necessary to unify a whole bunch of problems. For example, a green ball merges very strongly with cloth, and if the striped yellow ball stops so that its white pole is directed strictly towards the camera, then it will be almost as white as the cue ball is. The subtleties surfaced a whole billion, and with all of them I had to fight.I went over a whole sea of solutions, discarding them due to lack of accuracy, and finally I wrote the most accurate of them. I got a decisive tree, in each node of which there is a self-written classifier. For each ball found, I determine the color characteristics: average {R, G, B}, average {H, S, B}, the brightest and darkest color without taking into account color spots. Then I definitely find the cue ball as the whitest ball. Next, I try to determine the eight as the darkest ball. After all, you need to separate the colored from the striped. But the casket was not easy to open: I compiled three-dimensional tables of samples, photographed balls a thousand times in attempts to train the network, but still I was not able to build a hyperplane uniquely separating the clusters of solid and striped balls. Anyway, there are errors. For this case, I made a small error-correction-on-the-fly. More about this below.
Here, various orthonormal basis bases of turns, cluster statistics with predefined color of balls, and other mathematical basis were used, but it was not that ... and not that ... I went through a lot of options. In the end, our bot has a certain set of balls with their fairly accurate characteristics: there are always white and black balls, and sets of solid / striped. Believe me, not a little work has been done.
How is the possibility of breaking a pyramid determined?
Here I was relaxed: we create a simple classifier of the position of the pyramid (each ball is at the point of the pyramid) and if our move and our move is the first, then we break it. But it was not there! Something didn’t work! It turns out that cunning programmers added some noise to the initial positions of the balls in the pyramid. Clever! Otherwise, it would be possible to record an “ideal game” - an unmistakable series of punches leading to victory, and, constantly reproducing it, win. But they provided such protection here. Having slightly adjusted the classifier, I achieved success in recognizing the moment of breaking the pyramid.
When it is necessary to break the pyramid, the bot selects one of several luxurious options for breaking tightly programmed into it and implements it. Almost all of the above options make one or two balls immediately fly into the pockets. Well, or nakraynyak very much scatter balls on the table, which is only to my algorithm.
How is the number of points on the table determined?
Near my avatar and opponent's avatar there is a stack of clogged balls. It is a strip with clogged balls placed there with a slightly smaller radius than on the table. However, what to do? Recognizing the balls on the table alone is not enough to understand which series I play - striped or solid. So, it is necessary to recognize not only the number of balls in the stacks, but also the balls themselves! Pffff ... the algorithm of "subtracting the table" does not fit here, and the sizes are not the same.
... by
an incredible effort of will, I forced myself to write another recognizer
...
and the second incredible effort is to combine both of these recognizers into one universal recognition function. In fact, I had to write everything from scratch. This is the problem of insufficient planning. But now I indicate the region and size of the balls, and at the output I get the coordinates and characteristics of each ball! The victory of the mind!
Having determined the number and type of balls clogged by me and the opponent, the situation on the table becomes completely deterministic. Now the bot knows what and how he needs to score:
How to determine which balls to beat?
A strictly deterministic algorithm is programmed here. If we break the pyramid at the beginning of the game, then we can hit any ball (anyway, we won’t get into the black one - it’s hidden inside the pyramid). If the first move has already been completed, we look at the number of balls scored. If there are none, you can beat anyone except black. If only the enemy has it, take the opposite type and hit. If I have (and not only mine) - beat the same type. Finally, if I have clogged all the balls in my series except black - score black. All! ;)
How are opponent fouls determined?
Sometimes the opponent mows. In this case, the rules of the game oblige me to free kick: I have to put the cue ball anywhere on the table and strike. So, there are two problems: recognizing the opponent's foul and correctly setting the ball under attack.
The first problem is solved relatively simply. In a separate thread, a certain tracker is trying to find such a situation: now the opponent’s move and the “Fault!” Marker has appeared on the table. In this case, he informs the main stream that the next blow must be done with the production.
The second problem - the formulation problem - is solved a little more complicated. Although, I confess to you, friends, here I faked. I'm not trying to put a cue ball on some line of clogging one of the balls in my series. Not. I'm just trying to put the ball universally - as close as possible to the center of the table, where there are no obstacles. First, I recognize the situation on the table, then I calculate the nearest point, not closed to the center of the table, and put the ball there. While staging is in progress, I’ll almost certainly calculate the perfect shot.
How is angle and impact force calculated?
So, before me there was a task for a given time with a given configuration of balls on the table and a given rule of striking, to calculate all possible effective punches and choose the best one among them. Possible values of the set time: {20 seconds}. Possible configurations of balls: them? .. Possible rules for striking: {any except black, only solid, only striped, only black}.
Ball clogging
Before you get into the jungle of billiards, you must first understand the physics of what is happening. What do you need to score a ball?
To do this, draw an imaginary segment from the center of the pocket to the center of the ball and slightly extend it further to the intersection with the border of the ball. The intersection point is the point of impact. If you hit the ball on it, it will fly into a pocket.
In order for the cue ball to hit this point, it must not be directed to it, but to the point that is located from the point of impact by the radius of the cue ball further along the same imaginary line.
Well, then, I think you have already caught. In order for the cue ball to fly where it is necessary, you also need to build a line from the target point through the center of the cue ball and cross it with the far edge of the cue ball circumference.
So, from here a general rule is born: in order to direct any ball to a given point A , it is necessary to connect the point A and the center of this ball with an imaginary line and extend it to the intersection with the far boundary of the circle of the ball. This is where you hit the ball. I decided to make the bot’s game strategy the same as for people: the bot selects one ball under attack and hammer it. All. The simpler the system, the more reliable and easier it is to debug it.
Pockets
The pockets are different. And getting into them is subject to different laws. For example, you can get into the corner pocket in different ways:
But for each pocket I managed to find a universal point, rolling the ball to which from any place entails getting into the pocket:
I programmed the bot just to aim at these points. The only limitation that the pockets of long sides impose on themselves: the flying of balls into them is possible only in the casement of 70 degrees. It is also embedded in the code.
Simulated space
I decided to abandon the rebounds. No no, don’t be scared, not in the sense, of course;) To build such a simulated space in order to forget about rebounds altogether. They are in the game and remain, but they will not be in space. I only worked on the solution to this problem in the evening. I realized: the collision of a ball of radius R with a side of thickness 0 is the same as the collision of a material point of radius 0 with a side of thickness R :
This means that the calculation of physics can be significantly simplified: in terms of trajectories, we will work not with balls, but with material points. Further: according to the laws of the genre, the angle of incidence of the ball on board is equal to the angle of reflection. As in the case of light rays and a mirror surface. You ask: what does it have to do with it? I will answer. The collision of a material point with the side (ricocheting against the side) is the same as the continuation of the movement of the material point through the side into the space mirrored from this side. That is, if the ball could “see” forward in the direction of its movement, and the sides were mirrors, then this would result in:
In such a “mirror-board” space, I no longer need to think about ricochets. They flow by themselves. Plus, we connect the rule of motion of the material point, and it turns out generally luxurious.
In the simulated space, all strokes are straight lines, no rebounds. But on the table they already are.
Maximum impact force and cue ball path
Great, a lot of work done! But there is still an extremely important question, which we did not touch at all: what is the maximum way a cue ball can go? What is the energy in it? I do not want to hit balls every time with all my might; this will put the cue ball at risk of accidentally rolling into a pocket. I want to very accurately and accurately calculate the impact force. To do this, I need to know at what length of the cue from the cue ball in pixels the minimum impact occurs and how long it is, and at what length of the cue from the cue ball in pixels the maximum impact occurs and how long it takes. I also need to know what energy is taken from the ball when it hits the side. Now it remains to find out all this. With minimal strokes, everything is prosaic: it is measured at any moment. With maximums it is much, much more complicated. The diagonal of the table is not enough even for an average hit, so I clearly can not measure the length of its path.
I came up with this in two cases: horizontal and vertical. After making the appropriate measurements and equating the equations together, I would get the full length of the maximum trajectory of the ball and the coefficient of energy quenching on board. So I did. I waited for the moments when the opponent got a foul to gently put the cue ball right to the edges of the sides, so that nothing prevented the horizontal and vertical movement of the cue ball. And twice he struck with all his might: once horizontally, the other vertically. He took off his indicators: in a vertical impact, the cue ball bounced off the long sides 8 times and, having reached the rest of the energy for some other way, he stopped. With a horizontal impact, the number of rebounds was 5 with a tail. From here, knowing the dimensions of the table, it is easy to obtain equations, numerically solving which we obtain the full length of the maximum path,
Let x be the maximum length of the ball’s rolling path without collisions with the sides in pixels, and p <1 the coefficient of energy loss when hitting the side at right angles. The width w and height h of the table in pixels are known. Consider the horizontal case:
- x —— at the initial moment of time of the strongest impact, the ball has full rolling energy for the maximum path length x;
- x - w —— such energy and, accordingly, the path margin is possessed by a ball rolling horizontally from side to side to the width of the table w;
- p · (x - w) —— having hit the board, the ball lost energy and, therefore, the path margin according to the coefficient p;
- p · (x - w) - w —— having rolled again from side to side, the ball once again lost the path margin equal to the width of the table;
- p · (p · (x - w) - w) —— the ball hit the board again and lost energy according to p;
- p · (p · (x - w) - w) - w —— again rolling from side to side, already the third;
- p · (p · (p · (x - w) - w) - w) —– another blow to the side and loss of energy;
- p · (p · (p · (x - w) - w) - w) - w —– the fourth loss of energy and path margin when rolling from side to side;
- p · (p · (p · (p · (x - w) - w) - w) - w) —— impact on the board;
- p · (p · (p · (p · (x - w) - w) - w) - w) - 388 —— fifth, last roll from the side: the ball completely lost all its energy and path stock and remained at a distance of 388 pixels from the edge of the side.
We equate the last equation to zero. Similarly, we obtain the equation for the vertical case. Solving this nonlinear system of two equations with two unknowns numerically, I got the desired x and p.
Chain rules
Of course, the depth of impact can be any, if only enough energy. But due to the accumulation of errors, I decided to stop at number 4, that is, the maximum number of objects involved (including pockets) is 4. My cue ball can hit ball A , which will hit ball B , which will fall into the pocket. And then (!) The accuracy is lost so much that I introduced a number of restrictions on such attacks. They should be without ricochets about the sides, the distances between the balls and the pocket should be approximately equal and the angles of attack are close to elastic impacts. But such a fantasy does not shine for me yet:
Rollback cue ball
All suffering and calculations will be in vain if even after an enchantingly masterpiece hit our cue ball rolls back and falls into a pocket. Even through a rebound. Therefore, I immediately discard such blows from consideration, after which the bot may fail. To calculate the rollback of the cue ball, the strength and direction of the rollback after hitting the cue ball against the target ball are calculated. I thought everything would be simple: we calculate the remaining energy after an elastic / inelastic impact, how far and in which direction the cue ball will roll back, the direction using the cosine of the relative angle of attack, and see if the trajectory passes through the pockets. But no, a pitfall awaited me here too. After conducting a series of tests, I noticed that the actual rollback is significantly different from the simulated one.
Both the game’s navigation system (yellow) and common sense with calculations show that the cue ball will roll back along the green line. However, after a hit, he rolls on red:
This is a trap. It turns out that the game also takes into account the inertia of the torsion of the ball and its direction. I had to write and test the nonlinear function of calculating the rollback trajectory for almost four evenings. Such trifles infuriate, but in the end it turns out that these are not trifles at all. I was able to determine a less accurate function only by trial and error. But I did it! Now I can safely throw out the blows that lead the cue ball through the pockets as a result of the rollback.
Better hit feature
As a result of analyzing the table configuration, I received a collection of a large number of possible strokes. But how to choose the best of them? It is necessary to turn on the brain and evaluate each impact parameter. Logically, what would we like? It would be desirable to minimize the number of rebounds from the cue ball to the target ball: each rebound introduces a small, but an error. The distance from the cue ball to the target ball should be as small as possible, but not quite small, in order to be able to accurately aim. Oddly enough, these are two different conditions. Think about it. Further. The distance from the target ball to the pocket into which it should fall should be as small as possible. Of course. And this path should contain a minimum of rebounds, preferably zero. A strike is desirable medium strength, not too strong (errors of torsion and the physical engine of the game) and not too weak (errors of my bot already). The cue ball strike on the target ball should be as “direct” and elastic as possible: tangents are evil! The minimum rollback length automatically follows from here. Additional conditions came out of my lengthy scuba diving and pitfall analysis (not so important, but still significant): it is necessary that the target ball fly into the corner pockets at an angle as close as possible to 45 degrees, and into the pockets of long sides - at an angle no more than 35 degrees. There are some additional conditions, but I’ll keep silent about them. Additional conditions came out of my lengthy scuba diving and pitfall analysis (not so important, but still significant): it is necessary that the target ball fly into the corner pockets at an angle as close as possible to 45 degrees, and into the pockets of long sides - at an angle no more than 35 degrees. There are some additional conditions, but I’ll keep silent about them. Additional conditions came out of my lengthy scuba diving and pitfall analysis (not so important, but still significant): it is necessary that the target ball fly into the corner pockets at an angle as close as possible to 45 degrees, and into the pockets of long sides - at an angle no more than 35 degrees. There are some additional conditions, but I’ll keep silent about them.
But in essence, all these things are far from perfectly comparable with each other and with each other. For example, if the angle of attack (elasticity of impact) is somehow comparable with another angle of attack (say, 0 degrees is better than 50), then such a characteristic as the force of impact ...? For different trajectory lengths, different forces are needed, because there the distance is different and the cutting is different. If we translate the impact force into some relative indicator, then what to do with cutting? Indeed, for different strokes she is her own! And how to compare incomparable categories, such as, for example, the number of rebounds (a number from 0 to, say, 10) and the angle of entry of a ball into a pocket of a long side? What is more important?
Pffff ... Another significant problem arose in front of me. It was necessary to bring all these characteristics to some consistency. Say, to a numerical range from 0 to 1, where 0 is monstrously bad or impossible, and 1 is absolutely perfectly good. This was the next huge step in the work; search and selection of such functions that would reflect (and adequately reflect) all the presented characteristics in the corridor [0, 1]. And this is a huge job. Take the number of rebounds. Yes, it can be from 0 to 10, but on average 1 or 2 rebounds are considered the norm. 8 - this is an exceptional situation, which is extremely rare in the game. Therefore, linearly translating the range [0, 10] into the segment [0, 1] is stupid and unjustified. I had to look for “inverse” distribution functions for all characteristics, fit, dig them out, suck out of the finger.
Well, the next step is to find weights for these characteristics. Weight is the importance of performance. And here again the dilemma. What is more important than what? At first I tried to put all the characteristics the same weight, but the bot played disgusting. Then another stage of work began - a long and tedious one. Fitting and searching for the necessary coefficients. This phase also took me a couple of weeks, but I was lucky. I already felt all the situations so much that the adaptive method reached a very good selection. So far I have not found anything better;)
So, the main function being defined was ready! I recall, it consists of the sum of the products of the weighting coefficients and the fitting functions. As a result, for each stroke, I get the number of "good" hits from 0 to 1 (normalizing). Well, then it’s a matter of technology: we choose the best strike and hit.
Ball Cutting Correction
Over the months of testing, I found an interesting glitch. Either because of inaccuracies in the engine, or because of some of my jambs, the shock balls standing near the side are not always amenable to the general laws of striking. A must. Here's what happens: in a situation where I perfectly direct the shock ball standing near the long side into the pocket, instead of flying strictly parallel to the board and falling into the pocket, for some reason it hits the side and bounces, flying in the wrong direction . It feels like I'm undercutting. I introduced a special corrective function to bring cutting to the ideal. It is again taken from the ceiling and is a pure fit. But it works.
Adaptive search in 20 seconds
For everything about everything, we have only 20 seconds, and the bot may not have time to find a hit. Therefore, with a high priority stream, I am looking for so-called emergency strikes. These are blows with the goal of not hitting a ball, but at least touching their ball. If within 15 seconds of the search the bot did not find a single blow to block, it immediately implements an emergency hit on touch to avoid a foul. And I made the search for the impact adaptive. First, the table itself is taken as the simulated (the same mirror) space. If no blows were found, then the simulated space is increased three times horizontally and vertically: the vertical reflection along with balls and pockets “is attached” to the table to the left and right, and horizontal reflection above and below. If the blow is not found here - there is another completion of the simulated space. And so on until either 15 seconds have passed, or the number of “blocks” of the table does not exceed the maximum allowable number of rebounds; a ride on the ball simply does not have enough energy.
It’s necessary to score a green ball:
Aim and strike
It would seem that he has achieved everything: there is both an aiming point and a strike force. It remains only to implement it. But even here I came across difficulties, or rather, either inaccuracy of programming, or hidden protection from fellow programmers of the game Pool Billiard. But first things first. Between the aiming point and the cue ball is the angle of impact. Let's say it is 27 degrees:
The bot should find such a pixel on the table so that, having put the mouse there, the line of impact was exactly 27 degrees. Since the pixels are discrete, but not continuous, in the special search area, a search is made for the pixel that best suits the given angle.
Well, that would seem to be all! We put the mouse in the desired pixel, do a guy by the specified number of pixels to the cue ball and release. But no. Wrong balloon flies! What a curse !? In some cases, the ball hits perfectly, in part it is somehow doubtful, and sometimes not at all! I spent 4 days to find this floating error. Shoveled the entire code. It turned out that the matter was not on my side at all: the physical mouse (screen) did not coincide with the gaming mouse. It’s done on a flash. Either this is a bug, or a feature, but their coordinates differ by 4 pixels horizontally and by 1 vertically. By some miracle, I accidentally noticed this; introducing the appropriate amendments, I got an excellent result.
Correction of erroneous recognition of balls
Yes, ball recognition is not perfect for me. Sometimes a bot mistakenly classifies a striped ball as solid, and vice versa. The easiest way to correct this situation is when the incorrectly recognized ball is on the table. The most difficult thing is when there are clogged balls in the stack.
Suppose the bot incorrectly recognized the ball on the table. Let, for definiteness, the bot think that the ball is striped, when in fact it is solid. Bot scores striped. By chance, this particular ball was chosen under attack. What happens next? If the bot doesn’t strike its ball, it will receive a Fault and a miss pass. And this is not good. I did this: if at the time of aiming on a ball (if there are no bounces) in the game interface near the ball a green arrow lights up, then you can beat.
If it is red, then the bot immediately reclassifies it to the opposite type (now it is solid for the bot), discards all the hits found on it and takes the next best hit, not touching this particular ball. The bot is trying to hit another ball. If it is also incorrectly classified, the story repeats itself. And so on until the bot either has a timeout or ...
... the logic is much trickier. After all, such a situation is also possible: the beginning of the party; the bot scores the first and only ball. In fact, it is solid, while the bot thinks it is clogged with striped. This is just the second situation described at the beginning of the section.
What will happen next? The bot will be absolutely sure that it needs to score striped, when in fact - solid. The bot will aim at the first striped ball - the red arrow, the second striped ball - again the red arrow, the third - the same thing. In fact, this process will not last until the timeout. I programmed it this way: if more than half of the balls on the table give a red arrow, it means that the type of ball in the stack of clogged balls is simply incorrectly recognized. Then the bot immediately reclassifies the type of balls to be clogged from irregular striped to regular solid ones and is already looking for solid punches, taking itself out of a steep peak. And that’s all - if time is left.
How is chat going?
In war, any means are good. And, therefore, it is possible and necessary to seek such funds. For example, means of influence on the enemy. The game essentially completely closes opponents from each other. They interact only through the gaming table. Game table and ... chat! Yes, the game has a chat. And this is the maximum available channel of verbal communication. And that means exposure. What can be done through chat with the enemy? Calling him to surrender, of course, will not work, but you can coolly divert his attention and even pat his nerves! Ah yes method! I decided not to bother with the coherence of the broadcast text. After all, chat is a secondary task. Let it be just some short messages.
As a separate case, I programmed several options for greetings. They are spoken by the bot at the beginning of the game in order to a) attract the opponent to the chat function and b) immediately set him up so that I will speak with him. And good breeding forces me to answer, I tell you. To answer is to connect to the brain an additional distraction from the game functionality of talk and reaction to messages. I note that the vast majority of players respond to the greeting with a greeting. Excellent! Let them think that with them playing man (they even thought can not come, that there may be a robot)!
Well, then - the sausage shop! Here, jokes and jokes, and jokes, and teasers, and incoherent nonsense, and demotivating phrases come into play ... Out of ten people, about two seriously communicate with the bot. Many answer obscenities. Furious. The bot forces them. It's great!
Well, the chat functionality itself is implemented after the bot has hit and waiting for the physics to trigger; great place to "talk". I simply put the selected phrase on the clipboard and, through the on-screen baloon, send a message to the opponent. The tricks here are zero.
That's all
On this, my long and painstaking work on the bot was completed. It remains only to enjoy the fruits of labor.
Some video
I am posting for you a presentation video of a very old version of the bot:
And the video of the new version of the hours-long game in automatic mode:
Thanks for attention!
Only registered users can participate in the survey. Please come in.
Is the article helpful?
- 2.8% Not interesting and not useful: no longer need to write in Habr 11
- 8.9% Interesting, but not useful: the topics are “single” and “empty” 34
- 2.1% not interesting, but useful: just in case, keep, then suddenly come in handy 8
- 86% Both interesting and useful: with pleasure I will follow the work of the author 327