Jim Wright

Discussing all things around software engineering.

Tag: snake

  • Taking the longest way round

    Posted on
    Reading time 6 minutes
    Comments
    Eleven ways to play snake
    golang ai snake

    Stretching a route to keep the body trailing behind, and why it scores worse than walking straight at the fruit

    The two search players die because a short route leaves the snake coiled up next to itself. The obvious opposite idea is to take the longest route you can, so that by the time you arrive the tail has had time to get out of the way.

    It scores worse than walking straight at the fruit. It is also the single most useful piece of machinery in this series, because it is how you grow a route into a tour of the whole board.

  • The same path, less searching

    Posted on
    Reading time 6 minutes
    Comments
    Eleven ways to play snake
    golang ai snake

    A* finds the routes breadth first search finds, having looked at a fraction of the board

    Breadth first search expands in rings, so by the time it reaches a fruit four tiles away it has also visited everything four tiles in the opposite direction. A* keeps the same guarantee and skips most of that.

    This post is not really about playing snake - the two players score the same - it is about the search.

  • The shortest path to the fruit

    Posted on
    Reading time 7 minutes
    Comments
    Eleven ways to play snake
    golang ai snake

    Breadth first search, a bordered board, and why searching properly is barely worth six points

    The greedy player measures the distance to the fruit in a straight line, which stops being true the moment there is a snake in the way. The fix is to stop guessing and search for a real route through the board as it actually is.

    This is the first player with a search in it, and the first one to share machinery with the rest of the series.

  • Walking straight at the fruit

    Posted on
    Reading time 4 minutes
    Comments
    Eleven ways to play snake
    golang ai snake

    The greedy snake: no search, no lookahead, and three and a half times the score

    The random player scores six because it does not know where the fruit is. The obvious fix is to tell it: of the moves that do not kill me this tick, take the one that ends up nearest the fruit.

    That is the whole of the greedy player. There is no search and no lookahead, and it is worth three and a half times as much as random.

  • Playing snake at random

    Posted on
    Reading time 4 minutes
    Comments
    Eleven ways to play snake
    golang ai snake

    The simplest player there is, and the baseline everything else is measured against

    The first player I wrote does not know where the fruit is. It looks one tile ahead, throws away the moves that would kill it this tick, and picks from whatever is left at random.

    That sounds like a waste of a post, but it is the number every other player is measured against, and it turns out to be worth understanding why it scores what it does.

  • Eleven ways to play snake

    Posted on
    Reading time 5 minutes
    Comments
    Eleven ways to play snake
    golang ai snake

    A series on writing snake players in GO, from random moves to an evolved neural network

    I wanted a problem small enough to hold in my head and awkward enough to stay interesting. Snake is that. The rules fit in a sentence, and playing it well turns out to be a problem about not building a wall out of yourself.

    So I wrote a snake, and then I wrote eleven different ways of playing it. This series is one post per player, starting with the one that moves at random and ending on a neural network that was evolved rather than written.

  • 1
  • 2

Tags

Series