HTML preprocessors can make writing HTML more powerful or convenient. For instance, Markdown is designed to be easier to write and read for text documents and you could write a loop in Pug.
In CodePen, whatever you write in the HTML editor is what goes within the <body>
tags in a basic HTML5 template. So you don't have access to higher-up elements like the <html>
tag. If you want to add classes there that can affect the whole document, this is the place to do it.
In CodePen, whatever you write in the HTML editor is what goes within the <body>
tags in a basic HTML5 template. If you need things in the <head>
of the document, put that code here.
The resource you are linking to is using the 'http' protocol, which may not work when the browser is using https.
CSS preprocessors help make authoring CSS easier. All of them offer things like variables and mixins to provide convenient abstractions.
It's a common practice to apply CSS to a page that styles elements such that they are consistent across all browsers. We offer two of the most popular choices: normalize.css and a reset. Or, choose Neither and nothing will be applied.
To get the best cross-browser support, it is a common practice to apply vendor prefixes to CSS properties and values that require them to work. For instance -webkit-
or -moz-
.
We offer two popular choices: Autoprefixer (which processes your CSS server-side) and -prefix-free (which applies prefixes via a script, client-side).
Any URLs added here will be added as <link>
s in order, and before the CSS in the editor. You can use the CSS from another Pen by using its URL and the proper URL extension.
You can apply CSS to your Pen from any stylesheet on the web. Just put a URL to it here and we'll apply it, in the order you have them, before the CSS in the Pen itself.
You can also link to another Pen here (use the .css
URL Extension) and we'll pull the CSS from that Pen and include it. If it's using a matching preprocessor, use the appropriate URL Extension and we'll combine the code before preprocessing, so you can use the linked Pen as a true dependency.
JavaScript preprocessors can help make authoring JavaScript easier and more convenient.
Babel includes JSX processing.
Any URL's added here will be added as <script>
s in order, and run before the JavaScript in the editor. You can use the URL of any other Pen and it will include the JavaScript from that Pen.
You can apply a script from anywhere on the web to your Pen. Just put a URL to it here and we'll add it, in the order you have them, before the JavaScript in the Pen itself.
If the script you link to has the file extension of a preprocessor, we'll attempt to process it before applying.
You can also link to another Pen here, and we'll pull the JavaScript from that Pen and include it. If it's using a matching preprocessor, we'll combine the code before preprocessing, so you can use the linked Pen as a true dependency.
Search for and use JavaScript packages from npm here. By selecting a package, an import
statement will be added to the top of the JavaScript editor for this package.
Using packages here is powered by Skypack, which makes packages from npm not only available on a CDN, but prepares them for native JavaScript ES6 import
usage.
All packages are different, so refer to their docs for how they work.
If you're using React / ReactDOM, make sure to turn on Babel for the JSX processing.
If active, Pens will autosave every 30 seconds after being saved once.
If enabled, the preview panel updates automatically as you code. If disabled, use the "Run" button to update.
If enabled, your code will be formatted when you actively save your Pen. Note: your code becomes un-folded during formatting.
Visit your global Editor Settings.
e<!DOCTYPE html>
<html>
<head>
<title>TetNet</title>
<link href='https://fonts.googleapis.com/css?family=Inconsolata' rel='stylesheet' type='text/css'>
<style>
</style>
<script src="lib/cerebrum.js"></script>
<script src="https://code.jquery.com/jquery-3.1.0.min.js" integrity="sha256-cCueBR6CsyA4/9szpPfrX3s49M9vUU5BgtiJj06wt/s=" crossorigin="anonymous"></script>
</head>
<body>
<div id="output" class="text"></div>
<div id="score" class="text"></div>
<div id="instructions" class="text"><br /><b>[Key Commands]</b><br />Load Fully Evolved Archive: [CTRL]<br />Speed Up: [E]<br />Slow Down: [D]<br />Toggle AI: [A]<br />Move Shape: [Arrow Keys]<br />Rotate Shape: [Up Arrow]<br />Drop Shape: [Down Arrow]<br />Save State: [Q]<br />Load State: [W]<br />Get Archive: [G]<br />Load Archive: [R]<br />Pick Shape: [I,O,T,S,Z,J,L]</div>
<div id="signature" class="text">Created By Idrees Hassan<br />Questions? Just ask!<br /><a href="mailto:idrees@idreesinc.com" target="_top">idrees@idreesinc.com</a></div>
<script src="./tetnet.js"></script>
<script>
$(window).keydown(function (e){
if (e.ctrlKey) {
var archiveJSON = $.ajax({
url: "./archive.json",
async: false
}).responseText;
loadArchive(archiveJSON);
alert("Archive loaded successfully!");
}
});
</script>
<script type="text/javascript">
</script>
</body>
</html>
body {
background-color: #272821;
}
.text {
color: #706C5A;
font-family: Inconsolata, Courier, monospace;
font-size: 20px;
}
#output {
float: left;
padding-left: 20%;
}
#score {
padding-left: 55%;
}
#instructions {
float: left;
position: absolute;
left: 1.5%;
bottom: 3%;
font-size: small;
line-height: 110%;
}
#signature {
float: right;
position: absolute;
right: 1.5%;
bottom: 3%;
font-size: small;
line-height: 110%;
}
a:link {
color: inherit;
}
//Define 10x20 grid as the board
var grid = [
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
];
//Block shapes
var shapes = {
I: [[0,0,0,0], [1,1,1,1], [0,0,0,0], [0,0,0,0]],
J: [[2,0,0], [2,2,2], [0,0,0]],
L: [[0,0,3], [3,3,3], [0,0,0]],
O: [[4,4], [4,4]],
S: [[0,5,5], [5,5,0], [0,0,0]],
T: [[0,6,0], [6,6,6], [0,0,0]],
Z: [[7,7,0], [0,7,7], [0,0,0]]
};
//Block colors
var colors = ["F92338", "C973FF", "1C76BC", "FEE356", "53D504", "36E0FF", "F8931D"];
//Used to help create a seeded generated random number for choosing shapes. makes results deterministic (reproducible) for debugging
var rndSeed = 1;
//BLOCK SHAPES
//coordinates and shape parameter of current block we can update
var currentShape = {x: 0, y: 0, shape: undefined};
//store shape of upcoming block
var upcomingShape;
//stores shapes
var bag = [];
//index for shapes in the bag
var bagIndex = 0;
//GAME VALUES
//Game score
var score = 0;
// game speed
var speed = 500;
// boolean for changing game speed
var changeSpeed = false;
//for storing current state, we can load later
var saveState;
//stores current game state
var roundState;
//list of available game speeds
var speeds = [500,100,1,0];
//inded in game speed array
var speedIndex = 0;
//turn ai on or off
var ai = true;
//drawing game vs updating algorithms
var draw = true;
//how many so far?
var movesTaken = 0;
//max number of moves allowed in a generation
var moveLimit = 500;
//consists of move the 7 move parameters
var moveAlgorithm = {};
//set to highest rate move
var inspectMoveSelection = false;
//GENETIC ALGORITHM VALUES
//stores number of genomes, init at 50
var populationSize = 50;
//stores genomes
var genomes = [];
//index of current genome in genomes array
var currentGenome = -1;
//generation number
var generation = 0;
//stores values for a generation
var archive = {
populationSize: 0,
currentGeneration: 0,
elites: [],
genomes: []
};
//rate of mutation
var mutationRate = 0.05;
//helps calculate mutation
var mutationStep = 0.2;
//main function, called on load
function initialize() {
//init pop size
archive.populationSize = populationSize;
//get the next available shape from the bag
nextShape();
//applies the shape to the grid
applyShape();
//set both save state and current state from the game
saveState = getState();
roundState = getState();
//create an initial population of genomes
createInitialPopulation();
//the game loop
var loop = function(){
//boolean for changing game speed
if (changeSpeed) {
//restart the clock
//stop time
clearInterval(interval);
//set time, like a digital watch
interval = setInterval(loop, speed);
//and don't change it
changeInterval = false;
}
if (speed === 0) {
//no need to draw on screen elements
draw = false;
//updates the game (update fitness, make a move, evaluate next move)
update();
update();
update();
} else {
//draw the elements
draw = true;
}
//update regardless
update();
if (speed === 0) {
//now draw elements
draw = true;
//now update the score
updateScore();
}
};
//timer interval
var interval = setInterval(loop, speed);
}
document.onLoad = initialize();
//key options
window.onkeydown = function (event) {
var characterPressed = String.fromCharCode(event.keyCode);
if (event.keyCode == 38) {
rotateShape();
} else if (event.keyCode == 40) {
moveDown();
} else if (event.keyCode == 37) {
moveLeft();
} else if (event.keyCode == 39) {
moveRight();
} else if (shapes[characterPressed.toUpperCase()] !== undefined) {
removeShape();
currentShape.shape = shapes[characterPressed.toUpperCase()];
applyShape();
} else if (characterPressed.toUpperCase() == "Q") {
saveState = getState();
} else if (characterPressed.toUpperCase() == "W") {
loadState(saveState);
} else if (characterPressed.toUpperCase() == "D") {
//slow down
speedIndex--;
if (speedIndex < 0) {
speedIndex = speeds.length - 1;
}
speed = speeds[speedIndex];
changeSpeed = true;
} else if (characterPressed.toUpperCase() == "E") {
//speed up
speedIndex++;
if (speedIndex >= speeds.length) {
speedIndex = 0;
}
//adjust speed index
speed = speeds[speedIndex];
changeSpeed = true;
//Turn on/off AI
} else if (characterPressed.toUpperCase() == "A") {
ai = !ai;
} else if (characterPressed.toUpperCase() == "R") {
//load saved generation values
loadArchive(prompt("Insert archive:"));
} else if (characterPressed.toUpperCase() == "G") {
if (localStorage.getItem("archive") === null) {
alert("No archive saved. Archives are saved after a generation has passed, and remain across sessions. Try again once a generation has passed");
} else {
prompt("Archive from last generation (including from last session):", localStorage.getItem("archive"));
}
} else if (characterPressed.toUpperCase() == "F") {
//?
inspectMoveSelection = !inspectMoveSelection;
} else {
return true;
}
//outputs game state to the screen (post key press)
output();
return false;
};
/**
* Creates the initial population of genomes, each with random genes.
*/
function createInitialPopulation() {
//inits the array
genomes = [];
//for a given population size
for (var i = 0; i < populationSize; i++) {
//randomly initialize the 7 values that make up a genome
//these are all weight values that are updated through evolution
var genome = {
//unique identifier for a genome
id: Math.random(),
//The weight of each row cleared by the given move. the more rows that are cleared, the more this weight increases
rowsCleared: Math.random() - 0.5,
//the absolute height of the highest column to the power of 1.5
//added so that the algorithm can be able to detect if the blocks are stacking too high
weightedHeight: Math.random() - 0.5,
//The sum of all the column’s heights
cumulativeHeight: Math.random() - 0.5,
//the highest column minus the lowest column
relativeHeight: Math.random() - 0.5,
//the sum of all the empty cells that have a block above them (basically, cells that are unable to be filled)
holes: Math.random() * 0.5,
// the sum of absolute differences between the height of each column
//(for example, if all the shapes on the grid lie completely flat, then the roughness would equal 0).
roughness: Math.random() - 0.5,
};
//add them to the array
genomes.push(genome);
}
evaluateNextGenome();
}
/**
* Evaluates the next genome in the population. If there is none, evolves the population.
*/
function evaluateNextGenome() {
//increment index in genome array
currentGenome++;
//If there is none, evolves the population.
if (currentGenome == genomes.length) {
evolve();
}
//load current gamestate
loadState(roundState);
//reset moves taken
movesTaken = 0;
//and make the next move
makeNextMove();
}
/**
* Evolves the entire population and goes to the next generation.
*/
function evolve() {
console.log("Generation " + generation + " evaluated.");
//reset current genome for new generation
currentGenome = 0;
//increment generation
generation++;
//resets the game
reset();
//gets the current game state
roundState = getState();
//sorts genomes in decreasing order of fitness values
genomes.sort(function(a, b) {
return b.fitness - a.fitness;
});
//add a copy of the fittest genome to the elites list
archive.elites.push(clone(genomes[0]));
console.log("Elite's fitness: " + genomes[0].fitness);
//remove the tail end of genomes, focus on the fittest
while(genomes.length > populationSize / 2) {
genomes.pop();
}
//sum of the fitness for each genome
var totalFitness = 0;
for (var i = 0; i < genomes.length; i++) {
totalFitness += genomes[i].fitness;
}
//get a random index from genome array
function getRandomGenome() {
return genomes[randomWeightedNumBetween(0, genomes.length - 1)];
}
//create children array
var children = [];
//add the fittest genome to array
children.push(clone(genomes[0]));
//add population sized amount of children
while (children.length < populationSize) {
//crossover between two random genomes to make a child
children.push(makeChild(getRandomGenome(), getRandomGenome()));
}
//create new genome array
genomes = [];
//to store all the children in
genomes = genomes.concat(children);
//store this in our archive
archive.genomes = clone(genomes);
//and set current gen
archive.currentGeneration = clone(generation);
console.log(JSON.stringify(archive));
//store archive, thanks JS localstorage! (short term memory)
localStorage.setItem("archive", JSON.stringify(archive));
}
/**
* Creates a child genome from the given parent genomes, and then attempts to mutate the child genome.
* @param {Genome} mum The first parent genome.
* @param {Genome} dad The second parent genome.
* @return {Genome} The child genome.
*/
function makeChild(mum, dad) {
//init the child given two genomes (its 7 parameters + initial fitness value)
var child = {
//unique id
id : Math.random(),
//all these params are randomly selected between the mom and dad genome
rowsCleared: randomChoice(mum.rowsCleared, dad.rowsCleared),
weightedHeight: randomChoice(mum.weightedHeight, dad.weightedHeight),
cumulativeHeight: randomChoice(mum.cumulativeHeight, dad.cumulativeHeight),
relativeHeight: randomChoice(mum.relativeHeight, dad.relativeHeight),
holes: randomChoice(mum.holes, dad.holes),
roughness: randomChoice(mum.roughness, dad.roughness),
//no fitness. yet.
fitness: -1
};
//mutation time!
//we mutate each parameter using our mutationstep
if (Math.random() < mutationRate) {
child.rowsCleared = child.rowsCleared + Math.random() * mutationStep * 2 - mutationStep;
}
if (Math.random() < mutationRate) {
child.weightedHeight = child.weightedHeight + Math.random() * mutationStep * 2 - mutationStep;
}
if (Math.random() < mutationRate) {
child.cumulativeHeight = child.cumulativeHeight + Math.random() * mutationStep * 2 - mutationStep;
}
if (Math.random() < mutationRate) {
child.relativeHeight = child.relativeHeight + Math.random() * mutationStep * 2 - mutationStep;
}
if (Math.random() < mutationRate) {
child.holes = child.holes + Math.random() * mutationStep * 2 - mutationStep;
}
if (Math.random() < mutationRate) {
child.roughness = child.roughness + Math.random() * mutationStep * 2 - mutationStep;
}
return child;
}
/**
* Returns an array of all the possible moves that could occur in the current state, rated by the parameters of the current genome.
* @return {Array} An array of all the possible moves that could occur.
*/
function getAllPossibleMoves() {
var lastState = getState();
var possibleMoves = [];
var possibleMoveRatings = [];
var iterations = 0;
//for each possible rotation
for (var rots = 0; rots < 4; rots++) {
var oldX = [];
//for each iteration
for (var t = -5; t <= 5; t++) {
iterations++;
loadState(lastState);
//rotate shape
for (var j = 0; j < rots; j++) {
rotateShape();
}
//move left
if (t < 0) {
for (var l = 0; l < Math.abs(t); l++) {
moveLeft();
}
//move right
} else if (t > 0) {
for (var r = 0; r < t; r++) {
moveRight();
}
}
//if the shape has moved at all
if (!contains(oldX, currentShape.x)) {
//move it down
var moveDownResults = moveDown();
while (moveDownResults.moved) {
moveDownResults = moveDown();
}
//set the 7 parameters of a genome
var algorithm = {
rowsCleared: moveDownResults.rowsCleared,
weightedHeight: Math.pow(getHeight(), 1.5),
cumulativeHeight: getCumulativeHeight(),
relativeHeight: getRelativeHeight(),
holes: getHoles(),
roughness: getRoughness()
};
//rate each move
var rating = 0;
rating += algorithm.rowsCleared * genomes[currentGenome].rowsCleared;
rating += algorithm.weightedHeight * genomes[currentGenome].weightedHeight;
rating += algorithm.cumulativeHeight * genomes[currentGenome].cumulativeHeight;
rating += algorithm.relativeHeight * genomes[currentGenome].relativeHeight;
rating += algorithm.holes * genomes[currentGenome].holes;
rating += algorithm.roughness * genomes[currentGenome].roughness;
//if the move loses the game, lower its rating
if (moveDownResults.lose) {
rating -= 500;
}
//push all possible moves, with their associated ratings and parameter values to an array
possibleMoves.push({rotations: rots, translation: t, rating: rating, algorithm: algorithm});
//update the position of old X value
oldX.push(currentShape.x);
}
}
}
//get last state
loadState(lastState);
//return array of all possible moves
return possibleMoves;
}
/**
* Returns the highest rated move in the given array of moves.
* @param {Array} moves An array of possible moves to choose from.
* @return {Move} The highest rated move from the moveset.
*/
function getHighestRatedMove(moves) {
//start these values off small
var maxRating = -10000000000000;
var maxMove = -1;
var ties = [];
//iterate through the list of moves
for (var index = 0; index < moves.length; index++) {
//if the current moves rating is higher than our maxrating
if (moves[index].rating > maxRating) {
//update our max values to include this moves values
maxRating = moves[index].rating;
maxMove = index;
//store index of this move
ties = [index];
} else if (moves[index].rating == maxRating) {
//if it ties with the max rating
//add the index to the ties array
ties.push(index);
}
}
//eventually we'll set the highest move value to this move var
var move = moves[ties[0]];
//and set the number of ties
move.algorithm.ties = ties.length;
return move;
}
/**
* Makes a move, which is decided upon using the parameters in the current genome.
*/
function makeNextMove() {
//increment number of moves taken
movesTaken++;
//if its over the limit of moves
if (movesTaken > moveLimit) {
//update this genomes fitness value using the game score
genomes[currentGenome].fitness = clone(score);
//and evaluates the next genome
evaluateNextGenome();
} else {
//time to make a move
//we're going to re-draw, so lets store the old drawing
var oldDraw = clone(draw);
draw = false;
//get all the possible moves
var possibleMoves = getAllPossibleMoves();
//lets store the current state since we will update it
var lastState = getState();
//whats the next shape to play
nextShape();
//for each possible move
for (var i = 0; i < possibleMoves.length; i++) {
//get the best move. so were checking all the possible moves, for each possible move. moveception.
var nextMove = getHighestRatedMove(getAllPossibleMoves());
//add that rating to an array of highest rates moves
possibleMoves[i].rating += nextMove.rating;
}
//load current state
loadState(lastState);
//get the highest rated move ever
var move = getHighestRatedMove(possibleMoves);
//then rotate the shape as it says too
for (var rotations = 0; rotations < move.rotations; rotations++) {
rotateShape();
}
//and move left as it says
if (move.translation < 0) {
for (var lefts = 0; lefts < Math.abs(move.translation); lefts++) {
moveLeft();
}
//and right as it says
} else if (move.translation > 0) {
for (var rights = 0; rights < move.translation; rights++) {
moveRight();
}
}
//update our move algorithm
if (inspectMoveSelection) {
moveAlgorithm = move.algorithm;
}
//and set the old drawing to the current
draw = oldDraw;
//output the state to the screen
output();
//and update the score
updateScore();
}
}
/**
* Updates the game.
*/
function update() {
//if we have our AI turned on and the current genome is nonzero
//make a move
if (ai && currentGenome != -1) {
//move the shape down
var results = moveDown();
//if that didn't do anything
if (!results.moved) {
//if we lost
if (results.lose) {
//update the fitness
genomes[currentGenome].fitness = clone(score);
//move on to the next genome
evaluateNextGenome();
} else {
//if we didnt lose, make the next move
makeNextMove();
}
}
} else {
//else just move down
moveDown();
}
//output the state to the screen
output();
//and update the score
updateScore();
}
/**
* Moves the current shape down if possible.
* @return {Object} The results of the movement of the piece.
*/
function moveDown() {
//array of possibilities
var result = {lose: false, moved: true, rowsCleared: 0};
//remove the shape, because we will draw a new one
removeShape();
//move it down the y axis
currentShape.y++;
//if it collides with the grid
if (collides(grid, currentShape)) {
//update its position
currentShape.y--;
//apply (stick) it to the grid
applyShape();
//move on to the next shape in the bag
nextShape();
//clear rows and get number of rows cleared
result.rowsCleared = clearRows();
//check again if this shape collides with our grid
if (collides(grid, currentShape)) {
//reset
result.lose = true;
if (ai) {
} else {
reset();
}
}
result.moved = false;
}
//apply shape, update the score and output the state to the screen
applyShape();
score++;
updateScore();
output();
return result;
}
/**
* Moves the current shape to the left if possible.
*/
function moveLeft() {
//remove current shape, slide it over, if it collides though, slide it back
removeShape();
currentShape.x--;
if (collides(grid, currentShape)) {
currentShape.x++;
}
//apply the new shape
applyShape();
}
/**
* Moves the current shape to the right if possible.
*/
//same deal
function moveRight() {
removeShape();
currentShape.x++;
if (collides(grid, currentShape)) {
currentShape.x--;
}
applyShape();
}
/**
* Rotates the current shape clockwise if possible.
*/
//slide it if we can, else return to original rotation
function rotateShape() {
removeShape();
currentShape.shape = rotate(currentShape.shape, 1);
if (collides(grid, currentShape)) {
currentShape.shape = rotate(currentShape.shape, 3);
}
applyShape();
}
/**
* Clears any rows that are completely filled.
*/
function clearRows() {
//empty array for rows to clear
var rowsToClear = [];
//for each row in the grid
for (var row = 0; row < grid.length; row++) {
var containsEmptySpace = false;
//for each column
for (var col = 0; col < grid[row].length; col++) {
//if its empty
if (grid[row][col] === 0) {
//set this value to true
containsEmptySpace = true;
}
}
//if none of the columns in the row were empty
if (!containsEmptySpace) {
//add the row to our list, it's completely filled!
rowsToClear.push(row);
}
}
//increase score for up to 4 rows. it maxes out at 12000
if (rowsToClear.length == 1) {
score += 400;
} else if (rowsToClear.length == 2) {
score += 1000;
} else if (rowsToClear.length == 3) {
score += 3000;
} else if (rowsToClear.length >= 4) {
score += 12000;
}
//new array for cleared rows
var rowsCleared = clone(rowsToClear.length);
//for each value
for (var toClear = rowsToClear.length - 1; toClear >= 0; toClear--) {
//remove the row from the grid
grid.splice(rowsToClear[toClear], 1);
}
//shift the other rows
while (grid.length < 20) {
grid.unshift([0,0,0,0,0,0,0,0,0,0]);
}
//return the rows cleared
return rowsCleared;
}
/**
* Applies the current shape to the grid.
*/
function applyShape() {
//for each value in the current shape (row x column)
for (var row = 0; row < currentShape.shape.length; row++) {
for (var col = 0; col < currentShape.shape[row].length; col++) {
//if its non-empty
if (currentShape.shape[row][col] !== 0) {
//set the value in the grid to its value. Stick the shape in the grid!
grid[currentShape.y + row][currentShape.x + col] = currentShape.shape[row][col];
}
}
}
}
/**
* Removes the current shape from the grid.
*/
//same deal but reverse
function removeShape() {
for (var row = 0; row < currentShape.shape.length; row++) {
for (var col = 0; col < currentShape.shape[row].length; col++) {
if (currentShape.shape[row][col] !== 0) {
grid[currentShape.y + row][currentShape.x + col] = 0;
}
}
}
}
/**
* Cycles to the next shape in the bag.
*/
function nextShape() {
//increment the bag index
bagIndex += 1;
//if we're at the start or end of the bag
if (bag.length === 0 || bagIndex == bag.length) {
//generate a new bag of genomes
generateBag();
}
//if almost at end of bag
if (bagIndex == bag.length - 1) {
//store previous seed
var prevSeed = rndSeed;
//generate upcoming shape
upcomingShape = randomProperty(shapes);
//set random seed
rndSeed = prevSeed;
} else {
//get the next shape from our bag
upcomingShape = shapes[bag[bagIndex + 1]];
}
//get our current shape from the bag
currentShape.shape = shapes[bag[bagIndex]];
//define its position
currentShape.x = Math.floor(grid[0].length / 2) - Math.ceil(currentShape.shape[0].length / 2);
currentShape.y = 0;
}
/**
* Generates the bag of shapes.
*/
function generateBag() {
bag = [];
var contents = "";
//7 shapes
for (var i = 0; i < 7; i++) {
//generate shape randomly
var shape = randomKey(shapes);
while(contents.indexOf(shape) != -1) {
shape = randomKey(shapes);
}
//update bag with generated shape
bag[i] = shape;
contents += shape;
}
//reset bag index
bagIndex = 0;
}
/**
* Resets the game.
*/
function reset() {
score = 0;
grid = [[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
];
moves = 0;
generateBag();
nextShape();
}
/**
* Determines if the given grid and shape collide with one another.
* @param {Grid} scene The grid to check.
* @param {Shape} object The shape to check.
* @return {Boolean} Whether the shape and grid collide.
*/
function collides(scene, object) {
//for the size of the shape (row x column)
for (var row = 0; row < object.shape.length; row++) {
for (var col = 0; col < object.shape[row].length; col++) {
//if its not empty
if (object.shape[row][col] !== 0) {
//if it collides, return true
if (scene[object.y + row] === undefined || scene[object.y + row][object.x + col] === undefined || scene[object.y + row][object.x + col] !== 0) {
return true;
}
}
}
}
return false;
}
//for rotating a shape, how many times should we rotate
function rotate(matrix, times) {
//for each time
for (var t = 0; t < times; t++) {
//flip the shape matrix
matrix = transpose(matrix);
//and for the length of the matrix, reverse each column
for (var i = 0; i < matrix.length; i++) {
matrix[i].reverse();
}
}
return matrix;
}
//flip row x column to column x row
function transpose(array) {
return array[0].map(function(col, i) {
return array.map(function(row) {
return row[i];
});
});
}
/**
* Outputs the state to the screen.
*/
function output() {
if (draw) {
var output = document.getElementById("output");
var html = "<h1>TetNet</h1><h5>Evolutionary approach to Tetris AI</h5>var grid = [";
var space = " ";
for (var i = 0; i < grid.length; i++) {
if (i === 0) {
html += "[" + grid[i] + "]";
} else {
html += "<br />" + space + "[" + grid[i] + "]";
}
}
html += "];";
for (var c = 0; c < colors.length; c++) {
html = replaceAll(html, "," + (c + 1), ",<font color=\"" + colors[c] + "\">" + (c + 1) + "</font>");
html = replaceAll(html, (c + 1) + ",", "<font color=\"" + colors[c] + "\">" + (c + 1) + "</font>,");
}
output.innerHTML = html;
}
}
/**
* Updates the side information.
*/
function updateScore() {
if (draw) {
var scoreDetails = document.getElementById("score");
var html = "<br /><br /><h2> </h2><h2>Score: " + score + "</h2>";
html += "<br /><b>--Upcoming--</b>";
for (var i = 0; i < upcomingShape.length; i++) {
var next =replaceAll((upcomingShape[i] + ""), "0", " ");
html += "<br /> " + next;
}
for (var l = 0; l < 4 - upcomingShape.length; l++) {
html += "<br />";
}
for (var c = 0; c < colors.length; c++) {
html = replaceAll(html, "," + (c + 1), ",<font color=\"" + colors[c] + "\">" + (c + 1) + "</font>");
html = replaceAll(html, (c + 1) + ",", "<font color=\"" + colors[c] + "\">" + (c + 1) + "</font>,");
}
html += "<br />Speed: " + speed;
if (ai) {
html += "<br />Moves: " + movesTaken + "/" + moveLimit;
html += "<br />Generation: " + generation;
html += "<br />Individual: " + (currentGenome + 1) + "/" + populationSize;
html += "<br /><pre style=\"font-size:12px\">" + JSON.stringify(genomes[currentGenome], null, 2) + "</pre>";
if (inspectMoveSelection) {
html += "<br /><pre style=\"font-size:12px\">" + JSON.stringify(moveAlgorithm, null, 2) + "</pre>";
}
}
html = replaceAll(replaceAll(replaceAll(html, " ,", " "), ", ", " "), ",", " ");
scoreDetails.innerHTML = html;
}
}
/**
* Returns the current game state in an object.
* @return {State} The current game state.
*/
function getState() {
var state = {
grid: clone(grid),
currentShape: clone(currentShape),
upcomingShape: clone(upcomingShape),
bag: clone(bag),
bagIndex: clone(bagIndex),
rndSeed: clone(rndSeed),
score: clone(score)
};
return state;
}
/**
* Loads the game state from the given state object.
* @param {State} state The state to load.
*/
function loadState(state) {
grid = clone(state.grid);
currentShape = clone(state.currentShape);
upcomingShape = clone(state.upcomingShape);
bag = clone(state.bag);
bagIndex = clone(state.bagIndex);
rndSeed = clone(state.rndSeed);
score = clone(state.score);
output();
updateScore();
}
/**
* Returns the cumulative height of all the columns.
* @return {Number} The cumulative height.
*/
function getCumulativeHeight() {
removeShape();
var peaks = [20,20,20,20,20,20,20,20,20,20];
for (var row = 0; row < grid.length; row++) {
for (var col = 0; col < grid[row].length; col++) {
if (grid[row][col] !== 0 && peaks[col] === 20) {
peaks[col] = row;
}
}
}
var totalHeight = 0;
for (var i = 0; i < peaks.length; i++) {
totalHeight += 20 - peaks[i];
}
applyShape();
return totalHeight;
}
/**
* Returns the number of holes in the grid.
* @return {Number} The number of holes.
*/
function getHoles() {
removeShape();
var peaks = [20,20,20,20,20,20,20,20,20,20];
for (var row = 0; row < grid.length; row++) {
for (var col = 0; col < grid[row].length; col++) {
if (grid[row][col] !== 0 && peaks[col] === 20) {
peaks[col] = row;
}
}
}
var holes = 0;
for (var x = 0; x < peaks.length; x++) {
for (var y = peaks[x]; y < grid.length; y++) {
if (grid[y][x] === 0) {
holes++;
}
}
}
applyShape();
return holes;
}
/**
* Returns an array that replaces all the holes in the grid with -1.
* @return {Array} The modified grid array.
*/
function getHolesArray() {
var array = clone(grid);
removeShape();
var peaks = [20,20,20,20,20,20,20,20,20,20];
for (var row = 0; row < grid.length; row++) {
for (var col = 0; col < grid[row].length; col++) {
if (grid[row][col] !== 0 && peaks[col] === 20) {
peaks[col] = row;
}
}
}
for (var x = 0; x < peaks.length; x++) {
for (var y = peaks[x]; y < grid.length; y++) {
if (grid[y][x] === 0) {
array[y][x] = -1;
}
}
}
applyShape();
return array;
}
/**
* Returns the roughness of the grid.
* @return {Number} The roughness of the grid.
*/
function getRoughness() {
removeShape();
var peaks = [20,20,20,20,20,20,20,20,20,20];
for (var row = 0; row < grid.length; row++) {
for (var col = 0; col < grid[row].length; col++) {
if (grid[row][col] !== 0 && peaks[col] === 20) {
peaks[col] = row;
}
}
}
var roughness = 0;
var differences = [];
for (var i = 0; i < peaks.length - 1; i++) {
roughness += Math.abs(peaks[i] - peaks[i + 1]);
differences[i] = Math.abs(peaks[i] - peaks[i + 1]);
}
applyShape();
return roughness;
}
/**
* Returns the range of heights of the columns on the grid.
* @return {Number} The relative height.
*/
function getRelativeHeight() {
removeShape();
var peaks = [20,20,20,20,20,20,20,20,20,20];
for (var row = 0; row < grid.length; row++) {
for (var col = 0; col < grid[row].length; col++) {
if (grid[row][col] !== 0 && peaks[col] === 20) {
peaks[col] = row;
}
}
}
applyShape();
return Math.max.apply(Math, peaks) - Math.min.apply(Math, peaks);
}
/**
* Returns the height of the biggest column on the grid.
* @return {Number} The absolute height.
*/
function getHeight() {
removeShape();
var peaks = [20,20,20,20,20,20,20,20,20,20];
for (var row = 0; row < grid.length; row++) {
for (var col = 0; col < grid[row].length; col++) {
if (grid[row][col] !== 0 && peaks[col] === 20) {
peaks[col] = row;
}
}
}
applyShape();
return 20 - Math.min.apply(Math, peaks);
}
/**
* Loads the archive given.
* @param {String} archiveString The stringified archive.
*/
function loadArchive(archiveString) {
archive = JSON.parse(archiveString);
genomes = clone(archive.genomes);
populationSize = archive.populationSize;
generation = archive.currentGeneration;
currentGenome = 0;
reset();
roundState = getState();
console.log("Archive loaded!");
}
/**
* Clones an object.
* @param {Object} obj The object to clone.
* @return {Object} The cloned object.
*/
function clone(obj) {
return JSON.parse(JSON.stringify(obj));
}
/**
* Returns a random property from the given object.
* @param {Object} obj The object to select a property from.
* @return {Property} A random property.
*/
function randomProperty(obj) {
return(obj[randomKey(obj)]);
}
/**
* Returns a random property key from the given object.
* @param {Object} obj The object to select a property key from.
* @return {Property} A random property key.
*/
function randomKey(obj) {
var keys = Object.keys(obj);
var i = seededRandom(0, keys.length);
return keys[i];
}
function replaceAll(target, search, replacement) {
return target.replace(new RegExp(search, 'g'), replacement);
}
/**
* Returns a random number that is determined from a seeded random number generator.
* @param {Number} min The minimum number, inclusive.
* @param {Number} max The maximum number, exclusive.
* @return {Number} The generated random number.
*/
function seededRandom(min, max) {
max = max || 1;
min = min || 0;
rndSeed = (rndSeed * 9301 + 49297) % 233280;
var rnd = rndSeed / 233280;
return Math.floor(min + rnd * (max - min));
}
function randomNumBetween(min, max) {
return Math.floor(Math.random() * (max - min + 1) + min);
}
function randomWeightedNumBetween(min, max) {
return Math.floor(Math.pow(Math.random(), 2) * (max - min + 1) + min);
}
function randomChoice(propOne, propTwo) {
if (Math.round(Math.random()) === 0) {
return clone(propOne);
} else {
return clone(propTwo);
}
}
function contains(a, obj) {
var i = a.length;
while (i--) {
if (a[i] === obj) {
return true;
}
}
return false;
}
/**
* A node, representing a biological neuron.
* @param {Number} ID The ID of the node.
* @param {Number} val The value of the node.
*/
function Node(ID, val) {
this.id = ID;
this.incomingConnections = [];
this.outgoingConnections = [];
if (val === undefined) {
val = 0;
}
this.value = val;
this.bias = 0;
}
/**
* A connection, representing a biological synapse.
* @param {String} inID The ID of the incoming node.
* @param {String} outID The ID of the outgoing node.
* @param {Number} weight The weight of the connection.
*/
function Connection(inID, outID, weight) {
this.in = inID;
this.out = outID;
if (weight === undefined) {
weight = 1;
}
this.id = inID + ":" + outID;
this.weight = weight;
}
/**
* The neural network, containing nodes and connections.
* @param {Object} config The configuration to use.
*/
function Network(config) {
this.nodes = {};
this.inputs = [];
this.hidden = [];
this.outputs = [];
this.connections = {};
this.nodes.BIAS = new Node("BIAS", 1);
if (config !== undefined) {
var inputNum = config.inputNodes || 0;
var hiddenNum = config.hiddenNodes || 0;
var outputNum = config.outputNodes || 0;
this.createNodes(inputNum, hiddenNum, outputNum);
if (config.createAllConnections) {
this.createAllConnections(true);
}
}
}
/**
* Populates the network with the given number of nodes of each type.
* @param {Number} inputNum The number of input nodes to create.
* @param {Number} hiddenNum The number of hidden nodes to create.
* @param {Number} outputNum The number of output nodes to create.
*/
Network.prototype.createNodes = function(inputNum, hiddenNum, outputNum) {
for (var i = 0; i < inputNum; i++) {
this.addInput();
}
for (var j = 0; j < hiddenNum; j++) {
this.addHidden();
}
for (var k = 0; k < outputNum; k++) {
this.addOutput();
}
};
/**
* @param {Number} [value] The value to set the node to [Default is 0].
*/
Network.prototype.addInput = function(value) {
var nodeID = "INPUT:" + this.inputs.length;
if (value === undefined) {
value = 0;
}
this.nodes[nodeID] = new Node(nodeID, value);
this.inputs.push(nodeID);
};
/**
* Creates a hidden node.
*/
Network.prototype.addHidden = function() {
var nodeID = "HIDDEN:" + this.hidden.length;
this.nodes[nodeID] = new Node(nodeID);
this.hidden.push(nodeID);
};
/**
* Creates an output node.
*/
Network.prototype.addOutput = function() {
var nodeID = "OUTPUT:" + this.outputs.length;
this.nodes[nodeID] = new Node(nodeID);
this.outputs.push(nodeID);
};
/**
* Returns the node with the given ID.
* @param {String} nodeID The ID of the node to return.
* @return {Node} The node with the given ID.
*/
Network.prototype.getNodeByID = function(nodeID) {
return this.nodes[nodeID];
};
/**
* Returns the node of the given type at the given index.
* @param {String} type The type of node requested [Accepted arguments: "INPUT", "HIDDEN", "OUTPUT"].
* @param {Number} index The index of the node (from the array containing nodes of the requested type).
* @return {Node} The node requested. Will return null if no node is found.
*/
Network.prototype.getNode = function(type, index) {
if (type.toUpperCase() == "INPUT") {
return this.nodes[this.inputs[index]];
} else if (type.toUpperCase() == "HIDDEN") {
return this.nodes[this.hidden[index]];
} else if (type.toUpperCase() == "OUTPUT") {
return this.nodes[this.outputs[index]];
}
return null;
};
/**
* Returns the connection with the given ID.
* @param {String} connectionID The ID of the connection to return.
* @return {Connection} The connection with the given ID.
*/
Network.prototype.getConnection = function(connectionID) {
return this.connections[connectionID];
};
/**
* Calculates the values of the nodes in the neural network.
*/
Network.prototype.calculate = function calculate() {
this.updateNodeConnections();
for (var i = 0; i < this.hidden.length; i++) {
this.calculateNodeValue(this.hidden[i]);
}
for (var j = 0; j < this.outputs.length; j++) {
this.calculateNodeValue(this.outputs[j]);
}
};
/**
* Updates the node's to reference the current connections.
*/
Network.prototype.updateNodeConnections = function() {
for (var nodeKey in this.nodes) {
this.nodes[nodeKey].incomingConnections = [];
this.nodes[nodeKey].outgoingConnections = [];
}
for (var connectionKey in this.connections) {
this.nodes[this.connections[connectionKey].in].outgoingConnections.push(connectionKey);
this.nodes[this.connections[connectionKey].out].incomingConnections.push(connectionKey);
}
};
/**
* Calculates and updates the value of the node with the given ID. Node values are computed using a sigmoid function.
* @param {String} nodeId The ID of the node to update.
*/
Network.prototype.calculateNodeValue = function(nodeID) {
var sum = 0;
for (var incomingIndex = 0; incomingIndex < this.nodes[nodeID].incomingConnections.length; incomingIndex++) {
var connection = this.connections[this.nodes[nodeID].incomingConnections[incomingIndex]];
sum += this.nodes[connection.in].value * connection.weight;
}
this.nodes[nodeID].value = sigmoid(sum);
};
/**
* Creates a connection with the given values.
* @param {String} inID The ID of the node that the connection comes from.
* @param {String} outID The ID of the node that the connection enters.
* @param {Number} [weight] The weight of the connection [Default is 1].
*/
Network.prototype.addConnection = function(inID, outID, weight) {
if (weight === undefined) {
weight = 1;
}
this.connections[inID + ":" + outID] = new Connection(inID, outID, weight);
};
/**
* Creates all possible connections between nodes, not including connections to the bias node.
* @param {Boolean} randomWeights Whether to choose a random weight between -1 and 1, or to default to 1.
*/
Network.prototype.createAllConnections = function(randomWeights) {
if (randomWeights === undefined) {
randomWeights = false;
}
var weight = 1;
for (var i = 0; i < this.inputs.length; i++) {
for (var j = 0; j < this.hidden.length; j++) {
if (randomWeights) {
weight = Math.random() * 4 - 2;
}
this.addConnection(this.inputs[i], this.hidden[j], weight);
}
if (randomWeights) {
weight = Math.random() * 4 - 2;
}
this.addConnection("BIAS", this.inputs[i], weight);
}
for (var k = 0; k < this.hidden.length; k++) {
for (var l = 0; l < this.outputs.length; l++) {
if (randomWeights) {
weight = Math.random() * 4 - 2;
}
this.addConnection(this.hidden[k], this.outputs[l], weight);
}
if (randomWeights) {
weight = Math.random() * 4 - 2;
}
this.addConnection("BIAS", this.hidden[k], weight);
}
};
/**
* Sets the value of the node with the given ID to the given value.
* @param {String} nodeID The ID of the node to modify.
* @param {Number} value The value to set the node to.
*/
Network.prototype.setNodeValue = function(nodeID, value) {
this.nodes[nodeID].value = value;
};
/**
* Sets the values of the input neurons to the given values.
* @param {Array} array An array of values to set the input node values to.
*/
Network.prototype.setInputs = function(array) {
for (var i = 0; i < array.length; i++) {
this.nodes[this.inputs[i]].value = array[i];
}
};
/**
* Sets the value of multiple nodes, given an object with node ID's as parameters and node values as values.
* @param {Object} valuesByID The values to set the nodes to.
*/
Network.prototype.setMultipleNodeValues = function(valuesByID) {
for (var key in valuesByID) {
this.nodes[key].value = valuesByID[key];
}
};
/**
* A visualization of the neural network, showing all connections and nodes.
* @param {Object} config The configuration to use.
*/
function NetworkVisualizer(config) {
this.canvas = "NetworkVisualizer";
this.backgroundColor = "#FFFFFF";
this.nodeRadius = -1;
this.nodeColor = "grey";
this.positiveConnectionColor = "green";
this.negativeConnectionColor = "red";
this.connectionStrokeModifier = 1;
if (config !== undefined) {
if (config.canvas !== undefined) {
this.canvas = config.canvas;
}
if (config.backgroundColor !== undefined) {
this.backgroundColor = config.backgroundColor;
}
if (config.nodeRadius !== undefined) {
this.nodeRadius = config.nodeRadius;
}
if (config.nodeColor !== undefined) {
this.nodeColor = config.nodeColor;
}
if (config.positiveConnectionColor !== undefined) {
this.positiveConnectionColor = config.positiveConnectionColor;
}
if (config.negativeConnectionColor !== undefined) {
this.negativeConnectionColor = config.negativeConnectionColor;
}
if (config.connectionStrokeModifier !== undefined) {
this.connectionStrokeModifier = config.connectionStrokeModifier;
}
}
}
/**
* Draws the visualized network upon the canvas.
* @param {Network} network The network to visualize.
*/
NetworkVisualizer.prototype.drawNetwork = function(network) {
var canv = document.getElementById(this.canvas);
var ctx = canv.getContext("2d");
var radius;
ctx.fillStyle = this.backgroundColor;
ctx.fillRect(0, 0, canv.width, canv.height);
if (this.nodeRadius != -1) {
radius = this.nodeRadius;
} else {
radius = Math.min(canv.width, canv.height) / (Math.max(network.inputs.length, network.hidden.length, network.outputs.length, 3)) / 2.5;
}
var nodeLocations = {};
var inputX = canv.width / 5;
for (var inputIndex = 0; inputIndex < network.inputs.length; inputIndex++) {
nodeLocations[network.inputs[inputIndex]] = {x: inputX, y: canv.height / (network.inputs.length) * (inputIndex + 0.5)};
}
var hiddenX = canv.width / 2;
for (var hiddenIndex = 0; hiddenIndex < network.hidden.length; hiddenIndex++) {
nodeLocations[network.hidden[hiddenIndex]] = {x: hiddenX, y: canv.height / (network.hidden.length) * (hiddenIndex + 0.5)};
}
var outputX = canv.width / 5 * 4;
for (var outputIndex = 0; outputIndex < network.outputs.length; outputIndex++) {
nodeLocations[network.outputs[outputIndex]] = {x: outputX, y: canv.height / (network.outputs.length) * (outputIndex + 0.5)};
}
nodeLocations.BIAS = {x: canv.width / 3, y: radius / 2};
for (var connectionKey in network.connections) {
var connection = network.connections[connectionKey];
//if (connection.in != "BIAS" && connection.out != "BIAS") {
ctx.beginPath();
ctx.moveTo(nodeLocations[connection.in].x, nodeLocations[connection.in].y);
ctx.lineTo(nodeLocations[connection.out].x, nodeLocations[connection.out].y);
if (connection.weight > 0) {
ctx.strokeStyle = this.positiveConnectionColor;
} else {
ctx.strokeStyle = this.negativeConnectionColor;
}
ctx.lineWidth = connection.weight * this.connectionStrokeModifier;
ctx.lineCap = "round";
ctx.stroke();
//}
}
for (var nodeKey in nodeLocations) {
var node = network.getNodeByID(nodeKey);
ctx.beginPath();
if (nodeKey == "BIAS") {
ctx.arc(nodeLocations[nodeKey].x, nodeLocations[nodeKey].y, radius / 2.2, 0, 2 * Math.PI);
} else {
ctx.arc(nodeLocations[nodeKey].x, nodeLocations[nodeKey].y, radius, 0, 2 * Math.PI);
}
ctx.fillStyle = this.backgroundColor;
ctx.fill();
ctx.strokeStyle = this.nodeColor;
ctx.lineWidth = 3;
ctx.stroke();
ctx.globalAlpha = node.value;
ctx.fillStyle = this.nodeColor;
ctx.fill();
ctx.globalAlpha = 1;
}
};
BackpropNetwork.prototype = new Network();
BackpropNetwork.prototype.constructor = BackpropNetwork;
/**
* Neural network that is optimized via backpropagation.
* @param {Object} config The configuration to use.
*/
function BackpropNetwork(config) {
Network.call(this, config);
this.inputData = {};
this.targetData = {};
this.learningRate = 0.5;
this.step = 0;
this.totalErrorSum = 0;
this.averageError = [];
if (config !== undefined) {
if (config.learningRate !== undefined) {
this.learningRate = config.learningRate;
}
if (config.inputData !== undefined) {
this.setInputData(config.inputData);
}
if (config.targetData !== undefined) {
this.setTargetData(config.targetData);
}
}
}
/**
* Backpropagates the neural network, using the input and training data given. Currently does not affect connections to the bias node.
*/
BackpropNetwork.prototype.backpropagate = function() {
this.step++;
if (this.inputData[this.step] === undefined) {
this.averageError.push(this.totalErrorSum / this.step);
this.totalErrorSum = 0;
this.step = 0;
}
for (var inputKey in this.inputData[this.step]) {
this.nodes[inputKey].value = this.inputData[this.step][inputKey];
}
this.calculate();
var currentTargetData = this.targetData[this.step];
var totalError = this.getTotalError();
this.totalErrorSum += totalError;
var newWeights = {};
for (var i = 0; i < this.outputs.length; i++) {
var outputNode = this.nodes[this.outputs[i]];
for (var j = 0; j < outputNode.incomingConnections.length; j++) {
var hiddenToOutput = this.connections[outputNode.incomingConnections[j]];
var deltaRuleResult = -(currentTargetData[this.outputs[i]] - outputNode.value) * outputNode.value * (1 - outputNode.value) * this.nodes[hiddenToOutput.in].value;
newWeights[hiddenToOutput.id] = hiddenToOutput.weight - this.learningRate * deltaRuleResult;
}
}
for (var k = 0; k < this.hidden.length; k++) {
var hiddenNode = this.nodes[this.hidden[k]];
for (var l = 0; l < hiddenNode.incomingConnections.length; l++) {
var inputToHidden = this.connections[hiddenNode.incomingConnections[l]];
var total = 0;
for (var m = 0; m < hiddenNode.outgoingConnections.length; m++) {
var outgoing = this.connections[hiddenNode.outgoingConnections[m]];
var outgoingNode = this.nodes[outgoing.out];
total += ((-(currentTargetData[outgoing.out] - outgoingNode.value)) * (outgoingNode.value * (1 - outgoingNode.value))) * outgoing.weight;
}
var outOverNet = hiddenNode.value * (1 - hiddenNode.value);
var netOverWeight = this.nodes[inputToHidden.in].value;
var result = total * outOverNet * netOverWeight;
newWeights[inputToHidden.id] = inputToHidden.weight - this.learningRate * result;
}
}
for (var key in newWeights) {
this.connections[key].weight = newWeights[key];
}
};
/**
* Adds a target result to the target data. This will be compared to the output in order to determine error.
* @param {String} outputNodeID The ID of the output node whose value will be compared to the target.
* @param {Number} target The value to compare against the output when checking for errors.
*/
BackpropNetwork.prototype.addTarget = function(outputNodeID, target) {
this.targetData[outputNodeID] = target;
};
/**
* Sets the input data that will be compared to the target data.
* @param {Array} array An array containing the data to be inputted (ex. [0, 1] will set the first input node
* to have a value of 0 and the second to have a value of 1). Each array argument represents a single
* step, and will be compared against the parallel set in the target data.
*/
BackpropNetwork.prototype.setInputData = function() {
var all = arguments;
if (arguments.length == 1 && arguments[0].constructor == Array) {
all = arguments[0];
}
this.inputData = {};
for (var i = 0; i < all.length; i++) {
var data = all[i];
var instance = {};
for (var j = 0; j < data.length; j++) {
instance["INPUT:" + j] = data[j];
}
this.inputData[i] = instance;
}
};
/**
* Sets the target data that will be used to check for total error.
* @param {Array} array An array containing the data to be compared against (ex. [0, 1] will compare the first
* output node against 0 and the second against 1). Each array argument represents a single step.
*/
BackpropNetwork.prototype.setTargetData = function() {
var all = arguments;
if (arguments.length == 1 && arguments[0].constructor == Array) {
all = arguments[0];
}
this.targetData = {};
for (var i = 0; i < all.length; i++) {
var data = all[i];
var instance = {};
for (var j = 0; j < data.length; j++) {
instance["OUTPUT:" + j] = data[j];
}
this.targetData[i] = instance;
}
};
/**
* Calculates the total error of all the outputs' values compared to the target data.
* @return {Number} The total error.
*/
BackpropNetwork.prototype.getTotalError = function() {
var sum = 0;
for (var i = 0; i < this.outputs.length; i++) {
sum += Math.pow(this.targetData[this.step][this.outputs[i]] - this.nodes[this.outputs[i]].value, 2) / 2;
}
return sum;
};
/**
* A gene containing the data for a single connection in the neural network.
* @param {String} inID The ID of the incoming node.
* @param {String} outID The ID of the outgoing node.
* @param {Number} weight The weight of the connection to create.
* @param {Number} innovation The innovation number of the gene.
* @param {Boolean} enabled Whether the gene is expressed or not.
*/
function Gene(inID, outID, weight, innovation, enabled) {
if (innovation === undefined) {
innovation = 0;
}
this.innovation = innovation;
this.in = inID;
this.out = outID;
if (weight === undefined) {
weight = 1;
}
this.weight = weight;
if (enabled === undefined) {
enabled = true;
}
this.enabled = enabled;
}
/**
* Returns the connection that the gene represents.
* @return {Connection} The generated connection.
*/
Gene.prototype.getConnection = function() {
return new Connection(this.in, this.out, this.weight);
};
/**
* A genome containing genes that will make up the neural network.
* @param {Number} inputNodes The number of input nodes to create.
* @param {Number} outputNodes The number of output nodes to create.
*/
function Genome(inputNodes, outputNodes) {
this.inputNodes = inputNodes;
this.outputNodes = outputNodes;
this.genes = [];
this.fitness = -Number.MAX_VALUE;
this.globalRank = 0;
this.randomIdentifier = Math.random();
}
Genome.prototype.containsGene = function(inID, outID) {
for (var i = 0; i < this.genes.length; i++) {
if (this.genes[i].inID == inID && this.genes[i].outID == outID) {
return true;
}
}
return false;
};
/**
* A species of genomes that contains genomes which closely resemble one another, enough so that they are able to breed.
*/
function Species() {
this.genomes = [];
this.averageFitness = 0;
}
/**
* Culls the genomes to the given amount by removing less fit genomes.
* @param {Number} [remaining] The number of genomes to cull to [Default is half the size of the species (rounded up)].
*/
Species.prototype.cull = function(remaining) {
this.genomes.sort(compareGenomesDescending);
if (remaining === undefined) {
remaining = Math.ceil(this.genomes.length / 2);
}
while (this.genomes.length > remaining) {
this.genomes.pop();
}
};
/**
* Calculates the average fitness of the species.
*/
Species.prototype.calculateAverageFitness = function() {
var sum = 0;
for (var j = 0; j < this.genomes.length; j++) {
sum += this.genomes[j].fitness;
}
this.averageFitness = sum / this.genomes.length;
};
/**
* Returns the network that the genome represents.
* @return {Network} The generated network.
*/
Genome.prototype.getNetwork = function() {
var network = new Network();
network.createNodes(this.inputNodes, 0, this.outputNodes);
for (var i = 0; i < this.genes.length; i++) {
var gene = this.genes[i];
if (gene.enabled) {
if (network.nodes[gene.in] === undefined && gene.in.indexOf("HIDDEN") != -1) {
network.nodes[gene.in] = new Node(gene.in);
network.hidden.push(gene.in);
}
if (network.nodes[gene.out] === undefined && gene.out.indexOf("HIDDEN") != -1) {
network.nodes[gene.out] = new Node(gene.out);
network.hidden.push(gene.out);
}
network.addConnection(gene.in, gene.out, gene.weight);
}
}
return network;
};
/**
* Creates and optimizes neural networks via neuroevolution, using the Neuroevolution of Augmenting Topologies method.
* @param {Object} config The configuration to use.
*/
function Neuroevolution(config) {
this.genomes = [];
this.populationSize = 100;
this.mutationRates = {
createConnection: 0.05,
createNode: 0.02,
modifyWeight: 0.15,
enableGene: 0.05,
disableGene: 0.1,
createBias: 0.1,
weightMutationStep: 2
};
this.inputNodes = 0;
this.outputNodes = 0;
this.elitism = true;
this.deltaDisjoint = 2;
this.deltaWeights = 0.4;
this.deltaThreshold = 2;
this.hiddenNodeCap = 10;
this.fitnessFunction = function (network) {log("ERROR: Fitness function not set"); return -1;};
this.globalInnovationCounter = 1;
this.currentGeneration = 0;
this.species = [];
this.newInnovations = {};
if (config !== undefined) {
if (config.populationSize !== undefined) {
this.populationSize = config.populationSize;
}
if (config.inputNodes !== undefined) {
this.inputNodes = config.inputNodes;
}
if (config.outputNodes !== undefined) {
this.outputNodes = config.outputNodes;
}
if (config.mutationRates !== undefined) {
var configRates = config.mutationRates;
if (configRates.createConnection !== undefined) {
this.mutationRates.createConnection = configRates.createConnection;
}
if (configRates.createNode !== undefined) {
this.mutationRates.createNode = configRates.createNode;
}
if (configRates.modifyWeight !== undefined) {
this.mutationRates.modifyWeight = configRates.modifyWeight;
}
if (configRates.enableGene !== undefined) {
this.mutationRates.enableGene = configRates.enableGene;
}
if (configRates.disableGene !== undefined) {
this.mutationRates.disableGene = configRates.disableGene;
}
if (configRates.createBias !== undefined) {
this.mutationRates.createBias = configRates.createBias;
}
if (configRates.weightMutationStep !== undefined) {
this.mutationRates.weightMutationStep = configRates.weightMutationStep;
}
}
if (config.elitism !== undefined) {
this.elitism = config.elitism;
}
if (config.deltaDisjoint !== undefined) {
this.deltaDisjoint = config.deltaDisjoint;
}
if (config.deltaWeights !== undefined) {
this.deltaWeights = config.deltaWeights;
}
if (config.deltaThreshold !== undefined) {
this.deltaThreshold = config.deltaThreshold;
}
if (config.hiddenNodeCap !== undefined) {
this.hiddenNodeCap = config.hiddenNodeCap;
}
}
}
/**
* Populates the population with empty genomes, and then mutates the genomes.
*/
Neuroevolution.prototype.createInitialPopulation = function() {
this.genomes = [];
for (var i = 0; i < this.populationSize; i++) {
var genome = this.linkMutate(new Genome(this.inputNodes, this.outputNodes));
this.genomes.push(genome);
}
this.mutate();
};
/**
* Mutates the entire population based on the mutation rates.
*/
Neuroevolution.prototype.mutate = function() {
for (var i = 0; i < this.genomes.length; i++) {
var network = this.genomes[i].getNetwork();
if (Math.random() < this.mutationRates.createConnection) {
this.genomes[i] = this.linkMutate(this.genomes[i]);
}
if (Math.random() < this.mutationRates.createNode && this.genomes[i].genes.length > 0 && network.hidden.length < this.hiddenNodeCap) {
var geneIndex = randomNumBetween(0, this.genomes[i].genes.length - 1);
var gene = this.genomes[i].genes[geneIndex];
if (gene.enabled && gene.in.indexOf("INPUT") != -1 && gene.out.indexOf("OUTPUT") != -1) {
var newNum = -1;
var found = true;
while (found) {
newNum++;
found = false;
for (var j = 0; j < this.genomes[i].genes.length; j++) {
if (this.genomes[i].genes[j].in.indexOf("HIDDEN:" + newNum) != -1 || this.genomes[i].genes[j].out.indexOf("HIDDEN:" + newNum) != -1) {
found = true;
}
}
}
if (newNum < this.hiddenNodeCap) {
var nodeName = "HIDDEN:" + newNum;
this.genomes[i].genes[geneIndex].enabled = false;
this.genomes[i].genes.push(new Gene(gene.in, nodeName, 1, this.globalInnovationCounter));
this.globalInnovationCounter++;
this.genomes[i].genes.push(new Gene(nodeName, gene.out, gene.weight, this.globalInnovationCounter));
this.globalInnovationCounter++;
network = this.genomes[i].getNetwork();
}
}
}
if (Math.random() < this.mutationRates.createBias) {
if (Math.random() > 0.5 && network.inputs.length > 0) {
var inputIndex = randomNumBetween(0, network.inputs.length - 1);
if (network.getConnection("BIAS:" + network.inputs[inputIndex]) === undefined) {
this.genomes[i].genes.push(new Gene("BIAS", network.inputs[inputIndex]));
}
} else if (network.hidden.length > 0) {
var hiddenIndex = randomNumBetween(0, network.hidden.length - 1);
if (network.getConnection("BIAS:" + network.hidden[hiddenIndex]) === undefined) {
this.genomes[i].genes.push(new Gene("BIAS", network.hidden[hiddenIndex]));
}
}
}
for (var k = 0; k < this.genomes[i].genes.length; k++) {
this.genomes[i].genes[k] = this.pointMutate(this.genomes[i].genes[k]);
}
}
};
/**
* Attempts to create a new connection gene in the given genome.
* @param {Genome} genome The genome to mutate.
* @return {Genome} The mutated genome.
*/
Neuroevolution.prototype.linkMutate = function(genome) {
var network = genome.getNetwork();
var inNode = "";
var outNode = "";
if (Math.random() < 1/3 || network.hidden.length <= 0) {
inNode = network.inputs[randomNumBetween(0, this.inputNodes - 1)];
outNode = network.outputs[randomNumBetween(0, this.outputNodes - 1)];
} else if (Math.random() < 2/3) {
inNode = network.inputs[randomNumBetween(0, this.inputNodes - 1)];
outNode = network.hidden[randomNumBetween(0, network.hidden.length - 1)];
} else {
inNode = network.hidden[randomNumBetween(0, network.hidden.length - 1)];
outNode = network.outputs[randomNumBetween(0, this.outputNodes - 1)];
}
if (!genome.containsGene(inNode, outNode)) {
var newGene = new Gene(inNode, outNode, Math.random() * 2 - 1);
if (this.newInnovations[newGene.in + ":" + newGene.out] === undefined) {
this.newInnovations[newGene.in + ":" + newGene.out] = this.globalInnovationCounter;
newGene.innovation = this.globalInnovationCounter;
this.globalInnovationCounter++;
} else {
newGene.innovation = this.newInnovations[newGene.in + ":" + newGene.out];
}
genome.genes.push(newGene);
}
return genome;
};
/**
* Mutates the given gene based on the mutation rates.
* @param {Gene} gene The gene to mutate.
* @return {Gene} The mutated gene.
*/
Neuroevolution.prototype.pointMutate = function(gene) {
if (Math.random() < this.mutationRates.modifyWeight) {
gene.weight = gene.weight + Math.random() * this.mutationRates.weightMutationStep * 2 - this.mutationRates.weightMutationStep;
}
if (Math.random() < this.mutationRates.enableGene) {
gene.enabled = true;
}
if (Math.random() < this.mutationRates.disableGene) {
gene.enabled = false;
}
return gene;
};
/**
* Crosses two parent genomes with one another, forming a child genome.
* @param {Genome} firstGenome The first genome to mate.
* @param {Genome} secondGenome The second genome to mate.
* @return {Genome} The resultant child genome.
*/
Neuroevolution.prototype.crossover = function(firstGenome, secondGenome) {
var child = new Genome(firstGenome.inputNodes, firstGenome.outputNodes);
var firstInnovationNumbers = {};
for (var h = 0; h < firstGenome.genes.length; h++) {
firstInnovationNumbers[firstGenome.genes[h].innovation] = h;
}
var secondInnovationNumbers = {};
for (var j = 0; j < secondGenome.genes.length; j++) {
secondInnovationNumbers[secondGenome.genes[j].innovation] = j;
}
for (var i = 0; i < firstGenome.genes.length; i++) {
var geneToClone;
if (secondInnovationNumbers[firstGenome.genes[i].innovation] !== undefined) {
if (Math.random() < 0.5) {
geneToClone = firstGenome.genes[i];
} else {
geneToClone = secondGenome.genes[secondInnovationNumbers[firstGenome.genes[i].innovation]];
}
} else {
geneToClone = firstGenome.genes[i];
}
child.genes.push(new Gene(geneToClone.in, geneToClone.out, geneToClone.weight, geneToClone.innovation, geneToClone.enabled));
}
for (var k = 0; k < secondGenome.genes.length; k++) {
if (firstInnovationNumbers[secondGenome.genes[k].innovation] === undefined) {
var secondDisjoint = secondGenome.genes[k];
child.genes.push(new Gene(secondDisjoint.in, secondDisjoint.out, secondDisjoint.weight, secondDisjoint.innovation, secondDisjoint.enabled));
}
}
return child;
};
/**
* Evolves the population by creating a new generation and mutating the children.
*/
Neuroevolution.prototype.evolve = function() {
this.currentGeneration++;
this.newInnovations = {};
this.genomes.sort(compareGenomesDescending);
var children = [];
this.speciate();
this.cullSpecies();
this.calculateSpeciesAvgFitness();
var totalAvgFitness = 0;
var avgFitnesses = [];
for (var s = 0; s < this.species.length; s++) {
totalAvgFitness += this.species[s].averageFitness;
avgFitnesses.push(this.species[s].averageFitness);
}
var arr = [];
for (var j = 0; j < this.species.length; j++) {
var childrenToMake = Math.floor(this.species[j].averageFitness / totalAvgFitness * this.populationSize);
arr.push(childrenToMake);
if (childrenToMake > 0) {
children.push(this.species[j].genomes[0]);
}
for (var c = 0; c < childrenToMake - 1; c++) {
children.push(this.makeBaby(this.species[j]));
}
}
while (children.length < this.populationSize) {
children.push(this.makeBaby(this.species[randomNumBetween(0, this.species.length - 1)]));
}
this.genomes = [];
this.genomes = this.genomes.concat(children);
this.mutate();
this.speciate();
log(this.species.length);
};
/**
* Sorts the genomes into different species.
*/
Neuroevolution.prototype.speciate = function() {
this.species = [];
for (var i = 0; i < this.genomes.length; i++) {
var placed = false;
for (var j = 0; j < this.species.length; j++) {
if (!placed && this.species[j].genomes.length > 0 && this.isSameSpecies(this.genomes[i], this.species[j].genomes[0])) {
this.species[j].genomes.push(this.genomes[i]);
placed = true;
}
}
if (!placed) {
var newSpecies = new Species();
newSpecies.genomes.push(this.genomes[i]);
this.species.push(newSpecies);
}
}
};
/**
* Culls all the species to the given amount by removing less fit members of each species.
* @param {Number} [remaining] The number of genomes to cull all the species to [Default is half the size of the species].
*/
Neuroevolution.prototype.cullSpecies = function(remaining) {
var toRemove = [];
for (var i = 0; i < this.species.length; i++) {
this.species[i].cull(remaining);
if (this.species[i].genomes.length < 1) {
toRemove.push(this.species[i]);
}
}
for (var r = 0; r < toRemove.length; r++) {
this.species.remove(toRemove[r]);
}
};
/**
* Calculates the average fitness of all the species.
*/
Neuroevolution.prototype.calculateSpeciesAvgFitness = function() {
for (var i = 0; i < this.species.length; i++) {
this.species[i].calculateAverageFitness();
}
};
/**
* Creates a baby in the given species, with fitter genomes having a higher chance to reproduce.
* @param {Species} species The species to create a baby in.
* @return {Genome} The resultant baby.
*/
Neuroevolution.prototype.makeBaby = function(species) {
var mum = species.genomes[randomWeightedNumBetween(0, species.genomes.length - 1)];
var dad = species.genomes[randomWeightedNumBetween(0, species.genomes.length - 1)];
return this.crossover(mum, dad);
};
/**
* Calculates the fitness of all the genomes in the population.
*/
Neuroevolution.prototype.calculateFitnesses = function() {
for (var i = 0; i < this.genomes.length; i++) {
this.genomes[i].fitness = this.fitnessFunction(this.genomes[i].getNetwork());
}
};
/**
* Returns the relative compatibility metric for the given genomes.
* @param {Genome} genomeA The first genome to compare.
* @param {Genome} genomeB The second genome to compare.
* @return {Number} The relative compatibility metric.
*/
Neuroevolution.prototype.getCompatibility = function(genomeA, genomeB) {
var disjoint = 0;
var totalWeight = 0;
var aInnovationNums = {};
for (var i = 0; i < genomeA.genes.length; i++) {
aInnovationNums[genomeA.genes[i].innovation] = i;
}
var bInnovationNums = [];
for (var j = 0; j < genomeB.genes.length; j++) {
bInnovationNums[genomeB.genes[j].innovation] = j;
}
for (var k = 0; k < genomeA.genes.length; k++) {
if (bInnovationNums[genomeA.genes[k].innovation] === undefined) {
disjoint++;
} else {
totalWeight += Math.abs(genomeA.genes[k].weight - genomeB.genes[bInnovationNums[genomeA.genes[k].innovation]].weight);
}
}
for (var l = 0; l < genomeB.genes.length; l++) {
if (aInnovationNums[genomeB.genes[l].innovation] === undefined) {
disjoint++;
}
}
var n = Math.max(genomeA.genes.length, genomeB.genes.length);
return this.deltaDisjoint * (disjoint / n) + this.deltaWeights * (totalWeight / n);
};
/**
* Determines whether the given genomes are from the same species.
* @param {Genome} genomeA The first genome to compare.
* @param {Genome} genomeB The second genome to compare.
* @return {Boolean} Whether the given genomes are from the same species.
*/
Neuroevolution.prototype.isSameSpecies = function(genomeA, genomeB) {
return this.getCompatibility(genomeA, genomeB) < this.deltaThreshold;
};
/**
* Returns the genome with the highest fitness in the population.
* @return {Genome} The elite genome.
*/
Neuroevolution.prototype.getElite = function() {
this.genomes.sort(compareGenomesDescending);
return this.genomes[0];
};
//Private static functions
function sigmoid(t) {
return 1 / (1 + Math.exp(-t));
}
function randomNumBetween(min, max) {
return Math.floor(Math.random() * (max - min + 1) + min);
}
function randomWeightedNumBetween(min, max) {
return Math.floor(Math.pow(Math.random(), 2) * (max - min + 1) + min);
}
function compareGenomesAscending(genomeA, genomeB) {
return genomeA.fitness - genomeB.fitness;
}
function compareGenomesDescending(genomeA, genomeB) {
return genomeB.fitness - genomeA.fitness;
}
Array.prototype.remove = function() {
var what, a = arguments, L = a.length, ax;
while (L && this.length) {
what = a[--L];
while ((ax = this.indexOf(what)) !== -1) {
this.splice(ax, 1);
}
}
return this;
};
function log(text) {
console.log(text);
}
Also see: Tab Triggers