Jim Wright

Discussing all things around software engineering.

Tag: ai

  • 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.

  • Running a run

    Posted on
    Reading time 7 minutes
    Comments
    Writing NEAT in GO
    golang ai neatgo neat

    Evaluation, the loop, and making a stochastic algorithm reproducible enough to debug

    Every piece is built. This is the loop around them, the parallelism, and the thing that mattered more than any of it: making a stochastic algorithm repeat exactly.

  • Reproduction

    Posted on
    Reading time 6 minutes
    Comments
    Writing NEAT in GO
    golang ai neatgo neat

    Building the next generation in parallel without making the run depend on which goroutine won

    Every species knows how many offspring it is owed. This is the part that produces them - which is where the expensive work is, and where the temptation to parallelise it runs straight into the requirement that a seeded run be reproducible.

  • Selection

    Posted on
    Reading time 8 minutes
    Comments
    Writing NEAT in GO
    golang ai neatgo neat

    Fitness sharing, culling, and four places where an obvious-looking division is wrong

    Species exist so that a genome competes mainly against genomes like itself. This is the part that cashes that in: deciding how many offspring each species gets, which members are allowed to produce them, and which species do not get to continue at all.

    It is five short functions and I got three of them subtly wrong first.

  • Speciation

    Posted on
    Reading time 7 minutes
    Comments
    Writing NEAT in GO
    golang ai neatgo neat

    Measuring how different two genomes are, and why the threshold cannot be a constant

    A genome that has just grown a new node is worse than it was. It has an untuned bias, two untuned weights and no idea what the node is for, and in a straight fight with the rest of the population it loses and is gone.

    Speciation is the answer: genomes compete mainly against genomes like themselves, so new structure gets a few generations to prove itself.

Tags

Series