Laupok built an AI that plays Super Mario World by itself -- how it works

Laupok built an artificial intelligence that plays Super Mario World fully autonomously. It starts from zero: no pre-written scripts, no recorded frames. The AI learns alone, through random mutations and natural selection, to finish the game's levels. The project runs on BizHawk, a multiplatform emulator, via a Lua script of about 4200 lines.

What makes this project fascinating is that it rests on biological concepts applied to computing: Darwin's theory of evolution, artificial neural networks, and above all a specific algorithm called NEAT (NeuroEvolution of Augmenting Topologies). The AI knows nothing about the game at first. It tries actions at random, fails thousands of times, and little by little figures out how to move forward, jump, and survive.

In this article, we'll break all of that down -- concept by concept, line of code by line of code.

---

The setup: BizHawk, Lua, and Super Mario World

The BizHawk emulator

BizHawk is an open-source emulator supporting a ton of consoles -- NES, SNES, Genesis, PS1, Game Boy, and more. Its special feature is running Lua scripts alongside the game. Those scripts have access to the emulation's RAM, meaning they can read -- and modify -- any game data in real time.

Concretely, that means you can:

• Read Mario's position in the level
• Know which sprites (enemies, items) are on screen
• Know each tile's state around Mario
• Control the gamepad -- press any button

That's exactly what you need to make an AI play.

Super Mario World memory addresses

In Super Mario World RAM, each datum sits at a specific address. It's a bit like a neighborhood: each address is a "house" holding information. For example:

Address	Data
0x94-0x95	Mario's X position (16-bit, little-endian)
0x96-0x97	Mario's Y position
0x14C8+i	Sprite i state (>7 = alive)
0xE4+i	Sprite i low X position
0x14E0+i	Sprite i high X position
0xD8+i	Sprite i low Y position
0x14D4+i	Sprite i high Y position
0x170B+i	Extended sprite i type
0x0100	Game state (12 = level finished)
0x13D4	Pause active
0x0071	Mario death animation (9 = dead)
0x1C800+...	Level tile table

Sprite position uses two bytes: a "low" byte and a "high" byte, because position can exceed 255 pixels. The formula is always low + high × 256.

For tiles, it's more complex: base address is 0x1C800, and you compute the offset from the tile's x and y coords in the world, with a 16-pixel-per-tile step.

---

The basics: genetic algorithms and neural networks

Before diving into code, you need two fundamental concepts. Without them, nothing else makes sense.

Genetic algorithms

A genetic algorithm is a simulation of evolution theory. The core idea: you create a population of individuals, each with slightly different traits ("genes"). You let them "live" in an environment. Those doing best survive and reproduce. Those doing badly disappear.

Laupok illustrates it with a Kirby analogy:

• A Kirby population appears on terrain with spikes and tomatoes
• Spikes remove hit points, tomatoes restore them
• Each Kirby has genes: size, speed, hit points, behavior (flee, seek tomatoes, rush anywhere)

• After 15 seconds, you look at who survived longest
• The best Kirby reproduces with the others: babies inherit half the best one's genes and half the "worst" one's
• Babies undergo random mutations (a bit bigger, a bit faster...)
• Old Kirbies get replaced by the new ones
• Relaunch

After 180 generations (~15 hours), the Kirbies went from 15 seconds of survival to 15 minutes. They became small (reduced hitbox), fast, and permanently flee danger.

The crucial point: you don't define the solution. The algorithm finds it alone. And that's exactly what makes it powerful for problems where you don't know which parameter combination would be optimal.

Artificial neural networks

A neural network is a simplified mathematical model of the human brain. It consists of:

• Input neurons (inputs): what the network "sees"
• Output neurons (outputs): what the network "decides"
• Connections (weights): each connection has a weight amplifying or attenuating the signal

The principle is simple: each input neuron sends its value. It gets multiplied by the connection weight, then added to other signals. If the result exceeds a threshold (the activation function), the output neuron fires.

In Laupok's analogy with Mario and the mouse bit:

• The input neuron = distance between Mario and the bit
• The connection weight = Mario's sensitivity
• The output neuron = Mario screams or not

The closer the bit, the higher the input value. If the weight is strong, the output signal is strong, and Mario would scream. Changing the weight changes Mario's sensitivity.

In the AI's real neural network, it's the same logic, but at massive scale:

• 99 input neurons (11×9 tiles of Mario's view)
• 8 output neurons (A, B, X, Y, Up, Down, Left, Right)
• Hidden neurons in between
• Hundreds of connections with varied weights

---

NEAT: the algorithm that changes everything

The problem with classic genetic algorithms

If you naively combine a genetic algorithm with a neural network, you have a problem: you create 100 totally different neural networks, and you can't compare them. Each has its own neurons, connections, weights. How do you know whether two networks are "close" or "far"?

That's where NEAT comes in -- NeuroEvolution of Augmenting Topologies. Invented by Kenneth Stanley and Risto Miikkulainen in 2002, it's an algorithm solving exactly that problem.

Species

NEAT's first key mechanism is species. When a neural network becomes too different from another, it's classified into a different species. Similarity computes via three parameters:

1. Excess (EXCES_COEF = 0.50): the number of connections with no relation between two networks (different innovations)
2. Disjoint: same, but for connections sitting in the middle
3. Weight difference (POIDSDIFF_COEF = 0.92): the average weight difference between connections sharing the same innovation

The score formula:

score = (EXCES_COEF × disjoint) / max(nbConnections1 + nbConnections2, 1)
      + POIDSDIFF_COEF × weightDiff

If that score is below DIFF_LIMITE (1.0), both networks are in the same species. Otherwise, a new species is created.

Innovations

That's NEAT's genius. Every time a connection is created, it gets a unique global innovation number. That number follows the neural network even as it reproduces.

Concretely, when a baby is created by crossover, it inherits its parents' innovations. If two networks share the same innovation, it means they have a connection from the same ancestor. That's what lets you compare different-sized networks.

Crossover

When two neural networks reproduce, crossover works like this:

1. The fittest network becomes the "dominant parent"
2. The baby inherits all of the dominant's connections
3. For each connection sharing the same innovation, the other parent can replace it (50% chance)
4. Only the non-dominant parent's active connections can replace

That guarantees the baby is always at least as good as the best parent.

Mutations

After crossover, the baby undergoes mutations with configurable probabilities:

Mutation	Probability	Effect
Connection weight reset	25%	Weight fully randomized
Weight mutation	95%	Weight varies by ±0.80
Add connection	85%	New connection between two not-yet-linked neurons
Add neuron	39%	A hidden neuron inserted between two connected neurons

The neuron-add rate matters: it's what lets the network grow. At first, there are only inputs and outputs. Gradually, hidden neurons appear, making the network more and more complex.

---

The code: full walkthrough

Constants

The script starts with a constants block defining all tuning:

-- Mario's view around him
TAILLE_TILE = 16
TAILLE_VUE_W = TAILLE_TILE * 11  -- 176 pixels wide
TAILLE_VUE_H = TAILLE_TILE * 9   -- 144 pixels tall
NB_TILE_W = TAILLE_VUE_W / TAILLE_TILE  -- 11 tiles
NB_TILE_H = TAILLE_VUE_H / TAILLE_TILE  -- 9 tiles

-- Neural network
NB_INPUT = NB_TILE_W * NB_TILE_H  -- 99 inputs (visible tiles)
NB_OUTPUT = 8  -- A, B, X, Y, Up, Down, Left, Right
NB_INDIVIDU_POPULATION = 100  -- individuals per population
NB_NEURONE_MAX = 100000  -- hidden neuron cap

-- Fitness
FITNESS_LEVEL_FINI = 1000000  -- value when level is done
NB_FRAME_RESET_BASE = 33  -- frames with no progress before reset
NB_FRAME_RESET_PROGRES = 300  -- frames if progress detected

-- Species
EXCES_COEF = 0.50
POIDSDIFF_COEF = 0.92
DIFF_LIMITE = 1.00

-- Mutations
CHANCE_MUTATION_RESET_CONNEXION = 0.25
POIDS_CONNEXION_MUTATION_AJOUT = 0.80
CHANCE_MUTATION_POIDS = 0.95
CHANCE_MUTATION_CONNEXION = 0.85
CHANCE_MUTATION_NEURONE = 0.39

NB_INPUT is 99 because Mario's view is 11×9 tiles. Each tile is one input neuron. If the tile is empty, it's 0. If it's a block, it's 1. If it's an enemy, it's -1.

The 8 outputs map to SNES pad buttons: A, B, X, Y, Up, Down, Left, Right. Start, Select, L, and R are excluded to limit its decisions to the essentials.

Data structures

The script defines three main structures:

function newNeurone()
    local neurone = {}
    neurone.valeur = 0    -- current neuron value
    neurone.id = 0        -- unique id
    neurone.type = ""     -- "input", "output", or "hidden"
    return neurone
end

function newConnexion()
    local connexion = {}
    connexion.entree = 0     -- source neuron id
    connexion.sortie = 0     -- destination neuron id
    connexion.actif = true   -- can be disabled if a hidden neuron is inserted
    connexion.poids = 0      -- connection weight
    connexion.innovation = 0 -- unique innovation number
    connexion.allume = false -- for display: true if signal passes
    return connexion
end

function newReseau()
    local reseau = {
        nbNeurone = 0,        -- hidden neuron count
        fitness = 1,          -- performance (distance traveled)
        idEspeceParent = 0,   -- which species it belongs to
        lesNeurones = {},     -- neuron array
        lesConnexions = {}    -- connection array
    }
    -- Init with inputs
    for j = 1, NB_INPUT, 1 do
        ajouterNeurone(reseau, j, "input", 1)
    end
    -- Then outputs
    for j = NB_INPUT + 1, NB_INPUT + NB_OUTPUT, 1 do
        ajouterNeurone(reseau, j, "output", 0)
    end
    return reseau
end

At first, each network holds only inputs and outputs: no hidden neurons, no connections. The algorithm decides whether it needs any.

Mutations in detail

Weight mutation

function mutationPoidsConnexions(unReseau)
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            if math.random() < CHANCE_MUTATION_RESET_CONNEXION then
                -- 25%: full weight reset
                unReseau.lesConnexions[i].poids = genererPoids()
            else
                -- 75%: ±0.80 variation
                if math.random() >= 0.5 then
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids - POIDS_CONNEXION_MUTATION_AJOUT
                else
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids + POIDS_CONNEXION_MUTATION_AJOUT
                end
            end
        end
    end
end

The initial weight is always 1 or -1 (genererPoids()). The ±0.80 variation can swing it between negative and positive values, radically changing network behavior.

Adding a connection

function mutationAjouterConnexion(unReseau)
    local liste = {}
    -- Randomize the neuron list
    for i, v in ipairs(unReseau.lesNeurones) do
        local pos = math.random(1, #liste+1)
        table.insert(liste, pos, v)
    end

    local traitement = false
    for i = 1, #liste, 1 do
        for j = 1, #liste, 1 do
            if i ~= j then
                local n1 = liste[i]
                local n2 = liste[j]
                -- Valid connection: input→output, hidden→hidden, hidden→output
                if (n1.type == "input" and n2.type == "output") or
                   (n1.type == "hidden" and n2.type == "hidden") or
                   (n1.type == "hidden" and n2.type == "output") then
                    -- Check no connection already exists
                    local dejaConnexion = false
                    for k = 1, #unReseau.lesConnexions, 1 do
                        if unReseau.lesConnexions[k].entree == n1.id
                            and unReseau.lesConnexions[k].sortie == n2.id then
                            dejaConnexion = true
                            break
                        end
                    end
                    if dejaConnexion == false then
                        traitement = true
                        ajouterConnexion(unReseau, n1.id, n2.id)
                    end
                end
            end
            if traitement then break end
        end
        if traitement then break end
    end
end

You can't connect an output to an input (that would create a cycle), and you can't connect two already-linked neurons. Randomization guarantees exploring different possibilities each time.

Adding a neuron

The most interesting mutation:

function mutationAjouterNeurone(unReseau)
    if #unReseau.lesConnexions == 0 then return nil end
    if unReseau.nbNeurone == NB_NEURONE_MAX then return nil end

    -- Randomize connections
    local listeRandom = {}
    for i = 1, #unReseau.lesConnexions, 1 do
        local pos = math.random(1, #listeRandom+1)
        table.insert(listeRandom, pos, i)
    end

    for i = 1, #listeRandom, 1 do
        if unReseau.lesConnexions[listeRandom[i]].actif then
            -- Disable the existing connection
            unReseau.lesConnexions[listeRandom[i]].actif = false
            unReseau.nbNeurone = unReseau.nbNeurone + 1
            local indice = unReseau.nbNeurone + NB_INPUT + NB_OUTPUT

            -- Create the hidden neuron
            ajouterNeurone(unReseau, indice, "hidden", 1)

            -- Connect input to hidden neuron
            ajouterConnexion(unReseau,
                unReseau.lesConnexions[listeRandom[i]].entree,
                indice, genererPoids())

            -- Connect hidden neuron to output
            ajouterConnexion(unReseau,
                indice,
                unReseau.lesConnexions[listeRandom[i]].sortie,
                genererPoids())
            break
        end
    end
end

The mechanism: you take an existing connection, disable it, and insert a hidden neuron in the middle. The original connection gets replaced by two new ones: input→hidden and hidden→output. Like "cutting" a wire to splice in a switch.

That's what makes NEAT "augmenting topologies": the network grows over time. It starts simple and only gets complex if needed.

FeedForward

The function propagating signals through the network:

function feedForward(unReseau)
    -- Reset output neurons
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur = 0
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].allume = false
        end
    end

    -- Propagation
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local avantTraitement = unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur =
                unReseau.lesNeurones[unReseau.lesConnexions[i].entree].valeur *
                unReseau.lesConnexions[i].poids +
                unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur

            if avantTraitement ~= unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur then
                unReseau.lesConnexions[i].allume = true
            else
                unReseau.lesConnexions[i].allume = false
            end
        end
    end
end

Each active connection sends input_value × weight to the output neuron. The value accumulates (adds up). The allume flag is just for the network's visual display.

Reading the game memory

The getLesInputs() function translates Super Mario World's world into data the network understands:

function getLesInputs()
    local lesInputs = {}
    -- Init to 0 (gray = nothing)
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            lesInputs[getIndiceLesInputs(i, j)] = 0
        end
    end

    -- Sprites (enemies) = -1 (black)
    local lesSprites = getLesSprites()
    for i = 1, #lesSprites, 1 do
        local input = convertirPositionPourInput(getLesSprites()[i])
        if input.x > 0 and input.x < (TAILLE_VUE_W / TAILLE_TILE) + 1 then
            lesInputs[getIndiceLesInputs(input.x, input.y)] = -1
        end
    end

    -- Tiles (blocks) = tile value (white if > 0)
    local lesTiles = getLesTiles()
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local indice = getIndiceLesInputs(i, j)
            if lesTiles[indice] ~= 0 then
                lesInputs[indice] = lesTiles[indice]
            end
        end
    end

    return lesInputs
end

The input grid is a Mario-centered view: 11 tiles wide, 9 tall. Each tile is:

• 0 (gray): nothing
• 1 (white): solid block
• -1 (black): enemy

Enemies are read from two RAM lists: normal sprites (0x14C8-0x14F8) and extended sprites (0x170B-0x173B). For each living sprite (state > 7), compute its tile position relative to Mario and set -1 in the matching cell.

Fitness: how the AI knows it's improving

function majReseau(unReseau, marioBase)
    local mario = getPositionMario()

    if not niveauFini and memory.readbyte(0x0100) == 12 then
        -- Level done!
        unReseau.fitness = FITNESS_LEVEL_FINI
        niveauFini = true
    elseif marioBase.x < mario.x then
        -- Mario moving right
        unReseau.fitness = unReseau.fitness + (mario.x - marioBase.x)
        marioBase.x = mario.x
    end

    -- Update inputs
    local lesInputs = getLesInputs()
    for i = 1, NB_INPUT, 1 do
        unReseau.lesNeurones[i].valeur = lesInputs[i]
    end
end

Fitness is simple: it's the distance traveled rightward. If Mario advances 10 pixels, fitness rises by 10. If Mario goes back, nothing happens (no penalty). If the level is done (address 0x0100 == 12), fitness becomes 1,000,000.

It's intentionally simple. Only rightward progress counts: killing enemies earns nothing, dying costs nothing.

The smart reset

If Mario doesn't move for 33 frames, reset the level and move to the next individual. But if Mario made progress (its current fitness differs from the start), wait 300 frames -- giving the network a chance to "get" what it did right.

if fitnessAvant == laPopulation[idPopulation].fitness
   and memory.readbyte(0x13D4) == 0 then
     nbFrameStop = nbFrameStop + 1
     local nbFrameReset = NB_FRAME_RESET_BASE
     if fitnessInit ~= laPopulation[idPopulation].fitness
        and memory.readbyte(0x0071) ~= 9 then
         nbFrameReset = NB_FRAME_RESET_PROGRES
     end
     if nbFrameStop > nbFrameReset then
         nbFrameStop = 0
         lancerNiveau()
         idPopulation = idPopulation + 1
         -- ...
     end
end

The memory.readbyte(0x0071) ~= 9 check verifies Mario isn't in death animation. Resetting becomes pointless when Mario is already in death animation.

The main loop

The loop runs at 30 fps (Super Mario World's normal speed):

while true do
    local fitnessAvant = laPopulation[idPopulation].fitness

    -- Display (network, info)
    if forms.ischecked(estAccelere) then
        emu.limitframerate(false)  -- speed up
    else
        emu.limitframerate(true)   -- 30 fps
    end

    -- The 3 vital functions
    majReseau(laPopulation[idPopulation], marioBase)
    feedForward(laPopulation[idPopulation])
    appliquerLesBoutons(laPopulation[idPopulation])

    emu.frameadvance()
    nbFrame = nbFrame + 1

    -- Reset if no progress
    -- ...
    -- New generation once all individuals tested
    -- ...
end

The three vital functions are majReseau, feedForward, and appliquerLesBoutons. Disable just one and Mario stops moving.

Crossover

function crossover(unReseau1, unReseau2)
    local leReseau = newReseau()
    local leBon = unReseau1
    local leNul = unReseau2

    if leBon.fitness < leNul.fitness then
        leBon = unReseau2
        leNul = unReseau1
    end

    leReseau = copier(leBon)

    for i = 1, #leReseau.lesConnexions, 1 do
        for j = 1, #leNul.lesConnexions, 1 do
            if leReseau.lesConnexions[i].innovation == leNul.lesConnexions[j].innovation
               and leNul.lesConnexions[j].actif then
                if math.random() > 0.5 then
                    leReseau.lesConnexions[i] = leNul.lesConnexions[j]
                end
            end
        end
    end
    leReseau.fitness = 1
    return leReseau
end

The baby inherits from the fitter parent. For each connection sharing the same innovation, the other parent has a 50% chance to replace it -- but only if the connection is active. That's an important fix: without it, useless hidden neurons could get created.

Species selection

function nouvelleGeneration(laPopulation, lesEspeces)
    local laNouvellePopulation = newPopulation()
    local nbIndividuACreer = NB_INDIVIDU_POPULATION

    -- Average fitness per species
    for i = 1, #lesEspeces, 1 do
        lesEspeces[i].fitnessMoyenne = 0
        for j = 1, #lesEspeces[i].lesReseaux, 1 do
            lesEspeces[i].fitnessMoyenne =
                lesEspeces[i].fitnessMoyenne + lesEspeces[i].lesReseaux[j].fitness
        end
        lesEspeces[i].fitnessMoyenne =
            lesEspeces[i].fitnessMoyenne / #lesEspeces[i].lesReseaux
    end

    -- Each species creates children proportional to its average fitness
    for i = 1, #lesEspeces, 1 do
        local nbEnfant = math.ceil(
            #lesEspeces[i].lesReseaux *
            lesEspeces[i].fitnessMoyenne / fitnessMoyenneGlobal)

        for j = 1, nbEnfant, 1 do
            local unReseau = crossover(
                choisirParent(lesEspeces[i].lesReseaux),
                choisirParent(lesEspeces[i].lesReseaux))
            mutation(unReseau)
            laNouvellePopulation[indiceNouvelleEspece] = copier(unReseau)
        end
    end
end

The idea: a species with average fitness 10,000 gets to create way more children than one with average fitness 1. That's natural selection in action.

choisirParent uses roulette selection: the fitter an individual, the likelier it gets picked as a parent.

Saving and loading

Populations save to .pop files:

function sauvegarderUnReseau(unReseau, fichier)
    io.write(unReseau.nbNeurone .. "\n")
    io.write(#unReseau.lesConnexions .. "\n")
    io.write(unReseau.fitness .. "\n")
    for i = 1, unReseau.nbNeurone, 1 do
        local indice = NB_INPUT + NB_OUTPUT + i
        io.write(unReseau.lesNeurones[indice].id .. "\n")
    end
    for i = 1, #unReseau.lesConnexions, 1 do
        local actif = 1
        if unReseau.lesConnexions[i].actif ~= true then actif = 0 end
        io.write(actif .. "\n" ..
            unReseau.lesConnexions[i].entree .. "\n" ..
            unReseau.lesConnexions[i].sortie .. "\n" ..
            unReseau.lesConnexions[i].poids .. "\n" ..
            unReseau.lesConnexions[i].innovation .. "\n")
    end
end

Saving also includes the best individual of all previous populations. If the old population's best beats the new one's best, we take the old one back as base. It's a form of elitism: you never lose the best.

Drawing the network

Laupok added a neural network visualizer overlaid on the game:

function dessinerUnReseau(unReseau)
    -- Inputs: 11×9 grid around Mario
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local xT = ENCRAGE_X_INPUT + (i - 1) * TAILLE_INPUT
            local yT = ENCRAGE_Y_INPUT + (j - 1) * TAILLE_INPUT
            local couleurFond = "gray"
            if unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur < 0 then
                couleurFond = "black"   -- enemy
            elseif unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur > 0 then
                couleurFond = "white"   -- block
            end
            gui.drawRectangle(xT, yT, TAILLE_INPUT, TAILLE_INPUT, "black", couleurFond)
        end
    end

    -- Outputs: 8 buttons
    for i = 1, NB_OUTPUT, 1 do
        local xT = ENCRAGE_X_OUTPUT
        local yT = ENCRAGE_Y_OUTPUT + ESPACE_Y_OUTPUT * (i - 1)
        if sigmoid(unReseau.lesNeurones[i + NB_INPUT].valeur) then
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "white")
        else
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "black")
        end
    end

    -- Connections
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local alpha = 25
            if unReseau.lesConnexions[i].allume then alpha = 255 end
            local couleur = forms.createcolor(255, 255, 255, alpha)
            gui.drawLine(
                lesPositions[unReseau.lesConnexions[i].entree].x,
                lesPositions[lesConnexions[i].entree].y,
                lesPositions[unReseau.lesConnexions[i].sortie].x,
                lesPositions[lesConnexions[i].sortie].y,
                couleur)
        end
    end
end

Super useful for understanding what the network does. Active connections are white, inactive ones semi-transparent. Inputs are a white/black/gray cell grid. Outputs show which buttons are pressed.

---

Results

What the AI learned

Over hours (and days) of running, the AI discovered on its own:

1. Moving right: the most basic behavior, but one requiring holding Right down
2. Jumping over enemies: by connecting an "enemy detected" input to the A or B button
3. Avoiding obstacles: some networks learned to briefly back up to better move forward
4. Finishing levels: the best individual managed to finish Super Mario World's first level

Limitations

The project has limits:

• One level: the AI trains on one specific level. It doesn't automatically generalize to other levels
• Training time: it takes dozens of hours to reach satisfying results
• No understanding: the AI doesn't "understand" what it does. It optimizes a fitness function (distance traveled) via random mutations
• T-bagging: Laupok notes Mario tends to jump in place when it sees an enemy, simply because that raises fitness (it advances a bit while jumping)

---

How to reproduce the experiment

Laupok shared everything. Here are the steps:

1. Download BizHawk at tasvideos.org (Download section)
2. Get a USA Super Mario World ROM (private copy of your own cartridge)
3. Download the Lua script from Pastebin -- rename to mario.lua
4. Place the script in the same folder as the ROM
5. Launch BizHawk, open the ROM
6. In the Lua console: dofile("mario.lua") or via the Script > Open Script menu
7. Save a state at the level start (Savestate > Save State menu) and name it debut.state
8. Relaunch the script -- it works

The script includes a form with options:

• Speed up: disables the 30 fps cap to go faster
• Show network: displays the neural network overlay
• Show info: shows a banner with generation, fitness, species count
• Pause: pauses execution
• Save/Load: persists the current population to a .pop file

---

Sources and references

Resource	Link
Laupok's main video	j'ai créé une IA qui joue à mario toute seule
Code review + setup video	comment setup l'ia + code source review
Full source code	Pastebin Jcvdqhqm
Original NEAT paper	Stanley & Miikkulainen, "Evolving Neural Networks through Augmenting Topologies", 2002
N8Programs tutorial	NEAT implementation walkthrough (JavaScript, but concepts are identical)
16blings (Laupok's inspiration)	AI plays Super Mario World
BizHawk	tasvideos.org/BizHawk
Super Mario World memory map	SMW Central - RAM Map

---

Conclusion

What Laupok did is take an academic algorithm (NEAT, 2002), rewrite it in Lua for an emulator (BizHawk), and apply it to Super Mario World. The result: an AI learning from scratch to play the game, with zero prior knowledge, purely through random mutations and natural selection.

It's a beautiful example of genetic algorithm power. The recipe has three ingredients: natural selection, a bit of Lua, and lots of patience. No deep learning, no GPU, no massive training dataset.

The code is commented, shared, and Laupok made two explainer videos -- one for the big concepts, one for the code. If the topic interests you, dive in. It's more approachable than it looks.

Laupok a créé une IA qui joue à Super Mario World toute seule -- comment ça marche

Laupok a créé une intelligence artificielle qui joue à Super Mario World de manière totalement autonome. Elle part de zéro : aucun script prédéfini, aucune frame enregistrée. L'IA apprend seule, à coups de mutations aléatoires et de sélection naturelle, à finir les niveaux du jeu. Le projet tourne sur BizHawk, un émulateur multiplateforme, via un script Lua d'environ 4200 lignes.

Ce qui rend ce projet fascinant, c'est qu'il repose sur des concepts biologiques appliqués à l'informatique : la théorie de l'évolution de Darwin, les réseaux de neurones artificiels, et surtout un algorithme spécifique appelé NEAT (NeuroEvolution of Augmenting Topologies). L'IA ne connaît rien au jeu au départ. Elle teste des actions au hasard, échoue des milliers de fois, et petit à petit, elle comprend comment avancer, sauter, et survivre.

Dans cet article, on va décortiquer tout ça -- concept par concept, ligne de code par ligne de code.

---

Le setup : BizHawk, Lua, et Super Mario World

L'émulateur BizHawk

BizHawk est un émulateur open source qui supporte une tonne de consoles -- NES, SNES, Genesis, PS1, Game Boy, et bien d'autres. Sa particularité, c'est qu'il permet de lancer des scripts Lua en parallèle du jeu. Ces scripts ont accès à la mémoire vive (RAM) de l'émulation, ce qui signifie qu'ils peuvent lire -- et modifier -- n'importe quelle donnée du jeu en temps réel.

Concrètement, ça veut dire qu'on peut :

• Lire la position de Mario dans le niveau
• Savoir quels sprites (ennemis, items) sont à l'écran
• Connaître l'état de chaque tile (bloc) autour de Mario
• Contrôler la manette -- appuyer sur n'importe quel bouton

C'est exactement ce dont on a besoin pour faire jouer une IA.

Les adresses mémoire de Super Mario World

Dans la RAM de Super Mario World, chaque donnée est stockée à une adresse spécifique. C'est un peu comme un quartier : chaque adresse correspond à une "maison" qui contient une information. Par exemple :

Adresse	Donnée
0x94-0x95	Position X de Mario (16 bits, little-endian)
0x96-0x97	Position Y de Mario
0x14C8+i	État du sprite i (>7 = vivant)
0xE4+i	Position X basse du sprite i
0x14E0+i	Position X haute du sprite i
0xD8+i	Position Y basse du sprite i
0x14D4+i	Position Y haute du sprite i
0x170B+i	Type de l'extended sprite i
0x0100	État du jeu (12 = niveau fini)
0x13D4	Pause active
0x0071	Animation de mort de Mario (9 = mort)
0x1C800+...	Table des tiles du niveau

La position des sprites utilise deux octets : un octet "bas" et un octet "haut", parce que la position peut dépasser 255 pixels. La formule est toujours bas + haut × 256.

Pour les tiles, c'est plus complexe : l'adresse de base est 0x1C800, et on calcule l'offset en fonction des coordonnées x et y de la tile dans le monde, avec un pas de 16 pixels par tile.

---

Les bases : algorithmes génétiques et réseaux de neurones

Avant de plonger dans le code, il faut comprendre deux concepts fondamentaux. Sans eux, le reste n'a aucun sens.

Les algorithmes génétiques

Un algorithme génétique, c'est une simulation de la théorie de l'évolution. L'idée centrale : on crée une population d'individus, chacun avec des caractéristiques (des "gènes") légèrement différentes. On les fait "vivre" dans un environnement. Ceux qui s'en sortent le mieux survivent et se reproduisent. Ceux qui s'en sortent mal disparaissent.

Laupok illustre ça avec une analogie de Kirby :

• Une population de Kirby apparaît sur un terrain avec des piques et des tomates
• Les piques enlèvent des points de vie, les tomates en redonnent
• Chaque Kirby a des gènes : taille, vitesse, points de vie, comportement (fuir, chercher des tomates, foncer n'importe où)

• Après 15 secondes, on regarde qui a survécu le plus longtemps
• Le meilleur Kirby se reproduit avec les autres : les bébés héritent de la moitié des gènes du meilleur et de la moitié du "pire"
• Les bébés subissent des mutations aléatoires (un peu plus grand, un peu plus rapide...)
• Les anciens Kirby sont remplacés par les nouveaux
• On relance

Après 180 générations (~15 heures), les Kirby passent de 15 secondes de survie à 15 minutes. Ils sont devenus petits (zone de collision réduite), rapides, et fuient le danger en permanence.

Le point crucial : on ne définit pas la solution. L'algorithme la trouve tout seul. Et c'est exactement ça qui le rend puissant pour des problèmes où on ne sait pas quelle combinaison de paramètres serait optimale.

Les réseaux de neurones artificiels

Un réseau de neurones, c'est un modèle mathématique simplifié du cerveau humain. Il se compose de :

• Neurones d'entrée (inputs) : ce que le réseau "voit"
• Neurones de sortie (outputs) : ce que le réseau "décide"
• Connexions (poids) : chaque connexion a un poids qui amplifie ou atténue le signal

Le principe est simple : chaque neurone d'entrée envoie sa valeur. Elle est multipliée par le poids de la connexion, puis additionnée aux autres signaux. Si le résultat dépasse un certain seuil (la fonction d'activation), le neurone de sortie s'active.

Dans l'analogie de Laupok avec Mario et le bout de la souris :

• Le neurone d'entrée = la distance entre Mario et le bout
• Le poids de la connexion = la sensibilité de Mario
• Le neurone de sortie = Mario crie ou pas

Plus le bout est proche, plus la valeur d'entrée est élevée. Si le poids est fort, le signal envoyé en sortie est fort, et Mario crierait. En modifiant le poids, on modifie la sensibilité de Mario.

Dans le vrai réseau de neurones de l'IA, c'est la même logique, mais à une échelle massive :

• 99 neurones d'entrée (11×9 tiles de la vue de Mario)
• 8 neurones de sortie (A, B, X, Y, Haut, Bas, Gauche, Droite)
• Des neurones cachés (hidden) entre les deux
• Des centaines de connexions avec des poids variés

---

NEAT : l'algorithme qui change tout

Le problème des algorithmes génétiques classiques

Si on combine un algorithme génétique avec un réseau de neurones de manière naïve, on a un problème : on crée 100 réseaux de neurones complètement différents, et on ne sait pas les comparer. Chacun a ses propres neurones, ses propres connexions, ses propres poids. Comment savoir si deux réseaux sont "proches" ou "loin" ?

C'est là qu'intervient NEAT -- NeuroEvolution of Augmenting Topologies. Inventé par Kenneth Stanley et Risto Miikkulainen en 2002, c'est un algorithme qui résout exactement ce problème.

Les espèces

Le premier mécanisme clé de NEAT, ce sont les espèces. Quand un réseau de neurones devient trop différent d'un autre, il est classé dans une espèce différente. La similarité est calculée via trois paramètres :

1. Excess (EXCES_COEF = 0.50) : le nombre de connexions qui n'ont aucun rapport entre deux réseaux (innovations différentes)
2. Disjoint : pareil, mais pour les connexions qui se situent au milieu
3. Weight difference (POIDSDIFF_COEF = 0.92) : la différence de poids moyenne entre les connexions partageant la même innovation

La formule de score :

score = (EXCES_COEF × disjoint) / max(nbConnexions1 + nbConnexions2, 1)
      + POIDSDIFF_COEF × diffPoids

Si ce score est inférieur à DIFF_LIMITE (1.0), les deux réseaux sont dans la même espèce. Sinon, on crée une nouvelle espèce.

Les innovations

C'est le génie de NEAT. Chaque fois qu'une connexion est créée, elle reçoit un numéro d'innovation unique et global. Ce numéro suit le réseau de neurones même quand il se reproduit.

Concrètement, quand un bébé est créé par crossover, il hérite des innovations de ses parents. Si deux réseaux partagent la même innovation, ça veut dire qu'ils ont une connexion qui vient du même ancêtre. C'est ce qui permet de comparer des réseaux de tailles différentes.

Le crossover

Quand deux réseaux de neurones se reproduisent, le crossover fonctionne ainsi :

1. Le réseau le plus performant devient le "parent dominant"
2. Le bébé hérite de toutes les connexions du dominant
3. Pour chaque connexion partageant la même innovation, l'autre parent peut la remplacer (50% de chances)
4. Seules les connexions actives du parent non-dominant peuvent remplacer

Ça garantit que le bébé est toujours au moins aussi bon que le meilleur parent.

Les mutations

Après le crossover, le bébé subit des mutations avec des probabilités configurables :

Mutation	Probabilité	Effet
Reset poids connexion	25%	Le poids est totalement randomisé
Mutation poids	95%	Le poids varie de ±0.80
Ajout connexion	85%	Nouvelle connexion entre deux neurones pas encore liés
Ajout neurone	39%	Un neurone caché est inséré entre deux neurones connectés

Le taux d'ajout de neurone est important : c'est ce qui permet au réseau de grandir. Au départ, il n'y a que des entrées et des sorties. Progressivement, des neurones cachés apparaissent, rendant le réseau de plus en plus complexe.

---

Le code : walkthrough complet

Les constantes

Le script commence par un bloc de constantes qui définissent tout le paramétrage :

-- Vue de Mario autour de lui
TAILLE_TILE = 16
TAILLE_VUE_W = TAILLE_TILE * 11  -- 176 pixels en largeur
TAILLE_VUE_H = TAILLE_TILE * 9   -- 144 pixels en hauteur
NB_TILE_W = TAILLE_VUE_W / TAILLE_TILE  -- 11 tiles
NB_TILE_H = TAILLE_VUE_H / TAILLE_TILE  -- 9 tiles

-- Réseau de neurones
NB_INPUT = NB_TILE_W * NB_TILE_H  -- 99 inputs (tiles visibles)
NB_OUTPUT = 8  -- A, B, X, Y, Haut, Bas, Gauche, Droite
NB_INDIVIDU_POPULATION = 100  -- individus par population
NB_NEURONE_MAX = 100000  -- limite de neurones cachés

-- Fitness
FITNESS_LEVEL_FINI = 1000000  -- valeur quand le niveau est terminé
NB_FRAME_RESET_BASE = 33  -- frames sans progrès avant reset
NB_FRAME_RESET_PROGRES = 300  -- frames si progrès détecté

-- Espèces
EXCES_COEF = 0.50
POIDSDIFF_COEF = 0.92
DIFF_LIMITE = 1.00

-- Mutations
CHANCE_MUTATION_RESET_CONNEXION = 0.25
POIDS_CONNEXION_MUTATION_AJOUT = 0.80
CHANCE_MUTATION_POIDS = 0.95
CHANCE_MUTATION_CONNEXION = 0.85
CHANCE_MUTATION_NEURONE = 0.39

Le NB_INPUT est de 99 parce que la vue de Mario fait 11×9 tiles. Chaque tile est un neurone d'entrée. Si la tile est vide, elle vaut 0. Si c'est un bloc, elle vaut 1. Si c'est un ennemi, elle vaut -1.

Les 8 sorties correspondent aux boutons de la manette SNES : A, B, X, Y, Haut, Bas, Gauche, Droite. On exclut Start, Select, L et R pour limiter ses décisions à l'essentiel.

Les structures de données

Le script définit trois structures principales :

function newNeurone()
    local neurone = {}
    neurone.valeur = 0    -- valeur actuelle du neurone
    neurone.id = 0        -- identifiant unique
    neurone.type = ""     -- "input", "output", ou "hidden"
    return neurone
end

function newConnexion()
    local connexion = {}
    connexion.entree = 0     -- ID du neurone source
    connexion.sortie = 0     -- ID du neurone destination
    connexion.actif = true   -- peut être désactivé si un neurone caché est inséré
    connexion.poids = 0      -- poids de la connexion
    connexion.innovation = 0 -- numéro d'innovation unique
    connexion.allume = false -- pour l'affichage : true si le signal passe
    return connexion
end

function newReseau()
    local reseau = {
        nbNeurone = 0,        -- nombre de neurones cachés
        fitness = 1,          -- performance (distance parcourue)
        idEspeceParent = 0,   -- à quelle espèce il appartient
        lesNeurones = {},     -- tableau de neurones
        lesConnexions = {}    -- tableau de connexions
    }
    -- Initialisation avec les inputs
    for j = 1, NB_INPUT, 1 do
        ajouterNeurone(reseau, j, "input", 1)
    end
    -- Puis les outputs
    for j = NB_INPUT + 1, NB_INPUT + NB_OUTPUT, 1 do
        ajouterNeurone(reseau, j, "output", 0)
    end
    return reseau
end

Au départ, chaque réseau contient seulement des inputs et des outputs : aucun neurone caché, aucune connexion. C'est l'algorithme qui va décider s'il en faut.

Les mutations en détail

Mutation des poids

function mutationPoidsConnexions(unReseau)
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            if math.random() < CHANCE_MUTATION_RESET_CONNEXION then
                -- 25% : reset total du poids
                unReseau.lesConnexions[i].poids = genererPoids()
            else
                -- 75% : variation de ±0.80
                if math.random() >= 0.5 then
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids - POIDS_CONNEXION_MUTATION_AJOUT
                else
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids + POIDS_CONNEXION_MUTATION_AJOUT
                end
            end
        end
    end
end

Le poids initial est toujours 1 ou -1 (genererPoids()). La variation de ±0.80 peut le faire osciller entre des valeurs négatives et positives, ce qui change radicalement le comportement du réseau.

Ajout de connexion

function mutationAjouterConnexion(unReseau)
    local liste = {}
    -- Randomisation de la liste des neurones
    for i, v in ipairs(unReseau.lesNeurones) do
        local pos = math.random(1, #liste+1)
        table.insert(liste, pos, v)
    end

    local traitement = false
    for i = 1, #liste, 1 do
        for j = 1, #liste, 1 do
            if i ~= j then
                local n1 = liste[i]
                local n2 = liste[j]
                -- Connexion valide : input→output, hidden→hidden, hidden→output
                if (n1.type == "input" and n2.type == "output") or
                   (n1.type == "hidden" and n2.type == "hidden") or
                   (n1.type == "hidden" and n2.type == "output") then
                    -- Vérifier qu'il n'y a pas déjà une connexion
                    local dejaConnexion = false
                    for k = 1, #unReseau.lesConnexions, 1 do
                        if unReseau.lesConnexions[k].entree == n1.id
                            and unReseau.lesConnexions[k].sortie == n2.id then
                            dejaConnexion = true
                            break
                        end
                    end
                    if dejaConnexion == false then
                        traitement = true
                        ajouterConnexion(unReseau, n1.id, n2.id)
                    end
                end
            end
            if traitement then break end
        end
        if traitement then break end
    end
end

On ne peut pas connecter un output à un input (ça créerait un cycle), et on ne peut pas connecter deux neurones déjà liés. La randomisation garantit qu'on explore différentes possibilités à chaque fois.

Ajout de neurone

C'est la mutation la plus intéressante :

function mutationAjouterNeurone(unReseau)
    if #unReseau.lesConnexions == 0 then return nil end
    if unReseau.nbNeurone == NB_NEURONE_MAX then return nil end

    -- Randomisation des connexions
    local listeRandom = {}
    for i = 1, #unReseau.lesConnexions, 1 do
        local pos = math.random(1, #listeRandom+1)
        table.insert(listeRandom, pos, i)
    end

    for i = 1, #listeRandom, 1 do
        if unReseau.lesConnexions[listeRandom[i]].actif then
            -- Désactiver la connexion existante
            unReseau.lesConnexions[listeRandom[i]].actif = false
            unReseau.nbNeurone = unReseau.nbNeurone + 1
            local indice = unReseau.nbNeurone + NB_INPUT + NB_OUTPUT

            -- Créer le neurone caché
            ajouterNeurone(unReseau, indice, "hidden", 1)

            -- Connecter l'entrée au neurone caché
            ajouterConnexion(unReseau,
                unReseau.lesConnexions[listeRandom[i]].entree,
                indice, genererPoids())

            -- Connecter le neurone caché à la sortie
            ajouterConnexion(unReseau,
                indice,
                unReseau.lesConnexions[listeRandom[i]].sortie,
                genererPoids())
            break
        end
    end
end

Le mécanisme : on prend une connexion existante, on la désactive, et on insère un neurone caché au milieu. La connexion d'origine est remplacée par deux nouvelles connexions : entrée→caché et caché→sortie. C'est comme si on "coupait" un fil pour intercaler un interrupteur.

C'est ce qui rend NEAT "augmenting topologies" : le réseau grandit avec le temps. Il commence simple et devient complexe uniquement si c'est nécessaire.

Le feedForward

C'est la fonction qui propage les signaux à travers le réseau :

function feedForward(unReseau)
    -- Reset des neurones de sortie
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur = 0
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].allume = false
        end
    end

    -- Propagation
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local avantTraitement = unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur =
                unReseau.lesNeurones[unReseau.lesConnexions[i].entree].valeur *
                unReseau.lesConnexions[i].poids +
                unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur

            if avantTraitement ~= unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur then
                unReseau.lesConnexions[i].allume = true
            else
                unReseau.lesConnexions[i].allume = false
            end
        end
    end
end

Chaque connexion active envoie valeur_entrée × poids vers le neurone de sortie. La valeur est cumulée (additionnée). Le drapeau allume est juste pour l'affichage visuel du réseau.

La lecture de la mémoire du jeu

La fonction getLesInputs() est celle qui traduit le monde de Super Mario World en données compréhensibles par le réseau :

function getLesInputs()
    local lesInputs = {}
    -- Initialisation à 0 (gris = rien)
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            lesInputs[getIndiceLesInputs(i, j)] = 0
        end
    end

    -- Les sprites (ennemis) = -1 (noir)
    local lesSprites = getLesSprites()
    for i = 1, #lesSprites, 1 do
        local input = convertirPositionPourInput(getLesSprites()[i])
        if input.x > 0 and input.x < (TAILLE_VUE_W / TAILLE_TILE) + 1 then
            lesInputs[getIndiceLesInputs(input.x, input.y)] = -1
        end
    end

    -- Les tiles (blocs) = valeur de la tile (blanc si > 0)
    local lesTiles = getLesTiles()
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local indice = getIndiceLesInputs(i, j)
            if lesTiles[indice] ~= 0 then
                lesInputs[indice] = lesTiles[indice]
            end
        end
    end

    return lesInputs
end

La grille d'inputs est une vue centrée sur Mario : 11 tiles en largeur, 9 en hauteur. Chaque tile vaut :

• 0 (gris) : rien
• 1 (blanc) : bloc solide
• -1 (noir) : ennemi

Les ennemis sont lus depuis deux listes dans la RAM : les sprites normaux (0x14C8-0x14F8) et les extended sprites (0x170B-0x173B). Pour chaque sprite vivant (état > 7), on calcule sa position en tiles par rapport à Mario et on met -1 dans la case correspondante.

Le fitness : comment l'IA sait si elle progresse

function majReseau(unReseau, marioBase)
    local mario = getPositionMario()

    if not niveauFini and memory.readbyte(0x0100) == 12 then
        -- Niveau terminé !
        unReseau.fitness = FITNESS_LEVEL_FINI
        niveauFini = true
    elseif marioBase.x < mario.x then
        -- Mario avance vers la droite
        unReseau.fitness = unReseau.fitness + (mario.x - marioBase.x)
        marioBase.x = mario.x
    end

    -- Mise à jour des inputs
    local lesInputs = getLesInputs()
    for i = 1, NB_INPUT, 1 do
        unReseau.lesNeurones[i].valeur = lesInputs[i]
    end
end

La fitness est simple : c'est la distance parcourue vers la droite. Si Mario avance de 10 pixels, la fitness augmente de 10. Si Mario recule, rien ne se passe (pas de pénalité). Si le niveau est terminé (adresse 0x0100 == 12), la fitness devient 1 000 000.

C'est intentionnellement simple. Seule la progression vers la droite compte : tuer des ennemis ne rapporte rien, mourir ne coûte rien.

Le reset intelligent

Si Mario ne bouge pas pendant 33 frames, on reset le niveau et on passe à l'individu suivant. Mais si Mario a fait des progrès (sa fitness actuelle est différente de celle au début), on attend 300 frames -- ça donne une chance au réseau de "comprendre" ce qu'il a fait de bien.

if fitnessAvant == laPopulation[idPopulation].fitness
   and memory.readbyte(0x13D4) == 0 then
    nbFrameStop = nbFrameStop + 1
    local nbFrameReset = NB_FRAME_RESET_BASE
    if fitnessInit ~= laPopulation[idPopulation].fitness
       and memory.readbyte(0x0071) ~= 9 then
        nbFrameReset = NB_FRAME_RESET_PROGRES
    end
    if nbFrameStop > nbFrameReset then
        nbFrameStop = 0
        lancerNiveau()
        idPopulation = idPopulation + 1
        -- ...
    end
end

La condition memory.readbyte(0x0071) ~= 9 vérifie que Mario n'est pas en animation de mort. Le reset devient inutile quand Mario est déjà en animation de mort.

La boucle principale

La boucle tourne à 30 fps (la vitesse normale de Super Mario World) :

while true do
    local fitnessAvant = laPopulation[idPopulation].fitness

    -- Affichage (réseau, infos)
    if forms.ischecked(estAccelere) then
        emu.limitframerate(false)  -- accélérer
    else
        emu.limitframerate(true)   -- 30 fps
    end

    -- Les 3 fonctions vitales
    majReseau(laPopulation[idPopulation], marioBase)
    feedForward(laPopulation[idPopulation])
    appliquerLesBoutons(laPopulation[idPopulation])

    emu.frameadvance()
    nbFrame = nbFrame + 1

    -- Reset si pas de progrès
    -- ...
    -- Nouvelle génération si tous les individus testés
    -- ...
end

Les trois fonctions vitales sont majReseau, feedForward, et appliquerLesBoutons. Si on en désactive une seule, Mario ne bouge plus.

Le crossover

function crossover(unReseau1, unReseau2)
    local leReseau = newReseau()
    local leBon = unReseau1
    local leNul = unReseau2

    if leBon.fitness < leNul.fitness then
        leBon = unReseau2
        leNul = unReseau1
    end

    leReseau = copier(leBon)

    for i = 1, #leReseau.lesConnexions, 1 do
        for j = 1, #leNul.lesConnexions, 1 do
            if leReseau.lesConnexions[i].innovation == leNul.lesConnexions[j].innovation
               and leNul.lesConnexions[j].actif then
                if math.random() > 0.5 then
                    leReseau.lesConnexions[i] = leNul.lesConnexions[j]
                end
            end
        end
    end
    leReseau.fitness = 1
    return leReseau
end

Le bébé hérite du meilleur parent. Pour chaque connexion partageant la même innovation, l'autre parent a 50% de chances de la remplacer -- mais seulement si la connexion est active. C'est un correctif important : sans ça, des neurones cachés inutiles pouvaient être créés.

La sélection par espèces

function nouvelleGeneration(laPopulation, lesEspeces)
    local laNouvellePopulation = newPopulation()
    local nbIndividuACreer = NB_INDIVIDU_POPULATION

    -- Calcul fitness moyenne par espèce
    for i = 1, #lesEspeces, 1 do
        lesEspeces[i].fitnessMoyenne = 0
        for j = 1, #lesEspeces[i].lesReseaux, 1 do
            lesEspeces[i].fitnessMoyenne =
                lesEspeces[i].fitnessMoyenne + lesEspeces[i].lesReseaux[j].fitness
        end
        lesEspeces[i].fitnessMoyenne =
            lesEspeces[i].fitnessMoyenne / #lesEspeces[i].lesReseaux
    end

    -- Chaque espèce crée un nombre d'enfants proportionnel à sa fitness moyenne
    for i = 1, #lesEspeces, 1 do
        local nbEnfant = math.ceil(
            #lesEspeces[i].lesReseaux *
            lesEspeces[i].fitnessMoyenne / fitnessMoyenneGlobal)

        for j = 1, nbEnfant, 1 do
            local unReseau = crossover(
                choisirParent(lesEspeces[i].lesReseaux),
                choisirParent(lesEspeces[i].lesReseaux))
            mutation(unReseau)
            laNouvellePopulation[indiceNouvelleEspece] = copier(unReseau)
        end
    end
end

L'idée : une espèce avec une fitness moyenne de 10 000 a le droit de créer beaucoup plus d'enfants qu'une espèce avec une fitness moyenne de 1. C'est la sélection naturelle en action.

Le choisirParent utilise une sélection par roulette : plus un individu a de fitness, plus il a de chances d'être sélectionné comme parent.

La sauvegarde et le chargement

Les populations sont sauvegardées dans des fichiers .pop :

function sauvegarderUnReseau(unReseau, fichier)
    io.write(unReseau.nbNeurone .. "\n")
    io.write(#unReseau.lesConnexions .. "\n")
    io.write(unReseau.fitness .. "\n")
    for i = 1, unReseau.nbNeurone, 1 do
        local indice = NB_INPUT + NB_OUTPUT + i
        io.write(unReseau.lesNeurones[indice].id .. "\n")
    end
    for i = 1, #unReseau.lesConnexions, 1 do
        local actif = 1
        if unReseau.lesConnexions[i].actif ~= true then actif = 0 end
        io.write(actif .. "\n" ..
            unReseau.lesConnexions[i].entree .. "\n" ..
            unReseau.lesConnexions[i].sortie .. "\n" ..
            unReseau.lesConnexions[i].poids .. "\n" ..
            unReseau.lesConnexions[i].innovation .. "\n")
    end
end

La sauvegarde inclut aussi le meilleur individu de toutes les populations précédentes. Si le meilleur de l'ancienne population est meilleur que le meilleur de la nouvelle, on reprend l'ancien comme base. C'est une forme d'élitisme : on ne perd jamais le meilleur.

Le dessin du réseau

Laupok a ajouté un visualiseur du réseau de neurones en surimpression du jeu :

function dessinerUnReseau(unReseau)
    -- Inputs : grille 11×9 autour de Mario
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local xT = ENCRAGE_X_INPUT + (i - 1) * TAILLE_INPUT
            local yT = ENCRAGE_Y_INPUT + (j - 1) * TAILLE_INPUT
            local couleurFond = "gray"
            if unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur < 0 then
                couleurFond = "black"   -- ennemi
            elseif unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur > 0 then
                couleurFond = "white"   -- bloc
            end
            gui.drawRectangle(xT, yT, TAILLE_INPUT, TAILLE_INPUT, "black", couleurFond)
        end
    end

    -- Outputs : 8 boutons
    for i = 1, NB_OUTPUT, 1 do
        local xT = ENCRAGE_X_OUTPUT
        local yT = ENCRAGE_Y_OUTPUT + ESPACE_Y_OUTPUT * (i - 1)
        if sigmoid(unReseau.lesNeurones[i + NB_INPUT].valeur) then
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "white")
        else
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "black")
        end
    end

    -- Connexions
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local alpha = 25
            if unReseau.lesConnexions[i].allume then alpha = 255 end
            local couleur = forms.createcolor(255, 255, 255, alpha)
            gui.drawLine(
                lesPositions[unReseau.lesConnexions[i].entree].x,
                lesPositions[lesConnexions[i].entree].y,
                lesPositions[unReseau.lesConnexions[i].sortie].x,
                lesPositions[lesConnexions[i].sortie].y,
                couleur)
        end
    end
end

C'est super utile pour comprendre ce que le réseau fait. Les connexions actives sont blanches, les inactives sont semi-transparentes. Les inputs sont une grille de cases blanches/noires/grises. Les outputs montrent quels boutons sont enfoncés.

---

Les résultats

Ce que l'IA a appris

Au fil des heures (et des jours) d'exécution, l'IA a découvert par elle-même :

1. Avancer vers la droite : le comportement le plus basique, mais qui nécessite de maintenir le bouton Droite enfoncé
2. Sauter par-dessus les ennemis : en connectant un input "ennemi détecté" au bouton A ou B
3. Éviter les obstacles : certains réseaux ont appris à reculer temporairement pour mieux avancer
4. Finir des niveaux : le meilleur individu a pu terminer le premier niveau de Super Mario World

Les Limitations

Le projet a ses limites :

• Un seul niveau : l'IA est entraînée sur un seul niveau spécifique. Elle ne généralise pas automatiquement à d'autres niveaux
• Temps d'entraînement : il faut des dizaines d'heures pour atteindre des résultats satisfaisants
• Pas de compréhension : l'IA ne "comprend" pas ce qu'elle fait. Elle optimise une fonction de fitness (distance parcourue) via des mutations aléatoires
• T-bagging : Laupok note que Mario a tendance à sauter sur place quand il voit un ennemi, simplement parce que ça augmente la fitness (il avance un peu en sautant)

---

Comment reproduire l'expérience

Laupok a tout partagé. Voici les étapes :

1. Télécharger BizHawk sur tasvideos.org (section Download)
2. Obtenir une ROM USA de Super Mario World (copie privée de ta propre cartouche)
3. Télécharger le script Lua depuis Pastebin -- renommer en mario.lua
4. Placer le script dans le même dossier que la ROM
5. Lancer BizHawk, ouvrir la ROM
6. Dans la console Lua : dofile("mario.lua") ou via le menu Script > Open Script
7. Sauvegarder un state au début du niveau (menu Savestate > Save State) et le nommer debut.state
8. Relancer le script -- ça marche

Le script inclut un formulaire avec des options :

• Accélérer : désactive la limite de 30 fps pour aller plus vite
• Afficher réseau : montre le réseau de neurones en surimpression
• Afficher infos : affiche un bandeau avec la génération, la fitness, le nombre d'espèces
• Pause : met en pause l'exécution
• Sauvegarder/Charger : persiste la population actuelle dans un fichier .pop

---

Sources et références

Ressource	Lien
Vidéo principale de Laupok	j'ai créé une IA qui joue à mario toute seule
Vidéo code review + setup	comment setup l'ia + code source review
Code source complet	Pastebin Jcvdqhqm
Article original de NEAT	Stanley & Miikkulainen, "Evolving Neural Networks through Augmenting Topologies", 2002
Tutoriel de N8Programs	NEAT implementation walkthrough (JavaScript, mais les concepts sont identiques)
16blings (inspiration de Laupok)	AI plays Super Mario World
BizHawk	tasvideos.org/BizHawk
Mémoire de Super Mario World	SMW Central - RAM Map

---

Conclusion

Ce que Laupok a fait, c'est prendre un algorithme académique (NEAT, 2002), le réécrire en Lua pour un émulateur (BizHawk), et l'appliquer à Super Mario World. Le résultat : une IA qui apprend de zéro à jouer au jeu, sans aucune connaissance préalable, uniquement par mutations aléatoires et sélection naturelle.

C'est un exemple magnifique de la puissance des algorithmes génétiques. La recette tient en trois ingrédients : la sélection naturelle, un peu de Lua, et beaucoup de patience. Aucun deep learning, aucun GPU, aucune donnée d'entraînement massive.

Le code est commenté, partagé, et Laupok a fait deux vidéos explicatives -- une pour les grands concepts, une pour le code. Si le sujet t'intéresse, plonge dedans. C'est plus accessible qu'il n'y paraît.

Laupok 做了个自己玩超级马里奥世界的 AI，它是怎么跑的

Laupok 做了个自己玩超级马里奥世界的人工智能。全自动。从零起步：没有预设脚本，没有录像帧。AI 靠随机变异和自然选择学会通关。项目跑在 BizHawk 上，多平台模拟器，经约 4200 行 Lua 脚本。

迷人的是它用的概念全是生物学往计算机搬：达尔文进化论、人工神经网络，还有个叫 NEAT（NeuroEvolution of Augmenting Topologies）的算法。AI 开局对游戏一无所知。随机试动作，死几千次，慢慢学会前进、跳、活命。

这篇全拆，概念一个个来，代码一行行来。

---

环境：BizHawk、Lua、超级马里奥世界

BizHawk 模拟器

BizHawk 是开源模拟器，机种一堆，NES、SNES、Genesis、PS1、Game Boy 等等。特点是能并行跑 Lua 脚本。脚本读写模拟内存（RAM），实时读改游戏任何数据。

具体说能：

• 读马里奥在关卡的位置
• 知道屏幕上哪些 sprite（敌人、道具）
• 知道马里奥周围每块 tile 状态
• 按手柄，任意键

做 AI 正好全要。

超级马里奥世界内存地址

SMW 的 RAM 里每个数据固定地址。像街区：每地址是装信息的"房子"。比如：

地址	数据
0x94-0x95	马里奥 X 位置（16 位，小端）
0x96-0x97	马里奥 Y 位置
0x14C8+i	sprite i 状态（>7 活着）
0xE4+i	sprite i X 低字节
0x14E0+i	sprite i X 高字节
0xD8+i	sprite i Y 低字节
0x14D4+i	sprite i Y 高字节
0x170B+i	extended sprite i 类型
0x0100	游戏状态（12 = 过关）
0x13D4	暂停
0x0071	马里奥死亡动画（9 = 死了）
0x1C800+...	关卡 tile 表

sprite 位置两字节：低字节加高字节，位置超 255 像素就这么办。公式永远低 + 高 × 256。

tile 复杂：基址 0x1C800，按 tile 在世界 x y 坐标算偏移，tile 16 像素步进。

---

前置：遗传算法和神经网络

先讲两个基本概念。不懂后面全白看。

遗传算法

遗传算法就是进化论模拟。核心：建种群，个体基因各不相同。放环境里活。活得好的生，活不好的死。

Laupok 用卡比打比方：

• 卡比种群出生在带刺和番茄的场上
• 刺扣血，番茄回血
• 每只卡比有基因：大小、速度、血量、行为（跑、找番茄、乱冲）

• 15 秒后看谁活最久
• 最好的卡比和其他的生：宝宝一半基因来自最好的，一半来自"最烂"
• 宝宝随机变异（大一点、快一点……）
• 老卡比换掉新的
• 重来

180 代（约 15 小时）后，卡比从活 15 秒到活 15 分钟。变小了（受击面积小）、快了、永远躲危险。

关键：不定义解。算法自己找出来。这就是它在不知道最优参数组合长什么样的问题上强的原因。

人工神经网络

神经网络是简化版人脑数学模型。组成：

• 输入神经元：网络"看"到的
• 输出神经元：网络"决定"的
• 连接（权重）：每条连接有个权重放大或衰减信号

原理简单：每个输入发值。乘连接权重，加别的信号。如果结果过阈（激活函数），输出神经元激活。

Laupok 拿马里奥和鼠标指针打比方：

• 输入神经元 = 马里奥和指针距离
• 连接权重 = 马里奥敏感度
• 输出神经元 = 马里奥叫不叫

指针越近输入值越大。权重强输出信号强，马里奥叫。改权重改马里奥敏感度。

真 AI 神经网络同理，规模大：

• 99 输入神经元（马里奥视野 11x9 tile）
• 8 输出神经元（A、B、X、Y、上、下、左、右）
• 中间隐藏神经元
• 几百条权重各异的连接

---

NEAT：改命的算法

朴素遗传加神经网络的问题

遗传算法加神经网络直接拼，有麻烦：造 100 个完全不同的神经网络，没法比。神经元、连接、权重各不同。两网络"近"还是"远"？

NEAT 上场，NeuroEvolution of Augmenting Topologies。Kenneth Stanley 和 Risto Miikkulainen 2002 年发明，专解这个问题。

物种

NEAT 第一关键机制物种。神经网络和另一个差太多，分不同物种。相似度三参数：

1. Excess（EXCES_COEF = 0.50）：两网络风马牛不相及的连接数（不同 innovation）
2. Disjoint：同上，但是中间位置的连接
3. 权重差（POIDSDIFF_COEF = 0.92）：共享 innovation 连接的平均权重差

分数公式：

分数 = (EXCES_COEF × disjoint) / max(连接数1 + 连接数2, 1)
       + POIDSDIFF_COEF × 权重差

分数小于 DIFF_LIMITE（1.0），两网络同物种。否则开新物种。

innovation

NEAT 的天才。每条连接出生拿全局唯一 innovation 号。号码跟网络走，繁殖也带着。

实际宝宝交叉继承亲本 innovation。两网络共享 innovation，说明这条连接同祖。大小不同的网络也能比了。

交叉

两神经网络繁殖，交叉这么跑：

1. 成绩好的当"显性亲本"
2. 宝宝全盘继承显性的连接
3. 每条共享 innovation 的连接，非显性亲本 50% 概率替换
4. 只有非显性亲本活跃连接能替换

保证宝宝至少不比最好的亲本差。

变异

交叉后宝宝按可配概率变异：

变异	概率	效果
连接权重重置	25%	权重全随机
权重变异	95%	权重 ±0.80 浮动
加连接	85%	没连的两神经元连上
加神经元	39%	两连着的神经元中间插隐藏神经元

加神经元概率重要：网络长大。开局只有输入输出。隐藏神经元慢慢冒出来，网络越来越复杂。

---

代码：完整走读

常量

脚本开头一串常量定全部参数：

-- 马里奥周围视野
TAILLE_TILE = 16
TAILLE_VUE_W = TAILLE_TILE * 11  -- 宽 176 像素
TAILLE_VUE_H = TAILLE_TILE * 9   -- 高 144 像素
NB_TILE_W = TAILLE_VUE_W / TAILLE_TILE  -- 11 tile
NB_TILE_H = TAILLE_VUE_H / TAILLE_TILE  -- 9 tile

-- 神经网络
NB_INPUT = NB_TILE_W * NB_TILE_H  -- 99 输入（看得到的 tile）
NB_OUTPUT = 8  -- A、B、X、Y、上、下、左、右
NB_INDIVIDU_POPULATION = 100  -- 每代个体
NB_NEURONE_MAX = 100000  -- 隐藏神经元上限

-- Fitness
FITNESS_LEVEL_FINI = 1000000  -- 过关分值
NB_FRAME_RESET_BASE = 33  -- 没进展多少帧重置
NB_FRAME_RESET_PROGRES = 300  -- 有进展给多少帧

-- 物种
EXCES_COEF = 0.50
POIDSDIFF_COEF = 0.92
DIFF_LIMITE = 1.00

-- 变异
CHANCE_MUTATION_RESET_CONNEXION = 0.25
POIDS_CONNEXION_MUTATION_AJOUT = 0.80
CHANCE_MUTATION_POIDS = 0.95
CHANCE_MUTATION_CONNEXION = 0.85
CHANCE_MUTATION_NEURONE = 0.39

NB_INPUT 99 因为马里奥视野 11x9 tile。每 tile 一输入。tile 空 0。块 1。敌人 -1。

8 输出对应 SNES 手柄键：A、B、X、Y、上、下、左、右。Start、Select、L、R 不用，决策越少越好。

数据结构

脚本定三个主结构：

function newNeurone()
    local neurone = {}
    neurone.valeur = 0    -- 神经元当前值
    neurone.id = 0        -- 唯一标识
    neurone.type = ""     -- "input"、"output" 或 "hidden"
    return neurone
end

function newConnexion()
    local connexion = {}
    connexion.entree = 0     -- 源神经元 ID
    connexion.sortie = 0     -- 目标神经元 ID
    connexion.actif = true   -- 插隐藏神经元可关掉
    connexion.poids = 0      -- 连接权重
    connexion.innovation = 0 -- 唯一 innovation 号
    connexion.allume = false -- 显示用：有信号过就亮
    return connexion
end

function newReseau()
    local reseau = {
        nbNeurone = 0,        -- 隐藏神经元数
        fitness = 1,          -- 成绩（走多远）
        idEspeceParent = 0,   -- 属于哪个物种
        lesNeurones = {},     -- 神经元表
        lesConnexions = {}    -- 连接表
    }
    -- 先初始化输入
    for j = 1, NB_INPUT, 1 do
        ajouterNeurone(reseau, j, "input", 1)
    end
    -- 再输出
    for j = NB_INPUT + 1, NB_INPUT + NB_OUTPUT, 1 do
        ajouterNeurone(reseau, j, "output", 0)
    end
    return reseau
end

开局每个网络只有输入输出：无隐藏神经元，无连接。要不要长算法定。

变异细看

权重变异

function mutationPoidsConnexions(unReseau)
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            if math.random() < CHANCE_MUTATION_RESET_CONNEXION then
                -- 25%：权重全重置
                unReseau.lesConnexions[i].poids = genererPoids()
            else
                -- 75%：±0.80 浮动
                if math.random() >= 0.5 then
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids - POIDS_CONNEXION_MUTATION_AJOUT
                else
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids + POIDS_CONNEXION_MUTATION_AJOUT
                end
            end
        end
    end
end

初始权重永远 1 或 -1（genererPoids()）。±0.80 浮动能在正负间荡，网络行为大变。

加连接

function mutationAjouterConnexion(unReseau)
    local liste = {}
    -- 神经元表打乱
    for i, v in ipairs(unReseau.lesNeurones) do
        local pos = math.random(1, #liste+1)
        table.insert(liste, pos, v)
    end

    local traitement = false
    for i = 1, #liste, 1 do
        for j = 1, #liste, 1 do
            if i ~= j then
                local n1 = liste[i]
                local n2 = liste[j]
                -- 合法连接：输入→输出、隐藏→隐藏、隐藏→输出
                if (n1.type == "input" and n2.type == "output") or
                   (n1.type == "hidden" and n2.type == "hidden") or
                   (n1.type == "hidden" and n2.type == "output") then
                    -- 查是不是已经连了
                    local dejaConnexion = false
                    for k = 1, #unReseau.lesConnexions, 1 do
                        if unReseau.lesConnexions[k].entree == n1.id
                            and unReseau.lesConnexions[k].sortie == n2.id then
                            dejaConnexion = true
                            break
                        end
                    end
                    if dejaConnexion == false then
                        traitement = true
                        ajouterConnexion(unReseau, n1.id, n2.id)
                    end
                end
            end
            if traitement then break end
        end
        if traitement then break end
    end
end

输出连输入不行（成环），连过的 pair 不重连。打乱保证每次探索不同可能。

加神经元

最有意思的变异：

function mutationAjouterNeurone(unReseau)
    if #unReseau.lesConnexions == 0 then return nil end
    if unReseau.nbNeurone == NB_NEURONE_MAX then return nil end

    -- 连接打乱
    local listeRandom = {}
    for i = 1, #unReseau.lesConnexions, 1 do
        local pos = math.random(1, #listeRandom+1)
        table.insert(listeRandom, pos, i)
    end

    for i = 1, #listeRandom, 1 do
        if unReseau.lesConnexions[listeRandom[i]].actif then
            -- 关掉已有连接
            unReseau.lesConnexions[listeRandom[i]].actif = false
            unReseau.nbNeurone = unReseau.nbNeurone + 1
            local indice = unReseau.nbNeurone + NB_INPUT + NB_OUTPUT

            -- 建隐藏神经元
            ajouterNeurone(unReseau, indice, "hidden", 1)

            -- 输入连隐藏
            ajouterConnexion(unReseau,
                unReseau.lesConnexions[listeRandom[i]].entree,
                indice, genererPoids())

            -- 隐藏连输出
            ajouterConnexion(unReseau,
                indice,
                unReseau.lesConnexions[listeRandom[i]].sortie,
                genererPoids())
            break
        end
    end
end

机制：挑条已有连接关掉，中间插隐藏神经元。原来一条变两条：输入→隐藏和隐藏→输出。像把电线剪断中间串开关。

这就是 NEAT "augmenting topologies"：网络随时间长大。简单开局，只在必要时变复杂。

feedForward

信号前向传播函数：

function feedForward(unReseau)
    -- 输出神经元清零
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur = 0
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].allume = false
        end
    end

    -- 传播
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local avantTraitement = unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur =
                unReseau.lesNeurones[unReseau.lesConnexions[i].entree].valeur *
                unReseau.lesConnexions[i].poids +
                unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur

            if avantTraitement ~= unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur then
                unReseau.lesConnexions[i].allume = true
            else
                unReseau.lesConnexions[i].allume = false
            end
        end
    end
end

每条活跃连接送 输入值 × 权重 到输出神经元。值累加。allume 旗只管网络可视化：有信号过就亮。

读游戏内存

getLesInputs() 把超级马里奥世界翻译成网络懂的数据：

function getLesInputs()
    local lesInputs = {}
    -- 初始化 0（灰 = 空）
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            lesInputs[getIndiceLesInputs(i, j)] = 0
        end
    end

    -- sprite（敌人）= -1（黑）
    local lesSprites = getLesSprites()
    for i = 1, #lesSprites, 1 do
        local input = convertirPositionPourInput(getLesSprites()[i])
        if input.x > 0 and input.x < (TAILLE_VUE_W / TAILLE_TILE) + 1 then
            lesInputs[getIndiceLesInputs(input.x, input.y)] = -1
        end
    end

    -- tile（块）= tile 值（> 0 白）
    local lesTiles = getLesTiles()
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local indice = getIndiceLesInputs(i, j)
            if lesTiles[indice] ~= 0 then
                lesInputs[indice] = lesTiles[indice]
            end
        end
    end

    return lesInputs
end

输入格是以马里奥为中心的视野：宽 11 tile，高 9 tile。每格值：

• 0（灰）：空
• 1（白）：实心块
• -1（黑）：敌人

敌人从 RAM 两表读：普通 sprite（0x14C8-0x14F8）和 extended sprite（0x170B-0x173B）。每活 sprite（状态 > 7）算相对马里奥的 tile 位置，对应格写 -1。

fitness：AI 怎么知道有没有进步

function majReseau(unReseau, marioBase)
    local mario = getPositionMario()

    if not niveauFini and memory.readbyte(0x0100) == 12 then
        -- 过关！
        unReseau.fitness = FITNESS_LEVEL_FINI
        niveauFini = true
    elseif marioBase.x < mario.x then
        -- 马里奥向右走
        unReseau.fitness = unReseau.fitness + (mario.x - marioBase.x)
        marioBase.x = mario.x
    end

    -- 更新输入
    local lesInputs = getLesInputs()
    for i = 1, NB_INPUT, 1 do
        unReseau.lesNeurones[i].valeur = lesInputs[i]
    end
end

fitness 简单粗暴：向右走多远。马里奥右移 10 像素 fitness 加 10。后退不扣分。过关（地址 0x0100 == 12）fitness 直接 100 万。

故意简单。只有向右算数：杀怪不加分，死不扣分。

智能重置

马里奥 33 帧不动，重置关卡换下个个体。马里奥有进展（fitness 和开局不一样），等 300 帧，给网络"想明白"的机会。

if fitnessAvant == laPopulation[idPopulation].fitness
   and memory.readbyte(0x13D4) == 0 then
    nbFrameStop = nbFrameStop + 1
    local nbFrameReset = NB_FRAME_RESET_BASE
    if fitnessInit ~= laPopulation[idPopulation].fitness
       and memory.readbyte(0x0071) ~= 9 then
        nbFrameReset = NB_FRAME_RESET_PROGRES
    end
    if nbFrameStop > nbFrameReset then
        nbFrameStop = 0
        lancerNiveau()
        idPopulation = idPopulation + 1
        -- ...
    end
end

memory.readbyte(0x0071) ~= 9 查马里奥不在死亡动画。死了重置没意义。

主循环

循环跑 30 fps（超级马里奥世界正常速度）：

while true do
    local fitnessAvant = laPopulation[idPopulation].fitness

    -- 显示（网络、信息）
    if forms.ischecked(estAccelere) then
        emu.limitframerate(false)  -- 加速
    else
        emu.limitframerate(true)   -- 30 fps
    end

    -- 3 个 vital 函数
    majReseau(laPopulation[idPopulation], marioBase)
    feedForward(laPopulation[idPopulation])
    appliquerLesBoutons(laPopulation[idPopulation])

    emu.frameadvance()
    nbFrame = nbFrame + 1

    -- 没进展重置
    -- ...
    -- 全测完新一代
    -- ...
end

majReseau、feedForward、appliquerLesBoutons 三个缺一，马里奥不动。

交叉

function crossover(unReseau1, unReseau2)
    local leReseau = newReseau()
    local leBon = unReseau1
    local leNul = unReseau2

    if leBon.fitness < leNul.fitness then
        leBon = unReseau2
        leNul = unReseau1
    end

    leReseau = copier(leBon)

    for i = 1, #leReseau.lesConnexions, 1 do
        for j = 1, #leNul.lesConnexions, 1 do
            if leReseau.lesConnexions[i].innovation == leNul.lesConnexions[j].innovation
               and leNul.lesConnexions[j].actif then
                if math.random() > 0.5 then
                    leReseau.lesConnexions[i] = leNul.lesConnexions[j]
                end
            end
        end
    end
    leReseau.fitness = 1
    return leReseau
end

宝宝继承好亲本。每条共享 innovation 的连接，差亲本 50% 概率替换，只限活跃连接。重要修：不然没用的隐藏神经元乱生。

按物种选

function nouvelleGeneration(laPopulation, lesEspeces)
    local laNouvellePopulation = newPopulation()
    local nbIndividuACreer = NB_INDIVIDU_POPULATION

    -- 算每物种平均 fitness
    for i = 1, #lesEspeces, 1 do
        lesEspeces[i].fitnessMoyenne = 0
        for j = 1, #lesEspeces[i].lesReseaux, 1 do
            lesEspeces[i].fitnessMoyenne =
                lesEspeces[i].fitnessMoyenne + lesEspeces[i].lesReseaux[j].fitness
        end
        lesEspeces[i].fitnessMoyenne =
            lesEspeces[i].fitnessMoyenne / #lesEspeces[i].lesReseaux
    end

    -- 每物种按平均 fitness 比例生孩子
    for i = 1, #lesEspeces, 1 do
        local nbEnfant = math.ceil(
            #lesEspeces[i].lesReseaux *
            lesEspeces[i].fitnessMoyenne / fitnessMoyenneGlobal)

        for j = 1, nbEnfant, 1 do
            local unReseau = crossover(
                choisirParent(lesEspeces[i].lesReseaux),
                choisirParent(lesEspeces[i].lesReseaux))
            mutation(unReseau)
            laNouvellePopulation[indiceNouvelleEspece] = copier(unReseau)
        end
    end
end

思路：平均 fitness 10000 的物种比平均 1 的多生得多孩子。这就是自然选择。

choisirParent 轮盘赌：fitness 越高当爹概率越大。

保存和加载

种群存 .pop 文件：

function sauvegarderUnReseau(unReseau, fichier)
    io.write(unReseau.nbNeurone .. "\n")
    io.write(#unReseau.lesConnexions .. "\n")
    io.write(unReseau.fitness .. "\n")
    for i = 1, unReseau.nbNeurone, 1 do
        local indice = NB_INPUT + NB_OUTPUT + i
        io.write(unReseau.lesNeurones[indice].id .. "\n")
    end
    for i = 1, #unReseau.lesConnexions, 1 do
        local actif = 1
        if unReseau.lesConnexions[i].actif ~= true then actif = 0 end
        io.write(actif .. "\n" ..
            unReseau.lesConnexions[i].entree .. "\n" ..
            unReseau.lesConnexions[i].sortie .. "\n" ..
            unReseau.lesConnexions[i].poids .. "\n" ..
            unReseau.lesConnexions[i].innovation .. "\n")
    end
end

存全部种群加之前所有代最好的。如果老最好的比新一代最好的强，拿老的当底子。一种精英主义：最好的永不丢。

画网络

Laupok 给网络加了游戏内 overlay 可视化：

function dessinerUnReseau(unReseau)
    -- 输入：马里奥周围 11x9 格
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local xT = ENCRAGE_X_INPUT + (i - 1) * TAILLE_INPUT
            local yT = ENCRAGE_Y_INPUT + (j - 1) * TAILLE_INPUT
            local couleurFond = "gray"
            if unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur < 0 then
                couleurFond = "black"   -- 敌人
            elseif unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur > 0 then
                couleurFond = "white"   -- 块
            end
            gui.drawRectangle(xT, yT, TAILLE_INPUT, TAILLE_INPUT, "black", couleurFond)
        end
    end

    -- 输出：8 个键
    for i = 1, NB_OUTPUT, 1 do
        local xT = ENCRAGE_X_OUTPUT
        local yT = ENCRAGE_Y_OUTPUT + ESPACE_Y_OUTPUT * (i - 1)
        if sigmoid(unReseau.lesNeurones[i + NB_INPUT].valeur) then
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "white")
        else
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "black")
        end
    end

    -- 连接
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local alpha = 25
            if unReseau.lesConnexions[i].allume then alpha = 255 end
            local couleur = forms.createcolor(255, 255, 255, alpha)
            gui.drawLine(
                lesPositions[unReseau.lesConnexions[i].entree].x,
                lesPositions[lesConnexions[i].entree].y,
                lesPositions[unReseau.lesConnexions[i].sortie].x,
                lesPositions[lesConnexions[i].sortie].y,
                couleur)
        end
    end
end

看网络在干嘛超有用。活跃连接白色，不活跃半透明。输入是白黑灰格子。输出看哪个键按着。

---

成果

AI 学会了什么

跑几小时（几天）下来，AI 自己悟出：

1. 向右走：最基础，但右键得一直按着
2. 跳过敌人：敌人输入连 A 或 B 键
3. 绕障碍：有些网络学会暂时后退再前进
4. 过关：最好的个体打通超级马里奥世界第一关

局限

项目有墙：

• 只会一关：单关训的，不自动泛化到别的关
• 训练时间：像样结果要几十小时
• 不懂：AI 不"理解"自己干嘛。按 fitness 函数（走多远）随机变异优化
• 蹭地：Laupok 说马里奥见敌人爱原地跳，因为跳也往前蹭涨 fitness

---

复现实验

Laupok 全开源了。步骤：

1. 下 BizHawk tasvideos.org（Download 区）
2. 搞 USA 版超级马里奥世界 ROM（自己卡带备份）
3. 下 Lua 脚本 Pastebin，改名 mario.lua
4. 脚本和 ROM 放同一文件夹
5. 开 BizHawk，打开 ROM
6. Lua 控制台：dofile("mario.lua") 或菜单 Script > Open Script
7. 存档开头（菜单 Savestate > Save State）起名 debut.state
8. 重跑脚本，成了

脚本带表单选项：

• 加速：关 30 fps 上限跑更快
• 显示网络：overlay 显示神经网络
• 显示信息：横幅显示代数、fitness、物种数
• 暂停：暂停执行
• 保存/加载：当前种群存 .pop 文件

---

来源和参考

资源	链接
Laupok 主视频	j'ai créé une IA qui joue à mario toute seule
代码 review 加环境视频	comment setup l'ia + code source review
完整源码	Pastebin Jcvdqhqm
NEAT 原论文	Stanley & Miikkulainen, "Evolving Neural Networks through Augmenting Topologies", 2002
N8Programs 教程	NEAT implementation walkthrough（JavaScript，但概念一样）
16blings（Laupok 灵感）	AI plays Super Mario World
BizHawk	tasvideos.org/BizHawk
超级马里奥世界内存	SMW Central - RAM Map

---

结语

Laupok 做的事：拿学术算法（NEAT，2002），Lua 重写给模拟器（BizHawk），用到超级马里奥世界。结果：AI 从零学会玩游戏，零先验知识，纯随机变异加自然选择。

遗传算法威力的漂亮例子。配方三样：自然选择，一点 Lua，大把耐心。不用深度学习，不用 GPU，不用海量训练数据。

代码有注释，开源，Laupok 做了两个讲解视频，一个讲大概念，一个讲代码。感兴趣直接跳， 比看着好懂。

Laupokが1人で遊ぶスーパーマリオワールドAIを作った。仕組みはこうだ

Laupokはスーパーマリオワールドを完全自律で遊ぶ人工知能を作った。ゼロから始まる。定義済みスクリプトなし、記録フレームなしだ。AIはランダム変異と自然選択の力で1人で学んで、ゲームの面をクリアする。プロジェクトはマルチプラットエミュレータBizHawk上で、約4200行のLuaスクリプト経由で回る。

このプロジェクトを魅惑的にするのは、情報学に応用した生物概念の上に立ってることだ。ダーウィンの進化論と人工ニューラルネット、そしてNEAT（NeuroEvolution of Augmenting Topologies）って特定アルゴリズムだ。AIは最初ゲームを何も知らない。ランダムに行動を試して、何千回も失敗して、少しずつ前に進んで、跳んで、生き延びる方法を理解する。

この記事では全部ほどいていく。概念ごと、コード行ごとだ。

---

セットアップ：BizHawkとLuaとスーパーマリオワールド

BizHawkエミュレータ

BizHawkは大量の本体に対応するオープンソースエミュレータだ。NES、SNES、Genesis、PS1、Game Boy、その他いろいろだ。特徴はゲームと並行にLuaスクリプトを走らせられることだ。このスクリプトはエミュレーションのRAMにアクセスできる。つまりリアルタイムでゲームの任意データを読み書きできる。

具体的にはこうできる。

• 面内のマリオ位置を読む
• 画面にいるスプライト（敵、アイテム）を知る
• マリオ周辺の各タイル（ブロック）状態を知る
• コントローラーを操作する。任意ボタンを押せる

AIを遊ばせるのにまさに要るものだ。

スーパーマリオワールドのメモリアドレス

スーパーマリオワールドのRAMでは各データが特定アドレスに保存される。街区みたいなものだ。各アドレスが情報を含む「家」に対応する。たとえばこうだ。

アドレス	データ
0x94-0x95	マリオのX位置（16ビット、リトルエンディアン）
0x96-0x97	マリオのY位置
0x14C8+i	スプライトiの状態（7超は生存）
0xE4+i	スプライトiの下位X位置
0x14E0+i	スプライトiの上位X位置
0xD8+i	スプライトiの下位Y位置
0x14D4+i	スプライトiの上位Y位置
0x170B+i	extendedスプライトiの種別
0x0100	ゲーム状態（12は面クリア）
0x13D4	ポーズ中
0x0071	マリオ死亡アニメ（9は死亡）
0x1C800+...	面のタイルテーブル

スプライト位置は2バイト使う。下位バイトと上位バイトだ。位置が255ピクセルを超えうるからね。式はつねに下位 + 上位 × 256だ。

タイルはもっと複雑だ。ベースアドレスは0x1C800で、世界内のタイル座標xとyからオフセットを計算する。タイルあたり16ピクセル刻みだ。

---

基礎：遺伝アルゴリズムとニューラルネット

コードに潜る前に2つの根本概念を理解しなきゃいけない。これなしでは残りが無意味だ。

遺伝アルゴリズム

遺伝アルゴリズムは進化論のシミュレーションだ。中心発想：集団の個体を作って、各々少し違う特徴（「遺伝子」）を持つ。環境で「生き」させる。うまくやったものが生き残って繁殖する。ダメなものは消える。

Laupokはカービィの例えで示す。

• トゲとトマトのある地形にカービィ集団が現れる
• トゲは体力を奪い、トマトは回復する
• 各カービィは遺伝子を持つ。大きさ、速さ、体力、挙動（逃げる、トマト探す、どこでも突っ込む）

• 15秒後、誰がいちばん長く生き残ったか見る
• 最良カービィが他と繁殖する。赤ちゃんは最良の遺伝子半分と「最悪」の半分を受け継ぐ
• 赤ちゃんはランダム変異を受ける（ちょっと大きい、ちょっと速いなど）
• 古いカービィは新しいのに置き換わる
• 再開する

180世代後（約15時間）、カービィは生存15秒から15分になる。小さく（当たり判定縮小）、速く、常に危険から逃げるようになった。

重要な点：解を定義しない。アルゴリズムが1人で見つける。まさにそれが、どのパラメータ組み合わせが最適か分からない問題に強力なんだ。

人工ニューラルネット

ニューラルネットは人脳の単純化数学モデルだ。構成はこうだ。

• 入力ニューロン（inputs）：ネットが「見る」もの
• 出力ニューロン（outputs）：ネットが「決める」もの
• 接続（重み）：各接続は信号を増幅か減衰する重みを持つ

仕組みは単純だ。各入力ニューロンが値を送る。接続重みで掛けられて、他の信号と足される。結果があるしきい値（活性化関数）を超えたら出力ニューロンが発火する。

マリオとネズミの切れ端のLaupokの例えではこうだ。

• 入力ニューロン = マリオと切れ端の距離
• 接続重み = マリオの敏感さ
• 出力ニューロン = マリオが叫ぶかどうか

切れ端が近いほど入力値は高い。重みが強ければ出力信号は強くて、マリオは叫ぶだろう。重みを変えればマリオの敏感さが変わる。

AIの本物ニューラルネットでは同じ理屈だが、大規模だ。

• 99入力ニューロン（マリオ視界11×9タイル）
• 8出力ニューロン（A、B、X、Y、上、下、左、右）
• 間にある隠れニューロン（hidden）
• 重み様々の数百接続

---

NEAT：全部変えるアルゴリズム

古典遺伝アルゴリズムの問題

遺伝アルゴリズムとニューラルネットを素朴に組み合わせると問題が出る。まったく違うニューラルネット100個を作って、比べ方が分からない。各々独自ニューロン、独自接続、独自重みだ。2つのネットが「近い」か「遠い」かどう知るのか。

ここでNEAT、NeuroEvolution of Augmenting Topologiesの出番だ。Kenneth StanleyとRisto Miikkulainenが2002年に発明した。この問題を正確に解くアルゴリズムだ。

種

NEATの最初の鍵仕組みは種だ。ニューラルネットが別のものと違いすぎると、違う種に分類される。類似度は3パラメータで計算する。

1. Excess（EXCES_COEF = 0.50）：2ネット間で無関係な接続数（違う innovation）
2. Disjoint：同じだが、真ん中にある接続について
3. 重み差（POIDSDIFF_COEF = 0.92）：同じ innovation を共有する接続間の平均重み差

スコア式：

score = (EXCES_COEF × disjoint) / max(nbConnexions1 + nbConnexions2, 1)
      + POIDSDIFF_COEF × diffPoids

このスコアがDIFF_LIMITE（1.0）未満なら2ネットは同じ種だ。そうじゃなければ新種を作る。

innovation

NEATの天才的なところだ。接続が作られるたび、グローバルに一意なinnovation番号を受ける。この番号は繁殖してもニューラルネットに付いてくる。

具体的には、交叉で赤ちゃんが作られるとき両親の innovation を受け継ぐ。2ネットが同じ innovation を共有したら、同じ祖先由来の接続があるってことだ。大きさの違うネットを比べられるのはこれのおかげだ。

交叉

2つのニューラルネットが繁殖するとき、交叉はこう動く。

1. 高性能なネットが「優性親」になる
2. 赤ちゃんは優性の全接続を受け継ぐ
3. 同じ innovation を共有する各接続について、もう片方の親が置き換えうる（50パーセント）
4. 非優性親の活性接続だけが置き換えられる

赤ちゃんが最良親と少なくとも同等なことが保証される。

変異

交叉後、赤ちゃんは設定可能確率で変異を受ける。

変異	確率	効果
接続重みリセット	25%	重みは完全ランダム化
重み変異	95%	重みはプラスマイナス0.80変動
接続追加	85%	未接続2ニューロン間の新規接続
ニューロン追加	39%	接続済み2ニューロン間に隠れニューロン挿入

ニューロン追加率が大事だ。ネットが育つのを許す。最初は入出力だけだ。少しずつ隠れニューロンが現れて、ネットはますます複雑になる。

---

コード：完全ウォークスルー

定数

スクリプトは全部のパラメータを定義する定数ブロックから始まる。

-- マリオ周辺の視界
TAILLE_TILE = 16
TAILLE_VUE_W = TAILLE_TILE * 11  -- 幅176ピクセル
TAILLE_VUE_H = TAILLE_TILE * 9   -- 高さ144ピクセル
NB_TILE_W = TAILLE_VUE_W / TAILLE_TILE  -- 11タイル
NB_TILE_H = TAILLE_VUE_H / TAILLE_TILE  -- 9タイル

-- ニューラルネット
NB_INPUT = NB_TILE_W * NB_TILE_H  -- 99入力（見えるタイル）
NB_OUTPUT = 8  -- A、B、X、Y、上、下、左、右
NB_INDIVIDU_POPULATION = 100  -- 集団あたり個体数
NB_NEURONE_MAX = 100000  -- 隠れニューロン上限

-- Fitness
FITNESS_LEVEL_FINI = 1000000  -- 面終了時の値
NB_FRAME_RESET_BASE = 33  -- 進歩なしリセットまでのフレーム
NB_FRAME_RESET_PROGRES = 300  -- 進歩検出時のフレーム

-- 種
EXCES_COEF = 0.50
POIDSDIFF_COEF = 0.92
DIFF_LIMITE = 1.00

-- 変異
CHANCE_MUTATION_RESET_CONNEXION = 0.25
POIDS_CONNEXION_MUTATION_AJOUT = 0.80
CHANCE_MUTATION_POIDS = 0.95
CHANCE_MUTATION_CONNEXION = 0.85
CHANCE_MUTATION_NEURONE = 0.39

NB_INPUTが99なのはマリオ視界が11×9タイルだからだ。各タイルが入力ニューロン1つだ。タイルが空なら0だ。ブロックなら1だ。敵なら-1だ。

8出力はSNESコントローラーのボタンに対応する。A、B、X、Y、上、下、左、右だ。決定を要点に絞るためStart、Select、L、Rは除く。

データ構造

スクリプトは3つの主要構造を定義する。

function newNeurone()
    local neurone = {}
    neurone.valeur = 0    -- ニューロンの現在値
    neurone.id = 0        -- 一意ID
    neurone.type = ""     -- 「input」「output」「hidden」
    return neurone
end

function newConnexion()
    local connexion = {}
    connexion.entree = 0     -- ソースニューロンID
    connexion.sortie = 0     -- 宛先ニューロンID
    connexion.actif = true   -- 隠れニューロン挿入で無効化されうる
    connexion.poids = 0      -- 接続重み
    connexion.innovation = 0 -- 一意innovation番号
    connexion.allume = false -- 表示用：信号通過でtrue
    return connexion
end

function newReseau()
    local reseau = {
        nbNeurone = 0,        -- 隠れニューロン数
        fitness = 1,          -- 性能（進んだ距離）
        idEspeceParent = 0,   -- どの種に属するか
        lesNeurones = {},     -- ニューロンテーブル
        lesConnexions = {}    -- 接続テーブル
    }
    -- 入力で初期化
    for j = 1, NB_INPUT, 1 do
        ajouterNeurone(reseau, j, "input", 1)
    end
    -- 次に出力
    for j = NB_INPUT + 1, NB_INPUT + NB_OUTPUT, 1 do
        ajouterNeurone(reseau, j, "output", 0)
    end
    return reseau
end

最初、各ネットは入出力だけを含む。隠れニューロンなし、接続なしだ。要るかどうかはアルゴリズムが決める。

変異の詳細

重み変異

function mutationPoidsConnexions(unReseau)
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            if math.random() < CHANCE_MUTATION_RESET_CONNEXION then
                -- 25%：重みの完全リセット
                unReseau.lesConnexions[i].poids = genererPoids()
            else
                -- 75%：プラスマイナス0.80の変動
                if math.random() >= 0.5 then
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids - POIDS_CONNEXION_MUTATION_AJOUT
                else
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids + POIDS_CONNEXION_MUTATION_AJOUT
                end
            end
        end
    end
end

初期重みはつねに1か-1だ（genererPoids()）。プラスマイナス0.80の変動で負値と正値の間を揺れて、ネット挙動が根本から変わりうる。

接続追加

function mutationAjouterConnexion(unReseau)
    local liste = {}
    -- ニューロン一覧のランダム化
    for i, v in ipairs(unReseau.lesNeurones) do
        local pos = math.random(1, #liste+1)
        table.insert(liste, pos, v)
    end

    local traitement = false
    for i = 1, #liste, 1 do
        for j = 1, #liste, 1 do
            if i ~= j then
                local n1 = liste[i]
                local n2 = liste[j]
                -- 有効接続：inputからoutput、hiddenからhidden、hiddenからoutput
                if (n1.type == "input" and n2.type == "output") or
                   (n1.type == "hidden" and n2.type == "hidden") or
                   (n1.type == "hidden" and n2.type == "output") then
                    -- 接続済みでないか確認
                    local dejaConnexion = false
                    for k = 1, #unReseau.lesConnexions, 1 do
                        if unReseau.lesConnexions[k].entree == n1.id
                            and unReseau.lesConnexions[k].sortie == n2.id then
                            dejaConnexion = true
                            break
                        end
                    end
                    if dejaConnexion == false then
                        traitement = true
                        ajouterConnexion(unReseau, n1.id, n2.id)
                    end
                end
            end
            if traitement then break end
        end
        if traitement then break end
    end
end

outputからinputには繋げない（輪を作る）。繋がってる2ニューロンも繋げない。ランダム化で毎回違う可能性を探ることが保証される。

ニューロン追加

いちばん面白い変異だ。

function mutationAjouterNeurone(unReseau)
    if #unReseau.lesConnexions == 0 then return nil end
    if unReseau.nbNeurone == NB_NEURONE_MAX then return nil end

    -- 接続のランダム化
    local listeRandom = {}
    for i = 1, #unReseau.lesConnexions, 1 do
        local pos = math.random(1, #listeRandom+1)
        table.insert(listeRandom, pos, i)
    end

    for i = 1, #listeRandom, 1 do
        if unReseau.lesConnexions[listeRandom[i]].actif then
            -- 既存接続を無効化
            unReseau.lesConnexions[listeRandom[i]].actif = false
            unReseau.nbNeurone = unReseau.nbNeurone + 1
            local indice = unReseau.nbNeurone + NB_INPUT + NB_OUTPUT

            -- 隠れニューロンを作る
            ajouterNeurone(unReseau, indice, "hidden", 1)

            -- 入力を隠れニューロンへ接続
            ajouterConnexion(unReseau,
                unReseau.lesConnexions[listeRandom[i]].entree,
                indice, genererPoids())

            -- 隠れニューロンを出力へ接続
            ajouterConnexion(unReseau,
                indice,
                unReseau.lesConnexions[listeRandom[i]].sortie,
                genererPoids())
            break
        end
    end
end

仕組み：既存接続を1つ取って無効化して、真ん中に隠れニューロンを挿入する。元の接続は2つの新接続に置き換わる。入力から隠れへと隠れから出力へだ。電線を切って間にスイッチを挟むみたいなものだ。

これがNEATの「augmenting topologies」を作る。ネットは時間とともに育つ。単純に始まって、必要なら複雑になるだけだ。

feedForward

信号をネットに伝える関数だ。

function feedForward(unReseau)
    -- 出力ニューロンのリセット
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur = 0
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].allume = false
        end
    end

    -- 伝播
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local avantTraitement = unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur =
                unReseau.lesNeurones[unReseau.lesConnexions[i].entree].valeur *
                unReseau.lesConnexions[i].poids +
                unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur

            if avantTraitement ~= unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur then
                unReseau.lesConnexions[i].allume = true
            else
                unReseau.lesConnexions[i].allume = false
            end
        end
    end
end

各活性接続は出力ニューロンへ入力値 × 重みを送る。値は累積（加算）される。allumeフラグはネットの視覚表示用だ。

ゲームメモリの読み取り

getLesInputs()関数はスーパーマリオワールド世界をネットが分かるデータに翻訳する。

function getLesInputs()
    local lesInputs = {}
    -- 0で初期化（灰は無）
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            lesInputs[getIndiceLesInputs(i, j)] = 0
        end
    end

    -- スプライト（敵）= -1（黒）
    local lesSprites = getLesSprites()
    for i = 1, #lesSprites, 1 do
        local input = convertirPositionPourInput(getLesSprites()[i])
        if input.x > 0 and input.x < (TAILLE_VUE_W / TAILLE_TILE) + 1 then
            lesInputs[getIndiceLesInputs(input.x, input.y)] = -1
        end
    end

    -- タイル（ブロック）= タイル値（0超で白）
    local lesTiles = getLesTiles()
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local indice = getIndiceLesInputs(i, j)
            if lesTiles[indice] ~= 0 then
                lesInputs[indice] = lesTiles[indice]
            end
        end
    end

    return lesInputs
end

入力グリッドはマリオ中心の視界だ。幅11タイル、高さ9だ。各タイルはこうだ。

• 0（灰）：無
• 1（白）：固体ブロック
• -1（黒）：敵

敵はRAM内2リストから読む。通常スプライト（0x14C8-0x14F8）とextendedスプライト（0x170B-0x173B）だ。各生存スプライト（状態7超）について、マリオ相対のタイル位置を計算して対応マスに-1を置く。

fitness：AIが進歩を知る方法

function majReseau(unReseau, marioBase)
    local mario = getPositionMario()

    if not niveauFini and memory.readbyte(0x0100) == 12 then
        -- 面終了！
        unReseau.fitness = FITNESS_LEVEL_FINI
        niveauFini = true
    elseif marioBase.x < mario.x then
        -- マリオが右へ進む
        unReseau.fitness = unReseau.fitness + (mario.x - marioBase.x)
        marioBase.x = mario.x
    end

    -- 入力の更新
    local lesInputs = getLesInputs()
    for i = 1, NB_INPUT, 1 do
        unReseau.lesNeurones[i].valeur = lesInputs[i]
    end
end

fitnessは単純だ。右へ進んだ距離だ。マリオが10ピクセル進めばfitnessは10増える。マリオが戻っても何も起きない（罰なし）。面終了（アドレス0x0100が12）でfitnessは1,000,000になる。

わざと単純だ。数えるのは右への進行だけだ。敵を倒しても点なし、死んでも損なしだ。

賢いリセット

マリオが33フレーム動かなければ面をリセットして次の個体に行く。でもマリオが進歩してたら（現fitnessが開始時と違う）、300フレーム待つ。ネットが「うまくいったことを理解」する機会を与える。

if fitnessAvant == laPopulation[idPopulation].fitness
   and memory.readbyte(0x13D4) == 0 then
     nbFrameStop = nbFrameStop + 1
     local nbFrameReset = NB_FRAME_RESET_BASE
     if fitnessInit ~= laPopulation[idPopulation].fitness
        and memory.readbyte(0x0071) ~= 9 then
         nbFrameReset = NB_FRAME_RESET_PROGRES
     end
     if nbFrameStop > nbFrameReset then
         nbFrameStop = 0
         lancerNiveau()
         idPopulation = idPopulation + 1
         -- ...
     end
end

memory.readbyte(0x0071) ~= 9条件はマリオが死亡アニメ中か確認する。マリオがすでに死亡アニメならリセットは無駄だ。

メインループ

ループは30fpsで回る（スーパーマリオワールドの通常速度）。

while true do
    local fitnessAvant = laPopulation[idPopulation].fitness

    -- 表示（ネット、情報）
    if forms.ischecked(estAccelere) then
        emu.limitframerate(false)  -- 高速化
    else
        emu.limitframerate(true)   -- 30fps
    end

    -- 3つの生命線関数
    majReseau(laPopulation[idPopulation], marioBase)
    feedForward(laPopulation[idPopulation])
    appliquerLesBoutons(laPopulation[idPopulation])

    emu.frameadvance()
    nbFrame = nbFrame + 1

    -- 進歩なければリセット
    -- ...
    -- 全個体試験で新世代
    -- ...
end

3つの生命線関数はmajReseau、feedForward、appliquerLesBoutonsだ。1つ切るだけでマリオは動かなくなる。

交叉

function crossover(unReseau1, unReseau2)
    local leReseau = newReseau()
    local leBon = unReseau1
    local leNul = unReseau2

    if leBon.fitness < leNul.fitness then
        leBon = unReseau2
        leNul = unReseau1
    end

    leReseau = copier(leBon)

    for i = 1, #leReseau.lesConnexions, 1 do
        for j = 1, #leNul.lesConnexions, 1 do
            if leReseau.lesConnexions[i].innovation == leNul.lesConnexions[j].innovation
               and leNul.lesConnexions[j].actif then
                if math.random() > 0.5 then
                    leReseau.lesConnexions[i] = leNul.lesConnexions[j]
                end
            end
        end
    end
    leReseau.fitness = 1
    return leReseau
end

赤ちゃんは最良親を受け継ぐ。同じ innovation を共有する各接続について、もう片方の親が50パーセントで置き換える。ただし接続が活性の場合だけだ。大事な修正だ。これなしでは無駄な隠れニューロンが作られうる。

種による選択

function nouvelleGeneration(laPopulation, lesEspeces)
    local laNouvellePopulation = newPopulation()
    local nbIndividuACreer = NB_INDIVIDU_POPULATION

    -- 種ごとの平均fitness計算
    for i = 1, #lesEspeces, 1 do
        lesEspeces[i].fitnessMoyenne = 0
        for j = 1, #lesEspeces[i].lesReseaux, 1 do
            lesEspeces[i].fitnessMoyenne =
                lesEspeces[i].fitnessMoyenne + lesEspeces[i].lesReseaux[j].fitness
        end
        lesEspeces[i].fitnessMoyenne =
            lesEspeces[i].fitnessMoyenne / #lesEspeces[i].lesReseaux
    end

    -- 各種は平均fitness比例の子数を作る
    for i = 1, #lesEspeces, 1 do
        local nbEnfant = math.ceil(
            #lesEspeces[i].lesReseaux *
            lesEspeces[i].fitnessMoyenne / fitnessMoyenneGlobal)

        for j = 1, nbEnfant, 1 do
            local unReseau = crossover(
                choisirParent(lesEspeces[i].lesReseaux),
                choisirParent(lesEspeces[i].lesReseaux))
            mutation(unReseau)
            laNouvellePopulation[indiceNouvelleEspece] = copier(unReseau)
        end
    end
end

考え方：平均fitness 10,000の種は平均1の種よりずっと多くの子を作る権利がある。行動中の自然選択だ。

choisirParentはルーレット選択を使う。fitnessが高い個体ほど親に選ばれやすい。

保存と読み込み

集団は.popファイルに保存される。

function sauvegarderUnReseau(unReseau, fichier)
    io.write(unReseau.nbNeurone .. "\n")
    io.write(#unReseau.lesConnexions .. "\n")
    io.write(unReseau.fitness .. "\n")
    for i = 1, unReseau.nbNeurone, 1 do
        local indice = NB_INPUT + NB_OUTPUT + i
        io.write(unReseau.lesNeurones[indice].id .. "\n")
    end
    for i = 1, #unReseau.lesConnexions, 1 do
        local actif = 1
        if unReseau.lesConnexions[i].actif ~= true then actif = 0 end
        io.write(actif .. "\n" ..
            unReseau.lesConnexions[i].entree .. "\n" ..
            unReseau.lesConnexions[i].sortie .. "\n" ..
            unReseau.lesConnexions[i].poids .. "\n" ..
            unReseau.lesConnexions[i].innovation .. "\n")
    end
end

保存は過去全集団の最良個体も含む。旧集団の最良が新集団の最良より良ければ、旧を土台に取り戻す。エリート主義の一形態だ。最良は絶対失わない。

ネットの描画

Laupokはゲーム上に重ねるニューラルネット可視化を足した。

function dessinerUnReseau(unReseau)
    -- 入力：マリオ周辺11×9グリッド
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local xT = ENCRAGE_X_INPUT + (i - 1) * TAILLE_INPUT
            local yT = ENCRAGE_Y_INPUT + (j - 1) * TAILLE_INPUT
            local couleurFond = "gray"
            if unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur < 0 then
                couleurFond = "black"   -- 敵
            elseif unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur > 0 then
                couleurFond = "white"   -- ブロック
            end
            gui.drawRectangle(xT, yT, TAILLE_INPUT, TAILLE_INPUT, "black", couleurFond)
        end
    end

    -- 出力：8ボタン
    for i = 1, NB_OUTPUT, 1 do
        local xT = ENCRAGE_X_OUTPUT
        local yT = ENCRAGE_Y_OUTPUT + ESPACE_Y_OUTPUT * (i - 1)
        if sigmoid(unReseau.lesNeurones[i + NB_INPUT].valeur) then
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "white")
        else
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "black")
        end
    end

    -- 接続
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local alpha = 25
            if unReseau.lesConnexions[i].allume then alpha = 255 end
            local couleur = forms.createcolor(255, 255, 255, alpha)
            gui.drawLine(
                lesPositions[unReseau.lesConnexions[i].entree].x,
                lesPositions[lesConnexions[i].entree].y,
                lesPositions[unReseau.lesConnexions[i].sortie].x,
                lesPositions[lesConnexions[i].sortie].y,
                couleur)
        end
    end
end

ネットが何してるか理解するのに超便利だ。活性接続は白、不活性は半透明だ。入力は白黒灰マスのグリッドだ。出力はどのボタンが押されてるか示す。

---

結果

AIが学んだこと

何時間も（何日も）回すうちに、AIは1人で発見した。

1. 右へ進む：いちばん基本的挙動だが、右ボタン押しっぱなしが必要だ
2. 敵を飛び越える：「敵検出」入力をAかBボタンに繋いで
3. 障害物を避ける：一部のネットはもっと先へ進むため一時後退を学んだ
4. 面を終える：最良個体はスーパーマリオワールド1面を終えられた

限界

プロジェクトには限界がある。

• 1面だけ：AIは特定1面で訓練される。他面に自動一般化しない
• 訓練時間：満足いく結果に数十時間要る
• 理解なし：AIはやってることを「分かって」ない。fitness関数（進んだ距離）をランダム変異で最適化してる
• 屈伸煽り：敵を見るとマリオはその場跳びしがちだとLaupokは記す。跳ぶと少し進んでfitnessが上がるからだ

---

実験を再現する方法

Laupokは全部共有した。手順はこうだ。

1. BizHawkを落とす。tasvideos.orgから（Download節）
2. スーパーマリオワールドのUSA ROMを入手する（自分のカートリッジの私的コピー）
3. Luaスクリプトを落とす。Pastebinから。mario.luaに改名する
4. ROMと同じフォルダにスクリプトを置く
5. BizHawkを起動してROMを開く
6. Luaコンソールで：dofile("mario.lua")かメニューScript > Open Scriptから
7. 面頭でstateを保存する（メニューSavestate > Save State）。debut.stateと名付ける
8. スクリプトを再起動する。動く

スクリプトは選択肢付きフォームを含む。

• 高速化：30fps制限を外して速く進める
• ネット表示：ニューラルネットを重ねて見せる
• 情報表示：世代、fitness、種数の帯を表示する
• Pause：実行を止める
• 保存や読み込み：現集団を.popファイルに永続化する

---

出典と参照

リソース	リンク
Laupokのメイン動画	j'ai créé une IA qui joue à mario toute seule
コードレビューとsetup動画	comment setup l'ia + code source review
完全ソース	Pastebin Jcvdqhqm
NEAT原論文	Stanley & Miikkulainen, "Evolving Neural Networks through Augmenting Topologies", 2002
N8Programsのチュートリアル	NEAT implementation walkthrough（JavaScriptだが概念は同一）
16blings（Laupokの着想元）	AI plays Super Mario World
BizHawk	tasvideos.org/BizHawk
スーパーマリオワールドのメモリ	SMW Central - RAM Map

---

結論

Laupokがやったのは、学術アルゴリズム（NEAT、2002年）を取って、エミュレータ（BizHawk）用にLuaで書き直して、スーパーマリオワールドに適用したことだ。結果：事前知識ゼロで1人でゲームを遊ぶことを学ぶAIだ。ランダム変異と自然選択だけだ。

遺伝アルゴリズムの力の見事な例だ。レシピは3材料だ。自然選択、少しのLua、大量の忍耐だ。ディープラーニングなし、GPUなし、大量訓練データなしだ。

コードはコメント付きで共有されて、Laupokは2つの解説動画を作った。1つは大概念用、1つはコード用だ。興味が出たら潜って。見た目より取っ付きやすいよ。

Laupok이 혼자 Super Mario World를 하는 AI를 만들었어요. 어떻게 동작하나요

Laupok이 Super Mario World를 완전히 자율로 플레이하는 인공지능을 만들었어요. 0에서 출발해요. 미리 정해진 스크립트도 녹화된 프레임도 없어요. AI는 무작위 변이와 자연 선택으로 레벨을 끝내는 법을 혼자 배워요. 프로젝트는 멀티플랫폼 에뮬레이터 BizHawk 위에서 약 4200줄 Lua 스크립트로 돌아요.

이 프로젝트를 매혹적으로 만드는 것은 생물학 개념을 컴퓨터에 적용했다는 거예요. Darwin의 진화론과 인공 신경망, 그리고 NEAT(NeuroEvolution of Augmenting Topologies)라는 특정 알고리즘이요. AI는 처음에 게임에 대해 아무것도 몰라요. 무작위로 행동을 테스트하고 수천 번 실패하고, 조금씩 앞으로 가고 점프하고 살아남는 법을 이해해요.

이 글에서는 그 모든 것을 뜯어봐요. 개념별로, 코드 줄별로.

---

설정: BizHawk, Lua, Super Mario World

BizHawk 에뮬레이터

BizHawk는 여러 콘솔을 지원하는 오픈 소스 에뮬레이터예요. NES, SNES, Genesis, PS1, Game Boy 등등. 특징은 게임과 나란히 Lua 스크립트를 실행할 수 있다는 거예요. 이 스크립트들은 에뮬레이션의 RAM에 닿아서, 게임의 어떤 자료든 실시간으로 읽고 수정할 수 있어요.

구체적으로 할 수 있는 것은요.

• 레벨 속 Mario 위치 읽기
• 화면의 스프라이트(적, 아이템) 알기
• Mario 주변 각 타일(블록) 상태 알기
• 패드 조종. 어떤 버튼이든 누르기

AI가 플레이하게 하기에 정확히 필요한 것이에요.

Super Mario World 메모리 주소

Super Mario World RAM에서 각 자료는 특정 주소에 저장돼요. 동네 같아요. 각 주소가 정보를 담은 "집" 하나예요. 예를 들면요.

주소	자료
0x94-0x95	Mario X 위치 (16비트, 리틀엔디언)
0x96-0x97	Mario Y 위치
0x14C8+i	스프라이트 i 상태 (>7이면 살아 있음)
0xE4+i	스프라이트 i 하위 X 위치
0x14E0+i	스프라이트 i 상위 X 위치
0xD8+i	스프라이트 i 하위 Y 위치
0x14D4+i	스프라이트 i 상위 Y 위치
0x170B+i	확장 스프라이트 i 종류
0x0100	게임 상태 (12이면 레벨 끝)
0x13D4	일시정지 활성
0x0071	Mario 죽음 애니메이션 (9이면 사망)
0x1C800+...	레벨 타일 표

스프라이트 위치는 2바이트를 써요. 하위 바이트와 상위 바이트. 위치가 255픽셀을 넘을 수 있으니까요. 공식은 항상 하위 + 상위 × 256.

타일은 더 복잡해요. 베이스 주소 0x1C800, 월드에서 타일의 x와 y 좌표로 오프셋을 계산하고, 타일당 16픽셀 간격이에요.

---

기초: 유전 알고리즘과 신경망

코드에 들어가기 전에 두 가지 기본 개념을 이해해야 해요. 없으면 나머지가 의미가 없어요.

유전 알고리즘

유전 알고리즘이란 진화론의 시뮬레이션이에요. 핵심 생각: 서로 조금씩 다른 특성("유전자")을 가진 개체들의 집단을 만들어요. 환경에서 "살게" 해요. 잘 해내는 것들이 살아남고 번식해요. 못 해내는 것들은 사라져요.

Laupok은 Kirby 비유로 보여줘요.

• 가시와 토마토가 있는 지형에 Kirby 집단이 나와요
• 가시는 체력을 깎고 토마토는 채워줘요
• 각 Kirby에는 유전자가 있어요. 크기, 속도, 체력, 행동(도망, 토마토 찾기, 아무 데나 돌진)

• 15초 뒤 누가 가장 오래 살아남았는지 봐요
• 최고 Kirby가 다른 것들과 번식해요. 아기들은 최고의 절반과 "최악"의 절반 유전자를 물려받아요
• 아기들은 무작위 변이를 겪어요 (조금 더 크고, 조금 더 빠르고...)
• 옛 Kirby들은 새들로 교체돼요
• 다시 시작해요

180세대(~15시간) 뒤 Kirby들은 생존 15초에서 15분으로 가요. 작아지고(충돌 범위 축소), 빨라지고, 끊임없이 위험을 피해요.

핵심 지점: 해법을 정하지 않아요. 알고리즘이 혼자 찾아요. 최적의 매개변수 조합이 무엇인지 모르는 문제에 강력해지는 이유가 바로 그거예요.

인공 신경망

신경망은 인간 뇌의 단순 수학 모델이에요. 구성은요.

• 입력 뉴런 (inputs): 네트워크가 "보는" 것
• 출력 뉴런 (outputs): 네트워크가 "정하는" 것
• 연결 (가중치): 각 연결에는 신호를 키우거나 줄이는 가중치가 있어요

원리는 단순해요. 각 입력 뉴런이 값을 보내요. 연결 가중치가 곱해지고 다른 신호들에 더해져요. 결과가 일정 임계값(활성화 함수)을 넘으면 출력 뉴런이 켜져요.

Mario와 쥐 끝 비유에서요.

• 입력 뉴런 = Mario와 끝 사이 거리
• 연결 가중치 = Mario 민감도
• 출력 뉴런 = Mario가 소리를 지르거나 말거나

끝이 가까울수록 입력값이 커져요. 가중치가 강하면 출력 신호가 강하고, Mario가 소리를 질러요. 가중치를 바꾸면 Mario 민감도가 바뀌어요.

AI의 진짜 신경망에서는 같은 논리지만 규모가 달라요.

• 입력 뉴런 99개 (Mario 시야 11×9 타일)
• 출력 뉴런 8개 (A, B, X, Y, 위, 아래, 왼쪽, 오른쪽)
• 숨은 뉴런 (hidden) 사이에
• 가중치가 제각각인 수백 개 연결

---

NEAT: 모든 것을 바꾸는 알고리즘

고전 유전 알고리즘의 문제

유전 알고리즘과 신경망을 순진하게 합치면 문제가 있어요. 완전히 다른 신경망 100개를 만들고 비교할 방법을 몰라요. 각자 자기 뉴런과 연결, 가중치가 있어요. 두 네트워크가 "가까운지" "먼지" 어떻게 알까요?

거기에 NEAT가 와요. NeuroEvolution of Augmenting Topologies. Kenneth Stanley와 Risto Miikkulainen이 2002년에 발명했고, 바로 이 문제를 풀어요.

종

NEAT의 첫 핵심 구조는 종이에요. 신경망이 다른 것과 너무 달라지면 다른 종으로 분류돼요. 유사도는 세 매개변수로 계산돼요.

1. Excess (EXCES_COEF = 0.50): 두 네트워크 사이 아무 관계 없는 연결 수 (다른 혁신)
2. Disjoint: 마찬가지지만 중간에 있는 연결에 대해
3. 가중치 차이 (POIDSDIFF_COEF = 0.92): 같은 혁신을 공유하는 연결 사이 평균 가중치 차이

점수 공식:

score = (EXCES_COEF × disjoint) / max(nbConnexions1 + nbConnexions2, 1)
      + POIDSDIFF_COEF × diffPoids

이 점수가 DIFF_LIMITE(1.0)보다 작으면 두 네트워크는 같은 종이에요. 아니면 새 종을 만들어요.

혁신

NEAT의 천재성이에요. 연결이 만들어질 때마다 고유하고 전역적인 혁신 번호를 받아요. 이 번호는 번식해도 신경망을 따라다녀요.

구체적으로 아기가 교차로 만들어지면 부모의 혁신을 물려받아요. 두 네트워크가 같은 혁신을 공유하면 같은 조상에서 온 연결이 있다는 뜻이에요. 크기가 다른 네트워크를 비교할 수 있게 하는 것이 바로 이거예요.

교차

두 신경망이 번식하면 교차가 이렇게 동작해요.

1. 성능이 좋은 네트워크가 "우성 부모"가 돼요
2. 아기는 우성의 모든 연결을 물려받아요
3. 같은 혁신을 공유하는 각 연결마다 다른 부모가 대신할 수 있어요 (50퍼센트 확률)
4. 비우성 부모의 활성 연결만이 대신할 수 있어요

이렇게 하면 아기는 항상 최고 부모만큼은 좋아요.

변이

교차 뒤 아기는 설정 가능한 확률로 변이를 겪어요.

변이	확률	효과
연결 가중치 리셋	25%	가중치가 완전히 무작위돼요
가중치 변이	95%	가중치가 앞뒤 0.80씩 변해요
연결 추가	85%	아직 연결되지 않은 두 뉴런 사이 새 연결
뉴런 추가	39%	연결된 두 뉴런 사이에 숨은 뉴런 삽입

뉴런 추가율이 중요해요. 네트워크가 자라게 하는 것이 바로 이거예요. 처음에는 입력과 출력뿐이에요. 서서히 숨은 뉴런들이 나타나고 네트워크가 점점 복잡해져요.

---

코드: 전체 따라가기

상수

스크립트는 모든 매개변수를 정하는 상수 블록으로 시작해요.

-- Mario 주변 시야
TAILLE_TILE = 16
TAILLE_VUE_W = TAILLE_TILE * 11  -- 너비 176픽셀
TAILLE_VUE_H = TAILLE_TILE * 9   -- 높이 144픽셀
NB_TILE_W = TAILLE_VUE_W / TAILLE_TILE  -- 11타일
NB_TILE_H = TAILLE_VUE_H / TAILLE_TILE  -- 9타일

-- 신경망
NB_INPUT = NB_TILE_W * NB_TILE_H  -- 99개 입력 (보이는 타일)
NB_OUTPUT = 8  -- A, B, X, Y, Haut, Bas, Gauche, Droite
NB_INDIVIDU_POPULATION = 100  -- 집단당 개체
NB_NEURONE_MAX = 100000  -- 숨은 뉴런 한도

-- 적합도
FITNESS_LEVEL_FINI = 1000000  -- 레벨을 마치면 값
NB_FRAME_RESET_BASE = 33  -- 진전 없이 리셋까지 프레임
NB_FRAME_RESET_PROGRES = 300  -- 진전이 감지되면 프레임

-- 종
EXCES_COEF = 0.50
POIDSDIFF_COEF = 0.92
DIFF_LIMITE = 1.00

-- 변이
CHANCE_MUTATION_RESET_CONNEXION = 0.25
POIDS_CONNEXION_MUTATION_AJOUT = 0.80
CHANCE_MUTATION_POIDS = 0.95
CHANCE_MUTATION_CONNEXION = 0.85
CHANCE_MUTATION_NEURONE = 0.39

NB_INPUT이 99인 것은 Mario 시야가 11×9 타일이라서예요. 각 타일이 입력 뉴런 하나예요. 타일이 비었으면 0. 블록이면 1. 적이면 -1.

8개 출력은 SNES 패드 버튼에 해당해요. A, B, X, Y, 위, 아래, 왼쪽, 오른쪽. 결정을 핵심으로 한정하려고 Start, Select, L, R은 빼요.

자료구조

스크립트는 세 가지 주요 구조를 정해요.

function newNeurone()
    local neurone = {}
    neurone.valeur = 0    -- 현재 뉴런 값
    neurone.id = 0        -- 고유 식별자
    neurone.type = ""     -- "input", "output", 또는 "hidden"
    return neurone
end

function newConnexion()
    local connexion = {}
    connexion.entree = 0     -- 원천 뉴런 ID
    connexion.sortie = 0     -- 목적 뉴런 ID
    connexion.actif = true   -- 숨은 뉴런이 삽입되면 비활성화될 수 있어요
    connexion.poids = 0      -- 연결 가중치
    connexion.innovation = 0 -- 고유 혁신 번호
    connexion.allume = false -- 표시용: 신호가 지나가면 true
    return connexion
end

function newReseau()
    local reseau = {
        nbNeurone = 0,        -- 숨은 뉴런 수
        fitness = 1,          -- 성능 (간 거리)
        idEspeceParent = 0,   -- 어느 종에 속해요
        lesNeurones = {},     -- 뉴런 표
        lesConnexions = {}    -- 연결 표
    }
    -- 입력으로 초기화
    for j = 1, NB_INPUT, 1 do
        ajouterNeurone(reseau, j, "input", 1)
    end
    -- 다음 출력
    for j = NB_INPUT + 1, NB_INPUT + NB_OUTPUT, 1 do
        ajouterNeurone(reseau, j, "output", 0)
    end
    return reseau
end

처음에 각 네트워크는 입력과 출력만 있어요. 숨은 뉴런도 연결도 없어요. 필요한지 정하는 것이 알고리즘이에요.

변이 자세히

가중치 변이

function mutationPoidsConnexions(unReseau)
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            if math.random() < CHANCE_MUTATION_RESET_CONNEXION then
                -- 25% : 가중치 완전 리셋
                unReseau.lesConnexions[i].poids = genererPoids()
            else
                -- 75% : 앞뒤 0.80씩 변동
                if math.random() >= 0.5 then
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids - POIDS_CONNEXION_MUTATION_AJOUT
                else
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids + POIDS_CONNEXION_MUTATION_AJOUT
                end
            end
        end
    end
end

초기 가중치는 항상 1 또는 -1(genererPoids()). 앞뒤 0.80 변동이 음수와 양수 사이를 오가게 해서 네트워크 행동을 근본적으로 바꿔요.

연결 추가

function mutationAjouterConnexion(unReseau)
    local liste = {}
    -- 뉴런 목록 무작위화
    for i, v in ipairs(unReseau.lesNeurones) do
        local pos = math.random(1, #liste+1)
        table.insert(liste, pos, v)
    end

    local traitement = false
    for i = 1, #liste, 1 do
        for j = 1, #liste, 1 do
            if i ~= j then
                local n1 = liste[i]
                local n2 = liste[j]
                -- 유효 연결: input→output, hidden→hidden, hidden→output
                if (n1.type == "input" and n2.type == "output") or
                   (n1.type == "hidden" and n2.type == "hidden") or
                   (n1.type == "hidden" and n2.type == "output") then
                    -- 이미 연결이 있는지 확인
                    local dejaConnexion = false
                    for k = 1, #unReseau.lesConnexions, 1 do
                        if unReseau.lesConnexions[k].entree == n1.id
                            and unReseau.lesConnexions[k].sortie == n2.id then
                            dejaConnexion = true
                            break
                        end
                    end
                    if dejaConnexion == false then
                        traitement = true
                        ajouterConnexion(unReseau, n1.id, n2.id)
                    end
                end
            end
            if traitement then break end
        end
        if traitement then break end
    end
end

출력을 입력에 연결할 수 없어요 (사이클이 생겨요). 이미 연결된 두 뉴런도 연결할 수 없어요. 무작위화가 매번 다른 가능성을 탐색하도록 보장해요.

뉴런 추가

가장 흥미로운 변이예요.

function mutationAjouterNeurone(unReseau)
    if #unReseau.lesConnexions == 0 then return nil end
    if unReseau.nbNeurone == NB_NEURONE_MAX then return nil end

    -- 연결 무작위화
    local listeRandom = {}
    for i = 1, #unReseau.lesConnexions, 1 do
        local pos = math.random(1, #listeRandom+1)
        table.insert(listeRandom, pos, i)
    end

    for i = 1, #listeRandom, 1 do
        if unReseau.lesConnexions[listeRandom[i]].actif then
            -- 기존 연결 비활성화
            unReseau.lesConnexions[listeRandom[i]].actif = false
            unReseau.nbNeurone = unReseau.nbNeurone + 1
            local indice = unReseau.nbNeurone + NB_INPUT + NB_OUTPUT

            -- 숨은 뉴런 만들기
            ajouterNeurone(unReseau, indice, "hidden", 1)

            -- 입력을 숨은 뉴런에 연결
            ajouterConnexion(unReseau,
                unReseau.lesConnexions[listeRandom[i]].entree,
                indice, genererPoids())

            -- 숨은 뉴런을 출력에 연결
            ajouterConnexion(unReseau,
                indice,
                unReseau.lesConnexions[listeRandom[i]].sortie,
                genererPoids())
            break
        end
    end
end

구조: 기존 연결 하나를 가져와 비활성화하고, 중간에 숨은 뉴런을 끼워요. 원래 연결이 두 새 연결로 바뀌어요. 입력에서 숨은, 숨은에서 출력. 전선을 잘라서 스위치를 끼우는 것과 같아요.

NEAT가 "augmenting topologies"인 이유가 바로 이거예요. 네트워크가 시간과 함께 자라요. 단순하게 시작해서 필요할 때만 복잡해져요.

피드포워드

네트워크에 신호를 전파하는 함수예요.

function feedForward(unReseau)
    -- 출력 뉴런 리셋
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur = 0
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].allume = false
        end
    end

    -- 전파
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local avantTraitement = unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur =
                unReseau.lesNeurones[unReseau.lesConnexions[i].entree].valeur *
                unReseau.lesConnexions[i].poids +
                unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur

            if avantTraitement ~= unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur then
                unReseau.lesConnexions[i].allume = true
            else
                unReseau.lesConnexions[i].allume = false
            end
        end
    end
end

각 활성 연결이 입력값 × 가중치를 출력 뉴런으로 보내요. 값은 누적(덧셈)돼요. allume 깃발은 네트워크 시각 표시용일 뿐이에요.

게임 메모리 읽기

getLesInputs() 함수는 Super Mario World 세상을 네트워크가 이해하는 자료로 바꿔요.

function getLesInputs()
    local lesInputs = {}
    -- 0으로 초기화 (회색 = 없음)
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            lesInputs[getIndiceLesInputs(i, j)] = 0
        end
    end

    -- 스프라이트(적) = -1 (검정)
    local lesSprites = getLesSprites()
    for i = 1, #lesSprites, 1 do
        local input = convertirPositionPourInput(getLesSprites()[i])
        if input.x > 0 and input.x < (TAILLE_VUE_W / TAILLE_TILE) + 1 then
            lesInputs[getIndiceLesInputs(input.x, input.y)] = -1
        end
    end

    -- 타일(블록) = 타일 값 (0보다 크면 흰색)
    local lesTiles = getLesTiles()
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local indice = getIndiceLesInputs(i, j)
            if lesTiles[indice] ~= 0 then
                lesInputs[indice] = lesTiles[indice]
            end
        end
    end

    return lesInputs
end

입력 격자는 Mario 중심 시야예요. 너비 11타일, 높이 9타일. 각 타일 값은요.

• 0 (회색): 없음
• 1 (흰색): 고체 블록
• -1 (검정): 적

적은 RAM의 두 목록에서 읽어요. 일반 스프라이트(0x14C8-0x14F8)와 확장 스프라이트(0x170B-0x173B). 살아 있는 각 스프라이트(상태 > 7)마다 Mario 기준 타일 위치를 계산하고 해당 칸에 -1을 넣어요.

적합도: AI가 진전하는지 아는 방법

function majReseau(unReseau, marioBase)
    local mario = getPositionMario()

    if not niveauFini and memory.readbyte(0x0100) == 12 then
        -- 레벨 끝!
        unReseau.fitness = FITNESS_LEVEL_FINI
        niveauFini = true
    elseif marioBase.x < mario.x then
        -- Mario가 오른쪽으로 가요
        unReseau.fitness = unReseau.fitness + (mario.x - marioBase.x)
        marioBase.x = mario.x
    end

    -- 입력 고치기
    local lesInputs = getLesInputs()
    for i = 1, NB_INPUT, 1 do
        unReseau.lesNeurones[i].valeur = lesInputs[i]
    end
end

적합도는 단순해요. 오른쪽으로 간 거리예요. Mario가 10픽셀 가면 적합도가 10 올라가요. 뒤로 가면 아무 일도 없어요 (벌점 없어요). 레벨이 끝나면(주소 0x0100 == 12) 적합도가 1,000,000이 돼요.

일부러 단순해요. 오른쪽으로 가는 진전만이 중요해요. 적을 죽여도 아무것도 없고 죽어도 잃는 것 없어요.

영리한 리셋

Mario가 33프레임 동안 움직이지 않으면 레벨을 리셋하고 다음 개체로 넘어가요. 하지만 Mario가 진전했으면(현재 적합도가 시작 때와 다르면) 300프레임 기다려요. 네트워크가 잘한 것을 "이해"할 기회를 주는 거예요.

if fitnessAvant == laPopulation[idPopulation].fitness
   and memory.readbyte(0x13D4) == 0 then
    nbFrameStop = nbFrameStop + 1
    local nbFrameReset = NB_FRAME_RESET_BASE
    if fitnessInit ~= laPopulation[idPopulation].fitness
       and memory.readbyte(0x0071) ~= 9 then
        nbFrameReset = NB_FRAME_RESET_PROGRES
    end
    if nbFrameStop > nbFrameReset then
        nbFrameStop = 0
        lancerNiveau()
        idPopulation = idPopulation + 1
        -- ...
    end
end

memory.readbyte(0x0071) ~= 9 조건은 Mario가 죽음 애니메이션 중이 아닌지 확인해요. Mario가 이미 죽음 애니메이션 중이면 리셋이 소용없어져요.

주 루프

루프는 30fps(Super Mario World 정상 속도)로 돌아요.

while true do
    local fitnessAvant = laPopulation[idPopulation].fitness

    -- 표시 (네트워크, 정보)
    if forms.ischecked(estAccelere) then
        emu.limitframerate(false)  -- 빠르게
    else
        emu.limitframerate(true)   -- 30fps
    end

    -- 3개 생명 함수
    majReseau(laPopulation[idPopulation], marioBase)
    feedForward(laPopulation[idPopulation])
    appliquerLesBoutons(laPopulation[idPopulation])

    emu.frameadvance()
    nbFrame = nbFrame + 1

    -- 진전 없으면 리셋
    -- ...
    -- 모든 개체를 테스트하면 새 세대
    -- ...
end

세 생명 함수는 majReseau, feedForward, appliquerLesBoutons예요. 하나만 꺼도 Mario가 더 이상 움직이지 않아요.

교차

function crossover(unReseau1, unReseau2)
    local leReseau = newReseau()
    local leBon = unReseau1
    local leNul = unReseau2

    if leBon.fitness < leNul.fitness then
        leBon = unReseau2
        leNul = unReseau1
    end

    leReseau = copier(leBon)

    for i = 1, #leReseau.lesConnexions, 1 do
        for j = 1, #leNul.lesConnexions, 1 do
            if leReseau.lesConnexions[i].innovation == leNul.lesConnexions[j].innovation
               and leNul.lesConnexions[j].actif then
                if math.random() > 0.5 then
                    leReseau.lesConnexions[i] = leNul.lesConnexions[j]
                end
            end
        end
    end
    leReseau.fitness = 1
    return leReseau
end

아기는 좋은 부모를 물려받아요. 같은 혁신을 공유하는 각 연결마다 다른 부모가 50퍼센트 확률로 대신해요. 하지만 연결이 활성일 때만이요. 중요한 수정이에요. 이것이 없으면 쓸모없는 숨은 뉴런이 만들어질 수 있었어요.

종별 선택

function nouvelleGeneration(laPopulation, lesEspeces)
    local laNouvellePopulation = newPopulation()
    local nbIndividuACreer = NB_INDIVIDU_POPULATION

    -- 종별 평균 적합도 계산
    for i = 1, #lesEspeces, 1 do
        lesEspeces[i].fitnessMoyenne = 0
        for j = 1, #lesEspeces[i].lesReseaux, 1 do
            lesEspeces[i].fitnessMoyenne =
                lesEspeces[i].fitnessMoyenne + lesEspeces[i].lesReseaux[j].fitness
        end
        lesEspeces[i].fitnessMoyenne =
            lesEspeces[i].fitnessMoyenne / #lesEspeces[i].lesReseaux
    end

    -- 각 종은 평균 적합도에 비례해 아이를 만들어요
    for i = 1, #lesEspeces, 1 do
        local nbEnfant = math.ceil(
            #lesEspeces[i].lesReseaux *
            lesEspeces[i].fitnessMoyenne / fitnessMoyenneGlobal)

        for j = 1, nbEnfant, 1 do
            local unReseau = crossover(
                choisirParent(lesEspeces[i].lesReseaux),
                choisirParent(lesEspeces[i].lesReseaux))
            mutation(unReseau)
            laNouvellePopulation[indiceNouvelleEspece] = copier(unReseau)
        end
    end
end

생각: 평균 적합도 10,000인 종은 평균 1인 종보다 훨씬 많은 아이를 만들 권리가 있어요. 동작 중인 자연 선택이에요.

choisirParent는 룰렛 선택을 써요. 적합도가 높은 개체일수록 부모로 뽑힐 확률이 높아요.

저장과 불러오기

집단은 .pop 파일에 저장돼요.

function sauvegarderUnReseau(unReseau, fichier)
    io.write(unReseau.nbNeurone .. "\n")
    io.write(#unReseau.lesConnexions .. "\n")
    io.write(unReseau.fitness .. "\n")
    for i = 1, unReseau.nbNeurone, 1 do
        local indice = NB_INPUT + NB_OUTPUT + i
        io.write(unReseau.lesNeurones[indice].id .. "\n")
    end
    for i = 1, #unReseau.lesConnexions, 1 do
        local actif = 1
        if unReseau.lesConnexions[i].actif ~= true then actif = 0 end
        io.write(actif .. "\n" ..
            unReseau.lesConnexions[i].entree .. "\n" ..
            unReseau.lesConnexions[i].sortie .. "\n" ..
            unReseau.lesConnexions[i].poids .. "\n" ..
            unReseau.lesConnexions[i].innovation .. "\n")
    end
end

저장에는 이전 모든 집단 중 최고 개체도 포함돼요. 옛 집단 최고가 새 집단 최고보다 좋으면 옛 것을 토대로 다시 시작해요. 일종의 엘리트주의예요. 최고를 절대 잃지 않아요.

네트워크 그리기

Laupok은 게임 위에 신경망 시각화를 더했어요.

function dessinerUnReseau(unReseau)
    -- 입력: Mario 주변 11×9 격자
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local xT = ENCRAGE_X_INPUT + (i - 1) * TAILLE_INPUT
            local yT = ENCRAGE_Y_INPUT + (j - 1) * TAILLE_INPUT
            local couleurFond = "gray"
            if unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur < 0 then
                couleurFond = "black"   -- 적
            elseif unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur > 0 then
                couleurFond = "white"   -- 블록
            end
            gui.drawRectangle(xT, yT, TAILLE_INPUT, TAILLE_INPUT, "black", couleurFond)
        end
    end

    -- 출력: 8개 버튼
    for i = 1, NB_OUTPUT, 1 do
        local xT = ENCRAGE_X_OUTPUT
        local yT = ENCRAGE_Y_OUTPUT + ESPACE_Y_OUTPUT * (i - 1)
        if sigmoid(unReseau.lesNeurones[i + NB_INPUT].valeur) then
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "white")
        else
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "black")
        end
    end

    -- 연결
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local alpha = 25
            if unReseau.lesConnexions[i].allume then alpha = 255 end
            local couleur = forms.createcolor(255, 255, 255, alpha)
            gui.drawLine(
                lesPositions[unReseau.lesConnexions[i].entree].x,
                lesPositions[lesConnexions[i].entree].y,
                lesPositions[unReseau.lesConnexions[i].sortie].x,
                lesPositions[lesConnexions[i].sortie].y,
                couleur)
        end
    end
end

네트워크가 무엇을 하는지 이해하는 데 아주 유용해요. 활성 연결은 흰색, 비활성은 반투명. 입력은 흰색과 검정, 회색 칸 격자. 출력은 어떤 버튼이 눌렸는지 보여줘요.

---

결과

AI가 배운 것

실행 몇 시간(그리고 며칠)이 지나면서 AI는 혼자 발견했어요.

1. 오른쪽으로 가기: 가장 기본 행동이지만 오른쪽 버튼을 누르고 있어야 해요
2. 적 위로 점프하기: "적 감지" 입력을 A나 B 버튼에 연결해서
3. 장애물 피하기: 어떤 네트워크는 더 잘 가려고 잠시 뒤로 가는 법을 배웠어요
4. 레벨 끝내기: 최고 개체가 Super Mario World 첫 레벨을 마칠 수 있었어요

한계

프로젝트의 한계예요.

• 단일 레벨: AI는 특정 레벨 하나로 훈련돼요. 다른 레벨로 자동으로 일반화하지 않아요
• 훈련 시간: 만족스러운 결과에 수십 시간이 필요해요
• 이해 없음: AI는 무엇을 하는지 "이해"하지 않아요. 무작위 변이로 적합도 함수(간 거리)를 최적화해요
• T-배깅: Mario가 적을 보면 제자리 점프하는 경향이 있다고 Laupok은 적어요. 점프하면서 조금 가서 적합도가 올라가니까요

---

실험 재현 방법

Laupok이 전부 공유했어요. 단계는 이렇습니다.

1. tasvideos.org에서 BizHawk 다운로드 (Download 섹션)
2. Super Mario World USA 롬 구하기 (자기 카트리지의 사적 복사)
3. Pastebin에서 Lua 스크립트 다운로드. mario.lua로 이름 바꾸기
4. 롬과 같은 폴더에 스크립트 두기
5. BizHawk 실행, 롬 열기
6. Lua 콘솔에서: dofile("mario.lua") 또는 메뉴 Script > Open Script
7. 레벨 시작 지점에 세이브 스테이트 저장 (메뉴 Savestate > Save State). debut.state라고 이름 짓기
8. 스크립트 다시 실행. 돼요

스크립트에 옵션 폼이 들어 있어요.

• 가속: 30fps 한도를 꺼서 더 빠르게
• 네트워크 표시: 신경망을 오버레이로 보여줘요
• 정보 표시: 세대와 적합도, 종 수를 담은 배너를 보여줘요
• 일시정지: 실행을 멈춰요
• 저장과 불러오기: 현재 집단을 .pop 파일에 저장해요

---

출처와 참고

자료	링크
Laupok 주 영상	j'ai créé une IA qui joue à mario toute seule
코드 리뷰와 설정 영상	comment setup l'ia + code source review
완전한 소스 코드	Pastebin Jcvdqhqm
NEAT 원본 논문	Stanley & Miikkulainen, "Evolving Neural Networks through Augmenting Topologies", 2002
N8Programs 튜토리얼	NEAT implementation walkthrough (JavaScript지만 개념은 같아요)
16blings (Laupok 영감)	AI plays Super Mario World
BizHawk	tasvideos.org/BizHawk
Super Mario World 메모리	SMW Central - RAM Map

---

결론

Laupok이 한 것은 학술 알고리즘(NEAT, 2002년)을 가져와 에뮬레이터(BizHawk)용 Lua로 다시 쓰고 Super Mario World에 적용한 거예요. 결과: 사전 지식 없이 0에서 게임하는 법을 배우는 AI. 무작위 변이와 자연 선택만으로요.

유전 알고리즘의 힘을 보여주는 아름다운 예예요. 레시피는 세 재료예요. 자연 선택, Lua 조금, 인내 많이. 딥러닝도 없고, GPU도 없고, 대규모 훈련 자료도 없어요.

코드는 주석이 있고, 공유되고, Laupok이 설명 영상 둘을 만들었어요. 큰 개념용 하나, 코드용 하나. 주제에 관심 있으면 뛰어들어 보세요. 보기보다 쉬워요.

Laupok kendi kendine Super Mario World oynayan bir yapay zekâ yarattı, nasıl çalışıyor

Laupok Super Mario World oyununu tamamen özerk oynayan bir yapay zekâ yarattı. Sıfırdan başlar: önceden tanımlı script yok, kaydedilmiş kare yok. Yapay zekâ rastgele mutasyonlar ve doğal seçilim darbeleriyle oyunun seviyelerini bitirmeyi kendi kendine öğrenir. Proje çok platformlu bir emülatör olan BizHawk üzerinde yaklaşık 4200 satırlık bir Lua scriptiyle döner.

Bu projeyi büyüleyici yapan şey biyolojik kavramların bilişime uygulanmasına dayanmasıdır: Darwinin evrim teorisi, yapay sinir ağları ve hepsinden önemlisi NEAT (NeuroEvolution of Augmenting Topologies) adlı belirli bir algoritma. Yapay zekâ başlangıçta oyun hakkında hiçbir şey bilmez. Rastgele aksiyonları test eder, binlerce kez başarısız olur ve yavaş yavaş ilerlemeyi, zıplamayı ve hayatta kalmayı anlar.

Bu makalede bütün bunları didikleyeceğiz: kavram kavram, kod satırı kod satırı.

---

Kurulum: BizHawk, Lua ve Super Mario World

BizHawk emülatörü

BizHawk bir sürü konsolu destekleyen açık kaynak bir emülatördür: NES, SNES, Genesis, PS1, Game Boy ve daha niceleri. Özelliği oyunla paralel Lua scriptleri çalıştırmaya izin vermesidir. Bu scriptler emülasyonun RAM belleğine erişir, yani oyunun herhangi bir verisini gerçek zamanlı okuyabilir ve değiştirebilir.

Somut olarak bu şu demektir:

• Seviyede Marionun konumu okunabilir
• Ekranda hangi spriteların (düşmanlar, eşyalar) olduğu bilinebilir
• Mario etrafındaki her karenin (blok) durumu bilinebilir
• Gamepad kontrol edilebilir: herhangi bir düğmeye basılabilir

Bir yapay zekâyı oynatmak için gereken tam olarak budur.

Super Mario World bellek adresleri

Super Mario World RAMinde her veri belirli bir adreste saklanır. Biraz mahalle gibidir: her adres bir bilgi içeren bir "eve" karşılık gelir. Örneğin:

Adres	Veri
0x94-0x95	Marionun X konumu (16 bit, little-endian)
0x96-0x97	Marionun Y konumu
0x14C8+i	i spritının durumu (>7 = canlı)
0xE4+i	i spritının düşük X konumu
0x14E0+i	i spritının yüksek X konumu
0xD8+i	i spritının düşük Y konumu
0x14D4+i	i spritının yüksek Y konumu
0x170B+i	i genişletilmiş spritının türü
0x0100	Oyun durumu (12 = seviye bitti)
0x13D4	Duraklatma aktif
0x0071	Marionun ölüm animasyonu (9 = ölü)
0x1C800+...	Seviyenin kare tablosu

Spriteların konumu iki bayt kullanır: bir "düşük" bayt ve bir "yüksek" bayt, çünkü konum 255 pikseli aşabilir. Formül hep düşük + yüksek × 256 şeklindedir.

Kareler için daha karmaşıktır: taban adres 0x1C800dür ve ofset dünyada karenin x ve y koordinatlarına göre, kare başına 16 piksel adımla hesaplanır.

---

Temeller: genetik algoritmalar ve sinir ağları

Koda dalmadan önce iki temel kavramı anlamak gerekir. Onlar olmadan gerisi anlamsızdır.

Genetik algoritmalar

Bir genetik algoritma evrim teorisinin bir simülasyonudur. Merkez fikir: her biri biraz farklı özellikli ("gen") popülasyon yaratılır. Bir ortamda "yaşatılır". En iyi idare edenler hayatta kalır ve ürer. Kötü idare edenler kaybolur.

Laupok bunu bir Kirby benzetmesiyle gösterir:

• Dikenler ve domateslerle bir arazide bir Kirby popülasyonu belirir
• Dikenler can puanı götürür, domatesler geri verir
• Her Kirbynin genleri vardır: boyut, hız, can puanı, davranış (kaçmak, domates aramak, her yere dalmak)

• 15 saniye sonra kimin en uzun hayatta kaldığına bakılır
• En iyi Kirby diğerleriyle ürer: bebekler en iyinin genlerinin yarısını ve "en kötünün" yarısını kalıtır
• Bebekler rastgele mutasyonlara uğrar (biraz daha büyük, biraz daha hızlı...)
• Eski Kirbyler yenileriyle değiştirilir
• Yeniden başlatılır

180 nesil (~15 saat) sonra Kirbyler 15 saniyelik hayatta kalmadan 15 dakikaya geçer. Küçüldüler (azalmış çarpışma bölgesi), hızlandılar ve tehlikeden sürekli kaçarlar.

Kritik nokta: çözümü tanımlamayız. Algoritma onu kendi kendine bulur. Ve onu hangi parametre kombinasyonunun optimal olacağını bilmediğimiz problemler için güçlü yapan tam olarak budur.

Yapay sinir ağları

Bir sinir ağı insan beyninin basitleştirilmiş matematiksel bir modelidir. Şunlardan oluşur:

• Girdi nöronları (inputs): ağın "gördüğü"
• Çıktı nöronları (outputs): ağın "karar verdiği"
• Bağlantılar (ağırlıklar): her bağlantının sinyali güçlendiren ya da zayıflatan bir ağırlığı vardır

İlke basittir: her girdi nöronu değerini gönderir. Bağlantının ağırlığıyla çarpılır, sonra diğer sinyallerle toplanır. Sonuç belli bir eşiği aşarsa (aktivasyon fonksiyonu) çıktı nöronu etkinleşir.

Mario ve farenin ucuyla Laupok benzetmesinde:

• Girdi nöronu = Mario ile uç arasındaki mesafe
• Bağlantının ağırlığı = Marionun hassasiyeti
• Çıktı nöronu = Mario bağırır ya da bağırmaz

Uç ne kadar yakınsa girdi değeri o kadar yüksek olur. Ağırlık güçlüyse çıktıya gönderilen sinyal güçlüdür ve Mario bağırırdı. Ağırlığı değiştirerek Marionun hassasiyeti değiştirilir.

Yapay zekânın gerçek sinir ağında aynı mantıktır ama devasa ölçekte:

• 99 girdi nöronu (Marionun görüşünün 11×9 karesi)
• 8 çıktı nöronu (A, B, X, Y, Yukarı, Aşağı, Sol, Sağ)
• Arada gizli nöronlar (hidden)
• Çeşitli ağırlıklı yüzlerce bağlantı

---

NEAT: her şeyi değiştiren algoritma

Klasik genetik algoritmaların sorunu

Bir genetik algoritmayı naif şekilde bir sinir ağıyla birleştirirsek bir sorunumuz olur: tamamen farklı 100 sinir ağı yaratırız ve onları karşılaştırmayı bilmeyiz. Her birinin kendi nöronları, kendi bağlantıları, kendi ağırlıkları vardır. İki ağın "yakın" mı "uzak" mı olduğu nereden bilinir?

NEAT: NeuroEvolution of Augmenting Topologies devreye girdiği yer burasıdır. 2002de Kenneth Stanley ve Risto Miikkulainen tarafından icat edilmiş, tam bu sorunu çözen bir algoritmadır.

Türler

NEATin ilk kilit mekanizması türlerdir. Bir sinir ağı diğerinden çok farklılaştığında farklı bir türe sınıflanır. Benzerlik üç parametreyle hesaplanır:

1. Excess (EXCES_COEF = 0.50): iki ağ arasında hiç ilişkisi olmayan bağlantıların sayısı (farklı inovasyonlar)
2. Disjoint: aynısı ama ortada yer alan bağlantılar için
3. Ağırlık farkı (POIDSDIFF_COEF = 0.92): aynı inovasyonu paylaşan bağlantılar arasındaki ortalama ağırlık farkı

Skor formülü:

score = (EXCES_COEF × disjoint) / max(nbConnexions1 + nbConnexions2, 1)
      + POIDSDIFF_COEF × diffPoids

Bu skor DIFF_LIMITE (1.0) değerinden düşükse iki ağ aynı türdedir. Yoksa yeni bir tür oluşturulur.

İnovasyonlar

NEATin dehası budur. Bir bağlantı her oluşturulduğunda benzersiz ve global bir inovasyon numarası alır. Bu numara sinir ağını ürediğinde bile izler.

Somut olarak çaprazlamayla bir bebek yaratıldığında ebeveynlerinin inovasyonlarını kalıtır. İki ağ aynı inovasyonu paylaşıyorsa aynı atadan gelen bir bağlantıları olduğu demektir. Farklı boyutlardaki ağları karşılaştırmaya izin veren budur.

Çaprazlama

İki sinir ağı ürediğinde çaprazlama şöyle çalışır:

1. En performanslı ağ "baskın ebeveyn" olur
2. Bebek baskının tüm bağlantılarını kalıtır
3. Aynı inovasyonu paylaşan her bağlantı için diğer ebeveyn onun yerine geçebilir (%50 şans)
4. Yalnızca baskın olmayanın aktif bağlantıları yer değiştirebilir

Bu bebeğin hep en iyi ebeveyn kadar iyi olmasını garanti eder.

Mutasyonlar

Çaprazlamadan sonra bebek yapılandırılabilir olasılıklarla mutasyonlara uğrar:

Mutasyon	Olasılık	Etki
Bağlantı ağırlığı sıfırlama	%25	Ağırlık tamamen rastgelelenir
Ağırlık mutasyonu	%95	Ağırlık ±0,80 değişir
Bağlantı ekleme	%85	Henüz bağlı olmayan iki nöron arasında yeni bağlantı
Nöron ekleme	%39	Bağlı iki nöron arasına gizli bir nöron yerleştirilir

Nöron ekleme hızı önemlidir: ağın büyümesine izin veren budur. Başlangıçta yalnızca girdiler ve çıktılar vardır. Yavaş yavaş gizli nöronlar belirir, ağı gittikçe karmaşıklaştırır.

---

Kod: eksiksiz izlenecek yol

Sabitler

Script her şeyi tanımlayan bir sabit bloğuyla başlar:

-- Marionun etrafındaki görüşü
TAILLE_TILE = 16
TAILLE_VUE_W = TAILLE_TILE * 11  -- genişlikte 176 piksel
TAILLE_VUE_H = TAILLE_TILE * 9   -- yükseklikte 144 piksel
NB_TILE_W = TAILLE_VUE_W / TAILLE_TILE  -- 11 kare
NB_TILE_H = TAILLE_VUE_H / TAILLE_TILE  -- 9 kare

-- Sinir ağı
NB_INPUT = NB_TILE_W * NB_TILE_H  -- 99 girdi (görünür kareler)
NB_OUTPUT = 8  -- A, B, X, Y, Yukarı, Aşağı, Sol, Sağ
NB_INDIVIDU_POPULATION = 100  -- popülasyon başına birey
NB_NEURONE_MAX = 100000  -- gizli nöron limiti

-- Fitness
FITNESS_LEVEL_FINI = 1000000  -- seviye bitince değer
NB_FRAME_RESET_BASE = 33  -- ilerlemesiz sıfırlamadan önce kareler
NB_FRAME_RESET_PROGRES = 300  -- ilerleme tespit edilirse kareler

-- Türler
EXCES_COEF = 0.50
POIDSDIFF_COEF = 0.92
DIFF_LIMITE = 1.00

-- Mutasyonlar
CHANCE_MUTATION_RESET_CONNEXION = 0.25
POIDS_CONNEXION_MUTATION_AJOUT = 0.80
CHANCE_MUTATION_POIDS = 0.95
CHANCE_MUTATION_CONNEXION = 0.85
CHANCE_MUTATION_NEURONE = 0.39

NB_INPUT 99dur çünkü Marionun görüşü 11×9 karedir. Her kare bir girdi nöronudur. Kare boşsa 0 değerindedir. Blურვasa 1 değerindedir. Düşmansa -1 değerindedir.

8 çıktı SNES gamepad düğmelerine karşılık gelir: A, B, X, Y, Yukarı, Aşağı, Sol, Sağ. Kararlarını özle sınırlamak için Start, Select, L ve R hariç tutulur.

Veri yapıları

Script üç ana yapı tanımlar:

function newNeurone()
    local neurone = {}
    neurone.valeur = 0    -- nöronun mevcut değeri
    neurone.id = 0        -- benzersiz tanımlayıcı
    neurone.type = ""     -- "input", "output" ya da "hidden"
    return neurone
end

function newConnexion()
    local connexion = {}
    connexion.entree = 0     -- kaynak nöronun IDsi
    connexion.sortie = 0     -- hedef nöronun IDsi
    connexion.actif = true   -- gizli bir nöron yerleştirilirse devre dışı kalabilir
    connexion.poids = 0      -- bağlantının ağırlığı
    connexion.innovation = 0 -- benzersiz inovasyon numarası
    connexion.allume = false -- görüntü için: sinyal geçerse true
    return connexion
end

function newReseau()
    local reseau = {
        nbNeurone = 0,        -- gizli nöron sayısı
        fitness = 1,          -- performans (kat edilen mesafe)
        idEspeceParent = 0,   -- hangi türe ait
        lesNeurones = {},     -- nöron dizisi
        lesConnexions = {}    -- bağlantı dizisi
    }
    -- Girdilerle başlatma
    for j = 1, NB_INPUT, 1 do
        ajouterNeurone(reseau, j, "input", 1)
    end
    -- Sonra çıktılar
    for j = NB_INPUT + 1, NB_INPUT + NB_OUTPUT, 1 do
        ajouterNeurone(reseau, j, "output", 0)
    end
    return reseau
end

Başlangıçta her ağ yalnızca girdiler ve çıktılar içerir: gizli nöron yok, bağlantı yok. Gerekip gerekmediğine algoritma karar verecektir.

Mutasyonlar ayrıntılı

Ağırlık mutasyonu

function mutationPoidsConnexions(unReseau)
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            if math.random() < CHANCE_MUTATION_RESET_CONNEXION then
                -- 25% : ağırlığın toplam sıfırlanması
                unReseau.lesConnexions[i].poids = genererPoids()
            else
                -- 75% : ±0.80 değişim
                if math.random() >= 0.5 then
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids - POIDS_CONNEXION_MUTATION_AJOUT
                else
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids + POIDS_CONNEXION_MUTATION_AJOUT
                end
            end
        end
    end
end

Başlangıç ağırlığı hep 1 ya da -1dir (genererPoids()). ±0,80 değişim onu negatif ve pozitif değerler arasında salındırabilir, bu da ağın davranışını kökten değiştirir.

Bağlantı ekleme

function mutationAjouterConnexion(unReseau)
    local liste = {}
    -- Nöron listesinin rastgelelenmesi
    for i, v in ipairs(unReseau.lesNeurones) do
        local pos = math.random(1, #liste+1)
        table.insert(liste, pos, v)
    end

    local traitement = false
    for i = 1, #liste, 1 do
        for j = 1, #liste, 1 do
            if i ~= j then
                local n1 = liste[i]
                local n2 = liste[j]
                -- Geçerli bağlantı: input→output, hidden→hidden, hidden→output
                if (n1.type == "input" and n2.type == "output") or
                   (n1.type == "hidden" and n2.type == "hidden") or
                   (n1.type == "hidden" and n2.type == "output") then
                    -- Zaten bir bağlantı olmadığını doğrula
                    local dejaConnexion = false
                    for k = 1, #unReseau.lesConnexions, 1 do
                        if unReseau.lesConnexions[k].entree == n1.id
                            and unReseau.lesConnexions[k].sortie == n2.id then
                            dejaConnexion = true
                            break
                        end
                    end
                    if dejaConnexion == false then
                        traitement = true
                        ajouterConnexion(unReseau, n1.id, n2.id)
                    end
                end
            end
            if traitement then break end
        end
        if traitement then break end
    end
end

Bir output bir inputa bağlanamaz (döngü yaratırdı) ve zaten bağlı iki nöron bağlanamaz. Rastgeleleme her seferinde farklı olasılıkları keşfetmeyi garanti eder.

Nöron ekleme

En ilginç mutasyon budur:

function mutationAjouterNeurone(unReseau)
    if #unReseau.lesConnexions == 0 then return nil end
    if unReseau.nbNeurone == NB_NEURONE_MAX then return nil end

    -- Bağlantıların rastgelelenmesi
    local listeRandom = {}
    for i = 1, #unReseau.lesConnexions, 1 do
        local pos = math.random(1, #listeRandom+1)
        table.insert(listeRandom, pos, i)
    end

    for i = 1, #listeRandom, 1 do
        if unReseau.lesConnexions[listeRandom[i]].actif then
            -- Mevcut bağlantıyı devre dışı bırak
            unReseau.lesConnexions[listeRandom[i]].actif = false
            unReseau.nbNeurone = unReseau.nbNeurone + 1
            local indice = unReseau.nbNeurone + NB_INPUT + NB_OUTPUT

            -- Gizli nöronu oluştur
            ajouterNeurone(unReseau, indice, "hidden", 1)

            -- Girdiyi gizli nörona bağla
            ajouterConnexion(unReseau,
                unReseau.lesConnexions[listeRandom[i]].entree,
                indice, genererPoids())

            -- Gizli nöronu çıktıya bağla
            ajouterConnexion(unReseau,
                indice,
                unReseau.lesConnexions[listeRandom[i]].sortie,
                genererPoids())
            break
        end
    end
end

Mekanizma: mevcut bir bağlantı alınır, devre dışı bırakılır ve ortaya gizli bir nöron yerleştirilir. Orijinal bağlantı iki yeni bağlantıyla değiştirilir: girdi→gizli ve gizli→çıktı. Bu araya bir anahtar sokmak için bir teli "kesmek" gibidir.

NEATi "augmenting topologies" yapan budur: ağ zamanla büyür. Basit başlar ve yalnızca gerekirse karmaşıklaşır.

feedForward

Sinyalleri ağda yayan fonksiyondur:

function feedForward(unReseau)
    -- Çıktı nöronlarının sıfırlanması
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur = 0
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].allume = false
        end
    end

    -- Yayılım
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local avantTraitement = unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur =
                unReseau.lesNeurones[unReseau.lesConnexions[i].entree].valeur *
                unReseau.lesConnexions[i].poids +
                unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur

            if avantTraitement ~= unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur then
                unReseau.lesConnexions[i].allume = true
            else
                unReseau.lesConnexions[i].allume = false
            end
        end
    end
end

Her aktif bağlantı girdi_değeri × ağırlık değerini çıktı nöronuna gönderir. Değer birikimlidir (toplanır). allume bayrağı sadece ağın görsel gösterimi içindir.

Oyun belleğinin okunması

getLesInputs() fonksiyonu Super Mario World dünyasını ağın anlayabildiği verilere çevirendir:

function getLesInputs()
    local lesInputs = {}
    -- 0a başlatma (gri = hiçbir şey)
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            lesInputs[getIndiceLesInputs(i, j)] = 0
        end
    end

    -- Spritelar (düşmanlar) = -1 (siyah)
    local lesSprites = getLesSprites()
    for i = 1, #lesSprites, 1 do
        local input = convertirPositionPourInput(getLesSprites()[i])
        if input.x > 0 and input.x < (TAILLE_VUE_W / TAILLE_TILE) + 1 then
            lesInputs[getIndiceLesInputs(input.x, input.y)] = -1
        end
    end

    -- Kareler (bloklar) = karenin değeri (> 0 ise beyaz)
    local lesTiles = getLesTiles()
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local indice = getIndiceLesInputs(i, j)
            if lesTiles[indice] ~= 0 then
                lesInputs[indice] = lesTiles[indice]
            end
        end
    end

    return lesInputs
end

Girdi ızgarası Mario merkezli bir görünümdür: genişlikte 11 kare, yükseklikte 9. Her kare değeri:

• 0 (gri): hiçbir şey
• 1 (beyaz): katı blok
• -1 (siyah): düşman

Düşmanlar RAMdeki iki listeden okunur: normal spritelar (0x14C8-0x14F8) ve genişletilmiş spritelar (0x170B-0x173B). Her canlı sprite için (durum > 7) Marioya göre kare cinsinden konumu hesaplanır ve ilgili kutuya -1 konur.

Fitness: yapay zekâ ilerlediğini nereden bilir

function majReseau(unReseau, marioBase)
    local mario = getPositionMario()

    if not niveauFini and memory.readbyte(0x0100) == 12 then
        -- Seviye bitti!
        unReseau.fitness = FITNESS_LEVEL_FINI
        niveauFini = true
    elseif marioBase.x < mario.x then
        -- Mario sağa ilerliyor
        unReseau.fitness = unReseau.fitness + (mario.x - marioBase.x)
        marioBase.x = mario.x
    end

    -- Girdilerin güncellenmesi
    local lesInputs = getLesInputs()
    for i = 1, NB_INPUT, 1 do
        unReseau.lesNeurones[i].valeur = lesInputs[i]
    end
end

Fitness basittir: sağa kat edilen mesafedir. Mario 10 piksel ilerlerse fitness 10 artar. Mario geri giderse hiçbir şey olmaz (ceza yok). Seviye biterse (adres 0x0100 == 12) fitness 1 000 000 olur.

Bu bilinçli basittir. Yalnızca sağa ilerleme sayılır: düşman öldürmek bir şey kazandırmaz, ölmek bir şeye mal olmaz.

Akıllı sıfırlama

Mario 33 kare hareket etmezse seviyeyi sıfırlar ve sonraki bireye geçilir. Ama Mario ilerleme kaydettiyse (mevcut fitnessi baştakinden farklıysa) 300 kare beklenir: bu ağa iyi yaptığı şeyi "anlama" şansı verir.

if fitnessAvant == laPopulation[idPopulation].fitness
   and memory.readbyte(0x13D4) == 0 then
    nbFrameStop = nbFrameStop + 1
    local nbFrameReset = NB_FRAME_RESET_BASE
    if fitnessInit ~= laPopulation[idPopulation].fitness
       and memory.readbyte(0x0071) ~= 9 then
        nbFrameReset = NB_FRAME_RESET_PROGRES
    end
    if nbFrameStop > nbFrameReset then
        nbFrameStop = 0
        lancerNiveau()
        idPopulation = idPopulation + 1
        -- ...
    end
end

memory.readbyte(0x0071) ~= 9 koşulu Marionun ölüm animasyonunda olmadığını doğrular. Mario zaten ölüm animasyonundayken sıfırlama gereksiz olur.

Ana döngü

Döngü 30 fps döner (Super Mario World normal hızı):

while true do
    local fitnessAvant = laPopulation[idPopulation].fitness

    -- Görüntüleme (ağ, bilgiler)
    if forms.ischecked(estAccelere) then
        emu.limitframerate(false)  -- hızlandır
    else
        emu.limitframerate(true)   -- 30 fps
    end

    -- 3 hayati fonksiyon
    majReseau(laPopulation[idPopulation], marioBase)
    feedForward(laPopulation[idPopulation])
    appliquerLesBoutons(laPopulation[idPopulation])

    emu.frameadvance()
    nbFrame = nbFrame + 1

    -- İlerleme yoksa sıfırla
    -- ...
    -- Tüm bireyler test edildiyse yeni nesil
    -- ...
end

Üç hayati fonksiyon majReseau, feedForward ve appliquerLesBoutons dur. Birini bile devre dışı bırakırsak Mario artık hareket etmez.

Çaprazlama

function crossover(unReseau1, unReseau2)
    local leReseau = newReseau()
    local leBon = unReseau1
    local leNul = unReseau2

    if leBon.fitness < leNul.fitness then
        leBon = unReseau2
        leNul = unReseau1
    end

    leReseau = copier(leBon)

    for i = 1, #leReseau.lesConnexions, 1 do
        for j = 1, #leNul.lesConnexions, 1 do
            if leReseau.lesConnexions[i].innovation == leNul.lesConnexions[j].innovation
               and leNul.lesConnexions[j].actif then
                if math.random() > 0.5 then
                    leReseau.lesConnexions[i] = leNul.lesConnexions[j]
                end
            end
        end
    end
    leReseau.fitness = 1
    return leReseau
end

Bebek en iyi ebeveyni kalıtır. Aynı inovasyonu paylaşan her bağlantı için diğer ebeveynin onun yerine geçme şansı %50dir: ama yalnızca bağlantı aktifse. Bu önemli bir düzeltmedir: o olmadan gereksiz gizli nöronlar yaratılabilirdi.

Türlerle seçim

function nouvelleGeneration(laPopulation, lesEspeces)
    local laNouvellePopulation = newPopulation()
    local nbIndividuACreer = NB_INDIVIDU_POPULATION

    -- Tür başına ortalama fitness hesabı
    for i = 1, #lesEspeces, 1 do
        lesEspeces[i].fitnessMoyenne = 0
        for j = 1, #lesEspeces[i].lesReseaux, 1 do
            lesEspeces[i].fitnessMoyenne =
                lesEspeces[i].fitnessMoyenne + lesEspeces[i].lesReseaux[j].fitness
        end
        lesEspeces[i].fitnessMoyenne =
            lesEspeces[i].fitnessMoyenne / #lesEspeces[i].lesReseaux
    end

    -- Her tür ortalama fitnessiyle orantılı çocuk sayısı yaratır
    for i = 1, #lesEspeces, 1 do
        local nbEnfant = math.ceil(
            #lesEspeces[i].lesReseaux *
            lesEspeces[i].fitnessMoyenne / fitnessMoyenneGlobal)

        for j = 1, nbEnfant, 1 do
            local unReseau = crossover(
                choisirParent(lesEspeces[i].lesReseaux),
                choisirParent(lesEspeces[i].lesReseaux))
            mutation(unReseau)
            laNouvellePopulation[indiceNouvelleEspece] = copier(unReseau)
        end
    end
end

Fikir: ortalama fitnessi 10 000 olan bir tür, ortalama fitnessi 1 olan bir türden çok daha fazla çocuk yaratma hakkına sahiptir. Harekete geçen doğal seçilimdir.

choisirParent rulet seçimi kullanır: bir bireyin fitnessi ne kadar yüksekse ebeveyn seçilme şansı o kadar artar.

Kaydetme ve yükleme

Popülasyonlar .pop dosyalarına kaydedilir:

function sauvegarderUnReseau(unReseau, fichier)
    io.write(unReseau.nbNeurone .. "\n")
    io.write(#unReseau.lesConnexions .. "\n")
    io.write(unReseau.fitness .. "\n")
    for i = 1, unReseau.nbNeurone, 1 do
        local indice = NB_INPUT + NB_OUTPUT + i
        io.write(unReseau.lesNeurones[indice].id .. "\n")
    end
    for i = 1, #unReseau.lesConnexions, 1 do
        local actif = 1
        if unReseau.lesConnexions[i].actif ~= true then actif = 0 end
        io.write(actif .. "\n" ..
            unReseau.lesConnexions[i].entree .. "\n" ..
            unReseau.lesConnexions[i].sortie .. "\n" ..
            unReseau.lesConnexions[i].poids .. "\n" ..
            unReseau.lesConnexions[i].innovation .. "\n")
    end
end

Kaydetme tüm önceki popülasyonların en iyi bireyini de içerir. Eski popülasyonun en iyisi yeninin en iyisinden iyiyse eski temel olarak alınır. Bu bir elitizm biçimidir: en iyi asla kaybedilmez.

Ağın çizimi

Laupok oyunun üstüne sinir ağının bir görselleştiricisini ekledi:

function dessinerUnReseau(unReseau)
    -- Girdiler: Mario etrafında 11×9 ızgara
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local xT = ENCRAGE_X_INPUT + (i - 1) * TAILLE_INPUT
            local yT = ENCRAGE_Y_INPUT + (j - 1) * TAILLE_INPUT
            local couleurFond = "gray"
            if unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur < 0 then
                couleurFond = "black"   -- düşman
            elseif unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur > 0 then
                couleurFond = "white"   -- blok
            end
            gui.drawRectangle(xT, yT, TAILLE_INPUT, TAILLE_INPUT, "black", couleurFond)
        end
    end

    -- Çıktılar: 8 düğme
    for i = 1, NB_OUTPUT, 1 do
        local xT = ENCRAGE_X_OUTPUT
        local yT = ENCRAGE_Y_OUTPUT + ESPACE_Y_OUTPUT * (i - 1)
        if sigmoid(unReseau.lesNeurones[i + NB_INPUT].valeur) then
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "white")
        else
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "black")
        end
    end

    -- Bağlantılar
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local alpha = 25
            if unReseau.lesConnexions[i].allume then alpha = 255 end
            local couleur = forms.createcolor(255, 255, 255, alpha)
            gui.drawLine(
                lesPositions[unReseau.lesConnexions[i].entree].x,
                lesPositions[lesConnexions[i].entree].y,
                lesPositions[unReseau.lesConnexions[i].sortie].x,
                lesPositions[lesConnexions[i].sortie].y,
                couleur)
        end
    end
end

Ağın ne yaptığını anlamak için süper kullanışlıdır. Aktif bağlantılar beyazdır, inaktifler yarı saydamdır. Girdiler beyaz/siyah/gri kutu ızgarasıdır. Çıktılar hangi düğmelerin basılı olduğunu gösterir.

---

Sonuçlar

Yapay zekânın öğrendikleri

Çalışmanın saatleri (ve günleri) boyunca yapay zekâ kendi kendine keşfetti:

1. Sağa ilerlemek: en temel davranış ama Sağ düğmeyi basılı tutmayı gerektirir
2. Düşmanların üstünden zıplamak: "düşman tespit edildi" girdisini A ya da B düğmesine bağlayarak
3. Engellerden kaçınmak: bazı ağlar daha iyi ilerlemek için geçici geri gitmeyi öğrendi
4. Seviyeleri bitirmek: en iyi birey Super Mario World ilk seviyesini bitirebildi

Sınırlamalar

Projenin limitleri var:

• Tek seviye: yapay zekâ belirli tek bir seviyede eğitilir. Diğer seviyelere otomatik genellemez
• Eğitim süresi: tatmin edici sonuçlara ulaşmak için onlarca saat gerekir
• Anlama yok: yapay zekâ ne yaptığını "anlamaz". Rastgele mutasyonlarla bir fitness fonksiyonunu (kat edilen mesafe) optimize eder
• T-bagging: Laupok Marionun bir düşman görünce yerinde zıplama eğiliminde olduğunu not eder, sırf bu fitnessi artırdığı için (zıplayarak biraz ilerler)

---

Deneyimi nasıl yeniden üretmeli

Laupok her şeyi paylaştı. İşte adımlar:

1. BizHawkı indir tasvideos.org üzerinden (Download bölümü)
2. Super Mario World ABD ROMu edin (kendi kartuşunun özel kopyası)
3. Lua scriptini indir Pastebin üzerinden: mario.lua olarak yeniden adlandır
4. Scripti ROM ile aynı klasöre yerleştir
5. BizHawkı çalıştır, ROMu aç
6. Lua konsolunda: dofile("mario.lua") ya da Script > Open Script menüsüyle
7. Seviye başında bir durum kaydet (Savestate > Save State menüsü) ve debut.state olarak adlandır
8. Scripti yeniden çalıştır: çalışır

Script seçenekli bir form içerir:

• Hızlandır: daha hızlı gitmek için 30 fps limitini devre dışı bırakır
• Ağı göster: sinir ağını bindirmeli gösterir
• Bilgileri göster: nesil, fitness, tür sayısıyla bir şerit gösterir
• Duraklat: yürütmeyi duraklatır
• Kaydet/Yükle: mevcut popülasyonu bir .pop dosyasında saklar

---

Kaynaklar ve referanslar

Kaynak	Bağlantı
Laupok ana videosu	j'ai créé une IA qui joue à mario toute seule
Kod incelemesi + kurulum videosu	comment setup l'ia + code source review
Tam kaynak kodu	Pastebin Jcvdqhqm
NEAT orijinal makalesi	Stanley & Miikkulainen, "Evolving Neural Networks through Augmenting Topologies", 2002
N8Programs öğreticisi	NEAT implementation walkthrough (JavaScript ama kavramlar aynı)
16blings (Laupok ilhamı)	AI plays Super Mario World
BizHawk	tasvideos.org/BizHawk
Super Mario World belleği	SMW Central - RAM Map

---

Sonuç

Laupokun yaptığı şey akademik bir algoritmayı (NEAT, 2002) alıp bir emülatör (BizHawk) için Luada yeniden yazmak ve Super Mario Worlde uygulamaktır. Sonuç: önceden bilgi olmadan, yalnızca rastgele mutasyonlar ve doğal seçilimle oyunu oynamayı sıfırdan öğrenen bir yapay zekâ.

Bu genetik algoritmaların gücünün muhteşem bir örneğidir. Tarif üç malzemeye sığar: doğal seçilim, biraz Lua ve çok sabır. Derin öğrenme yok, GPU yok, devasa eğitim verisi yok.

Kod yorumlu, paylaşılmış ve Laupok iki açıklayıcı video yapmış: biri büyük kavramlar, biri kod için. Konu ilgini çekerse dal içine. Göründüğünden daha erişilebilir.

Laupok ha creato un'IA che gioca a Super Mario World da sola: come funziona

Laupok ha creato un'intelligenza artificiale che gioca a Super Mario World in modo totalmente autonomo. Parte da zero: nessuno script predefinito, nessun frame registrato. L'IA impara da sola, a colpi di mutazioni casuali e selezione naturale, a finire i livelli del gioco. Il progetto gira su BizHawk, un emulatore multipiattaforma, via uno script Lua di circa 4200 righe.

Ciò che rende questo progetto affascinante, è che poggia su concetti biologici applicati all'informatica: la teoria dell'evoluzione di Darwin, le reti neurali artificiali, e soprattutto un algoritmo specifico chiamato NEAT (NeuroEvolution of Augmenting Topologies). L'IA non sa niente del gioco all'inizio. Prova azioni a caso, fallisce migliaia di volte, e piano piano capisce come avanzare, saltare, e sopravvivere.

In questo articolo, smontiamo tutto questo: concetto per concetto, riga di codice per riga di codice.

---

Il setup: BizHawk, Lua, e Super Mario World

L'emulatore BizHawk

BizHawk è un emulatore open source che supporta una tonnellata di console: NES, SNES, Genesis, PS1, Game Boy, e molte altre. La sua particolarità, è che permette di lanciare script Lua in parallelo al gioco. Questi script hanno accesso alla memoria viva (RAM) dell'emulazione, il che significa che possono leggere, e modificare, qualsiasi dato del gioco in tempo reale.

In concreto, vuol dire che possiamo:

• Leggere la posizione di Mario nel livello
• Sapere quali sprite (nemici, item) sono a schermo
• Conoscere lo stato di ogni tile (blocco) intorno a Mario
• Controllare il pad: premere qualsiasi pulsante

È esattamente ciò di cui abbiamo bisogno per far giocare un'IA.

Gli indirizzi memoria di Super Mario World

Nella RAM di Super Mario World, ogni dato è salvato a un indirizzo specifico. È un po' come un quartiere: ogni indirizzo corrisponde a una "casa" che contiene un'informazione. Per esempio:

Indirizzo	Dato
0x94-0x95	Posizione X di Mario (16 bit, little-endian)
0x96-0x97	Posizione Y di Mario
0x14C8+i	Stato dello sprite i (>7 = vivo)
0xE4+i	Posizione X bassa dello sprite i
0x14E0+i	Posizione X alta dello sprite i
0xD8+i	Posizione Y bassa dello sprite i
0x14D4+i	Posizione Y alta dello sprite i
0x170B+i	Tipo dell'extended sprite i
0x0100	Stato del gioco (12 = livello finito)
0x13D4	Pausa attiva
0x0071	Animazione di morte di Mario (9 = morte)
0x1C800+...	Tabella delle tile del livello

La posizione degli sprite usa due byte: un byte "basso" e un byte "alto", perché la posizione può superare 255 pixel. La formula è sempre basso + alto × 256.

Per le tile, è più complesso: l'indirizzo di base è 0x1C800, e si calcola l'offset in base alle coordinate x e y della tile nel mondo, con un passo di 16 pixel per tile.

---

Le basi: algoritmi genetici e reti neurali

Prima di tuffarci nel codice, bisogna capire due concetti fondamentali. Senza, il resto non ha senso.

Gli algoritmi genetici

Un algoritmo genetico, è una simulazione della teoria dell'evoluzione. L'idea centrale: creiamo una popolazione di individui, ognuno con caratteristiche (i "geni") leggermente diverse. Li facciamo "vivere" in un ambiente. Quelli che se la cavano meglio sopravvivono e si riproducono. Quelli che se la cavano male spariscono.

Laupok lo illustra con un'analogia di Kirby:

• Una popolazione di Kirby appare su un terreno con spuntoni e pomodori
• Gli spuntoni tolgono punti vita, i pomodori ne ridanno
• Ogni Kirby ha geni: taglia, velocità, punti vita, comportamento (fuggire, cercare pomodori, andare a caso)
• Dopo 15 secondi, guardiamo chi è sopravvissuto più a lungo
• Il miglior Kirby si riproduce con gli altri: i bebè ereditano metà dei geni del migliore e metà del "peggiore"
• I bebè subiscono mutazioni casuali (un po' più grande, un po' più rapido...)
• I vecchi Kirby sono sostituiti dai nuovi
• Si rilancia

Dopo 180 generazioni (circa 15 ore), i Kirby passano da 15 secondi di sopravvivenza a 15 minuti. Sono diventati piccoli (zona di collisione ridotta), rapidi, e fuggono il pericolo in permanenza.

Il punto cruciale: non definiamo la soluzione. L'algoritmo la trova da solo. Ed è esattamente ciò che lo rende potente per problemi dove non sappiamo quale combinazione di parametri sarebbe ottimale.

Le reti neurali artificiali

Una rete neurale, è un modello matematico semplificato del cervello umano. Si compone di:

• Neuroni di ingresso (input): ciò che la rete "vede"
• Neuroni di uscita (output): ciò che la rete "decide"
• Connessioni (pesi): ogni connessione ha un peso che amplifica o attenua il segnale

Il principio è semplice: ogni neurone di ingresso invia il suo valore. È moltiplicato per il peso della connessione, poi sommato agli altri segnali. Se il risultato supera una certa soglia (la funzione di attivazione), il neurone di uscita si attiva.

Nell'analogia di Laupok con Mario e il pezzo di topo:

• Il neurone di ingresso = la distanza tra Mario e il pezzo
• Il peso della connessione = la sensibilità di Mario
• Il neurone di uscita = Mario urla o no

Più il pezzo è vicino, più il valore di ingresso è alto. Se il peso è forte, il segnale inviato in uscita è forte, e Mario urlerebbe. Modificando il peso, modifichi la sensibilità di Mario.

Nella vera rete neurale dell'IA, è la stessa logica, ma su scala massiccia:

• 99 neuroni di ingresso (11×9 tile della vista di Mario)
• 8 neuroni di uscita (A, B, X, Y, Su, Giù, Sinistra, Destra)
• Neuroni nascosti (hidden) tra i due
• Centinaia di connessioni con pesi vari

---

NEAT: l'algoritmo che cambia tutto

Il problema degli algoritmi genetici classici

Se combiniamo un algoritmo genetico con una rete neurale in modo ingenuo, abbiamo un problema: creiamo 100 reti neurali completamente diverse, e non sappiamo confrontarle. Ognuna ha i suoi neuroni, le sue connessioni, i suoi pesi. Come sapere se due reti sono "vicine" o "lontane"?

È lì che interviene NEAT: NeuroEvolution of Augmenting Topologies. Inventato da Kenneth Stanley e Risto Miikkulainen nel 2002, è un algoritmo che risolve esattamente questo problema.

Le specie

Il primo meccanismo chiave di NEAT, sono le specie. Quando una rete neurale diventa troppo diversa da un'altra, è classificata in una specie diversa. La similarità è calcolata via tre parametri:

1. Excess (EXCES_COEF = 0.50): il numero di connessioni che non hanno alcun rapporto tra due reti (innovazioni diverse)
2. Disjoint: uguale, ma per le connessioni che stanno nel mezzo
3. Differenza di peso (POIDSDIFF_COEF = 0.92): la differenza media di peso tra le connessioni che condividono la stessa innovazione

La formula di punteggio:

score = (EXCES_COEF × disjoint) / max(nbConnessioni1 + nbConnessioni2, 1)
      + POIDSDIFF_COEF × diffPesi

Se questo punteggio è sotto DIFF_LIMITE (1.0), le due reti sono nella stessa specie. Altrimenti, si crea una nuova specie.

Le innovazioni

È il genio di NEAT. Ogni volta che una connessione è creata, riceve un numero di innovazione unico e globale. Questo numero segue la rete neurale anche quando si riproduce.

In concreto, quando un bebè è creato per crossover, eredita le innovazioni dei suoi genitori. Se due reti condividono la stessa innovazione, vuol dire che hanno una connessione che viene dallo stesso antenato. È ciò che permette di confrontare reti di taglie diverse.

Il crossover

Quando due reti neurali si riproducono, il crossover funziona così:

1. La rete più performante diventa il "genitore dominante"
2. Il bebè eredita tutte le connessioni del dominante
3. Per ogni connessione che condivide la stessa innovazione, l'altro genitore può sostituirla (50% di probabilità)
4. Solo le connessioni attive del genitore non dominante possono sostituire

Garantisce che il bebè sia sempre almeno bravo quanto il miglior genitore.

Le mutazioni

Dopo il crossover, il bebè subisce mutazioni con probabilità configurabili:

Mutazione	Probabilità	Effetto
Reset peso connessione	25%	Il peso è totalmente randomizzato
Mutazione peso	95%	Il peso varia di ±0.80
Aggiunta connessione	85%	Nuova connessione tra due neuroni non ancora collegati
Aggiunta neurone	39%	Un neurone nascosto è inserito tra due neuroni connessi

Il tasso di aggiunta neurone è importante: è ciò che permette alla rete di crescere. All'inizio, ci sono solo ingressi e uscite. Progressivamente, neuroni nascosti appaiono, rendendo la rete sempre più complessa.

---

Il codice: walkthrough completo

Le costanti

Lo script inizia con un blocco di costanti che definiscono tutto il setup:

-- Vista di Mario intorno a lui (11x9 tile)
TAILLE_TILE = 16
TAILLE_VUE_W = TAILLE_TILE * 11  -- 176 pixel in larghezza
TAILLE_VUE_H = TAILLE_TILE * 9   -- 144 pixel in altezza
NB_TILE_W = TAILLE_VUE_W / TAILLE_TILE  -- 11 tile
NB_TILE_H = TAILLE_VUE_H / TAILLE_TILE  -- 9 tile

-- Rete neurale
NB_INPUT = NB_TILE_W * NB_TILE_H  -- 99 input (tile visibili)
NB_OUTPUT = 8  -- A, B, X, Y, Su, Giù, Sinistra, Destra
NB_INDIVIDU_POPULATION = 100  -- individui per popolazione
NB_NEURONE_MAX = 100000  -- limite di neuroni nascosti

-- Fitness
FITNESS_LEVEL_FINI = 1000000  -- valore quando il livello è finito
NB_FRAME_RESET_BASE = 33  -- frame senza progresso prima del reset
NB_FRAME_RESET_PROGRES = 300  -- frame se progresso rilevato

-- Specie
EXCES_COEF = 0.50
POIDSDIFF_COEF = 0.92
DIFF_LIMITE = 1.00

-- Mutazioni
CHANCE_MUTATION_RESET_CONNEXION = 0.25
POIDS_CONNEXION_MUTATION_AJOUT = 0.80
CHANCE_MUTATION_POIDS = 0.95
CHANCE_MUTATION_CONNEXION = 0.85
CHANCE_MUTATION_NEURONE = 0.39

Il NB_INPUT è 99 perché la vista di Mario fa 11×9 tile. Ogni tile è un neurone di ingresso. Se la tile è vuota, vale 0. Se è un blocco, vale 1. Se è un nemico, vale -1.

Le 8 uscite corrispondono ai pulsanti del pad SNES: A, B, X, Y, Su, Giù, Sinistra, Destra. Escludiamo Start, Select, L e R per limitare le sue decisioni all'essenziale.

Le strutture dati

Lo script definisce tre strutture principali:

-- crea un neurone vuoto
function newNeurone()
    local neurone = {}
    neurone.valeur = 0    -- valore attuale del neurone
    neurone.id = 0        -- identificatore unico
    neurone.type = ""     -- "input", "output", o "hidden"
    return neurone
end

-- crea una connessione vuota
function newConnexion()
    local connexion = {}
    connexion.entree = 0     -- ID del neurone sorgente
    connexion.sortie = 0     -- ID del neurone destinazione
    connexion.actif = true   -- può essere disattivata se un neurone nascosto è inserito
    connexion.poids = 0      -- peso della connessione
    connexion.innovation = 0 -- numero di innovazione unico
    connexion.allume = false -- per la visualizzazione: true se il segnale passa
    return connexion
end

-- crea una rete con input e output, senza connessioni
function newReseau()
    local reseau = {
        nbNeurone = 0,        -- numero di neuroni nascosti
        fitness = 1,          -- performance (distanza percorsa)
        idEspeceParent = 0,   -- a quale specie appartiene
        lesNeurones = {},     -- tabella di neuroni
        lesConnexions = {}    -- tabella di connessioni
    }
    -- Inizializzazione con gli input
    for j = 1, NB_INPUT, 1 do
        ajouterNeurone(reseau, j, "input", 1)
    end
    -- Poi gli output
    for j = NB_INPUT + 1, NB_INPUT + NB_OUTPUT, 1 do
        ajouterNeurone(reseau, j, "output", 0)
    end
    return reseau
end

All'inizio, ogni rete contiene solo input e output: nessun neurone nascosto, nessuna connessione. È l'algoritmo che deciderà se ne servono.

Le mutazioni in dettaglio

Mutazione dei pesi

-- muta i pesi: reset totale o variazione ±0.80
function mutationPoidsConnexions(unReseau)
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            if math.random() < CHANCE_MUTATION_RESET_CONNEXION then
                -- 25%: reset totale del peso
                unReseau.lesConnexions[i].poids = genererPoids()
            else
                -- 75%: variazione di ±0.80
                if math.random() >= 0.5 then
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids - POIDS_CONNEXION_MUTATION_AJOUT
                else
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids + POIDS_CONNEXION_MUTATION_AJOUT
                end
            end
        end
    end
end

Il peso iniziale è sempre 1 o -1 (genererPoids()). La variazione di ±0.80 può farlo oscillare tra valori negativi e positivi, il che cambia radicalmente il comportamento della rete.

Aggiunta di connessione

-- aggiunge una connessione tra due neuroni non ancora collegati
function mutationAjouterConnexion(unReseau)
    local liste = {}
    -- Randomizzazione della lista dei neuroni
    for i, v in ipairs(unReseau.lesNeurones) do
        local pos = math.random(1, #liste+1)
        table.insert(liste, pos, v)
    end

    local traitement = false
    for i = 1, #liste, 1 do
        for j = 1, #liste, 1 do
            if i ~= j then
                local n1 = liste[i]
                local n2 = liste[j]
                -- Connessione valida: input→output, hidden→hidden, hidden→output
                if (n1.type == "input" and n2.type == "output") or
                   (n1.type == "hidden" and n2.type == "hidden") or
                   (n1.type == "hidden" and n2.type == "output") then
                    -- Verifica che non ci sia già una connessione
                    local dejaConnexion = false
                    for k = 1, #unReseau.lesConnexions, 1 do
                        if unReseau.lesConnexions[k].entree == n1.id
                            and unReseau.lesConnexions[k].sortie == n2.id then
                            dejaConnexion = true
                            break
                        end
                    end
                    if dejaConnexion == false then
                        traitement = true
                        ajouterConnexion(unReseau, n1.id, n2.id)
                    end
                end
            end
            if traitement then break end
        end
        if traitement then break end
    end
end

Non possiamo connettere un output a un input (creerebbe un ciclo), e non possiamo connettere due neuroni già collegati. La randomizzazione garantisce di esplorare possibilità diverse ogni volta.

Aggiunta di neurone

È la mutazione più interessante:

-- inserisce un neurone nascosto nel mezzo di una connessione
function mutationAjouterNeurone(unReseau)
    if #unReseau.lesConnexions == 0 then return nil end
    if unReseau.nbNeurone == NB_NEURONE_MAX then return nil end

    -- Randomizzazione delle connessioni
    local listeRandom = {}
    for i = 1, #unReseau.lesConnexions, 1 do
        local pos = math.random(1, #listeRandom+1)
        table.insert(listeRandom, pos, i)
    end

    for i = 1, #listeRandom, 1 do
        if unReseau.lesConnexions[listeRandom[i]].actif then
            -- Disattiva la connessione esistente
            unReseau.lesConnexions[listeRandom[i]].actif = false
            unReseau.nbNeurone = unReseau.nbNeurone + 1
            local indice = unReseau.nbNeurone + NB_INPUT + NB_OUTPUT

            -- Crea il neurone nascosto
            ajouterNeurone(unReseau, indice, "hidden", 1)

            -- Connette l'ingresso al neurone nascosto
            ajouterConnexion(unReseau,
                unReseau.lesConnexions[listeRandom[i]].entree,
                indice, genererPoids())

            -- Connette il neurone nascosto all'uscita
            ajouterConnexion(unReseau,
                indice,
                unReseau.lesConnexions[listeRandom[i]].sortie,
                genererPoids())
            break
        end
    end
end

Il meccanismo: prendiamo una connessione esistente, la disattiviamo, e inseriamo un neurone nascosto in mezzo. La connessione di origine è sostituita da due nuove connessioni: ingresso→nascosto e nascosto→uscita. È come se "tagliassimo" un filo per intercalare un interruttore.

È ciò che rende NEAT "augmenting topologies": la rete cresce col tempo. Inizia semplice e diventa complessa solo se necessario.

Il feedForward

È la funzione che propaga i segnali attraverso la rete:

-- propaga i segnali ingresso→uscita sommandoli
function feedForward(unReseau)
    -- Reset dei neuroni di uscita
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur = 0
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].allume = false
        end
    end

    -- Propagazione
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local avantTraitement = unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur =
                unReseau.lesNeurones[unReseau.lesConnexions[i].entree].valeur *
                unReseau.lesConnexions[i].poids +
                unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur

            if avantTraitement ~= unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur then
                unReseau.lesConnexions[i].allume = true
            else
                unReseau.lesConnexions[i].allume = false
            end
        end
    end
end

Ogni connessione attiva invia valore_ingresso × peso verso il neurone di uscita. Il valore è cumulato (sommato). Il flag allume è solo per la visualizzazione grafica della rete.

La lettura della memoria del gioco

La funzione getLesInputs() è quella che traduce il mondo di Super Mario World in dati comprensibili dalla rete:

-- costruisce la griglia 11x9: 0 vuoto, 1 blocco, -1 nemico
function getLesInputs()
    local lesInputs = {}
    -- Inizializzazione a 0 (grigio = niente)
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            lesInputs[getIndiceLesInputs(i, j)] = 0
        end
    end

    -- Gli sprite (nemici) = -1 (nero)
    local lesSprites = getLesSprites()
    for i = 1, #lesSprites, 1 do
        local input = convertirPositionPourInput(getLesSprites()[i])
        if input.x > 0 and input.x < (TAILLE_VUE_W / TAILLE_TILE) + 1 then
            lesInputs[getIndiceLesInputs(input.x, input.y)] = -1
        end
    end

    -- Le tile (blocchi) = valore della tile (bianco se > 0)
    local lesTiles = getLesTiles()
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local indice = getIndiceLesInputs(i, j)
            if lesTiles[indice] ~= 0 then
                lesInputs[indice] = lesTiles[indice]
            end
        end
    end

    return lesInputs
end

La griglia di input è una vista centrata su Mario: 11 tile in larghezza, 9 in altezza. Ogni tile vale:

• 0 (grigio): niente
• 1 (bianco): blocco solido
• -1 (nero): nemico

I nemici sono letti da due liste nella RAM: gli sprite normali (0x14C8-0x14F8) e gli extended sprite (0x170B-0x173B). Per ogni sprite vivo (stato > 7), calcoliamo la sua posizione in tile rispetto a Mario e mettiamo -1 nella casella corrispondente.

Il fitness: come l'IA sa se progredisce

-- aggiorna fitness con la distanza percorsa verso destra
function majReseau(unReseau, marioBase)
    local mario = getPositionMario()

    if not niveauFini and memory.readbyte(0x0100) == 12 then
        -- Livello finito!
        unReseau.fitness = FITNESS_LEVEL_FINI
        niveauFini = true
    elseif marioBase.x < mario.x then
        -- Mario avanza verso destra
        unReseau.fitness = unReseau.fitness + (mario.x - marioBase.x)
        marioBase.x = mario.x
    end

    -- Aggiornamento degli input
    local lesInputs = getLesInputs()
    for i = 1, NB_INPUT, 1 do
        unReseau.lesNeurones[i].valeur = lesInputs[i]
    end
end

La fitness è semplice: è la distanza percorsa verso destra. Se Mario avanza di 10 pixel, la fitness aumenta di 10. Se Mario indietreggia, non succede niente (nessuna penalità). Se il livello è finito (indirizzo 0x0100 == 12), la fitness diventa 1 000 000.

È volutamente semplice. Solo la progressione verso destra conta: uccidere nemici non rende niente, morire non costa niente.

Il reset intelligente

Se Mario non si muove per 33 frame, resettiamo il livello e passiamo all'individuo successivo. Ma se Mario ha fatto progressi (la sua fitness attuale è diversa da quella all'inizio), aspettiamo 300 frame: dà una chance alla rete di "capire" cosa ha fatto di bene.

-- reset se Mario è fermo: 33 frame, 300 se ci sono progressi
if fitnessAvant == laPopulation[idPopulation].fitness
   and memory.readbyte(0x13D4) == 0 then
    nbFrameStop = nbFrameStop + 1
    local nbFrameReset = NB_FRAME_RESET_BASE
    if fitnessInit ~= laPopulation[idPopulation].fitness
       and memory.readbyte(0x0071) ~= 9 then
        nbFrameReset = NB_FRAME_RESET_PROGRES
    end
    if nbFrameStop > nbFrameReset then
        nbFrameStop = 0
        lancerNiveau()
        idPopulation = idPopulation + 1
        -- ...
    end
end

La condizione memory.readbyte(0x0071) ~= 9 verifica che Mario non sia in animazione di morte. Il reset diventa inutile quando Mario è già in animazione di morte.

Il ciclo principale

Il ciclo gira a 30 fps (la velocità normale di Super Mario World):

-- ciclo principale: aggiorna, propaga, premi pulsanti
while true do
    local fitnessAvant = laPopulation[idPopulation].fitness

    -- Visualizzazione (rete, info)
    if forms.ischecked(estAccelere) then
        emu.limitframerate(false)  -- accelerare
    else
        emu.limitframerate(true)   -- 30 fps
    end

    -- Le 3 funzioni vitali
    majReseau(laPopulation[idPopulation], marioBase)
    feedForward(laPopulation[idPopulation])
    appliquerLesBoutons(laPopulation[idPopulation])

    emu.frameadvance()
    nbFrame = nbFrame + 1

    -- Reset se niente progresso
    -- ...
    -- Nuova generazione se tutti gli individui testati
    -- ...
end

Le tre funzioni vitali sono majReseau, feedForward, e appliquerLesBoutons. Se ne disattiviamo una sola, Mario non si muove più.

Il crossover

-- il bebè eredita dal migliore, l'altro può sostituire al 50%
function crossover(unReseau1, unReseau2)
    local leReseau = newReseau()
    local leBon = unReseau1
    local leNul = unReseau2

    if leBon.fitness < leNul.fitness then
        leBon = unReseau2
        leNul = unReseau1
    end

    leReseau = copier(leBon)

    for i = 1, #leReseau.lesConnexions, 1 do
        for j = 1, #leNul.lesConnexions, 1 do
            if leReseau.lesConnexions[i].innovation == leNul.lesConnexions[j].innovation
               and leNul.lesConnexions[j].actif then
                if math.random() > 0.5 then
                    leReseau.lesConnexions[i] = leNul.lesConnexions[j]
                end
            end
        end
    end
    leReseau.fitness = 1
    return leReseau
end

Il bebè eredita dal miglior genitore. Per ogni connessione che condivide la stessa innovazione, l'altro genitore ha il 50% di probabilità di sostituirla: ma solo se la connessione è attiva. È una correzione importante: senza, neuroni nascosti inutili potevano essere creati.

La selezione per specie

-- ogni specie crea figli in proporzione alla sua fitness media
function nouvelleGeneration(laPopulation, lesEspeces)
    local laNouvellePopulation = newPopulation()
    local nbIndividuACreer = NB_INDIVIDU_POPULATION

    -- Calcolo fitness media per specie
    for i = 1, #lesEspeces, 1 do
        lesEspeces[i].fitnessMoyenne = 0
        for j = 1, #lesEspeces[i].lesReseaux, 1 do
            lesEspeces[i].fitnessMoyenne =
                lesEspeces[i].fitnessMoyenne + lesEspeces[i].lesReseaux[j].fitness
        end
        lesEspeces[i].fitnessMoyenne =
            lesEspeces[i].fitnessMoyenne / #lesEspeces[i].lesReseaux
    end

    -- Ogni specie crea un numero di figli proporzionale alla sua fitness media
    for i = 1, #lesEspeces, 1 do
        local nbEnfant = math.ceil(
            #lesEspeces[i].lesReseaux *
            lesEspeces[i].fitnessMoyenne / fitnessMoyenneGlobal)

        for j = 1, nbEnfant, 1 do
            local unReseau = crossover(
                choisirParent(lesEspeces[i].lesReseaux),
                choisirParent(lesEspeces[i].lesReseaux))
            mutation(unReseau)
            laNouvellePopulation[indiceNouvelleEspece] = copier(unReseau)
        end
    end
end

L'idea: una specie con una fitness media di 10 000 ha il diritto di creare molti più figli di una specie con una fitness media di 1. È la selezione naturale in azione.

Il choisirParent usa una selezione a roulette: più un individuo ha fitness, più ha probabilità di essere selezionato come genitore.

Il salvataggio e il caricamento

Le popolazioni sono salvate in file .pop:

-- salva neuroni e connessioni in un file .pop
function sauvegarderUnReseau(unReseau, fichier)
    io.write(unReseau.nbNeurone .. "\n")
    io.write(#unReseau.lesConnexions .. "\n")
    io.write(unReseau.fitness .. "\n")
    for i = 1, unReseau.nbNeurone, 1 do
        local indice = NB_INPUT + NB_OUTPUT + i
        io.write(unReseau.lesNeurones[indice].id .. "\n")
    end
    for i = 1, #unReseau.lesConnexions, 1 do
        local actif = 1
        if unReseau.lesConnexions[i].actif ~= true then actif = 0 end
        io.write(actif .. "\n" ..
            unReseau.lesConnexions[i].entree .. "\n" ..
            unReseau.lesConnexions[i].sortie .. "\n" ..
            unReseau.lesConnexions[i].poids .. "\n" ..
            unReseau.lesConnexions[i].innovation .. "\n")
    end
end

Il salvataggio include anche il miglior individuo di tutte le popolazioni precedenti. Se il migliore della vecchia popolazione è migliore del migliore della nuova, riprendiamo il vecchio come base. È una forma di elitismo: non perdiamo mai il migliore.

Il disegno della rete

Laupok ha aggiunto un visualizzatore della rete neurale in overlay sul gioco:

-- disegna input, output e connessioni in overlay
function dessinerUnReseau(unReseau)
    -- Input: griglia 11×9 intorno a Mario
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local xT = ENCRAGE_X_INPUT + (i - 1) * TAILLE_INPUT
            local yT = ENCRAGE_Y_INPUT + (j - 1) * TAILLE_INPUT
            local couleurFond = "gray"
            if unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur < 0 then
                couleurFond = "black"   -- nemico
            elseif unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur > 0 then
                couleurFond = "white"   -- blocco
            end
            gui.drawRectangle(xT, yT, TAILLE_INPUT, TAILLE_INPUT, "black", couleurFond)
        end
    end

    -- Output: 8 pulsanti
    for i = 1, NB_OUTPUT, 1 do
        local xT = ENCRAGE_X_OUTPUT
        local yT = ENCRAGE_Y_OUTPUT + ESPACE_Y_OUTPUT * (i - 1)
        if sigmoid(unReseau.lesNeurones[i + NB_INPUT].valeur) then
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "white")
        else
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "black")
        end
    end

    -- Connessioni
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local alpha = 25
            if unReseau.lesConnexions[i].allume then alpha = 255 end
            local couleur = forms.createcolor(255, 255, 255, alpha)
            gui.drawLine(
                lesPositions[unReseau.lesConnexions[i].entree].x,
                lesPositions[lesConnexions[i].entree].y,
                lesPositions[unReseau.lesConnexions[i].sortie].x,
                lesPositions[lesConnexions[i].sortie].y,
                couleur)
        end
    end
end

È super utile per capire cosa fa la rete. Le connessioni attive sono bianche, le inattive sono semi-trasparenti. Gli input sono una griglia di caselle bianche/nere/grigie. Gli output mostrano quali pulsanti sono premuti.

---

I risultati

Cosa l'IA ha imparato

Col passare di ore (e giorni) di esecuzione, l'IA ha scoperto da sola:

1. Avanzare verso destra: il comportamento più basico, ma che richiede di tenere premuto il pulsante Destra
2. Saltare sopra i nemici: connettendo un input "nemico rilevato" al pulsante A o B
3. Evitare gli ostacoli: certe reti hanno imparato a indietreggiare temporaneamente per avanzare meglio
4. Finire livelli: il miglior individuo ha potuto finire il primo livello di Super Mario World

I limiti

Il progetto ha i suoi limiti:

• Un solo livello: l'IA è allenata su un solo livello specifico. Non generalizza automaticamente ad altri livelli
• Tempo di allenamento: servono decine di ore per raggiungere risultati soddisfacenti
• Niente comprensione: l'IA non "capisce" cosa fa. Ottimizza una funzione di fitness (distanza percorsa) via mutazioni casuali
• T-bagging: Laupok nota che Mario tende a saltare sul posto quando vede un nemico, semplicemente perché aumenta la fitness (avanza un po' saltando)

---

Come riprodurre l'esperimento

Laupok ha condiviso tutto. Ecco i passi:

1. Scarica BizHawk su tasvideos.org (sezione Download)
2. Ottieni una ROM USA di Super Mario World (copia privata della tua cartuccia)
3. Scarica lo script Lua da Pastebin: rinomina in mario.lua
4. Metti lo script nella stessa cartella della ROM
5. Lancia BizHawk, apri la ROM
6. Nella console Lua: dofile("mario.lua") o via il menu Script > Open Script
7. Salva uno state all'inizio del livello (menu Savestate > Save State) e chiamalo debut.state
8. Rilancia lo script: funziona

Lo script include un form con opzioni:

• Accelerare: disattiva il limite di 30 fps per andare più in fretta
• Mostra rete: mostra la rete neurale in overlay
• Mostra info: mostra un banner con generazione, fitness, numero di specie
• Pausa: mette in pausa l'esecuzione
• Salva/Carica: persiste la popolazione attuale in un file .pop

---

Fonti e riferimenti

Risorsa	Link
Video principale di Laupok	ho creato un'IA che gioca a mario da sola
Video code review + setup	come setuppare l'ia + code source review
Codice sorgente completo	Pastebin Jcvdqhqm
Articolo originale di NEAT	Stanley e Miikkulainen, "Evolving Neural Networks through Augmenting Topologies", 2002
Tutorial di N8Programs	NEAT implementation walkthrough (JavaScript, ma i concetti sono identici)
16blings (ispirazione di Laupok)	AI plays Super Mario World
BizHawk	tasvideos.org/BizHawk
Memoria di Super Mario World	SMW Central - RAM Map

---

Conclusione

Ciò che Laupok ha fatto, è prendere un algoritmo accademico (NEAT, 2002), riscriverlo in Lua per un emulatore (BizHawk), e applicarlo a Super Mario World. Il risultato: un'IA che impara da zero a giocare al gioco, senza alcuna conoscenza previa, solo con mutazioni casuali e selezione naturale.

È un esempio magnifico della potenza degli algoritmi genetici. La ricetta sta in tre ingredienti: la selezione naturale, un po' di Lua, e tanta pazienza. Niente deep learning, niente GPU, niente dati di allenamento enormi.

Il codice è commentato, condiviso, e Laupok ha fatto due video esplicativi: uno per i grandi concetti, uno per il codice. Se il tema ti interessa, tuffati dentro. È più accessibile di quanto sembri.

Laupok hat eine KI gebaut, die Super Mario World allein spielt, so funktioniert es

Laupok hat eine künstliche Intelligenz gebaut, die Super Mario World völlig autonom spielt. Sie startet bei null: Kein vordefiniertes Skript, kein aufgezeichneter Frame. Die KI lernt allein, durch zufällige Mutationen und natürliche Selektion, die Spiellevel zu beenden. Das Projekt läuft auf BizHawk, einem Multi-Plattform-Emulator, via ein Lua-Skript von etwa 4200 Zeilen.

Was dieses Projekt faszinierend macht, ist, dass es auf biologischen Konzepten angewandt auf Informatik beruht: Darwins Evolutionstheorie, künstliche neuronale Netze und vor allem ein spezifischer Algorithmus namens NEAT (NeuroEvolution of Augmenting Topologies). Die KI weiß anfangs nichts über das Spiel. Sie testet zufällige Aktionen, scheitert tausendfach, und nach und nach versteht sie, wie man vorankommt, springt und überlebt.

In diesem Artikel zerlegen wir das alles, Konzept für Konzept, Codezeile für Codezeile.

---

Das Setup: BizHawk, Lua und Super Mario World

Der BizHawk-Emulator

BizHawk ist ein Open-Source-Emulator, der eine Tonne Konsolen unterstützt, NES, SNES, Genesis, PS1, Game Boy und viele mehr. Seine Besonderheit ist, dass er Lua-Skripte parallel zum Spiel starten kann. Diese Skripte haben Zugriff auf den Arbeitsspeicher (RAM) der Emulation, was heißt, dass sie alle Spieldaten live lesen und modifizieren können.

Konkret heißt das, man kann:

• Marios Position im Level lesen
• Wissen, welche Sprites (Gegner, Items) auf dem Bildschirm sind
• Den Zustand jeder Tile (Block) um Mario kennen
• Den Controller steuern, jeden Button drücken

Genau das braucht man, um eine KI spielen zu lassen.

Die Speicheradressen von Super Mario World

Im RAM von Super Mario World liegt jede Dateneinheit an einer spezifischen Adresse. Ein bisschen wie ein Viertel: Jede Adresse entspricht einem "Haus", das eine Information enthält. Zum Beispiel:

Adresse	Daten
0x94-0x95	Marios X-Position (16 Bit, Little-Endian)
0x96-0x97	Marios Y-Position
0x14C8+i	Zustand des Sprites i (>7 = lebend)
0xE4+i	Untere X-Position des Sprites i
0x14E0+i	Obere X-Position des Sprites i
0xD8+i	Untere Y-Position des Sprites i
0x14D4+i	Obere Y-Position des Sprites i
0x170B+i	Typ des Extended Sprites i
0x0100	Spielzustand (12 = Level beendet)
0x13D4	Pause aktiv
0x0071	Marios Todesanimation (9 = tot)
0x1C800+...	Level-Tile-Tabelle

Die Sprite-Position nutzt zwei Bytes: Ein "unteres" und ein "oberes" Byte, weil die Position 255 Pixel übersteigen kann. Die Formel ist immer unten + oben × 256.

Für Tiles ist es komplexer: Die Basisadresse ist 0x1C800, und man berechnet den Offset je nach x- und y-Koordinaten der Tile in der Welt, mit 16 Pixeln Schritt pro Tile.

---

Die Basics: Genetische Algorithmen und neuronale Netze

Bevor wir in den Code tauchen, muss man zwei fundamentale Konzepte verstehen. Ohne sie ergibt der Rest keinen Sinn.

Die genetischen Algorithmen

Ein genetischer Algorithmus ist eine Simulation der Evolutionstheorie. Die zentrale Idee: Man erschafft eine Population von Individuen, jedes mit leicht unterschiedlichen Eigenschaften ("Genen"). Man lässt sie in einer Umgebung "leben". Die, die sich am besten schlagen, überleben und pflanzen sich fort. Die, die sich schlecht schlagen, verschwinden.

Laupok illustriert das mit einer Kirby-Analogie:

• Eine Kirby-Population erscheint auf einem Terrain mit Stacheln und Tomaten
• Die Stacheln nehmen Lebenspunkte, die Tomaten geben welche zurück
• Jeder Kirby hat Gene: Größe, Geschwindigkeit, Lebenspunkte, Verhalten (fliehen, Tomaten suchen, irgendwohin rennen)

• Nach 15 Sekunden schaut man, wer am längsten überlebt hat
• Der beste Kirby pflanzt sich mit den anderen fort: Die Babys erben die Hälfte der Gene des Besten und die Hälfte des "Schlechtesten"
• Die Babys erleiden zufällige Mutationen (etwas größer, etwas schneller...)
• Die alten Kirbys werden durch die neuen ersetzt
• Man startet neu

Nach 180 Generationen (~15 Stunden) gehen die Kirbys von 15 Sekunden Überleben auf 15 Minuten. Sie wurden klein (reduzierte Kollisionszone), schnell und fliehen permanent vor Gefahr.

Der entscheidende Punkt: Man definiert die Lösung nicht. Der Algorithmus findet sie allein. Und genau das macht ihn mächtig für Probleme, bei denen man nicht weiß, welche Parameterkombination optimal wäre.

Die künstlichen neuronalen Netze

Ein neuronales Netz ist ein vereinfachtes mathematisches Modell des menschlichen Gehirns. Es besteht aus:

• Input-Neuronen: Was das Netz "sieht"
• Output-Neuronen: Was das Netz "entscheidet"
• Verbindungen (Gewichte): Jede Verbindung hat ein Gewicht, das das Signal verstärkt oder dämpft

Das Prinzip ist simpel: Jedes Input-Neuron schickt seinen Wert. Er wird mit dem Verbindungsgewicht multipliziert, dann zu den anderen Signalen addiert. Wenn das Ergebnis eine gewisse Schwelle übersteigt (die Aktivierungsfunktion), aktiviert sich das Output-Neuron.

In Laupoks Analogie mit Mario und dem Mäuseende:

• Das Input-Neuron = die Distanz zwischen Mario und dem Ende
• Das Verbindungsgewicht = Marios Sensibilität
• Das Output-Neuron = Mario schreit oder nicht

Je näher das Ende, desto höher der Inputwert. Wenn das Gewicht stark ist, ist das Outputsignal stark, und Mario würde schreien. Indem man das Gewicht ändert, ändert man Marios Sensibilität.

Im echten neuronalen Netz der KI ist es dieselbe Logik, aber in massivem Maßstab:

• 99 Input-Neuronen (11×9 Tiles von Marios Sicht)
• 8 Output-Neuronen (A, B, X, Y, Hoch, Runter, Links, Rechts)
• Versteckte Neuronen (hidden) dazwischen
• Hunderte Verbindungen mit variierten Gewichten

---

NEAT: der Algorithmus, der alles ändert

Das Problem klassischer genetischer Algorithmen

Wenn man einen genetischen Algorithmus naiv mit einem neuronalen Netz kombiniert, hat man ein Problem: Man erschafft 100 völlig verschiedene neuronale Netze und weiß nicht, wie man sie vergleicht. Jedes hat eigene Neuronen, eigene Verbindungen, eigene Gewichte. Wie weiß man, ob zwei Netze "nah" oder "fern" sind?

Hier kommt NEAT ins Spiel, NeuroEvolution of Augmenting Topologies. Erfunden von Kenneth Stanley und Risto Miikkulainen 2002, löst es exakt dieses Problem.

Die Spezies

Der erste Schlüsselmechanismus von NEAT sind die Spezies. Wenn ein neuronales Netz zu verschieden von einem anderen wird, wird es in eine andere Spezies klassifiziert. Die Ähnlichkeit wird via drei Parameter berechnet:

1. Excess (EXCES_COEF = 0.50): Die Zahl der Verbindungen, die gar nichts miteinander zu tun haben (verschiedene Innovationen)
2. Disjoint: Dasselbe, aber für Verbindungen, die in der Mitte liegen
3. Gewichtsdifferenz (POIDSDIFF_COEF = 0.92): Die mittlere Gewichtsdifferenz zwischen Verbindungen mit derselben Innovation

Die Score-Formel:

score = (EXCES_COEF × disjoint) / max(nbConnexions1 + nbConnexions2, 1)
      + POIDSDIFF_COEF × diffPoids

Wenn dieser Score unter DIFF_LIMITE (1.0) liegt, sind beide Netze in derselben Spezies. Sonst erstellt man eine neue Spezies.

Die Innovationen

Das ist NEATs Genie. Jedes Mal, wenn eine Verbindung erstellt wird, erhält sie eine global eindeutige Innovations-Nummer. Diese Nummer folgt dem neuronalen Netz, selbst wenn es sich fortpflanzt.

Konkret erbt ein per Crossover erstelltes Baby die Innovationen seiner Eltern. Wenn zwei Netze dieselbe Innovation teilen, heißt das, dass sie eine Verbindung haben, die vom selben Vorfahren kommt. Das erlaubt, verschieden große Netze zu vergleichen.

Der Crossover

Wenn sich zwei neuronale Netze fortpflanzen, funktioniert der Crossover so:

1. Das leistungsstärkste Netz wird der "dominante Elternteil"
2. Das Baby erbt alle Verbindungen des Dominanten
3. Für jede Verbindung mit derselben Innovation kann der andere Elternteil sie ersetzen (50% Chance)
4. Nur aktive Verbindungen des nicht-dominanten Elternteils können ersetzen

Das garantiert, dass das Baby immer mindestens so gut ist wie der beste Elternteil.

Die Mutationen

Nach dem Crossover erleidet das Baby Mutationen mit konfigurierbaren Wahrscheinlichkeiten:

Mutation	Wahrscheinlichkeit	Effekt
Verbindungsgewicht-Reset	25%	Das Gewicht wird total randomisiert
Gewichts-Mutation	95%	Das Gewicht variiert um ±0.80
Verbindungs-Hinzufügung	85%	Neue Verbindung zwischen zwei noch nicht verbundenen Neuronen
Neuronen-Hinzufügung	39%	Ein verstecktes Neuron wird zwischen zwei verbundenen Neuronen eingefügt

Die Neuronen-Hinzufügungsrate ist wichtig: Sie erlaubt dem Netz zu wachsen. Anfangs gibt es nur Inputs und Outputs. Progressiv erscheinen versteckte Neuronen, was das Netz immer komplexer macht.

---

Der Code: kompletter Walkthrough

Die Konstanten

Das Skript beginnt mit einem Konstantenblock, der das ganze Setting definiert:

-- Marios Sicht um ihn herum
TAILLE_TILE = 16
TAILLE_VUE_W = TAILLE_TILE * 11  -- 176 Pixel Breite
TAILLE_VUE_H = TAILLE_TILE * 9   -- 144 Pixel Höhe
NB_TILE_W = TAILLE_VUE_W / TAILLE_TILE  -- 11 Tiles
NB_TILE_H = TAILLE_VUE_H / TAILLE_TILE  -- 9 Tiles

-- Neuronales Netz
NB_INPUT = NB_TILE_W * NB_TILE_H  -- 99 Inputs (sichtbare Tiles)
NB_OUTPUT = 8  -- A, B, X, Y, Hoch, Runter, Links, Rechts
NB_INDIVIDU_POPULATION = 100  -- Individuen pro Population
NB_NEURONE_MAX = 100000  -- Limit versteckter Neuronen

-- Fitness
FITNESS_LEVEL_FINI = 1000000  -- Wert wenn Level beendet
NB_FRAME_RESET_BASE = 33  -- Frames ohne Fortschritt vor Reset
NB_FRAME_RESET_PROGRES = 300  -- Frames wenn Fortschritt erkannt

-- Spezies
EXCES_COEF = 0.50
POIDSDIFF_COEF = 0.92
DIFF_LIMITE = 1.00

-- Mutationen
CHANCE_MUTATION_RESET_CONNEXION = 0.25
POIDS_CONNEXION_MUTATION_AJOUT = 0.80
CHANCE_MUTATION_POIDS = 0.95
CHANCE_MUTATION_CONNEXION = 0.85
CHANCE_MUTATION_NEURONE = 0.39

Das NB_INPUT ist 99, weil Marios Sicht 11×9 Tiles macht. Jede Tile ist ein Input-Neuron. Wenn die Tile leer ist, ist sie 0 wert. Wenn es ein Block ist, ist sie 1 wert. Wenn es ein Gegner ist, ist sie -1 wert.

Die 8 Outputs entsprechen den SNES-Controller-Buttons: A, B, X, Y, Hoch, Runter, Links, Rechts. Man schließt Start, Select, L und R aus, um seine Entscheidungen aufs Wesentliche zu begrenzen.

Die Datenstrukturen

Das Skript definiert drei Hauptstrukturen:

function newNeurone()
    local neurone = {}
    neurone.valeur = 0    -- aktueller Neuronwert
    neurone.id = 0        -- eindeutige Kennung
    neurone.type = ""     -- "input", "output" oder "hidden"
    return neurone
end

function newConnexion()
    local connexion = {}
    connexion.entree = 0     -- Quellneuron-ID
    connexion.sortie = 0     -- Zielneuron-ID
    connexion.actif = true   -- kann deaktiviert werden wenn ein verstecktes Neuron eingefügt wird
    connexion.poids = 0      -- Verbindungsgewicht
    connexion.innovation = 0 -- eindeutige Innovationsnummer
    connexion.allume = false -- für Anzeige : true wenn Signal durchgeht
    return connexion
end

function newReseau()
    local reseau = {
        nbNeurone = 0,        -- Zahl versteckter Neuronen
        fitness = 1,          -- Leistung (zurückgelegte Distanz)
        idEspeceParent = 0,   -- zu welcher Spezies es gehört
        lesNeurones = {},     -- Neuronentabelle
        lesConnexions = {}    -- Verbindungstabelle
    }
    -- Initialisierung mit Inputs
    for j = 1, NB_INPUT, 1 do
        ajouterNeurone(reseau, j, "input", 1)
    end
    -- Dann Outputs
    for j = NB_INPUT + 1, NB_INPUT + NB_OUTPUT, 1 do
        ajouterNeurone(reseau, j, "output", 0)
    end
    return reseau
end

Anfangs enthält jedes Netz nur Inputs und Outputs: Kein verstecktes Neuron, keine Verbindung. Der Algorithmus entscheidet, ob er welche braucht.

Die Mutationen im Detail

Gewichts-Mutation

function mutationPoidsConnexions(unReseau)
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            if math.random() < CHANCE_MUTATION_RESET_CONNEXION then
                -- 25% : totaler Gewichtsreset
                unReseau.lesConnexions[i].poids = genererPoids()
            else
                -- 75% : Variation um ±0.80
                if math.random() >= 0.5 then
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids - POIDS_CONNEXION_MUTATION_AJOUT
                else
                    unReseau.lesConnexions[i].poids =
                        unReseau.lesConnexions[i].poids + POIDS_CONNEXION_MUTATION_AJOUT
                end
            end
        end
    end
end

Das Initialgewicht ist immer 1 oder -1 (genererPoids()). Die ±0.80-Variation kann es zwischen negativen und positiven Werten oszillieren lassen, was das Netzverhalten radikal ändert.

Verbindungs-Hinzufügung

function mutationAjouterConnexion(unReseau)
    local liste = {}
    -- Randomisierung der Neuronenliste
    for i, v in ipairs(unReseau.lesNeurones) do
        local pos = math.random(1, #liste+1)
        table.insert(liste, pos, v)
    end

    local traitement = false
    for i = 1, #liste, 1 do
        for j = 1, #liste, 1 do
            if i ~= j then
                local n1 = liste[i]
                local n2 = liste[j]
                -- Gültige Verbindung : input→output, hidden→hidden, hidden→output
                if (n1.type == "input" and n2.type == "output") or
                   (n1.type == "hidden" and n2.type == "hidden") or
                   (n1.type == "hidden" and n2.type == "output") then
                    -- Prüfen dass noch keine Verbindung existiert
                    local dejaConnexion = false
                    for k = 1, #unReseau.lesConnexions, 1 do
                        if unReseau.lesConnexions[k].entree == n1.id
                            and unReseau.lesConnexions[k].sortie == n2.id then
                            dejaConnexion = true
                            break
                        end
                    end
                    if dejaConnexion == false then
                        traitement = true
                        ajouterConnexion(unReseau, n1.id, n2.id)
                    end
                end
            end
            if traitement then break end
        end
        if traitement then break end
    end
end

Man kann keinen Output mit einem Input verbinden (das würde einen Zyklus erzeugen), und man kann keine zwei schon verbundenen Neuronen verbinden. Die Randomisierung garantiert, dass man jedes Mal verschiedene Möglichkeiten erkundet.

Neuronen-Hinzufügung

Das ist die interessanteste Mutation:

function mutationAjouterNeurone(unReseau)
    if #unReseau.lesConnexions == 0 then return nil end
    if unReseau.nbNeurone == NB_NEURONE_MAX then return nil end

    -- Randomisierung der Verbindungen
    local listeRandom = {}
    for i = 1, #unReseau.lesConnexions, 1 do
        local pos = math.random(1, #listeRandom+1)
        table.insert(listeRandom, pos, i)
    end

    for i = 1, #listeRandom, 1 do
        if unReseau.lesConnexions[listeRandom[i]].actif then
            -- Existierende Verbindung deaktivieren
            unReseau.lesConnexions[listeRandom[i]].actif = false
            unReseau.nbNeurone = unReseau.nbNeurone + 1
            local indice = unReseau.nbNeurone + NB_INPUT + NB_OUTPUT

            -- Verstecktes Neuron erstellen
            ajouterNeurone(unReseau, indice, "hidden", 1)

            -- Input mit verstecktem Neuron verbinden
            ajouterConnexion(unReseau,
                unReseau.lesConnexions[listeRandom[i]].entree,
                indice, genererPoids())

            -- Verstecktes Neuron mit Output verbinden
            ajouterConnexion(unReseau,
                indice,
                unReseau.lesConnexions[listeRandom[i]].sortie,
                genererPoids())
            break
        end
    end
end

Der Mechanismus: Man nimmt eine existierende Verbindung, deaktiviert sie und fügt ein verstecktes Neuron in der Mitte ein. Die Ursprungsverbindung wird durch zwei neue ersetzt: Input→hidden und hidden→Output. Als schneide man ein Kabel durch, um einen Schalter dazwischenzusetzen.

Das macht NEAT "augmenting topologies": Das Netz wächst mit der Zeit. Es startet simpel und wird nur komplex, wenn nötig.

Das FeedForward

Das ist die Funktion, die Signale durchs Netz propagiert:

function feedForward(unReseau)
    -- Reset der Output-Neuronen
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur = 0
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].allume = false
        end
    end

    -- Propagation
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local avantTraitement = unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur
            unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur =
                unReseau.lesNeurones[unReseau.lesConnexions[i].entree].valeur *
                unReseau.lesConnexions[i].poids +
                unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur

            if avantTraitement ~= unReseau.lesNeurones[unReseau.lesConnexions[i].sortie].valeur then
                unReseau.lesConnexions[i].allume = true
            else
                unReseau.lesConnexions[i].allume = false
            end
        end
    end
end

Jede aktive Verbindung schickt Inputwert × Gewicht zum Output-Neuron. Der Wert wird kumuliert (addiert). Das allume-Flag ist nur für die visuelle Netzanzeige.

Das Lesen des Spielspeichers

Die Funktion getLesInputs() übersetzt die Super-Mario-World-Welt in netzverständliche Daten:

function getLesInputs()
    local lesInputs = {}
    -- Initialisierung auf 0 (grau = nichts)
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            lesInputs[getIndiceLesInputs(i, j)] = 0
        end
    end

    -- Die Sprites (Gegner) = -1 (schwarz)
    local lesSprites = getLesSprites()
    for i = 1, #lesSprites, 1 do
        local input = convertirPositionPourInput(getLesSprites()[i])
        if input.x > 0 and input.x < (TAILLE_VUE_W / TAILLE_TILE) + 1 then
            lesInputs[getIndiceLesInputs(input.x, input.y)] = -1
        end
    end

    -- Die Tiles (Blöcke) = Tile-Wert (weiß wenn > 0)
    local lesTiles = getLesTiles()
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local indice = getIndiceLesInputs(i, j)
            if lesTiles[indice] ~= 0 then
                lesInputs[indice] = lesTiles[indice]
            end
        end
    end

    return lesInputs
end

Das Input-Grid ist eine auf Mario zentrierte Sicht: 11 Tiles breit, 9 hoch. Jede Tile ist wert:

• 0 (grau): nichts
• 1 (weiß): solider Block
• -1 (schwarz): Gegner

Gegner werden aus zwei RAM-Listen gelesen: Normale Sprites (0x14C8-0x14F8) und Extended Sprites (0x170B-0x173B). Für jeden lebenden Sprite (Zustand > 7) berechnet man seine Tile-Position relativ zu Mario und setzt -1 ins entsprechende Feld.

Die Fitness: wie die KI weiß, ob sie vorankommt

function majReseau(unReseau, marioBase)
    local mario = getPositionMario()

    if not niveauFini and memory.readbyte(0x0100) == 12 then
        -- Level beendet !
        unReseau.fitness = FITNESS_LEVEL_FINI
        niveauFini = true
    elseif marioBase.x < mario.x then
        -- Mario geht nach rechts voran
        unReseau.fitness = unReseau.fitness + (mario.x - marioBase.x)
        marioBase.x = mario.x
    end

    -- Input-Update
    local lesInputs = getLesInputs()
    for i = 1, NB_INPUT, 1 do
        unReseau.lesNeurones[i].valeur = lesInputs[i]
    end
end

Die Fitness ist simpel: Es ist die nach rechts zurückgelegte Distanz. Wenn Mario 10 Pixel vorankommt, steigt die Fitness um 10. Wenn Mario zurückgeht, passiert nichts (keine Penalty). Wenn das Level beendet ist (Adresse 0x0100 == 12), wird die Fitness 1.000.000.

Absichtlich simpel. Nur Fortschritt nach rechts zählt: Gegner töten bringt nichts, Sterben kostet nichts.

Der intelligente Reset

Wenn sich Mario 33 Frames nicht bewegt, resettet man das Level und geht zum nächsten Individuum. Aber wenn Mario Fortschritt gemacht hat (seine aktuelle Fitness unterscheidet sich von der am Anfang), wartet man 300 Frames, das gibt dem Netz eine Chance zu "verstehen", was es gut gemacht hat.

if fitnessAvant == laPopulation[idPopulation].fitness
   and memory.readbyte(0x13D4) == 0 then
    nbFrameStop = nbFrameStop + 1
    local nbFrameReset = NB_FRAME_RESET_BASE
    if fitnessInit ~= laPopulation[idPopulation].fitness
       and memory.readbyte(0x0071) ~= 9 then
        nbFrameReset = NB_FRAME_RESET_PROGRES
    end
    if nbFrameStop > nbFrameReset then
        nbFrameStop = 0
        lancerNiveau()
        idPopulation = idPopulation + 1
        -- ...
    end
end

Die Bedingung memory.readbyte(0x0071) ~= 9 prüft, dass Mario nicht in Todesanimation ist. Der Reset wird unnütz, wenn Mario schon in Todesanimation ist.

Die Hauptschleife

Die Schleife läuft mit 30 fps (Super Mario Worlds normale Geschwindigkeit):

while true do
    local fitnessAvant = laPopulation[idPopulation].fitness

    -- Anzeige (Netz, Infos)
    if forms.ischecked(estAccelere) then
        emu.limitframerate(false)  -- beschleunigen
    else
        emu.limitframerate(true)   -- 30 fps
    end

    -- Die 3 vitalen Funktionen
    majReseau(laPopulation[idPopulation], marioBase)
    feedForward(laPopulation[idPopulation])
    appliquerLesBoutons(laPopulation[idPopulation])

    emu.frameadvance()
    nbFrame = nbFrame + 1

    -- Reset wenn kein Fortschritt
    -- ...
    -- Neue Generation wenn alle Individuen getestet
    -- ...
end

Die drei vitalen Funktionen sind majReseau, feedForward und appliquerLesBoutons. Wenn man nur eine deaktiviert, bewegt sich Mario nicht mehr.

Der Crossover

function crossover(unReseau1, unReseau2)
    local leReseau = newReseau()
    local leBon = unReseau1
    local leNul = unReseau2

    if leBon.fitness < leNul.fitness then
        leBon = unReseau2
        leNul = unReseau1
    end

    leReseau = copier(leBon)

    for i = 1, #leReseau.lesConnexions, 1 do
        for j = 1, #leNul.lesConnexions, 1 do
            if leReseau.lesConnexions[i].innovation == leNul.lesConnexions[j].innovation
               and leNul.lesConnexions[j].actif then
                if math.random() > 0.5 then
                    leReseau.lesConnexions[i] = leNul.lesConnexions[j]
                end
            end
        end
    end
    leReseau.fitness = 1
    return leReseau
end

Das Baby erbt vom besten Elternteil. Für jede Verbindung mit derselben Innovation hat der andere Elternteil 50% Chance zu ersetzen, aber nur wenn die Verbindung aktiv ist. Ein wichtiger Fix: Ohne das konnten nutzlose versteckte Neuronen erstellt werden.

Die Spezies-Selektion

function nouvelleGeneration(laPopulation, lesEspeces)
    local laNouvellePopulation = newPopulation()
    local nbIndividuACreer = NB_INDIVIDU_POPULATION

    -- Mittlere Fitness pro Spezies berechnen
    for i = 1, #lesEspeces, 1 do
        lesEspeces[i].fitnessMoyenne = 0
        for j = 1, #lesEspeces[i].lesReseaux, 1 do
            lesEspeces[i].fitnessMoyenne =
                lesEspeces[i].fitnessMoyenne + lesEspeces[i].lesReseaux[j].fitness
        end
        lesEspeces[i].fitnessMoyenne =
            lesEspeces[i].fitnessMoyenne / #lesEspeces[i].lesReseaux
    end

    -- Jede Spezies erstellt Kinderzahl proportional zu ihrer mittleren Fitness
    for i = 1, #lesEspeces, 1 do
        local nbEnfant = math.ceil(
            #lesEspeces[i].lesReseaux *
            lesEspeces[i].fitnessMoyenne / fitnessMoyenneGlobal)

        for j = 1, nbEnfant, 1 do
            local unReseau = crossover(
                choisirParent(lesEspeces[i].lesReseaux),
                choisirParent(lesEspeces[i].lesReseaux))
            mutation(unReseau)
            laNouvellePopulation[indiceNouvelleEspece] = copier(unReseau)
        end
    end
end

Die Idee: Eine Spezies mit mittlerer Fitness 10.000 darf viel mehr Kinder erstellen als eine mit mittlerer Fitness 1. Das ist natürliche Selektion in Aktion.

Das choisirParent nutzt Roulette-Selektion: Je mehr Fitness ein Individuum hat, desto höher seine Chance, als Elternteil selektiert zu werden.

Das Speichern und Laden

Populationen werden in .pop-Dateien gespeichert:

function sauvegarderUnReseau(unReseau, fichier)
    io.write(unReseau.nbNeurone .. "\n")
    io.write(#unReseau.lesConnexions .. "\n")
    io.write(unReseau.fitness .. "\n")
    for i = 1, unReseau.nbNeurone, 1 do
        local indice = NB_INPUT + NB_OUTPUT + i
        io.write(unReseau.lesNeurones[indice].id .. "\n")
    end
    for i = 1, #unReseau.lesConnexions, 1 do
        local actif = 1
        if unReseau.lesConnexions[i].actif ~= true then actif = 0 end
        io.write(actif .. "\n" ..
            unReseau.lesConnexions[i].entree .. "\n" ..
            unReseau.lesConnexions[i].sortie .. "\n" ..
            unReseau.lesConnexions[i].poids .. "\n" ..
            unReseau.lesConnexions[i].innovation .. "\n")
    end
end

Das Speichern schließt auch das beste Individuum aller vorherigen Populationen ein. Wenn das Beste der alten Population besser ist als das Beste der neuen, nimmt man das alte als Basis wieder. Eine Form von Elitismus: Man verliert nie das Beste.

Das Netzzeichnen

Laupok hat einen neuronalen Netz-Visualisierer als Spiel-Overlay hinzugefügt:

function dessinerUnReseau(unReseau)
    -- Inputs : 11×9-Grid um Mario
    for i = 1, NB_TILE_W, 1 do
        for j = 1, NB_TILE_H, 1 do
            local xT = ENCRAGE_X_INPUT + (i - 1) * TAILLE_INPUT
            local yT = ENCRAGE_Y_INPUT + (j - 1) * TAILLE_INPUT
            local couleurFond = "gray"
            if unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur < 0 then
                couleurFond = "black"   -- Gegner
            elseif unReseau.lesNeurones[getIndiceLesInputs(i, j)].valeur > 0 then
                couleurFond = "white"   -- Block
            end
            gui.drawRectangle(xT, yT, TAILLE_INPUT, TAILLE_INPUT, "black", couleurFond)
        end
    end

    -- Outputs : 8 Buttons
    for i = 1, NB_OUTPUT, 1 do
        local xT = ENCRAGE_X_OUTPUT
        local yT = ENCRAGE_Y_OUTPUT + ESPACE_Y_OUTPUT * (i - 1)
        if sigmoid(unReseau.lesNeurones[i + NB_INPUT].valeur) then
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "white")
        else
            gui.drawRectangle(xT, yT, TAILLE_OUTPUT_W, TAILLE_OUTPUT_H, "white", "black")
        end
    end

    -- Verbindungen
    for i = 1, #unReseau.lesConnexions, 1 do
        if unReseau.lesConnexions[i].actif then
            local alpha = 25
            if unReseau.lesConnexions[i].allume then alpha = 255 end
            local couleur = forms.createcolor(255, 255, 255, alpha)
            gui.drawLine(
                lesPositions[unReseau.lesConnexions[i].entree].x,
                lesPositions[lesConnexions[i].entree].y,
                lesPositions[unReseau.lesConnexions[i].sortie].x,
                lesPositions[lesConnexions[i].sortie].y,
                couleur)
        end
    end
end

Super nützlich, um zu verstehen, was das Netz tut. Aktive Verbindungen sind weiß, inaktive semi-transparent. Inputs sind ein Grid weiß/schwarz/grauer Felder. Outputs zeigen, welche Buttons gedrückt sind.

---

Die Ergebnisse

Was die KI gelernt hat

Im Laufe stunden- (und tage-) langer Läufe hat die KI allein entdeckt:

1. Nach rechts vorankommen: Das basischste Verhalten, erfordert aber, den Rechts-Button gedrückt zu halten
2. Über Gegner springen: Indem man einen "Gegner erkannt"-Input mit Button A oder B verbindet
3. Hindernissen ausweichen: Manche Netze lernten, temporär zurückzuweichen, um besser voranzukommen
4. Level beenden: Das beste Individuum konnte Super Mario Worlds erstes Level beenden

Die Grenzen

Das Projekt hat seine Grenzen:

• Ein einziges Level: Die KI ist auf ein spezifisches Level trainiert. Sie generalisiert nicht automatisch auf andere Level
• Trainingszeit: Es braucht Dutzende Stunden, um befriedigende Ergebnisse zu erreichen
• Kein Verständnis: Die KI "versteht" nicht, was sie tut. Sie optimiert eine Fitnessfunktion (zurückgelegte Distanz) via Zufallsmutationen
• T-Bagging: Laupok merkt an, dass Mario dazu neigt, auf der Stelle zu springen, wenn er einen Gegner sieht, einfach weil das die Fitness erhöht (er kommt springend etwas voran)

---

Das Experiment reproduzieren

Laupok hat alles geteilt. Hier die Schritte:

1. BizHawk herunterladen auf tasvideos.org (Download-Bereich)
2. Eine USA-ROM von Super Mario World besorgen (Privatkopie deiner eigenen Cartridge)
3. Das Lua-Skript herunterladen von Pastebin, umbenennen zu mario.lua
4. Das Skript in denselben Ordner wie die ROM legen
5. BizHawk starten, die ROM öffnen
6. In der Lua-Konsole: dofile("mario.lua") oder via Menü Skript > Skript öffnen
7. Einen State am Levelanfang speichern (Menü Savestate > State speichern) und debut.state nennen
8. Das Skript neu starten, es geht

Das Skript enthält ein Formular mit Optionen:

• Beschleunigen: Deaktiviert das 30-fps-Limit, um schneller zu gehen
• Netz anzeigen: Zeigt das neuronale Netz als Overlay
• Infos anzeigen: Zeigt ein Banner mit Generation, Fitness, Spezieszahl
• Pause: Pausiert die Ausführung
• Speichern/Laden: Persistiert die aktuelle Population in einer .pop-Datei

---

Quellen und Referenzen

Ressource	Link
Laupoks Hauptvideo	Ich habe eine KI gebaut, die Mario allein spielt
Video Code-Review + Setup	KI-Setup + Quellcode-Review
Kompletter Quellcode	Pastebin Jcvdqhqm
Originaler NEAT-Artikel	Stanley & Miikkulainen, "Evolving Neural Networks through Augmenting Topologies", 2002
N8Programs-Tutorial	NEAT implementation walkthrough (JavaScript, aber Konzepte identisch)
16blings (Laupoks Inspiration)	AI plays Super Mario World
BizHawk	tasvideos.org/BizHawk
Super-Mario-World-Speicher	SMW Central - RAM Map

---

Fazit

Was Laupok gemacht hat, ist einen akademischen Algorithmus (NEAT, 2002) nehmen, ihn in Lua für einen Emulator (BizHawk) neu schreiben und auf Super Mario World anwenden. Das Ergebnis: Eine KI, die von null lernt, das Spiel zu spielen, ohne jegliches Vorwissen, nur durch Zufallsmutationen und natürliche Selektion.

Ein wunderschönes Beispiel für die Macht genetischer Algorithmen. Das Rezept passt in drei Zutaten: Natürliche Selektion, etwas Lua und viel Geduld. Kein Deep Learning, keine GPU, keine massiven Trainingsdaten.

Der Code ist kommentiert, geteilt, und Laupok hat zwei Erklärvideos gemacht, eines für die großen Konzepte, eines für den Code. Wenn dich das Thema interessiert, tauch ein. Zugänglicher, als es scheint.