The neural network learns the “Q function”, which takes as input the current environment state and outputs a vector containing expected rewards for each possible action. While it’s a bit tricky to grasp at first, the reasoning behind it is extremely elegant. ĭeep Q-Learning is a specific type of DRL.
#IMPLEMENT A CLASSIC SNAKE GAME CODE#
The example below comes from Code Bullet, while another example by Greer Viau can also be found on YouTube.ĭiagram of Reinforcement Learning. If the inputs only describe whether there are obstacles are in the immediate vicinity of the snake, then the snake isn’t aware of the “big picture” and is prone to getting trapped inside of its own tail. The performance is dependent on the inputs available to the model. Once the model is trained, predicting the next move is fast.Ĭons: Can be slow to converge because mutations are random. To play around with and visualize learning via genetic algorithm, see this tool by Keiwan. Over time, the evolutionary pressure will select for better and better models. Some of these mutations will hurt, some will not have any effect, and some will be beneficial. A new generation is then bred from the best individuals, with the addition of random mutations (e.g. In the case of Snake, the fitness function would just pick snakes with the highest scores. models) die, a fitness function selects the best individuals from a given generation. neural networks with random weights) are initialized in an environment and set loose. Each instance of a model corresponds to an organism in the natural selection analogy, while the model’s parameters correspond to the organism’s genes. The output would be an action like turn left or turn right. An input might be the snake’s distance to obstacles in the four main directions (up, down, left, right). A machine learning model (could be a neural network, for example, but does not need to be) maps perceptual inputs to action outputs. This approach is modeled off of biological evolution and natural selection. Genetic algorithms are another popular approach to this type of problem. The example below comes from AlphaPhoenix on YouTube. Requires some familiarity with graph theory. Pros: Guaranteed to beat the game, eventually.Ĭons: No machine learning involved - the algorithm must be encoded by hand. One approach even implemented this on an old Nokia phone! There are other non-ML techniques for playing snake, such as using the A* algorithm to find the shortest path to the food, but unlike the Hamiltonian Cycle approach, this is not guaranteed to beat the game. This involves dynamically cutting and restitching the Hamiltonian cycle to reach the apple quickly. Several approaches I found on the Internet are essentially just optimizations on this naive first approach, finding clever ways to cut off bits of the cycle without trapping the snake, so that the apple can be reached in fewer moves. Image by Author based on screenshot of Google Snake (Fair Use). If the snake just stays on this cycle, it is guaranteed to win. This is about 40,000 moves for a 20x20 board.Ī Hamiltonian cycle passing through all points of the board. Since this number decreases as the snake gets longer, we expect that on average, the snake will need ~N⁴/4 moves to beat the game using this strategy. If the apples appear randomly, we would expect that the snake will need to pass through half the currently open squares to reach the apple from its current position, or around N²/2 moves at the start of the game. In an NxN grid, it will take ~N² apples to grow a tail long enough to fill the board. This will work every time, but it is very boring and also wastes a lot of moves. Create a cyclic path that goes through every square on the board without crossing itself (this is known as a Hamiltonian Cycle), and then just keep following this cyclical path until the snake’s head is as long as the entire path. The game of Snake actually has a trivial, unbeatable solution. There’s a lot to be learned from these topics, so let’s dive right in! 1. Broadly speaking, the approaches to an AI Snake agent belong to one of three categories: non-ML approaches, genetic algorithms, and reinforcement learning. In this article, I review the pros and cons of various approaches, and include links to the original sources. The goal is to eat as many apples as possible without running into a wall or the snake’s ever-increasing tail.īuilding an AI agent to play Snake is a classic programming challenge, with many videos on YouTube showing various attempts using a wide range of techniques.
With each apple eaten, the tail’s snake grows one unit. The player controls a snake by pressing the arrow keys, and the snake has to maneuver around the screen, eating apples. You’ve probably played, or at least seen, the game of Snake before.
0 kommentar(er)
