We write AI for Vindinium on single-board computers. Part 3: from theory to practice. Effectively hunt for mines in PP
A series of articles on writing AI for multiplayer online game of the bagel genre, limited by the performance of a single-board computer.
In this part of the article we will look at one of the most understandable and obedient AI in bagels, write simple rules that can be easily managed and talk about collecting statistics.
But before that, a little bit about the sublime: janvarev launched a very convenient leaderboard , by which you can track your ranking among players who played for ten days. Join you too! The first five users of Hiktaims, who will occupy a place higher thangold postcard from Moscow! I am a poor student, I live on a scholarship. The only condition is that the bot's nickname must be the same as Hicktimes (or at least look like).
')
→ Part 1
→ Part 2
First you need to understand what are potential fields (PP), for this we need this and this article.
In general, PP can be represented as a map of the signal propagation from an object to all cells of the field, skirting obstacles. Here, for example, the spread of the field near the player R (id = 4), the darker, the weaker the field.
There are implementations using pseudo-code , which allows working on software with most programming languages.
The calculation of potential fields for all mines, players and taverns is not a very difficult task, which even a single-board computer can cope with due programmer's straightforwardness.
Now look at this task fully:
Now we will work on points:
Frankly speaking, there is nothing to talk about. The official website is available for quick start kits in 28 programming languages. By the way, it is very easy to do without them, because there are only POST requests and work with json. For python, there are requests and json modules that do all the dirty work themselves. In the second part was given the code that works with server responses.
Here you need to say a few words:
Above, I said that there are no barriers for the implementation of a potential field in my PL. Personally, I liked a very concise and quick solution from here , it’s only worth transferring a part of the emit function to your code, with a bit of fine-tuning with a file. It is necessary to divide all objects into three categories:
- Emptiness - saves and distributes further the charge of the field. Spunpoints and empty cells belong to such objects. By the way, a spunpoint must spread a charge, even if a character is standing on it.
- Barrier - does not save or distribute further the charge of the field. Such objects are all obstacles with which the player cannot interact (marked on the map "##").
- Battery - retains the value of the charge, but does not distribute further. This is necessary so that the field goes around these objects. Such objects are mines, players, taverns. If, for example, a player blocks a passage a width of one square, the signal will not be able to spread further.
Now, if it makes sense to bother with the speed of work, you need to divide the task into N parts (in the case of a single-board quad-core computer N = 3, in order to save one core for the main process and for the internal needs of the operating system) and feed the map and coordinates to the processes to get potential maps of all objects (my implementation on Python3 in one thread does not cope with a map size of 28x28 with 40+ objects, it is necessary to parallelize).
Now we can turn to any point of the map to find out the distance of objects to it.
Pretty clumsy, non-optimized, but for starters, it will. It was one of the very first AI sketches for
Consider the ways in which you can search for mines on the map:
Pros:
+ The easiest way.
Minuses:
- All other components of this venture
Comment:
If you stand at a crossroads with the same distance to the two nearest mines, you can choose any.
Three fights, laid out a little higher, reveal all the unviability of this method. Superfluous moves, illogical movements, turning circles - everything is replete with redundancy.
Pros:
+ Now AI will choose quantitatively more pleasant way.
+ Easy to implement.
Minuses:
- There is a better way.
Comment:
This method is really incredibly good. We will not look for the closest option, but the best one in the short term. For implementation, you can use the addition of all weights with the formula, for example, 600 / (n + 1), where n is the distance to the object. This will help to accurately reach the best place at an equal distance, and also makes more attractive points with more mines. In this case, it is worth making the mine itself, for example, with a weight of 1000 units, for otherwise the cell next to the two mines will have a similar attractiveness as the mine itself (600/1 = 600/2 + 600/2). The average Elo points for 100 battles increased from 1550 to 1833 only with a change in the method of searching for mines, this says a lot.
Part of the map, where this method will be effective
The algorithm is as follows:
Pros:
+ A much better way to find mines.
+ Looks for the best "chains" to search for mines.
+ The most effective way, if not the existence of rivals.
Minuses:
- May be somewhat resource intensive.
- Does not take into account the activities of enemies.
Comment:
This method has advantages that cannot be ignored. If you work in this direction, you can achieve significant success, even sticking to the resources of the single-board. The estimated number of moves and the number of mines captured can be used as an estimating function or, for example,
If you have an idea to find mines, put it in the comments, because I have nothing else to come to mind.
But how to make sure that the change in the bot engine made it better?
Decide on the collected material. For me, the choice was simple:
- viewUrl - a link by which you can view the battle
- the place that we occupied in the battle
- the ratio of our gold and gold of the winner as an indicator of the success of the battle
- current Elo points
- whether we dropped out of the game prematurely (this can happen if there were problems with the Internet or if we crossed the limit of 1 second to send a solution)
- the size of the card (which often correlates with the winning place)
Now you need to choose a way to save this information. If you choose from simple, there are two options: .scv and Google Forms. It should be said that GF may be a more convenient option, as it adds a timestamp from under the box and statistics are available online. How to enter the answers in the form, you can search for the query "submit google form programming_lang".
In the meantime, Hiktaim users have question number 2:
The screenshot shows a piece of the map:
Q - our player
S - enemy spawnpoint
The programmer Oknoz decided to add such a property: if the owner of an enemy spawnpoint has a dangerously small number of health points, then the spawnpoint begins to emit a repulsive potential field, which does not encourage close finding near this spawnpoint. But the player was trapped, becoming an excellent prey for an enemy player as soon as he was reborn. Oknoz is thinking about what needs to be done to prevent such situations from happening.
Any guesses? One of the possible solutions I will write in the comments under the spoiler.
So, step by step, you can create a brave and mighty warrior who will cross his swords with alpha-beta clipping and minimax adherents on an equal footing!
In the next part, we will consider possible behaviors for taverns, spunpoints, opponents, see how fields are formed, what a blocking is a priority field, and consider whether it is worth painting over the dead ends. And, of course, a couple of words about competing algorithms.
→ Link to Vindinium
→ The link to the Vindinium subreddium is a very useful thing, there you can hear the answers to very interesting and intricate questions.
→ Link to my githab with some old insights from Vindinium
In this part of the article we will look at one of the most understandable and obedient AI in bagels, write simple rules that can be easily managed and talk about collecting statistics.
But before that, a little bit about the sublime: janvarev launched a very convenient leaderboard , by which you can track your ranking among players who played for ten days. Join you too! The first five users of Hiktaims, who will occupy a place higher than
Zonko 0.11 in the leaderboard on September 30th, will receive a ')
→ Part 1
→ Part 2
Potential fields ...
First you need to understand what are potential fields (PP), for this we need this and this article.
In general, PP can be represented as a map of the signal propagation from an object to all cells of the field, skirting obstacles. Here, for example, the spread of the field near the player R (id = 4), the darker, the weaker the field.
There are implementations using pseudo-code , which allows working on software with most programming languages.
The calculation of potential fields for all mines, players and taverns is not a very difficult task, which even a single-board computer can cope with due programmer's straightforwardness.
Now look at this task fully:
- We receive from the server information about the state of the game;
- We get the coordinates of taverns, players, mines - significant game objects;
- We consider the potential field of all game objects, add to the general dictionary of the form:
- id -; - Using magic, we get the decision which way we will go this time.
Now we will work on points:
1. Information about the state of the game
Frankly speaking, there is nothing to talk about. The official website is available for quick start kits in 28 programming languages. By the way, it is very easy to do without them, because there are only POST requests and work with json. For python, there are requests and json modules that do all the dirty work themselves. In the second part was given the code that works with server responses.
2. Get the coordinates of game objects
Here you need to say a few words:
- The coordinates of all four players are available in
game - heroes - hero_id - pos; - Taverns and spawnpoints are the only immutable objects on the map. They do not move, do not pass from one hand to another. Their location can be remembered once and for all;
- The coordinates of the mines will have to get out of the map every time, because they tend to change their owner;
- Then we pack all this into one “name - coordinate” dictionary, and the mines and taverns should be numbered.
How does the final stage look like for me:
In this case, the first character of the key indicates the type of object, the last - the number of identical objects. 0, 1, 2, 3, 4 denote mines and their belonging to any player (0 is a neutral mine, 3 is a mine owned by a third player). Q, W, E, R are four players respectively, A, S, D, F are their spawn points. The values ​​are coordinates.
{'0_0': [4, 2],
'0_1': [4, 13],
'0_2': [11, 2],
'0_3': [11, 13],
'A_0': [3, 3],
'D_0': [12, 12],
'E_0': [12, 12],
'F_0': [3, 12],
'Q_0': [3, 3],
'R_0': [3, 12],
'S_0': [12, 3],
'W_0': [12, 3],
't_0': [3, 4],
't_1': [3, 11],
't_2': [12, 4],
't_3': [12, 11]}In this case, the first character of the key indicates the type of object, the last - the number of identical objects. 0, 1, 2, 3, 4 denote mines and their belonging to any player (0 is a neutral mine, 3 is a mine owned by a third player). Q, W, E, R are four players respectively, A, S, D, F are their spawn points. The values ​​are coordinates.
3. Calculate potential fields
Above, I said that there are no barriers for the implementation of a potential field in my PL. Personally, I liked a very concise and quick solution from here , it’s only worth transferring a part of the emit function to your code, with a bit of fine-tuning with a file. It is necessary to divide all objects into three categories:
- Emptiness - saves and distributes further the charge of the field. Spunpoints and empty cells belong to such objects. By the way, a spunpoint must spread a charge, even if a character is standing on it.
- Barrier - does not save or distribute further the charge of the field. Such objects are all obstacles with which the player cannot interact (marked on the map "##").
- Battery - retains the value of the charge, but does not distribute further. This is necessary so that the field goes around these objects. Such objects are mines, players, taverns. If, for example, a player blocks a passage a width of one square, the signal will not be able to spread further.
Now, if it makes sense to bother with the speed of work, you need to divide the task into N parts (in the case of a single-board quad-core computer N = 3, in order to save one core for the main process and for the internal needs of the operating system) and feed the map and coordinates to the processes to get potential maps of all objects (my implementation on Python3 in one thread does not cope with a map size of 28x28 with 40+ objects, it is necessary to parallelize).
Multiprocessing for python
I use the module concurrent.futures, I beckon the simplicity of working with processes and threads.
How do I break a task:
How do I break a task:
g = list(board.objects.keys()) # , , # if len(g)%3 == 0: missions = (g[:len(g)//3], g[len(g)//3:2*len(g)//3], g[2*len(g)//3:]) else: missions = (g[:len(g)//3+1], g[len(g)//3+1:2*len(g)//3+1] , g[2*len(g)//3+1:]) pot_field = zero_field(data['game']['board']['size']) # , with concurrent.futures.ProcessPoolExecutor(max_workers=3) as pool: pp = [] for i in range(3): #worker_layer pp.append(pool.submit(worker_layer, board, targets=missions[i], coors=targets)) for i in pp: m = i.result() # if pot_field =='': pot_field = m else: for key in pot_field.keys(): if key in m: pot_field[key].update(m[key]) 4. Magic
Now we can turn to any point of the map to find out the distance of objects to it.
Starter kit to build is not the most intelligent AI
In order to verify that we are still doing everything correctly, I propose such a simple, but not without flaws, scheme:
- Take five points from our object: (x, y) - Stay, (x-1, y) - North, (x + 1, y) - South, (x, y-1) - West, (x, y + 1) - East. Eliminate those points that run into barriers ("##").
- For each of the remaining points:
- Find the signal value from the nearest tavern, the nearest not to our mine (= the smallest signal value for the selected categories);
- Take answer = 0;
- We use the rule for the nearest mine:
- If our_health <21 and distance_to_working == 0, then answer- = 100;
- Otherwise, if the distance to the mine == 0, then answer + = 990;
- Otherwise, answer + = 49 + mod (50, distance_to + 1);
- We use the rule for the nearest tavern:
- If our_health> 80 and distance_to_taverny == 0, then answer- = 100;
- Otherwise, if our health is> 50 or gold_number <2, then ignore;
- Otherwise, if distance_to_ tavern == 0, then answer + = 100;
- Otherwise, answer + = mod (mod (200, our_health), distance_to_ tavern + 1);
- We use the rule for each enemy:
- If our_health-health_ of the enemy> -19 and the number of employees> 0 and distance == 1, then answer + = 80;
- Our_Health-Health_Enemy> -19 and number of employees> 0 and distance == 1, then answer + = 100;
- Otherwise, if the distance is <4 and our_health <45, then answer + = -100 + 8 * distance;
- Select the point with the highest answer value, send the direction.
Pretty clumsy, non-optimized, but for starters, it will. It was one of the very first AI sketches for
Zaraza 0.1 . Try running the AI ​​by following these instructions and see a glimpse of the mind. For how the AI ​​plays according to these rules, you can see here , here and here . It becomes clear that on large maps, where they rarely encounter enemies, the AI ​​can fight with the fighters, simply avoiding meetings, and on medium and small maps, where clashes are inevitable, this primordium of intelligence cannot combat other AI. We need to work on optimizing the engine.Object exploration: mines
Consider the ways in which you can search for mines on the map:
Method 1 - Go to the nearest mine
Pros:
+ The easiest way.
Minuses:
- All other components of this venture
Comment:
If you stand at a crossroads with the same distance to the two nearest mines, you can choose any.
Three fights, laid out a little higher, reveal all the unviability of this method. Superfluous moves, illogical movements, turning circles - everything is replete with redundancy.
Method 2 - add weight for a good choice.
Pros:
+ Now AI will choose quantitatively more pleasant way.
+ Easy to implement.
Minuses:
- There is a better way.
Comment:
This method is really incredibly good. We will not look for the closest option, but the best one in the short term. For implementation, you can use the addition of all weights with the formula, for example, 600 / (n + 1), where n is the distance to the object. This will help to accurately reach the best place at an equal distance, and also makes more attractive points with more mines. In this case, it is worth making the mine itself, for example, with a weight of 1000 units, for otherwise the cell next to the two mines will have a similar attractiveness as the mine itself (600/1 = 600/2 + 600/2). The average Elo points for 100 battles increased from 1550 to 1833 only with a change in the method of searching for mines, this says a lot.
Method 3 - some plan that he follows
Part of the map, where this method will be effective
The algorithm is as follows:
- We make a list of all the mines that we can conquer with the current amount of health (to successfully mine a mine, you need to have at least 21 health units. Obviously, there will be enough of us for a maximum of 4 mines).
- Mentally we go to each mine, we win.
- Now we repeat paragraph 1 and 2, starting from the place of conquering a certain mine exactly until we have a list of all possible scenarios for capturing nearby mines (and for health counters, no more than four mines can be captured), you can even build a tree such combinations. Fortunately, the distance from each point to the mine we have.
- You can also look further - to assess the distance to the tavern, because it is a vital thing in this cycle.
- Choose the most delicious option
Pros:
+ A much better way to find mines.
+ Looks for the best "chains" to search for mines.
+ The most effective way, if not the existence of rivals.
Minuses:
- May be somewhat resource intensive.
- Does not take into account the activities of enemies.
Comment:
This method has advantages that cannot be ignored. If you work in this direction, you can achieve significant success, even sticking to the resources of the single-board. The estimated number of moves and the number of mines captured can be used as an estimating function or, for example,
( )/( ) . There may be many interesting ideas.Way geektimes
If you have an idea to find mines, put it in the comments, because I have nothing else to come to mind.
But how to make sure that the change in the bot engine made it better?
Collect statistics for 50/100/250 games!
Decide on the collected material. For me, the choice was simple:
- viewUrl - a link by which you can view the battle
- the place that we occupied in the battle
- the ratio of our gold and gold of the winner as an indicator of the success of the battle
- current Elo points
- whether we dropped out of the game prematurely (this can happen if there were problems with the Internet or if we crossed the limit of 1 second to send a solution)
- the size of the card (which often correlates with the winning place)
Now you need to choose a way to save this information. If you choose from simple, there are two options: .scv and Google Forms. It should be said that GF may be a more convenient option, as it adds a timestamp from under the box and statistics are available online. How to enter the answers in the form, you can search for the query "submit google form programming_lang".
Task at home
In the meantime, Hiktaim users have question number 2:
The screenshot shows a piece of the map:
Q - our player
S - enemy spawnpoint
The programmer Oknoz decided to add such a property: if the owner of an enemy spawnpoint has a dangerously small number of health points, then the spawnpoint begins to emit a repulsive potential field, which does not encourage close finding near this spawnpoint. But the player was trapped, becoming an excellent prey for an enemy player as soon as he was reborn. Oknoz is thinking about what needs to be done to prevent such situations from happening.
Any guesses? One of the possible solutions I will write in the comments under the spoiler.
Conclusion
So, step by step, you can create a brave and mighty warrior who will cross his swords with alpha-beta clipping and minimax adherents on an equal footing!
In the next part, we will consider possible behaviors for taverns, spunpoints, opponents, see how fields are formed, what a blocking is a priority field, and consider whether it is worth painting over the dead ends. And, of course, a couple of words about competing algorithms.
→ Link to Vindinium
→ The link to the Vindinium subreddium is a very useful thing, there you can hear the answers to very interesting and intricate questions.
→ Link to my githab with some old insights from Vindinium
Source: https://habr.com/ru/post/370767/
All Articles