In case you have any remarks or questions they are always welcome at either the education commissie, via the slack channel ec-helpme, or at our e-mail address education@serpentineai.nl.
In this lesson we are going to talk about the following things:
The GitHub links for this lesson are: Browse, Zip, Diff.
The links are currently only available for members.
In the previous section we managed to check the neighbouring cells of our position. In this lesson we are going to extend our search range to all possible tiles that we can reach. For this we have to implement a pathfinding/search algorithm. There are many different pathfinding algorithms, , A*, Dijkstra, Multi-agent etc.... For this tutorial we will take a look at one of the more intuitive algorithms namely Breadth-First Search (or BFS). First we will talk about the intuition of the algorithm, and then about the implementation.
For which tiles do you know if they are reachable? The neighbours for which check_left() or it's equivalent returns true. For all of these reachable neighbours we can again look at neighbours that can be reached and are not yet visited. And so on and so forth.
Do we really consider all reachable tiles this way though? Yes, because if a tile isn't connected via neighbours to your agents tile, there is simply no way to reach it. (In this game you can't jump or teleport or something like that.)
So by continuously checking the neighbours of the neighbours, we can find all reachable spots. For more information check the tab [BFS references]. Especially take a look at the animation to get a visual view of what is happening in the algorithm.
The term node, will be used to indicate a point on the grid (or graph). There is a start node, which is given to the algorithm and a function graph.neigbours(node) that returns the neighbouring nodes.
frontier = Queue()
frontier.put(start)
reached = set()
reached.add(start)
while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in reached:
frontier.put(next)
reached.add(next)
The above code explains what we are going to do:
frontier: will be a list that maintains all the places that we still have to visit, starting with our start location.reached: will be a set, which is similar to a list, but can not contain duplicates. That maintains all the (unique) nodes that we can reach / have visitedfrontier, this makes sure that the frontier list will get empty eventuallyIn the next lesson we'll look at how to actually get to a certain reachable tile, but for now we will keep it (relatively) simple and only look at which tiles are reachable. By doing this we will work on the code structure that is needed for pathfinding in the next lesson.
Let's declare a function can_move_to() in the class MyAgent that uses BFS to find a goal location. In our case it is more important to know if we can reach a specific spot, in comparison to knowing all reachable locations. The reason for this is that we do not just want to know if we we can reach a spot but also how we can reach it later on.
For this method (function in a class) we will need the parameters board and my_location just like the check_left() method. Along with this we ofcourse need goal_location. (same format as my_location) and don't forget 'type hinting'. Knowing the types of the parameters will make it easier to code the method.
The following sections will you guide you through the pseudocode to build the BFS algorithm.
def can_move_to(self, board: np.array, my_location: tuple, goal_location: tuple) -> bool:
""" BFS to a goal location. Returns True if it can be reached."""
pass
The pass keyword indicates to yourself, the compiler and others that the content still needs to be added.
But what should the content be? First of all we need one list to store all the tiles our algorithm has already 'visited' and one to store all the reachable neighbours of these tiles (excluding the ones that are on the first list). Let's call them visited and to_visit. We'll add my_location to the to_visit list. This might seem strange as our agent is already on this location, but the algorithm hasn't 'visited' my_location yet.
def can_move_to(self, board: np.array, my_location: tuple, goal_location: tuple) -> bool:
""" BFS to a goal location. Returns True if it can be reached."""
to_visit = [my_location]
visited = []
The BFS algorithm now prescribes to continually take one element out of to_visit and add all it's reachable neighbours to to_visit, until the goal tile is reached. As we need to repeat this action a lot of times a loop is a perfect fit. But what kind of loop should we use? Well, for loops are only applicable if the number of iterations is known before the loop starts, so in this instance we can only use a while loop.
We want to keep looping until there are no more visitable tiles. This can be implemented by while to_visit:, which will continue until to_visit is empty. At the start of every loop we'll want to take out the item at position 0. For taking an item out of a list we can use var.pop(index). Where var is variable of the type list from which you will take out an element, located at the position index.
The element in the list at index 0 is "in the front" of the list. We want to look at the points near our agents position first when using BFS. By appending (adding to the end) all elements we add to to_visit and extracting all elements at the front we ensure elements that are closer and thus added earlier, also get extracted earlier.
def can_move_to(self, board: np.array, my_location: tuple, goal_location: tuple) -> bool:
""" BFS to a goal location. Returns True if it can be reached."""
to_visit = [my_location]
visited = []
while to_visit:
point = to_visit.pop(0)
It's already time for another loop! This time to loop through all the possible neighbours. This needs to happen a predetermined amount of times, namely 4, so this time a for loop will work great. There is one big problem though, can you spot which?
The problem is that we do not yet have a list of these neighbours, so how will we get them? The coordinates of point (the tile that BFS is currently visiting) are known and we know the neighbours are left, right, up and down. Therefore we can compute the neighbours manually.
First, we'll need to store the neighbouring directions so we can loop over them. It is convenient to have a name for every direction as well as the change in coordinates a step in that direction would make. e.g.: a step to the left would decrease the x-coordinate by one, or formulated as a np.array: np.array([0, -1]). There are multiple ways to store this information. In this lesson we will use a dictionary, where the name of the direction is the key and the np.array the value.
There are two ways of making a dict in python, where the first method is based on the syntax key: value. The second method is assuming key=value, where the key has to be string, and has similar contrains to naming variables in python
directions = {
"left": np.array([0, -1]),
"right": np.array([0, 1]),
"up": np.array([-1, 0]),
"down": np.array([1, 0])
}
or
directions = dict(
left=np.array([0, -1]),
right=np.array([0, 1]),
up=np.array([-1, 0]),
down=np.array([1, 0])
)
Remember that numpy coordinates are stored as row, column (or y, x) instead of x, y.
Now that we have something to loop through we still need to program the loop and compute the new locations. The syntax for looping through a dictionary is for key, value in dictionary.items():. It is possible to add np.arrays using +, but point is stored as a tuple and we want our neighbour new_point to be a tuple again. Luckily converting these two is straight forward. np.array(point) will result in a np.array and tuple(np.array) will do the exact opposite.
directions = dict(left=np.array([0, -1]), right=np.array([0, 1]),
up=np.array([-1, 0]), down=np.array([1, 0]))
while to_visit:
point = to_visit.pop(0)
for key, value in directions.items():
# By making it a numpy array we can add the values
new_point = tuple(np.array(point) + value)
There is a special word for converting a variable type to another type in programming languages. This is called type casting. Now what is special about python, is that this type casting and type inferring is happing under the hood in the python.
For example:
my_int = 10
my_float = 5.0
There is no need for explicitly saying my_int = int(10) or prefixing it like int my_int or float my_float in python. The advantage is that all conversions are done for you. The disadvantage is that you don't always get the types that you expect in the end.
Great! Now that we have a possible neighbour we can check whether it is our goal. If it is, we can (for now) simply return True. Therefore we early terminate our BFS and do not have to wait for the whole method to finish.
directions = dict(left=np.array([0, -1]), right=np.array([0, 1]),
up=np.array([-1, 0]), down=np.array([1, 0]))
while to_visit:
point = to_visit.pop(0)
for key, value in directions.items():
# By making it a numpy array we can add the values
new_point = tuple(np.array(point) + value)
# Check if we have found the location
if new_point == goal_location:
return True
In order to check the nodes we have to do 3 things:
If the new_point is not our goal we'll need to keep looking. But before we can start looking at the neighbours of new_point we need to verify that this new neighbour is actually a valid move for our BFS algorithm. So with valid we mean: whether new_point is on the board, whether new_point isn't already visited and whether new_point is passable.
To test whether new_point is on the board we will used an if statement, followed by the continue keyword. continue will cause the current iteration of the loop to end. This fits our goal well, because we don't want to run the other tests if the point is not on the board. Remember that the coordinates of the board go from 0 up to (and including) 7.
The check whether new_point is already visited can be done in a similar way. Remember that element in var is True if var contains element.
The last check is a lot harder to make as the functions we made for checking whether a point is passible (e.g.: check_left()) all only work for one direction. So to check whether new_point is passable we need to use anif statement for every direction.
Each of these if statements should check whether we want to move in a certain direction (e.g.: left) and whether we can move in this direction (e.g. with check_left()). If this is the case, we can append new_point to the to_visit list. First implement this for moving left, and then add the other directions.
Remember that the key value of our looping dictionary was the direction name, see if you can use that value here.
Our example of this check uses the max() and min() function to make the code more compact, but this is by no means necessary.
# Either the row or column value is not on the board.
if min(new_point) < 0 or max(new_point) > 7:
continue
# We have already seen that point
if new_point in visited:
continue
There are similar if statements for the other directions.
if key == "left" and self.check_left(board, tuple(point)):
to_visit.append(new_point)
Note: we use the key value from our directions dictionary to find out in which direction we have to check.
Now we are almost done, there are two more things that we have to do.
for loop has ended we should not forget to add point to visited.while loop.The first things you can try yourself, as for the second one we will return False. As that is the opposite of the return True statemenent that we put in the code for if we could find the goal.
Since this is python make sure that you have indented the visited and return False at the correct levels. Otherwise the code will not run as expected.
while to_visit:
...
for key, value in directions.items():
...
if key == "left" and self.check_left(board, tuple(point)):
to_visit.append(new_point)
if key == "right" and self.check_right(board, tuple(point)):
to_visit.append(new_point)
if key == "up" and self.check_up(board, tuple(point)):
to_visit.append(new_point)
if key == "down" and self.check_down(board, tuple(point)):
to_visit.append(new_point)
visited.append(point)
return False
To test whether our method works we can set a goal ourself and call can_move_to(). Put the following code inside the act() method and run the program.
goal_location = (2, 2)
if self.can_move_to(board, my_location, goal_location):
print("Can now move to this location: ", goal_location)
Now that we have are finished implementing this we are going to commit this to the file management system. In the terminal we are going to type the following commands:
git add *
git commit -m "finished Pommerman lesson 3"
git push
The last line (git push) is only for the users that have created a repository on GitHub. Now if you would go and check it out in your own repository on GitHub.com you will see that the file serpentine/my_agent.py has been updated with the above code and the commit message is added.
In this lesson we took a look at the Breadth-First Search (BFS), a pathfinding algorithm. We started an implementation of this algorithm, resulting in a function that returns whether a specific tile can be reached from the agents current position.
If you are unsure if your code is correct, and you are a member, you can use the GitHub links to check. (back to top)