Q-Learning is a model-free reinforcement learning algorithm that learns an optimal action-value function, or Q-function, which tells how good it is to take a certain action in a certain situation. Deep learning helps Q-Learning handle larger and harder tasks by using a neural network.

• Hyperparamaters are external configuration variables that define the training process of the deep learning model.
• Learning Rate (α): how much the model should change with each training step
• Discount Factor (γ): how much the agent values future vs immediate rewards
• Exploration Rate (ϵ): probability the agent will take a random action instead of the best-known action

The Epsilon-Greedy policy is a simple decision-making strategy that balances exploration and exploitation. Exploitation involves choosing the action that is believed to yield the highest reward while exploration involves selecting a random action to discover potentially better options. The parameter epsilon controls this balance, beginning training with a high exploration rate that slowly decays to a minimum after each iteration.

To stabilize training, past experiences are stored in a replay buffer. Instead of training on only the most recent experience, the agent randomly samples a batch of experiences from the buffer. This allows the agent to learn from the same experiences multiple times, reducing the correlation between consecutive experiences.

The Q-values and target Q-values are then calculated. A loss function measures the difference between these values and the network is updated based on the gradients of the loss.

Just like the original game, there are pellets scattered across the level that the player must gather to win. There are 4 ghosts that navigate the maze and are constantly alternating between chasing the player and scattering to their respective corners of the map. Each ghost also has a unique targeting system when they are in chase mode.

• Blinky (Red): The player's position
• Pinky (Pink): 4 tiles in front of the player's position
• Inky (Cyan): The end of the vector from Blinky's position to the player's position times 2
• Clyde (Orange): The player's position if they are farther than 8 tiles away, the bottom-left corner of the map otherwise

The game officially begins when the first pellet is obtained. Blinky enters the maze first, and the rest become active as the player progresses the level. There are also 4 power pellets, one near each corner of the map, that will briefly frighten the ghosts and allow them to be eaten by the player. If a ghost is eaten, they are sent back to their home area and are temporarily inactive. Otherwise, if the player is eaten by a ghost, the player respawns at the starting point and loses a life. If all 3 lives are lost, the game is over.

Two lists, an open list and a closed list, are used to prevent the algorithm from checking a tile more than once and to allow backtracking if needed. Nodes in the closed list represent tiles that have been visited, while nodes in the open list represent tiles that are available to be visited. Initially, the open list contains just the start node.

The algorithm begins by checking if the open list is empty. An empty open list means that all available tiles have been checked and a path from the start tile to the end tile does not exist. Otherwise, set the current node to the next node in the open list and move it to the closed list. If the current node is the end node, a path has been found and the algorithm exits. Each node keeps track of their parent node, allowing the path to be reconstructed. If the current node is not the end node, generate all available neighbors and add them to the open list. This process repeats until all nodes have been checked or a path to the end node has been found.

All four of the implemented algorithms function in this way, only differing by how they select the next node from the open list. Breadth-First Search uses the first-in, first-out (FIFO) method, and Depth-First Search uses the last-in, first-out (LIFO) method. Greedy Best-First Search explores the tile that is closest to the end. The estimated path cost from a given node to the end node, also known as the node's h-cost, is calculated for each node when they are created, and the open list is sorted by shortest h-cost. A* utilizes each node's h-cost, but also takes into account each node's g-cost. This is the exact path cost from a given node to the start node. A node's f-cost is the sum of a its g-cost and h-cost, and A* chooses the next node with the lowest f-cost.