AI Challenge 2011 Ants. In the eyes of the participant Murashka (15th place)
The tournament attracted by its simplicity and gathered a wide audience. The idea came to taste and high school students and wise guru experience, remembering even the world computer chess championship in 1972.
The algorithms used by the leaders were approximately the same; there were two basic ones — search in width ( BFS ), to determine the nearest path to long-range targets and a minimax in close combat. The devil was hiding in the correct method of selecting goals and fine-tuning the details.
BFS illustration for multiple sources (by BenJackson):
To find the details that affect the result, it was necessary to do a lot of theoretical and experimental work.
For fast implementation, have a simple, easily modifiable core of the algorithm.
To set up quick and accurate tests to determine the usefulness of innovation (70 percent, it would seem, the useful changes had a negative effect).
But at the time of the start I did not know all this and, based on a quick analysis of the forum, I began to struggle with the time limit. In the end, a fast, but cumbersome and wide search variant was born, which was cumbersome and not very convenient for experimentation. The first version was ready in a few days, she only knew how to collect food, but easily climbed into the Top 100 on the official server.
I wanted something big and clean, but in the end it was realized with a truncated minimax and worked quite well.
Each turn, 5 cards were calculated on the assumption that the enemy would move all the ants in one direction or stand still. Then the map was divided into squares of 5 * 5 cells and my ants, entering the attack zone (5 pieces maximum), moved in all possible ways. The obtained results were collected by a minimax in the assessment and the most favorable combination of moves was chosen. For more correct processing of the joints, the 5 * 5 grid itself also slightly shifted each turn.
')
Now it was possible to equate the enemy ants closest to heal to food, the attack algorithm itself did the rest.
Details that significantly improved the game looked quite trivial:
I tried to implement the scheme proposed by Memetix (final 10th place)
According to the algorithm, each cell on the map was suggested to give value, according to the distance from the target. It would have been wonderful for me in the attack algorithm — I would simply add value to the overall score and a minimax would get the best combination. But right away nothing good happened - the collection of food was worse than the existing version and it was not possible to defeat the ants crowding at the intersections of the “fields” even after various dances with repulsion. There was no time left to finish the method. It was decided to leave as is and bring to mind the existing code.
The last coefficients are selected. 8 (4 + 4) copies with two different sets of constants hang on a TCP server around the clock. But to determine who does not help it better - constant timeouts due to the large number of players or when approaching a limit of 200 ants (teams to the server go a long time). In addition, the variation in the class of bots does not allow the evaluation algorithm to correctly determine the rating. The test set of cards also shows inconsistent results, so the final version goes slightly more aggressive (due to the 5x5 mask offset technique when calculating the attack) version. Also at the last moment, a bonus for moving in the direction of the food at the time of the attack is bolted. Tests together swore that it is useful.
The official server is in chaos, most of the major participants resubmit with the latest changes.
4 games without surprises. The choice of opponents is random.
Games are going very slowly.
Starting with the 5th installment, the organizers included the TrueSkill rating assessment algorithm - the rating consists of two factors: mu - the rating itself and sigma - reflecting the system's confidence in the rating. The overall rating is mu-3 * sigma. Contenders are selected with a close rating and with a smaller sigma. In practice, this led to the fact that because of the large sigma, the top bots play much less frequently than others.
For Goosebumps, the 5th game ended in that, having passed under the cover of the fog of war, on a small poor map, a bot that was not in the first two hundred, stole the only heal. Total -4 to mu and place in the fifth hundred. The casino is open with chic.
The rating of some players is considered with errors. Errors are corrected once again, the servers are restarted.
Games go even slower.
The starter packs enjoyed playing 20 games with each other with pleasure, the leaders gazing at them with envy and 6 games in assets. The organizers change the selection algorithm of rivals in order to equalize the number of games, after which they cut off to 5000th place. And in the evening up to the 3000th and extend the competition for a day and a half. Hallelujah!
Clipping in 2000 and 1000 places.
The Russian team teapotahedron at a distance of one game from xathis, all in anticipation of a change of leader ... no luck.
Murashka peacefully whispers in 20-ke.
Clipping in 500 places.
teapotahedron goes down (finish in 5th place).
But the script of the previous day is repeated with the Ukrainian GreenTea. This time successfully - the change of leader really happened 2 hours before the servers stopped. In addition, the algorithm for selecting opponents gave another failure, picking up the participant outside the cut-off limit of 500, and allocated all the server power to compensate for the unplayed games - the entire top half of an hour carefully sucks a paw.
But the miracle did not happen, xathis confidently and deservedly regained the first place, with which I congratulate him.
Murashka, who occupied 14th place a couple of hours before the finish, was ahead of Komaki from the last game in the in-person meeting. And at the same time, it was passed by the Russian SDil_ and Meduz. Again, the casino, but everything could be worse - the 15th place for this set of cards is a good result.
The fast but cumbersome code complicated the modification and landed a flight of fancy.
Much time is lost on trying to resolve a non-minimax battle.
Little attention is paid to the competent definition of goals and the distribution of ants between them. The ants tended to lump up in front of a group of opponents, instead of going to places where there are no enemies and capture the map.
Walking systems would definitely give an advantage, but how correctly and quickly to realize it did not occur.
The initial distribution was not effective. The closer to the heal, the more often the distant target could change as a result of the ants twitching, not knowing where to go.
Catching up an opponent who has a head start in a few months is harder than it seems.
Testing system, which allows to determine the utility - it is very important.
On the last day, everything changes dramatically, and the final competition is very different from testing.
Small errors need to be disposed of immediately - they accumulate and can lead to the fact that a good strategy will stop working and will be discarded for testing.
The idea is excellent, the work has been done tremendously, the organizers deserve all thanks. Without errors, too, was not, but we live in an imperfect world.
The controversial decision was to leave the bots competition from the starter pack. Organizers can be understood - I wanted to declare the mass. But with more than modest computing power, it caused inconvenience to real participants. However, the error is recognized and promised to filter for the future.
A set of cards with highly unstable results is also not entirely clear, because it is obvious that there are enough errors to correct TrueSkill.
Sharp surges and falls in ratings are probably also due to the set of maps and features of the selection algorithm, which was not sufficiently random. My version is that within the total set of final maps, clusters have been formed, which are sharply beneficial to one bots and not beneficial to others. As soon as the rating system, assessed by TrueSkill, came to an equilibrium state, the card selection algorithm ran into the next such combination and mixed the table for 5-10 games. Sigma closer to the end shrank to a minimum, already did not affect anything and could not compensate for the surges.
Final rating
Winner Report
Lastly, a little Ant-Art in the performance of Goosebumps.
All with the coming and good luck in the competition!
The algorithms used by the leaders were approximately the same; there were two basic ones — search in width ( BFS ), to determine the nearest path to long-range targets and a minimax in close combat. The devil was hiding in the correct method of selecting goals and fine-tuning the details.
BFS illustration for multiple sources (by BenJackson):
To find the details that affect the result, it was necessary to do a lot of theoretical and experimental work.
For fast implementation, have a simple, easily modifiable core of the algorithm.
To set up quick and accurate tests to determine the usefulness of innovation (70 percent, it would seem, the useful changes had a negative effect).
But at the time of the start I did not know all this and, based on a quick analysis of the forum, I began to struggle with the time limit. In the end, a fast, but cumbersome and wide search variant was born, which was cumbersome and not very convenient for experimentation. The first version was ready in a few days, she only knew how to collect food, but easily climbed into the Top 100 on the official server.
The collision algorithm with the enemy
I wanted something big and clean, but in the end it was realized with a truncated minimax and worked quite well.
Each turn, 5 cards were calculated on the assumption that the enemy would move all the ants in one direction or stand still. Then the map was divided into squares of 5 * 5 cells and my ants, entering the attack zone (5 pieces maximum), moved in all possible ways. The obtained results were collected by a minimax in the assessment and the most favorable combination of moves was chosen. For more correct processing of the joints, the 5 * 5 grid itself also slightly shifted each turn.
')
Now it was possible to equate the enemy ants closest to heal to food, the attack algorithm itself did the rest.
Details that significantly improved the game looked quite trivial:
- don't stand on your heel if you have nothing else to do or under attack
- don't push each other
- retreat to your heal
- bypass attacked cells
- prioritize attacking enemies that are too close to heal
- in the process of attack, move towards food (otherwise they would hang opposite the enemy)
- in a one-on-one game behave more aggressively.
2 weeks before deadline
I tried to implement the scheme proposed by Memetix (final 10th place)
According to the algorithm, each cell on the map was suggested to give value, according to the distance from the target. It would have been wonderful for me in the attack algorithm — I would simply add value to the overall score and a minimax would get the best combination. But right away nothing good happened - the collection of food was worse than the existing version and it was not possible to defeat the ants crowding at the intersections of the “fields” even after various dances with repulsion. There was no time left to finish the method. It was decided to leave as is and bring to mind the existing code.
Deadline day
The last coefficients are selected. 8 (4 + 4) copies with two different sets of constants hang on a TCP server around the clock. But to determine who does not help it better - constant timeouts due to the large number of players or when approaching a limit of 200 ants (teams to the server go a long time). In addition, the variation in the class of bots does not allow the evaluation algorithm to correctly determine the rating. The test set of cards also shows inconsistent results, so the final version goes slightly more aggressive (due to the 5x5 mask offset technique when calculating the attack) version. Also at the last moment, a bonus for moving in the direction of the food at the time of the attack is bolted. Tests together swore that it is useful.
The official server is in chaos, most of the major participants resubmit with the latest changes.
Finals
The first day
4 games without surprises. The choice of opponents is random.
Games are going very slowly.
Second day
Starting with the 5th installment, the organizers included the TrueSkill rating assessment algorithm - the rating consists of two factors: mu - the rating itself and sigma - reflecting the system's confidence in the rating. The overall rating is mu-3 * sigma. Contenders are selected with a close rating and with a smaller sigma. In practice, this led to the fact that because of the large sigma, the top bots play much less frequently than others.
For Goosebumps, the 5th game ended in that, having passed under the cover of the fog of war, on a small poor map, a bot that was not in the first two hundred, stole the only heal. Total -4 to mu and place in the fifth hundred. The casino is open with chic.
The rating of some players is considered with errors. Errors are corrected once again, the servers are restarted.
Games go even slower.
Third day
The starter packs enjoyed playing 20 games with each other with pleasure, the leaders gazing at them with envy and 6 games in assets. The organizers change the selection algorithm of rivals in order to equalize the number of games, after which they cut off to 5000th place. And in the evening up to the 3000th and extend the competition for a day and a half. Hallelujah!
Day four
Clipping in 2000 and 1000 places.
The Russian team teapotahedron at a distance of one game from xathis, all in anticipation of a change of leader ... no luck.
Murashka peacefully whispers in 20-ke.
Day Five - Final
Clipping in 500 places.
teapotahedron goes down (finish in 5th place).
But the script of the previous day is repeated with the Ukrainian GreenTea. This time successfully - the change of leader really happened 2 hours before the servers stopped. In addition, the algorithm for selecting opponents gave another failure, picking up the participant outside the cut-off limit of 500, and allocated all the server power to compensate for the unplayed games - the entire top half of an hour carefully sucks a paw.
But the miracle did not happen, xathis confidently and deservedly regained the first place, with which I congratulate him.
Murashka, who occupied 14th place a couple of hours before the finish, was ahead of Komaki from the last game in the in-person meeting. And at the same time, it was passed by the Russian SDil_ and Meduz. Again, the casino, but everything could be worse - the 15th place for this set of cards is a good result.
Errors
The fast but cumbersome code complicated the modification and landed a flight of fancy.
Much time is lost on trying to resolve a non-minimax battle.
Little attention is paid to the competent definition of goals and the distribution of ants between them. The ants tended to lump up in front of a group of opponents, instead of going to places where there are no enemies and capture the map.
Walking systems would definitely give an advantage, but how correctly and quickly to realize it did not occur.
The initial distribution was not effective. The closer to the heal, the more often the distant target could change as a result of the ants twitching, not knowing where to go.
Notes on the future
Catching up an opponent who has a head start in a few months is harder than it seems.
Testing system, which allows to determine the utility - it is very important.
On the last day, everything changes dramatically, and the final competition is very different from testing.
Small errors need to be disposed of immediately - they accumulate and can lead to the fact that a good strategy will stop working and will be discarded for testing.
Organization
The idea is excellent, the work has been done tremendously, the organizers deserve all thanks. Without errors, too, was not, but we live in an imperfect world.
The controversial decision was to leave the bots competition from the starter pack. Organizers can be understood - I wanted to declare the mass. But with more than modest computing power, it caused inconvenience to real participants. However, the error is recognized and promised to filter for the future.
A set of cards with highly unstable results is also not entirely clear, because it is obvious that there are enough errors to correct TrueSkill.
Sharp surges and falls in ratings are probably also due to the set of maps and features of the selection algorithm, which was not sufficiently random. My version is that within the total set of final maps, clusters have been formed, which are sharply beneficial to one bots and not beneficial to others. As soon as the rating system, assessed by TrueSkill, came to an equilibrium state, the card selection algorithm ran into the next such combination and mixed the table for 5-10 games. Sigma closer to the end shrank to a minimum, already did not affect anything and could not compensate for the surges.
Final rating
Winner Report
Lastly, a little Ant-Art in the performance of Goosebumps.
All with the coming and good luck in the competition!
Source: https://habr.com/ru/post/135280/
All Articles