Google AI Challenge. How to write your bot. Part 1, 2
This topic is a translation of the first two parts of the guide on writing your own bot for the Google AI Challenge.
All code is written in Python.
Step 1: How to avoid collisions
Plan
To ants do not come across it is necessary:
1) Prevent the movement of one ant to another;
2) Prevent the movement of two ants to the same point;
3) track the location information of all our ants.
Implementation
To track information about where ants are located, we will use a dictionary (aka HashMap, associative array, JavaScript-object). Each key of the array will be a position, and the value will be an ant that moves to this point. The location will be a tuple (list, array) of two values - rows and columns on the map. Then we can check the list before moving so that 2 ants do not move to the same place. Every time we move an ant, we need to update the list.
This check will be useful later in the tutorial, so we will make a function that checks if this step is possible. It returns a logical (true or false) value.
Code
Let's cut out the comments from the code from the example and insert the new code: new code:
')
def do_turn(self, ants): # track all moves, prevent collisions orders = {} def do_move_direction(loc, direction): new_loc = ants.destination(loc, direction) if (ants.unoccupied(new_loc) and new_loc not in orders): ants.issue_order((loc, direction)) orders[new_loc] = loc return True else: return False # default move for ant_loc in ants.my_ants(): directions = ('n','e','s','w') for direction in directions: if do_move_direction(ant_loc, direction): break (Note: Make sure the indents are correct. In Python, indents define blocks of code and scope, so indents must be correct)
The Do_move_direction function takes an ant position (tuple (row, column)) and direction ('N', 'e', 'S' or 'W') and tries to execute the movement. This function is inside a class method (which is also a function) and this is normal in Python. (If you are writing in another language, you may need to put the function in a different place) We use some predefined functions from the initial bot:
ants.destination takes the location and direction and returns the destination for us. This function handles the movement of an ant over the edge of the map; we do not need to think about it.
ants.unoccupied takes a location and determines if an ant can be moved there. This is better than ants.passable, which will not allow us to move to food or other ants.
The associative orders array is used to track current movements. The new_loc busy check and its absence in the orders array will help prevent collisions.
Result
Let's run the bot again and see:
C:\aichallenge>tutorial.cmd
running for 60 turns
ant_count c_turns climb? cutoff food r_turn ranking_bots s_alive s_hills score w_turn winning
turn 0 stats: [1,1,0] 0 [1,1] - 18 0 None [1,1] [1,1] [1,1] 0 None
turn 1 stats: [1,1,0] 0 [1,1] - 16 1 [0,0] [1,1] [1,1] [1,1] 1 [0,1]
turn 2 stats: [2,1,0] 0 [1,1] - 16 1 [0,0] [1,1] [1,1] [1,1] 1 [0,1]
...
turn 60 stats: [1,5,0] 0 [1,1] - 12 1 [0,0] [1,1] [1,1] [1,1] 1 [0,1]
score 1 1
status survived survived
playerturns 60 60Repeat: http://aichallenge.org/ants_tutorial_step_1.php
Already better, but still not very good. One lone ant came out and fought with HunterBot. This is not a suicide, but an improvement. In addition, we created a helper function that will come in handy later.
Step 2: Collect Food
Plan
We need more than two ants to win, and there is food not far from the starting position of the ant! Let's try to collect it. We have to move the ant to the food to collect it. We also want to do this effectively. Have you noticed that HunterBot sent half of all its ants for food in the last game? It seems that this may be ineffective.
We are going to implement something similar to the priority queue. We will make a list of all our ants, and then see how far it is from each meal. Then we will sort the list and send each ant to the nearest food, but only one ant to one food. Other ants will be free and will be engaged in other important matters. We will also get rid of the silly default moves that are left from the starting bot.
Implementation
To track information about the food, for which the ants are already going, we need another array. It will store the location of the target food as a key, and the location of the ants that follow it as a value. We can check the target key to make sure that we do not send two ants to the same food. We will create another helper function to make a slightly different type of movement. Instead of the location of the ants and the direction, we will make the location of the ants and the target location, and the function will figure out the direction.
Code
Create the following functions after the do_move_direction function:
targets = {} def do_move_location(loc, dest): directions = ants.direction(loc, dest) for direction in directions: if do_move_direction(loc, direction): targets[dest] = loc return True break else: return False Array of targets tracks ants and their target is food. We use another standard bot function to help us:
ants.direction takes the current location and target, and returns a list of the nearest direction "in a straight line". If the target is at the top left, it will return ['N', 'W'], and we should then try to move our ant in one of these two directions. If the target is right below, it will return ['S'] - a list of one element.
Replace the move function with this:
# find close food ant_dist = [] for food_loc in ants.food(): for ant_loc in ants.my_ants(): dist = ants.distance(ant_loc, food_loc) ant_dist.append((dist, ant_loc, food_loc)) ant_dist.sort() for dist, ant_loc, food_loc in ant_dist: if food_loc not in targets and ant_loc not in targets.values(): do_move_location(ant_loc, food_loc) Here we have a list - ant_dist - which will store for each ant the combination of food and distance as a tuple (distance, ant_loc, food_loc). The list is built with a nested loop to give us every combination. Next we sort the list. Python lists have several useful sorting functions. To sort a tuple, the python will compare the first values of each tuple, and then, if they are the same, move to the second value, and so on. That is why we saved the distance as the first value to make sure that the shortest distance is first on the list.
Next, we loop through the sorted list to check if we have any free ants that can collect food. Food_loc not in targets checks if the food has an ant that is already following it. Ant_loc not in targets.values () checks that the ant has not yet been given the task. If the ant is found, we call do_move_location.
Result
Let's run the bot again and see:
C:\aichallenge>tutorial.cmd
running for 60 turns
ant_count c_turns climb? cutoff food r_turn ranking_bots s_alive s_hills score w_turn winning
turn 0 stats: [1,1,0] 0 [1,1] - 18 0 None [1,1] [1,1] [1,1] 0 None
turn 1 stats: [1,1,0] 0 [1,1] - 16 1 [0,0] [1,1] [1,1] [1,1] 1 [0,1]
turn 2 stats: [1,1,0] 0 [1,1] - 16 1 [0,0] [1,1] [1,1] [1,1] 1 [0,1]
...
turn 60 stats: [4,6,0] 0 [1,1] - 6 1 [0,0] [1,1] [1,1] [1,1] 1 [0,1]
score 1 1
status survived survived
playerturns 60 60Repeat: http://aichallenge.org/ants_tutorial_step_2.php
All the food we could see was captured. If you look closely at the repetition, you can see we still have 3 ant anthill that can not appear. In the future it is better to take care of this. If ants can't get out, they can't help us win.
Original:
PS while this article was passing through the sandbox, webkumo published a similar article . His article contains Ants Tutorial and Step 1: Avoiding collisions, this is Step 1: Avoiding collisions and Step 2: Gathering Food.
Source: https://habr.com/ru/post/130931/
All Articles