From 444b2b5abfbb70473b0785b38eaba1df4197ae69 Mon Sep 17 00:00:00 2001 From: sanine Date: Sun, 12 Nov 2023 05:17:19 -0600 Subject: refactor genome to include size information --- src/genome/genome.js | 95 ++++++++++-------------- src/genome/genome.test.js | 185 +++++++++++++++++++++++++--------------------- src/mind/topology.js | 4 +- src/simulation/game.js | 22 +++--- src/simulation/senses.js | 3 +- src/simulation/trial.js | 12 +++ 6 files changed, 169 insertions(+), 152 deletions(-) create mode 100644 src/simulation/trial.js diff --git a/src/genome/genome.js b/src/genome/genome.js index bc569ff..20974fc 100644 --- a/src/genome/genome.js +++ b/src/genome/genome.js @@ -5,38 +5,25 @@ import { network } from '../mind/topology.js'; // check if a given genome is valid and compute its size -export function get_size(num_input, num_output, genome) { - const [ max_index, max_weight ] = genome.reduce( - ([max_index, max_weight ], [ source, sink, weight]) => [ - Math.max(max_index, source, sink), - Math.max(max_weight, Math.abs(weight)), - ], - [ 0, 0 ] +export function validate_genome(genome) { + const { n_input, n_internal, n_output } = genome; + console.log(n_input + n_internal); + return genome.genes.reduce( + (acc, [source, sink, weight]) => acc && ( + (source < n_input+n_internal) && + (sink >= n_input) + ), + true ); - - if (max_index < num_input + num_output - 1) { - return -1; - } - else if (max_weight > 4.0) { - return -1; - } - else { - return max_index + 1; - } } - // parse a genome into a useable neural net -export function parse_genome(num_input, num_output, genome) { - const size = get_size(num_input, num_output, genome); - if (size < 0) { - // bad genome - throw new Error('invalid genome sequence!'); - } +export function parse_genome(genome) { + const { n_input, n_internal, n_output } = genome; - const n = genome.reduce( + const n = genome.genes.reduce( (acc, [source, sink, weight]) => acc.connect(source, sink, weight), - network(num_input, size-num_input-num_output, num_output) + network(n_input, n_internal, n_output) ); return n; @@ -100,27 +87,26 @@ export function mut_gene_weight(weight_max, gene, r) { // expand the size of the neural net encoded by the genome // relabels internal indices so that there is one extra internal neuron -export function mut_genome_expand( - [n_input, n_internal, n_output, genome], r -) { - const expand_index = Math.floor(n_internal * r) + n_input; - const new_genome = genome.map(([source, sink, weight]) => [ +export function mut_genome_expand(genome, r) { + const expand_index = Math.floor(genome.n_internal * r) + genome.n_input; + const new_genes = genome.genes.map(([source, sink, weight]) => [ source >= expand_index ? source+1 : source, sink >= expand_index ? sink+1 : sink, weight, ]); - return [ - n_input, n_internal+1, n_output, new_genome, - ]; + return { + ...genome, + n_internal: genome.n_internal+1, + genes: new_genes, + }; } // contract the size of the neural net encoded by the genome // relabels internal indices so that there is one less internal neuron -export function mut_genome_contract( - [n_input, n_internal, n_output, genome], r -) { +export function mut_genome_contract(genome, r) { + const { n_input, n_internal, n_output } = genome; const contract_idx = Math.floor(n_internal * r) + n_input; // decrement sources on the contract index too, to prevent invalid genomes @@ -128,42 +114,39 @@ export function mut_genome_contract( // decrement sinks only after the contract index const new_sink = (sink) => sink > contract_idx ? sink-1 : sink; - const new_genome = genome.map(([source, sink, weight]) => [ + const new_genes = genome.genes.map(([source, sink, weight]) => [ new_source(source), new_sink(sink), weight, ]); - return [ - n_input, n_internal-1, n_output, new_genome - ]; + return { + ...genome, + n_internal: n_internal-1, + genes: new_genes, + }; } // append a newly generated gene to the end of the genome -export function mut_genome_insert( - [n_input, n_internal, n_output, genome], - weight_max, - r1, r2, r3 -) { +export function mut_genome_insert(genome, weight_max, r1=Math.random(), r2=Math.random(), r3=Math.random()) { + const { n_input, n_internal, n_output } = genome; const source = Math.floor((n_input + n_internal) * r1); const sink = Math.floor((n_internal + n_output) * r2) + n_input; const weight = weight_max * ((2*r3)-1); - return [ - n_input, n_internal, n_output, - [...genome, [source, sink, weight]], - ]; + return { + ...genome, + genes: [...genome.genes, [source, sink, weight]], + }; } // delete a gene from the genome -export function mut_genome_delete( - [n_input, n_internal, n_output, genome], r -) { - const del_idx = Math.floor(r * genome.length); - const new_genome = genome.filter((_, idx) => idx != del_idx); - return [n_input, n_internal, n_output, new_genome]; +export function mut_genome_delete(genome, r) { + const del_idx = Math.floor(r * genome.genes.length); + const genes = genome.genes.filter((_, idx) => idx != del_idx); + return { ...genome, genes }; } diff --git a/src/genome/genome.test.js b/src/genome/genome.test.js index 37bdacc..bc64e4e 100644 --- a/src/genome/genome.test.js +++ b/src/genome/genome.test.js @@ -1,7 +1,14 @@ 'use strict'; +// genome structure +// { +// genes: gene[] +// n_input, n_internal, n_output +// } + + import { - get_size, + validate_genome, parse_genome, mut_gene_source, mut_gene_sink, @@ -13,20 +20,39 @@ import { } from './genome'; -test('genome validation and size', () => { - expect(get_size(0, 0, [ [ 0, 0, 1.0 ] ])).toBe(1); - expect(get_size(2, 1, [ [ 0, 2, 1 ] ])).toBe(3); - expect(get_size(2, 1, [ [ 0, 1, 1 ] ])).toBe(-1); - expect(get_size(2, 1, [ [ 0, 2, 5 ] ])).toBe(-1); +test('genome validation', () => { + expect(validate_genome({ + n_input: 0, n_internal: 1, n_output: 0, + genes: [[0, 0, 1.0]], + })).toBe(true); + expect(validate_genome({ + n_input: 2, n_internal: 0, n_output: 1, + genes: [[0, 2, 1]], + })).toBe(true); + expect(validate_genome({ + n_input: 2, n_internal: 0, n_output: 1, + genes: [[2, 0, 1]], + })).toBe(false); + expect(validate_genome({ + n_input: 2, n_internal: 0, n_output: 1, + genes: [[2, 2, 1]], + })).toBe(false); + expect(validate_genome({ + n_input: 2, n_internal: 1, n_output: 1, + genes: [[3, 2, 1]], + })).toBe(false); }); test('parse a genome into a neural net', () => { - const n = parse_genome(1, 1, [ - [0, 1, 1], - [1, 1, 1], - [1, 2, 1] - ]); + const n = parse_genome({ + n_input: 1, n_internal: 1, n_output: 1, + genes: [ + [0, 1, 1], + [1, 1, 1], + [1, 2, 1] + ] + }); expect(n.input_count).toBe(1); expect(n.output_count).toBe(1); @@ -121,48 +147,45 @@ test('expand genome', () => { const n_internal = 3; const n_output = 1; - const genome = [ - [0, 1, 0], - [1, 2, 0], - [2, 3, 0], - [3, 4, 0], - ]; - - expect(mut_genome_expand([ - n_input, n_internal, n_output, genome - ], 0.0)).toEqual([ - n_input, n_internal+1, n_output, - [ + const genome = { + n_input, n_internal, n_output, + genes: [ + [0, 1, 0], + [1, 2, 0], + [2, 3, 0], + [3, 4, 0], + ], + }; + + expect(mut_genome_expand(genome, 0.0)).toEqual({ + n_input, n_internal: n_internal+1, n_output, + genes: [ [0, 2, 0], [2, 3, 0], [3, 4, 0], [4, 5, 0], ], - ]); + }); - expect(mut_genome_expand([ - n_input, n_internal, n_output, genome - ], 0.5)).toEqual([ - n_input, n_internal+1, n_output, - [ + expect(mut_genome_expand(genome, 0.5)).toEqual({ + n_input, n_internal: n_internal+1, n_output, + genes: [ [0, 1, 0], [1, 3, 0], [3, 4, 0], [4, 5, 0], ], - ]); + }); - expect(mut_genome_expand([ - n_input, n_internal, n_output, genome - ], 0.99)).toEqual([ - n_input, n_internal+1, n_output, - [ + expect(mut_genome_expand(genome, 0.99)).toEqual({ + n_input, n_internal: n_internal+1, n_output, + genes: [ [0, 1, 0], [1, 2, 0], [2, 4, 0], [4, 5, 0], ], - ]); + }); }); @@ -171,48 +194,45 @@ test('contract genome', () => { const n_internal = 3; const n_output = 1; - const genome = [ - [0, 1, 0], - [1, 2, 1], - [2, 3, 2], - [3, 4, 3], - ]; - - expect(mut_genome_contract([ - n_input, n_internal, n_output, genome - ], 0.0)).toEqual([ - n_input, n_internal-1, n_output, - [ + const genome = { + n_input, n_internal, n_output, + genes: [ + [0, 1, 0], + [1, 2, 1], + [2, 3, 2], + [3, 4, 3], + ], + }; + + expect(mut_genome_contract(genome, 0.0)).toEqual({ + n_input, n_internal: n_internal-1, n_output, + genes: [ [0, 1, 0], [0, 1, 1], [1, 2, 2], [2, 3, 3], ], - ]); + }); - expect(mut_genome_contract([ - n_input, n_internal, n_output, genome - ], 0.5)).toEqual([ - n_input, n_internal-1, n_output, - [ + expect(mut_genome_contract(genome, 0.5)).toEqual({ + n_input, n_internal: n_internal-1, n_output, + genes: [ [0, 1, 0], [1, 2, 1], [1, 2, 2], [2, 3, 3], ], - ]); + }); - expect(mut_genome_contract([ - n_input, n_internal, n_output, genome - ], 0.99)).toEqual([ - n_input, n_internal-1, n_output, - [ + expect(mut_genome_contract(genome, 0.99)).toEqual({ + n_input, n_internal: n_internal-1, n_output, + genes: [ [0, 1, 0], [1, 2, 1], [2, 3, 2], [2, 3, 3], ], - ]); + }); }); @@ -223,21 +243,21 @@ test('insert new genes', () => { const n_output = 1; const weight_max = 4; - expect(mut_genome_insert([ + expect(mut_genome_insert({ n_input, n_internal, n_output, - [] - ], weight_max, 0, 0.5, 0)).toEqual([ + genes: [] + }, weight_max, 0, 0.5, 0)).toEqual({ n_input, n_internal, n_output, - [[0, 2, -4]] - ]); + genes: [[0, 2, -4]] + }); - expect(mut_genome_insert([ + expect(mut_genome_insert({ n_input, n_internal, n_output, - [[0, 2, -4]] - ], weight_max, 0.99, 0, 1)).toEqual([ + genes: [[0, 2, -4]] + }, weight_max, 0.99, 0, 1)).toEqual({ n_input, n_internal, n_output, - [[0, 2, -4], [2, 1, 4]] - ]); + genes: [[0, 2, -4], [2, 1, 4]] + }); }); @@ -245,21 +265,18 @@ test('remove genes', () => { const n_input = 0; const n_output = 0; const n_internal = 3; - const genome = [ - [0, 1, 0], [1, 2, 0], - ]; + const genome = { + n_input, n_internal, n_output, + genes: [[0, 1, 0], [1, 2, 0]], + }; - expect(mut_genome_delete([ - n_input, n_internal, n_output, genome - ], 0.0)).toEqual([ + expect(mut_genome_delete(genome, 0.0)).toEqual({ n_input, n_internal, n_output, - [[1, 2, 0]], - ]); + genes: [[1, 2, 0]], + }); - expect(mut_genome_delete([ - n_input, n_internal, n_output, genome - ], 0.99)).toEqual([ + expect(mut_genome_delete(genome, 0.99)).toEqual({ n_input, n_internal, n_output, - [[0, 1, 0]], - ]); + genes: [[0, 1, 0]], + }); }); diff --git a/src/mind/topology.js b/src/mind/topology.js index 9c5ecf7..9f2569d 100644 --- a/src/mind/topology.js +++ b/src/mind/topology.js @@ -49,11 +49,11 @@ function is_hidden(n, index) { export function network_connect(n, source, sink, weight) { if (is_input(n, sink)) { // inputs cannot be sinks - throw new Error("attempt to use input as sink"); + throw new Error(`attempt to use input as sink (${source} -> ${sink})`); } if (is_output(n, source)) { // outputs cannot be sources - throw new Error("attempt to use output as source"); + throw new Error(`attempt to use output as source (${source} -> ${sink})`); } return create({ diff --git a/src/simulation/game.js b/src/simulation/game.js index 20c5e4e..f95fbc4 100644 --- a/src/simulation/game.js +++ b/src/simulation/game.js @@ -2,10 +2,13 @@ import { random_choice, apply, shuffle } from '../util.js'; +import { mut_genome_insert, parse_genome } from '../genome/genome.js'; +import { world_update } from '../world/world.js'; import { senses } from './senses.js'; import { actions } from './actions.js'; import { lattice_rules } from './lattice_rules.js'; import { validity } from './validity.js'; +import { postprocess } from './postprocess.js'; function is_wall(size, x, y) { @@ -89,22 +92,22 @@ export function create_world(size, teams) { // games // } +const N_INPUT = senses.reduce((acc, sense) => acc + sense.size, 0); +const N_OUTPUT = actions.reduce((acc, action) => acc + action.size, 0); +const MAX_MUTATIONS = 15; + let agent_id = 0; export function create_agent(genome, n_internal) { return { id: agent_id++, // !!!! side effect !!!! - net: parse_genome, + net: parse_genome(N_INPUT, N_OUTPUT, genome), state: [...Array(n_internal)].map(_ => (2*Math.random()) - 1), } } -const N_INPUT = senses.reduce((acc, sense) => acc + sense.size, 0); -const N_OUTPUT = actions.reduce((acc, action) => acc + action.size, 0); -const MAX_MUTATIONS = 15; - export function create_team(size, genome_size, n_internal) { const genome = apply( @@ -112,6 +115,7 @@ export function create_team(size, genome_size, n_internal) { genome_size, [N_INPUT, n_internal, N_OUTPUT, []], ).slice(-1)[0]; + console.log(N_INPUT, N_OUTPUT, genome); const agents = [...Array(size)].map(_ => create_agent(genome, n_internal)); return { agents, genome, score: 0, games: 0 }; @@ -149,7 +153,7 @@ export function child_team(team, keep=Math.floor(team.size/2)) { export function create_game(teams, team_indices) { - const world = create_world(999, team_indices.map(i => teams[i].agents)); + const world = create_world(100, team_indices.map(i => teams[i].agents)); return { world, team_indices, time: 0 }; } @@ -157,7 +161,7 @@ export function create_game(teams, team_indices) { export function step_game(game) { return { ...game, - world: world_update(world, postprocess), + world: world_update(game.world, postprocess), time: game.time + 1, }; } @@ -202,7 +206,7 @@ function random_indices(teams) { acc.splice(idx, 1); return acc; }, - teams.keys() + [...teams.keys()] ); } @@ -239,7 +243,7 @@ export function update_epoch(epoch) { return [...Array(count > 0 ? count : 1)].map(x => team) }) .flat(); - const new_teams = [...Array(epoch.teams.length] + const new_teams = [...Array(epoch.teams.length)] .reduce((acc) => child_team(random_choice(source_teams)), []); return create_epoch(new_teams); } diff --git a/src/simulation/senses.js b/src/simulation/senses.js index 23775b6..ca07442 100644 --- a/src/simulation/senses.js +++ b/src/simulation/senses.js @@ -157,7 +157,7 @@ const see = { const [x, y] = vision_idx_to_world_pos(world, agent, idx); return see_cell(world, x, y); }); - return world.agents.reduce( + const result = world.agents.reduce( (acc, a) => { const idx = world_pos_to_vision_idx(world, agent, a.x, a.y); if (idx < 0 || idx > VIS_WIDTH*VIS_HEIGHT) { @@ -169,6 +169,7 @@ const see = { }, vision ); + return result; }, }; diff --git a/src/simulation/trial.js b/src/simulation/trial.js new file mode 100644 index 0000000..3dedf01 --- /dev/null +++ b/src/simulation/trial.js @@ -0,0 +1,12 @@ +'use strict'; + +import { create_team, create_epoch, update_epoch } from './game.js'; + +const start_teams = [...Array(50)].map(x => create_team(32, 5, 5)); + +let epoch = create_epoch(start_teams); + +while (epoch.epoch < 1) { + console.log('update'); + epoch = update_epoch(epoch); +} -- cgit v1.2.1