2. Snake

2.1. Introduction

What is a Genetic Algorithm?

We should all know by now that Evolutionary Computing is about applying evolving solutions to problems that require adaptive strategy.

Which is fancy for “Making solutions that change with the problem”

I can think of know better example for problems that change and require similar yet modified solutions than Video Games.

Today’s video games are beyond complex, but if we go back to 1976 in the very young days of video games we can find an arcade game called Blockade.

../../_images/blockade.jpg

Blockade, created by Gremlin Industries, was the first of a kind of games called “Snake Games”

Many games spawned from Blockade, for example the 1982 game Tron and the most popular 1998 game Snake which was included on the Nokia 6110 cellphone.

../../_images/tron.png ../../_images/nokia.jpg

“Snake Games” are the kind of game we are going to be teaching an Evolutionary Neural Network to play.

Snake games have very basic rules and inner workings:

  • A snake exists in a bounded area

  • Each frame the snake moves straight one unit

  • Input can be used to turn the snake 90 degrees in either direction

  • The snake gains length by collecting something in its path or simply by lengthening each frame

  • The snake cannot run into itself, or it dies

  • The snake cannot run into the walls defining its space or it dies

  • The goal is to become as long as possible.

2.3. Project Topic Description

As opposed to the examples above using neural networks, I will be using a evolutionary neural network (ENN) that actively trains and improves.

In addition to that I will be changing some of the rules of a standard snake game:

  • The walls will not kill the snake, instead they loop left to right and top to bottom similar to the paths on the sides of the screen in Pac-Man

  • To balance the lack of walls, obstacles called bombs are added to the game

The goal of our snake ENN will remain mostly the same, maximise length and avoid death

2.4. Methodology

This snake game implementation, originally created by Christian Thompson, has been HEAVILY modified to include the new game rules described above and to improve the general function of the game.

Additional modifications were made to include edge cases like, fruits spawning on the snake, fruits spawning on bombs, bombs spawning at the snakes spawn position, etc.

In addition to that the size of the board the snake is in can be changed and will not always be a square For our snake to know what it is doing we are tracking these things and feeding them to our ENN as input:

  • Coordinates of snake head

  • Coordinates of snake tail segments

  • Coordinates of fruit

  • Coordinates of bombs

  • Dimensions of board

Our ENN will give key presses of W, A, S, and D as output to control the snake.

2.5. Prediction

As the implementation of this has not yet been completed, here are some predictions on what will happen.

Early Generations:

  • Random moves

  • Most snakes will die quickly as they don’t know what is killing them

  • MAYBE a lucky run will get multiple fruits

  • Portal walls cause extreme confusion

Middle Generations:

  • Snakes learn basic survival behavior, bombs and its tail is what is killing it

  • Start moving towards fruit

  • Simple bomb avoidance, make it look like the snake is scared of the bombs

  • Portal walls used scarcely due to previous confusions

Later Generations:

  • Development of path planning

  • Efficient fruit collecting

  • Confidently navigating close to bombs

  • Smart use of portal walls

There are multiple strategies that the ENN could use, standard games of snake benefit from zigzagging from top to bottom, or spiraling in and out from the centre.

Now due to the obstacles introduced by the bombs using a zigzag or spiral technique will almost never produce a perfect solution.

I predict that the best solution in this game of snake will resemble a zigzag solution with bombs wrapped by the snake.

Notice how I said best and not perfect as shown in the example bellow, a perfect run of snake is not possible based on the placement of bombs.

../../_images/example.png

A perfect run is not possible here because of the placement of the bombs.

Similar placements of bombs may allow for all spaces to be occupied by the snake, however the position in which the snake enters and exits an area surrounding bombs play a huge part in whether or not it can “solve” the arrangement

2.6. Completion

To complete this project my game of snake will be used to train the ENN to solve many different games of snake with different board dimensions and different number and location of bombs.

The project will be updated here on GitHub,

2.7. Citations

Anderson, Ezra. “A.I Learns Snake And Wins - Part 1.” YouTube, YouTube, 8 Oct. 2022, https://www.youtube.com/watch?v=G8NEj5InvVA.

Code Bullet. “A.I. Learns to Play Snake Using Deep Q Learning.” YouTube, YouTube, 12 July 2019, https://www.youtube.com/watch?v=-NJ9frfAWRo.

Code Bullet. “AI Learns to Play Snake Using Genetic Algorithm and Deep Learning.” YouTube, YouTube, 7 Dec. 2017, https://www.youtube.com/watch?v=3bhP7zulFfY.

Code Bullet. “I Created a PERFECT SNAKE A.I.” YouTube, YouTube, 28 Nov. 2019, https://www.youtube.com/watch?v=tjQIO1rqTBE&t=278s.

Goggin Gerard. Global Mobile Media. Taylor & Francis Group, 2010, ProQuest Ebook Central, https://ebookcentral.proquest.com/lib/stfx/detail.action?docID=958113, Accessed 25 Nov. 2024.

Thompson, Christian, et al. “A Simple Snake Game Made in Python 3.” GitHub Gist, 2 Sept. 2018, https://gist.github.com/wynand1004/ec105fd2f457b10d971c09586ec44900.