Snake Game AI

This lesson will teach you how to turn the snake game from a human-played game to an AI-played game

If you have not completed the previous lesson to set up the snake game, you can start from this template Snake Game.

Snake AI Introduction



    What was your best score at the snake game? The maximum score for the game in a 10x10 grid would be 100, but that would take a lot of practice to be able to do.

    Although you can practice and become better, there will always be things that humans will find more challenging than a programmed AI. One challenge is the speed of the game. The computer can make decisions much faster than you could, not matter how good your reflexes.

    However, people tend to be better at computers when it comes to long-term planning. Unless there is a specific solved solution to a problem, a program might not be flexible in their decision making to make the right call in a situation.

    This lesson will be about expanding our snake game so that we can create our own AI systems to try to play the game. We're going to:

    1. Refactor the current system so that it is easier to plug-and-play different AI strategies
    2. Create an AI that acts completely randomly
    3. Create an AI that acts randomly, but also reasonably
    4. Create an AI that tries to get to the goal as fast as possible

Refactoring Model System



    Our system right now is designed for a person to play it. Inside of Game class, we have a bunch of logic related to taking in user input and handling it.

    In order to expand our system, we're going to create a system where each mode of playing the game is a different model, called a Solver.

    We already have one model, which is having the player use the keypad to make decisions, so we're going to start with that.

    To do that, we're going to:

    1. Create a base model class with two methods, move() and user_input()
    2. Create a child model class called HumanSolver that will allow the player to play with the arrow keys.
    3. Have our Game class take in a model to decide how movement and user input works, and moving relevant functionality over to the model system.

    First, let's create our base model class. Create a new python file called base_game_model.py. 

    class BaseGameModel:

    def __init__(self, model_name):
        self.model_name = model_name
        
    def move(self, environment):
        pass

    def user_input(self, event):
        pass


    For right now, we just have the methods of this class stubbed, which means they don't do anything. But when we implement a specific model, it's going to change the class's behavior.

    Next, We're going to create the HumanSolver class. Create a file called human_solver.py. Most of the code here is simply taken from the Game class, with a few minor adjustments

    1. The user_input() method no longer handles pressing "q" to exit the game. That behavior will be handled at the top game level
    2. We inherit from the BaseGameModel class, and we use that class's init() method to set up our model's name. 

    from base_game_model import BaseGameModel
from pygame.locals import K_UP, K_DOWN, K_LEFT, K_RIGHT
from action import Action

class HumanSolver(BaseGameModel):

    action = None

    def __init__(self):
        BaseGameModel.__init__(self, "Human")

    def move(self, environment):
        if self.action is None:
            return environment.snake_action
        backward_action = self.action[0] == environment.snake_action[0] * -1 or self.action[1] == environment.snake_action[1] * -1
        return environment.snake_action if backward_action else self.action

    def user_input(self, event):
        if event.key == K_UP:
            self.action = Action.up
        elif event.key == K_DOWN:
            self.action = Action.down
        elif event.key == K_LEFT:
            self.action = Action.left
        elif event.key == K_RIGHT:
            self.action = Action.right


    Most of this code should look familiar. It's code that was inside the Game class.

    Now that we have our human_solver model set up, we need to go clean up our Game class.

    Firstly, we're going to change our imports, and we're going to have the class take in one more variable, a model

    We're only going to recognize the q key input, and we're going to import our new HumanSolver class. After taking in the model, we're going to store it inside the Game class. 
    import pygame
import sys
from constants import Constants
from point import Point
from color import Color
from environment import Environment
from objects import WallScreenObject, SnakeScreenObject, FruitScreenObject
from action import Action
from pygame.locals import K_q
from human_solver import HumanSolver

class Game:

    pygame.init()
    pygame.display.set_caption("Snake Game")
    action = None

    def __init__(self, model, fps, screen_width, screen_height):
 
        self.model = model
        self.screen = pygame.display.set_mode((screen_width, screen_height))
        self.fps = fps


    Make sure to remove the move() and user_input() methods from the class, so that you don't get mixed up with adding the model system.

    Now, we're going to change our play_screen() method to let the model handle movement and user input. 

        def play_screen(self):
        for event in pygame.event.get():
            if event.type == pygame.KEYDOWN:
                if (event.key == pygame.K_q):
                    self.quit_game()
                else:
                    self.model.user_input(event)
        pygame.time.Clock().tick(self.fps)
        self.environment.eat_fruit_if_possible()
        move_action = self.model.move(self.environment)
        if (self.environment.step(move_action) == False):
            self.game_started = False
        self.sync_screen_with_environment()
        self.draw_screen()
        pygame.display.update()


    Lastly, we're going to initialize our model, and pass it in to the instantiation of the Game class at the bottom of the code. 

            score_text_rect.center = (self.navigation_bar_height/2, self.navigation_bar_height/2)
        self.screen.blit(score_text, score_text_rect)
        
solver = HumanSolver()
Game(solver, Constants.FPS, Constants.SCREEN_WIDTH, Constants.SCREEN_HEIGHT+Constants.NAVIGATION_BAR_HEIGHT)


    If you did everything right, you should be able to play the game the exact same way as before! When working on a big project, it can be helpful to revisit your code to prepare for adding additional functionality.

    With our new model setup, creating new AI to try to win the snake game will be a snap.

Random AI



    Playing a game can be tiring and stressful sometimes! It's time to let the computer take over.

    The first AI that we are going to make is a purely random AI. It won't have any intelligence, it will just pick a direction and try to go there on every step.

    This AI can be a great baseline when you're making a customized AI. If the AI logic that you write isn't more effective than a purely random AI, it might be time to go back to the drawing board.

    To make this AI, we're going to do the following:

    1. Add a helper functionality inside of Environment to make choosing directions easier
    2. Create a new model class
    3. Set our model to play inside of our game.

    To get started, go to the Environment class and add this new method.

    This method will take the list of all actions, and remove the action of the reverse direction. That way, our random AI can't choose that option (all other potentially terrible actions allowed!) 

        def eat_fruit_if_possible(self):
        if self.fruit[0] == self.snake[0]:
            self.snake_length += 1
            self.set_fruit()
            return True
        return False
    
    def possible_actions_for_current_action(self, current_action):
        actions = Action.all()
        reverse_action = (current_action[0] * -1, current_action[1] * -1)
        actions.remove(reverse_action)
        return actions


    Next, create a new python file called random_ai_solver.py and create a new class. This class will be very simple. 
    import random
from base_game_model import BaseGameModel

class RandomSolver(BaseGameModel):

    def __init__(self):
        BaseGameModel.__init__(self, "Random")

    def move(self, environment):
        potential_actions = environment.possible_actions_for_current_action(environment.snake_action)
        return random.choice(potential_actions)


    When this AI decides how to move, it just gets the list of possible actions and picks one completely at random.

    While HumanSolver class that we implemented used player input to determine the move action, this model can make that decision on its own.

    Next, import the RandomSolver class to the top of the game.py file. 
    from environment import Environment
from objects import WallScreenObject, SnakeScreenObject, FruitScreenObject
from action import Action
from pygame.locals import K_q
from human_solver import HumanSolver
from random_ai_solver import RandomSolver

class Game:


    Then, we can create our solver the same way as before, and change it out with our new RandomSolver 
            score_text_rect.center = (self.navigation_bar_height/2, self.navigation_bar_height/2)
        self.screen.blit(score_text, score_text_rect)
        
solver = RandomSolver()
Game(solver, Constants.FPS, Constants.SCREEN_WIDTH, Constants.SCREEN_HEIGHT+Constants.NAVIGATION_BAR_HEIGHT)


    Run the code and watch it go! It's not very smart, but sometimes it gets the fruit. More often than not, it runs into a wall or into itself.



    Going a little too slow for you? Check out the Constants class and change the frames per second from 5 to a higher number. Since it's not a person playing, feel free to go very high to see how fast the game will go!

    We may be able to make this AI a little bit smarter so at least it doesn't crash into the wall continually.

Random AI with Avoidance



    So the random AI isn't that smart. But randomness isn't always a bad strategy. Sometimes it just needs to be paired with a little awareness.

    To give our AI awareness, we're going to have it still make choices randomly...but instead of moving TOWARDS its doom, when it's about to run into an obstacle, we'll have the AI pick a different route.

    To make our AI a little smarter, we're going to:

    1. Create a new model class
    2. Have the AI look one move ahead to see if an action will cause it to crash
    3. Pick randomly from actions that will NOT cause the snake to crash!

    To start, create a new python file called random_avoidance_solver.py.

    This AI model will do the following:

    1. Get the list of all possible actions
    2. Check to see if those actions would run into an obstacle
    3. Randomly pick from actions that do NOT run into obstacles 

    import random
from base_game_model import BaseGameModel
from point import Point


class RandomAvoidanceSolver(BaseGameModel):

    action = None
    
    def __init__(self):
        BaseGameModel.__init__(self, "Random_Avoidance")

    def move(self, environment):
        BaseGameModel.move(self, environment)
        all_actions = environment.possible_actions_for_current_action(environment.snake_action)
        
        #This list will contain all actions which avoid obstacles
        obstacle_avoidance_actions = []
        for action in all_actions:
            head = environment.snake[0]
            x, y = action
            new = Point(x=(head.x + x),
                        y=(head.y + y))
            #Check to see that the new point you made does not contain a snake point or a wall point
            if ((not new in environment.snake) and (not new in environment.wall)):
                #If the new position caused by that action does not cause an immediate crash, add it to our list
                obstacle_avoidance_actions.append(action)
        
        #If there is no action that will allow you to avoid a crash, just keep going forwards
        if (len(obstacle_avoidance_actions) == 0):
            return environment.snake_action
        else:
            return random.choice(obstacle_avoidance_actions)


    Next, import the class to the Game class and use it instead of the purely random AI. 

    from action import Action
from pygame.locals import K_q
from human_solver import HumanSolver
from random_ai_solver import RandomSolver
from random_avoidance_solver import RandomAvoidanceSolver
				  
            score_text_rect.center = (self.navigation_bar_height/2, self.navigation_bar_height/2)
        self.screen.blit(score_text, score_text_rect)
        
solver = RandomAvoidanceSolver()
Game(solver, Constants.FPS, Constants.SCREEN_WIDTH, Constants.SCREEN_HEIGHT+Constants.NAVIGATION_BAR_HEIGHT)


    This AI is a lot smarter already! While the Random AI could barely get above a length of 1, the Random Avoidance AI can easily get above 5, with enough time, of course.



    Sure, you could increase the frames per second to an unreasonable number to get the AI to go super fast, but what if we want the AI to get the highest possible score in the smallest number of moves?

    We're going to need a little bit of a smarter approach if we want the AI to be more direct in trying to achieve the goal.

Shortest Path AI



    For this AI, we're going to tell the AI to take the shortest path it can to the goal, while also trying to not run into obstacles.

    So this AI will have two ways of thinking:

    1. If I can travel towards the goal, travel towards the goal
    2. If traveling towards the goal will cause me to crash, don't travel towards the goal

    We'll start by creating another model. Create a file called direct_path_solver.py

    Our strategy for writing the move() method will be:

    1. Check the location of the head of the snake relative to the fruit
    2. Pick all direction actions that will move the snake closer to the fruit
    3. If any of those actions would cause us to crash, don't use them
    4. If there are no actions that would not cause us to crash, pick a random non-crash action
    5. If, finally, there are no valid moves, accept your fate and crash.

    Let's get started! 

    import random
from base_game_model import BaseGameModel
from point import Point
from action import Action

class DirectPathSolver(BaseGameModel):
    
    def __init__(self):
        BaseGameModel.__init__(self, "Direct Path")
        
    def move(self, environment):
        BaseGameModel.move(self, environment)
        
        preferred_actions = []
        #Check the location of the fruit relative to the snake head
        if (environment.fruit[0].x > environment.snake[0].x):
            #If the fruit is to the right of the snake
            preferred_actions.append(Action.right)
        elif (environment.fruit[0].x < environment.snake[0].x):
            #If the fruit is to the right of the snake
            preferred_actions.append(Action.left)
        
        #Check the location of the fruit relative to the snake head
        if (environment.fruit[0].y < environment.snake[0].y):
            #If the fruit is above the snake
            preferred_actions.append(Action.up)
        elif (environment.fruit[0].y > environment.snake[0].y):
            #If the fruit is below the snake
            preferred_actions.append(Action.down)


    This is the first part, where we check the position of the snake relative to the fruit, and add our actions to our preferred actions list.

    Before we continue with the move code, we're going to set up a helper function. Since we have to check valid paths twice, once for our preferred list and once for the random list, it's a good idea to make this a separate function inside the class.

    This is the same functionality we used for the Random Avoidance AI, only now if there are no valid paths we return None to indicate the lack of valid paths. 

        def move(self, environment):
        BaseGameModel.move(self, environment)
        
        preferred_actions = []
        #Check the location of the fruit relative to the snake head
        if (environment.fruit[0].x > environment.snake[0].x):
            #If the fruit is to the right of the snake
            preferred_actions.append(Action.right)
        elif (environment.fruit[0].x < environment.snake[0].x):
            #If the fruit is to the right of the snake
            preferred_actions.append(Action.left)
        
        #Check the location of the fruit relative to the snake head
        if (environment.fruit[0].y < environment.snake[0].y):
            #If the fruit is above the snake
            preferred_actions.append(Action.up)
        elif (environment.fruit[0].y > environment.snake[0].y):
            #If the fruit is below the snake
            preferred_actions.append(Action.down)
            
    def check_path(self, environment, actions_list):
        obstacle_avoidance_actions = []
        for action in actions_list:
            head = environment.snake[0]
            x, y = action
            new = Point(x=(head.x + x),
                        y=(head.y + y))
            #If you won't run into a wall 
            if ((not new in environment.snake) and (not new in environment.wall)):
                obstacle_avoidance_actions.append(action)
        
        if (len(obstacle_avoidance_actions) == 0):
            return None
        else:
            return random.choice(obstacle_avoidance_actions)


    This is the last part of the move logic. Here is where we:

    1. Check that at least 1 of our preferred actions does not crash.
    2. If there are no valid preferred actions, check all actions
    3. If there are still no valid actions, move forward to crash
    4. But if there are valid actions, pick pick one at random to move to. 

        def move(self, environment):
        BaseGameModel.move(self, environment)
        
        preferred_actions = []
        #Check the location of the fruit relative to the snake head
        if (environment.fruit[0].x > environment.snake[0].x):
            #If the fruit is to the right of the snake
            preferred_actions.append(Action.right)
        elif (environment.fruit[0].x < environment.snake[0].x):
            #If the fruit is to the right of the snake
            preferred_actions.append(Action.left)
        
        #Check the location of the fruit relative to the snake head
        if (environment.fruit[0].y < environment.snake[0].y):
            #If the fruit is above the snake
            preferred_actions.append(Action.up)
        elif (environment.fruit[0].y > environment.snake[0].y):
            #If the fruit is below the snake
            preferred_actions.append(Action.down)
            
        #Pick an action from the preferred list
        picked_action = self.check_path(environment, preferred_actions)
        #If you can't use any preferred actions without dying,
        #pick a random action to perform
        if (picked_action is None):
            all_actions = environment.possible_actions_for_current_action(environment.snake_action)
            avoidance_action = self.check_path(environment, all_actions)
            if (avoidance_action is None):
                return environment.snake_action
            else:
                return avoidance_action
        else:
            return picked_action


    Add the import to the top of game.py. 

    from human_solver import HumanSolver
from random_ai_solver import RandomSolver
from random_avoidance_solver import RandomAvoidanceSolver
from direct_path_solver import DirectPathSolver


    Then set up the model for the game to play. 

            score_text_rect.center = (self.navigation_bar_height/2, self.navigation_bar_height/2)
        self.screen.blit(score_text, score_text_rect)
        
solver = DirectPathSolver()
Game(solver, Constants.FPS, Constants.SCREEN_WIDTH, Constants.SCREEN_HEIGHT+Constants.NAVIGATION_BAR_HEIGHT)


    Now this is an AI! It knows how to do two different things, move close when it can, and move away from danger when it needs to.



    Unfortunately, this AI has one major weakness. When the snake's tail gets too long, it tends to run into it, especially when the head and fruit are separated by it.

    It knows when it needs to turn tot not immediately run into something, but it has trouble thinking more than 1 move ahead.

    There are many other problem solving strategies you can teach your AI. We'll save the deep neural net AI for the next project, but check out the additional challenges if you want to work on this project more.

    Just for fun, here's an example of the same AI playing when the FPS has been turned up to 30...



Additional Challenges



    There is a general rule in the game of snake...the longer your tail, the more circuitous route you should take. Why not create an AI that changes the way that it thinks the longer its tail is?



    Thinking in terms of usability, right now we change the models inside of the code. But what if the player of the game was able to change the model on the front end using buttons?



    Ready for a real challenge? There is a way to write an AI that plays a perfect game of snake (with an enormous amount of moves, of course.) You will need to teach the AI to master the art of patience...
    1. Instead of taking the shortest path, you need to find the longest path possible to the fruit!
    2. In order to take the longest path, you will need to visit as many squares as possible before obtaining the fruit, so that the snake's tail won't be in the way.
    3. For more information, read about the Hamiltonian Path Algorithm
    4. An alternative approach that might be easier...have the snake follow a very specific path across the board, so it will sweep the entire board for the fruit every time a new one appears, ensuring the tail is as long as possible.



    To change the game up a bit, how about if there were multiple fruit on the board? What AI would perform best under those conditions?