path: root/src/simulation/game.js

'use strict';


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) {
  return (
    x === 0 || x === size-1 ||
    y === 0 || y === size-1
  );
}
function is_corner(size, x, y) {
  const subsize = Math.floor(size/3);
  return (
    (x < subsize || x >= 2*subsize) &&
    (y < subsize || y >= 2*subsize)
  );
}
export function get_team(size, x, y) {
  const subsize = Math.floor(size/3);
  if (y < subsize) {
    return 0;
  } else if (x >= 2*subsize) {
    return 1;
  } else if (y >= 2*subsize) {
    return 2;
  } else if (x < subsize) {
    return 3;
  } else {
    return undefined;
  }
}

export function setup_board(size) {
  const lattice = [...Array(size)]
    .map(() => [...Array(size)])
    .map((row, y) => row.map((_, x) => {
      if (is_wall(size, x, y)) {
        return { type: 'immutable', flags: {} };
      } else if (is_corner(size, x, y)) {
        return { type: 'immutable', flags: {} };
      } else {
        const team = get_team(size, x, y);
        return { type: 'empty', flags: { team } };
      }
    }));
  return lattice;
}


export function create_world(size, teams) {
  const lattice = setup_board(size);

  const agents = teams.reduce(
    (agents, team, team_num) => {
      const team_cells = lattice.map((row, y) => row.map((cell, x) => [x, y, cell])).flat()
        // only check cells with the right team
        .filter(([x, y, cell]) => cell.type === 'empty' && cell.flags.team === team_num)
      return agents.concat(team.reduce(
        (acc, agent) => {
          const available_cells = team_cells.filter(([x, y, cell]) => acc.reduce(
            (occupied, a) => occupied && ((a.x !== x) || (a.y !== y)),
            true
          ))
          const [x, y, ..._] = random_choice(available_cells);
          const orientation = random_choice([ 'n', 'e', 's', 'w' ]);
          return [...acc, {...agent, x, y, flags: { ...agent.flags, orientation } }];
        },
        []
      ));
    },
    []
  ).flat();

  return { lattice, lattice_rules, agents, actions, senses, validity };
};


// team structure:
// {
//   agents
//   genome
//   score
//   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(genome),
  state: [...Array(n_internal)].map(_ => (2*Math.random()) - 1),
  }
}



export function create_team(size, genome_size, n_internal) {
  const genome = apply(
    s => mut_genome_insert(s, 4),
    genome_size,
    {n_input: N_INPUT, n_internal, n_output: N_OUTPUT, genes: []},
  );
  console.log(N_INPUT, N_OUTPUT, genome);

  const agents = [...Array(size)].map(_ => create_agent(genome, n_internal));
  return { agents, genome, score: 0, games: 0 };
}


export function child_team(team, keep=Math.floor(team.size/2)) {
  const n_internal = get_size(team.genome) - N_INPUT - N_OUTPUT;
  const genome = apply(
    s => mutate_genome(s, 4),
    Math.floor(MAX_MUTATIONS * Math.random()),
    [N_INPUT, n_internal, N_OUTPUT, team.genome]
  );

  const old_agents = [...Array(team.agents.length - keep)].reduce(
    (acc, _) => {
      const idx = Math.floor(Math.random() * acc.length);
      acc.splice(idx, 1);
      return acc;
    },
  );
  const new_agents = [...Array(team.agents.length - keep)].map(_ => create_agent(genome, n_internal));
  const agents = [old_agents, new_agents].flat();

  return { agents, genome, score: 0, games: 0 };
}


// game structure:
// {
//   world: world
//   team_indices: number[]
//   time: number
// }


export function create_game(teams, team_indices) {
  const world = create_world(100, team_indices.map(i => teams[i].agents));
  return { world, team_indices, time: 0 };
}


export function step_game(game) {
  return {
    ...game,
    world: world_update(game.world, postprocess),
    time: game.time + 1,
  };
}


function score(lattice, team_num) {
  const size = lattice.length;

  // count number of flags in the team's area
  return lattice
    .map((row, y) => row.map((cell, x) => [x, y, cell]))
    .flat()
    .filter(([x, y, cell]) => get_team(size, x, y) === team_num && cell.type === 'flag')
    .length;
}

export function finish_game(teams, game) {
  const scores = [0, 1, 2, 3].map(t => score(game.world.lattice, t));
  return game.team_indices.reduce(
    (acc, idx, i) => {
      const team = teams[idx];
      acc.splice(idx, 1, {...team, score: team.score + scores[i], games: team.games+1});
      return acc;
    },
    teams,
  );
}



// epoch structure
// {
//   game
//   time
//   teams
// }

function random_indices(teams) {
  return [...Array(teams.length - 4)].reduce(
    (acc) => {
      const idx = Math.floor(Math.random() * acc.length);
      acc.splice(idx, 1);
      return acc;
    },
    [...teams.keys()]
  );
}

let epoch_num = 0;
export function create_epoch(teams) {
  return {
    game: create_game(teams, random_indices(teams)),
    time: 0,
    epoch: epoch_num++, // !!!! side effects !!!!
    teams,
  }
}


const GAME_STEPS = 5000
const EPOCH_STEPS = 200

export function update_epoch(epoch) {
  if (epoch.game.time < GAME_STEPS) {
    return { ...epoch, game: step_game(epoch.game) };
  } else if (epoch.time < EPOCH_STEPS) {
    return { 
      ...epoch, 
      teams: finish_game(epoch.teams, epoch.game),
      game: create_game(epoch.teams, random_indices(epoch.teams)), 
      time: epoch.time+1 
    };
  } else {
    // epoch complete!!
    const source_teams = epoch.teams
      .map(team => {
        const normalized_score = team.score/team.games;
        const count = Math.ceil(16*normalized_score);
        return [...Array(count > 0 ? count : 1)].map(x => team)
      })
      .flat();
    const new_teams = [...Array(epoch.teams.length)]
      .reduce((acc) => child_team(random_choice(source_teams)), []);
    return create_epoch(new_teams);
  }
}