Snake AI

We are going to write a computer player (“ai”) for a snake.

The tick handler will give each computer controlled snake a chance to choose a new direction just before the game state updates. The key ai function will have a signature like this:

ai-function: snake world -> posn(direction)

In fact, most of the code will be building up or reducing the list of possible choices, so expect most AI-related functions to take in a list of directions in addition to the snake and the world, and put out a possibly smaller list of directions - the best choices according to that level of the AI.

Levels of AI

There are different levels of “AI” that a computer player could have. We will build up from the simplest to the most complex, making sure each step along the way works before moving to the next.

0. Randomly choose one of the four possible directions.
1. Move randomly, just do not go back on yourself.
2. Avoid the boundary walls in addition to the above.
3. Get an apple if you are right next to it, in addition to the above.
4. Move toward the nearest apple, in addition to the above.

None of the functions we are thinking of writing will have any “global strategy”. Expect these computer snakes to drive themselves in circles that cause them to die.

Level 0

A snake can only move one of four directions.

(define DIRECTIONS
  (list (make-posn 0 -1)   (make-posn  0 1)
        (make-posn 1  0)   (make-posn -1 0)))

We will need a random choice function.

;; random-choice: list-of-things -> thing
(define (random-choice things)
   (list-ref things (random (length things))))

One problem I had was that I needed to be careful to make sure there was not an error when there were no choices (snake has to crash). My level 0 AI keeps going straight if there are no possibilities (for not crashing).

(define (level-0 snake world possible)
   (if (empty? possible)
       (sn-dir snake)
       (random-choice possible)))
(define (ai-level-0 snake-world)
   (level-0 snake world DIRECTIONS))

Level 1

The level 1 function just needs to avoid going back on itself. That means do not pick the move that gives you the first of the body. There are lots of ways to do this, so if you like the sound of something just do it.

One way: write a helper function to figure out if a single direction is safe. Given a direction, find out if moving the head one unit in that direction will not hit the first position of the body. If so, consider it one of the possibilities.

• head-move: snake posn(direction) -> posn(new head posn)
• hit-first-body?: posn snake -> boolean
• is-safe-dir?: snake posn(direction) -> boolean
• only-safe: snake world possible(list of directions) -> list-of-posn(safe directions) Apply is-safe-dir? to all of the possible directions, eliminating the unsafe ones.

Notice how I build on my level-0 function in level-1? That is a good pattern to use!

(define (level-1 snake world possible)
  (level-0 snake world
           (only-safe snake world possible)))