A search agent for a Game of Thrones themed search problem. This project includes both a generic representation of a search problem and its required constituants, as well as a specific implementation of the Winter has come search problem.
This project uses search to help Jon Snow save Westeros. The field where the white walkers are frozen in place can be thought of as an m x n grid of cells where m, n >= 4 . A grid cell is either free or contains one of the following: a white walker, Jon Snow, the dragonstone, or an obstacle. Jon Snow can move in the four directions as long as the cell in the direction of movement does not contain an obstacle or a living white walker. To obtain the dragonglass by which the white walkers can be killed, Jon has to go to the cell where the dragonstone lies to pick up a fixed number of pieces of dragonglass that he can carry. In order to kill a white walker, Jon has to be in an adjacent cell. An adjacent cell is a cell that lies one step to the north, south, east, or west. With a single move using the same piece of dragonglass, Jon can kill all adjacent white walkers. If Jon steps out of a cell where he used a piece of dragonglass to kill adjacent walkers, that piece of dragonglass becomes unusable. Once a white walker is killed, Jon can move through the cell where the walker was. If Jon runs out of dragonglass before all the white walkers are killed, he has to go back to the dragonstone to pick up more pieces of dragonglass. The project formulates a plan that Jon can follow to kill all the white walkers. An optimal plan is one where Jon uses the least number of pieces of dragonglass to kill all the white walkers.
- Breadth-first search.
- Depth-first search.
- Iterative deepening search.
- Uniform-cost search.
- Greedy search.
- A* search.
- Optimal attacks.
- Manhattan distance and attack.
Our implementation for the search tree node goes as follows, we included the current state of the world, the parent node of this current node, the operator applied on said node to generate this one. We also included the total path cost from the root as well as the depth of the node in the search tree.
The class also includes a method that gets the complete path from this node to the root as a list of search tree nodes. This was used to backtrack when the search algorithm finds a node that passes the goal test, so that we are able to get the sequence of operators need to get the solution.
The search problem class contains a list of the possible operators and the initial state of the world. Moreover, it includes the goal test function which checks if a search tree node satisfied the goal condition defined in the problem. Additionally, it includes a path cost function which calculates the cost of a sequence of operators.
The search functions as follows, It contains a data structure which is defined by the queuing function. The initial state is added into a search tree node with no cost, parent or operator and said node is added into the data structure. From then out a node is removed from the data structure and is checked if it passes the goal test. If the node passes the goal test, then a solution is found and the method returns the node. Otherwise, the node is expanded by applying all other operators on it and adding the resulting nodes using to the queue using the queuing function. This process continues until a node passes the goal test, in which case a solution is found, or the queue becomes empty, which indicates that the is no solution for said problem.
To expand a node, all operators are applied on said node, and if they are applicable they resulting nodes are added into a list which is returned to the search method as the result of expansion of the input nodes.
The implementation for Save Westeros goes as follows, we generate the grid with a fixed size, random locations and random number of White Walkers and Obstacles. A single Dragon Stone at a random location. Then we initialize our 5 operators with their costs.
Westeros State is a child class of the abstract class state, it is responsible for representing the current state of the world in the Save Westeros problem. It consists of the following:
- grid: a reference to the map generated by the genGrid() function. This map is not manipulated in any way and only there for reference.
- width, height: variables representing the width and the height of the grid.
- jonX, jonY: represents the current position of the agent in the grid.
- dragonStone: the position of the dragon stone cell were the agent can go and pick up dragon glass.
- obstacles: A hash set containing the positions of the obstacles in the map. This hash set is never modified.
- whiteWalkers: A hash set containing the positions of the white walkers in the map. This hash set is never altered. When an attack action succeeds this hash set is cloned and the update is applied to the new one.
- dragonStoneLimit: The amount of the dragon glass the agent can pick when visiting a dragon stone cell.
- dragonStoneCarried: The amount of dragon glass the agent is currently carrying.
- enemyCount: The number of white walkers still alive in the map.
The genGrid function is responsible for generating a grid with random number and position of white walkers and obstacles, and a random position for the dragon stone. The method implementation goes as follows, we randomize the number of the white walkers and obstacles within a range of 10 percent to 25 percent of the grid size, then we initialize a hash set for the obstacles with the number of obstacles to be generated as its size, and do the same for the white walkers. Then we used a do while that picks a random x and random y values within the size of the grid and checks the corresponding cell if its cell (n-1, m-1) it goes back to the loop and randomizes another location as this position is the initial position for Jon Snow. After we randomize a valid position, we add the dragon stone in this cell. then we go into another loop were we keep generating random positions and we only output a cell when it is equal to null meaning that this cell does not contain anything, whenever we find a valid cell we add it to the hash set of white walkers and decrement the whitewalkers to be summoned count. We keep doing this till the whitewalkers to be summoned count reaches zero. Then we do the same process with the obstacles. After we spawn the cells with obstacles, we loop over the whole grid and check every cell, if the cell is equal to null it means that there is no obstacle or whitewalker or dragonstone so we mark the cell as an empty cell.
An operator is an object which has a cost and name of the operator. It has an abstract method called apply that every operator should implement, this method takes a search tree node as input and outputs either the new node to be expanded or null in case that the operator cannot be done. It uses a path cost function to calculate the cost for the new generated node.
When the agent decides to go north, we check that the cell is not on the most north column of the map and the new cell does not contain a white walker or an obstacle. If the input node is not a root node, we check that the parent node was not at the same new position to avoid repetitive redundant moves, unless the number of Dragon Glass changed, as that indicates that the movement had a purpose other than just moving around, which would be visiting the Dragon Stone cell. If the new cell we are going to is a dragon stone cell, the dragon glass is collected automatically and the dragon stone capacity of the agent is filled.
When the agent decides to go south, we check that the cell is not on the most south column of the map and the new cell does not contain a white walker or an obstacle. If the input node is not a root node, we check that the parent node was not at the same new position to avoid repetitive redundant moves, unless the number of Dragon Glass changed, as that indicates that the movement had a purpose other than just moving around, which would be visiting the Dragon Stone cell. If the new cell we are going to is a dragon stone cell, the dragon glass is collected automatically and the dragon stone capacity of the agent is filled.
When the agent decides to go east, we check that the cell is not on the most east column of the map and the new cell does not contain a white walker or an obstacle. If the input node is not a root node, we check that the parent node was not at the same new position to avoid repetitive redundant moves, unless the number of Dragon Glass changed, as that indicates that the movement had a purpose other than just moving around, which would be visiting the Dragon Stone cell. If the new cell we are going to is a dragon stone cell, the dragon glass is collected automatically and the dragon stone capacity of the agent is filled.
When the agent decides to go west, we check that the cell is not on the most west column of the map and the new cell does not contain a white walker or an obstacle. If the input node is not a root node, we check that the parent node was not at the same new position to avoid repetitive redundant moves, unless the number of Dragon Glass changed, as that indicates that the movement had a purpose other than just moving around, which would be visiting the Dragon Stone cell. If the new cell we are going to is a dragon stone cell, the dragon glass is collected automatically and the dragon stone capacity of the agent is filled.
When the agent decides to use the Attack operator the following sequence is done, we check that Jon Snow has at least one dragon stone, then we check if there are any enemies in the adjacent positions in the four cardinal directions of his position. In case any of the two conditions failed the operator is considered non applicable, and no new state is returned as a result of applying the attack operator. In the case that both conditions were satisfied, we update the carried dragon stones by checking the current cell, if its a dragon stone cell, the carried dragon stones is set to the dragon stones limit, otherwise we decrement one dragon stone. To do the attack operation we initialize a counter for the enemies killed then we clone the hash set containing the enemies location to a new hash set, then we start checking every one of the four cells, if an enemy exists, we remove it from the hash set and increment the enemies killed counter. Finally, we initialize a new state with the updated enemy set, carried dragon stones and the number of enemies killed. The cost of the attack should be higher than the movement cost needed to go from the initial position to the farthest point in the map. This is to allow optimal dragon stone usage as the agent should be allowed to move as much as it needs to get the optimal position for an attack.
The DFS is implemented as a stack of search tree nodes. DFS can add and remove nodes from the stack by .push() and .pop() functions of the Java Stack implementation respectively.
This stack data structure was chosen due to how DFS works, which is by adding new nodes to the beginning of the queue, and removing nodes from the beginning of the queue, making it a LIFO data structure.
The BFS is implemented as a linked list of search tree nodes. BFS can add and remove nodes from the linked list using the .add() and .removeFirst() functions of the Java LinkedList implementation respectively.
This linked list data structure was chosen due to how BFS works, which is by adding new nodes to the beginning of the queue, and removing nodes from the end of the queue, making it a FIFO data structure.
The Iterative Deepening Search is implemented similar to DFS, where it uses a generic stack data structure for its operations. However it has a max depth variable which determines how deep a node could be when added. We start with a depth of zero and we start expanding the nodes till we have an empty queue. Once the queue is empty, we increment the depth by 1 and we clear the stack and iterate all over again starting from the initial State. We do this till we find our goal or iterate over the max depth.
The uniform cost search is implemented as a priority queue of search tree nodes. We are using a comparator here to order the nodes based on their path cost. By doing so, we are guranteed to get the solution with the actual lowest cost, since we sort nodes based on their path cost and we retrieve the node with the lowest cost in the queue. Thus, when having positive costs, the path between the root node and the first node that passes the goal test should produce an optimal plan.
Greedy Search is implemented as a priority queue of search tree nodes. It is also using a comparator same as the Uniform Cost Search. The difference here is that it prioritizes the nodes based on the estimate from a chosen heuristic function.
A Star Search is implemented as a priority queue of search tree nodes. It is also using a comparator same as the Uniform Cost Search and Greedy Search. The difference here is that it prioritizes the nodes based on the path cost summed with the value from the heuristic function.
This heuristic estimates the cost to be the number of enemies divided by three, rounded upward to the nearest integer, then multiplied by the attack cost. This heuristic does not take into consideration the movement cost, both in terms of reaching the While Walkers and to pick up the Dragon Stone. Moreover, it assumes that each attack would kill three White Walkers, which is the optimal case as killing four white walkers with one attack is not possible with the given problem restrictions. So at any point this estimate is going to be lower or equal to the cost needed to reach the goal state. Therefore this heuristic is admissible.
This estimate from this heuristic function depends on whether the agent has at least one Dragon Glass or not, as well as the enemy count. If it does, then the estimate is equal to the Manhattan distance to the furthest agent from the target, minus one, multiplied by the movement cost, summed with the attack cost. This estimates how much it would cost to kill the last enemy in terms of moving adjacent to them and performing an attack.
If the agent does not have any Dragon Glass, then the estimate is equal to the Manhattan distance to the Dragon Stone, and the Manhattan Distance to the furthest enemy from the Dragon Stone position, minus one, multiplied by the movement cost, summed with the attack cost. This estimates how much it would cost to kill the last enemy in terms of moving to the Dragon Stone to pick up Dragon Glass, then moving adjacent to them and performing an attack.
If the enemy count is equal to zero, the heuristic function estimates the cost to be zero.
This heuristic is admissible as it only cares about the last enemy, so it definitely underestimates when there's more than one enemy. And in the case of one enemy, it either exactly estimates the cost needed to kill it, or underestimates it if there are obstacles in the way to it, so the movement cost would be greater than the Manhattan distance.
Done as a part of Artificial Intelligence course.