What is a Knight’s Tour?

Before we discuss what a knight’s tour is, we have to know about knights in chess. The knight in chess is the piece that is shaped like a horse.

The knight can move in an “L-shaped” pattern, where it can move forward twice and then decide whether to move right or left. Here is a simple illustration on how that would look like.

If we display all of the current possible moves for the knight, we get this pattern.

The knight can move to the square marked red, and then repeat the process on the new square. A knight’s tour is a sequence of moves that a knight can make in order to visit every chess square exactly once.

The Idea

As I was pondering on how to efficiently generate possible solutions, I stumbled upon some great videos on Genetic Algorithms created by Daniel Shiffman where he illustrated Genetic Algorithms using p5js, a javascript library for creative coding. The videos gave me an idea: What if I use genetic algorithm in the knight’s tour problem? So before doing the actual code, I did some research regarding genetic algorithm.

Genetic Algorithm

You can easily guess what the algorithm does by looking at its name; It’s all in the genes. Genetic Algorithm takes inspiration from Charles Darwin’s evolution theory, where he described evolution as “descend with modification”. Organisms survive by constantly adapting themselves with their own environments. Let’s make an example using giraffes. Suppose that a long long long time ago giraffes were all short.

They lived happily until they needed another food source: the leaves of trees. Since they are all too short to reach the leaves, most of them died of starvation. One day, a mutation occurred on one of the giraffes and it grew taller than the other.

The tall giraffe was more likely to survive – hence, more likely to breed and pass on its traits. After generations of passing down the “tall” trait, more giraffes received the trait and becoming taller.

Eventually, the tall giraffes took over the majority of the gene pool and slowly reducing the number of short giraffes until it’s no more.

From the short example above, genetic algorithm can be summarized in 4 steps:

1. Create gene pool (Breeding session)
2. Create candidates from the gene pool with a chance of mutation (New giraffes are born)
3. Select the best performing candidate (Best surviving giraffe)
4. Breed a new gene pool using the best candidates

For every time these steps are done, we say that it has passed one generation (basically saying one iteration but cooler). We keep looping the steps until we find a satisfying solution for our specific case. In the knight tour’s case, looping will stop when a valid tour is found.

Implementation

Now that we have our base concept established, let’s test our understanding by going hands on with the code!

Overview

We will organize the code as follows:

libraries/
     p5.min.js
 chromosome.js
 index.html
 knight.js
 population.js
 sketch.js
 table.js

We need to download p5.min.js from the official website to use the library.

Setting Up the Chess Table

First, let’s create a chess table. It’s just going to be simple table to give us some better visuals. Here’s the code for it:

// Table function holds the table entity
function Table()  {
  // show function draws the table on canvas
  this.show = function()  {
    noStroke();
    textAlign(CENTER);

    let x=0
    let y=0

    // loop through each squares and apply a checkerboard pattern
    // while also numbering each square
    for(var i=0;i<cols;i++)  {
      for(var j=0; j<cols; j++)  {
        // set the background color
        if((i+j)%2===0) fill(255);
        else fill(0);

        // draw the square
        rect((j*scl)+x,y, scl, scl);

        // set the text color & size
        if((i+j)%2===0) fill(0);
        else fill(255);
        textSize(scl/3);

        // draw the index of the square
        text(i*cols+j, (j*scl)+x+(scl/2), y+scl-(scl/2));

        // draw the x and y coordinates of the square
        textSize(scl/6);
        text("x : "+j +"  "+ "y : "+i, (j*scl)+x+(scl/2), y+scl-10);
      }
      // move to the next row
      y+=scl;
    }
  }
}

The table function holds the function show() that iterates through the number of columns and rows and starts drawing square by square with the following conditions:

• The color of the square;
• The size(scl) of the square, this will be uniform for all squares; and
• The x and y coordinates of the square.

The show function will work later on after we implement the function inside the sketch.js. It will look like this:

Creating the Knight

Now let’s start coding the knight. Each knight will hold these variables:

• X and Y coordinate
• Number of steps already taken
• Paths Taken in every move
• Fitness Function

The X and Y coordinates will tell the current position of the knight. When a knight moves, we track the number of steps that it has taken and also store the (x,y) coordinates of the move taken.

Let’s initialize the knight function.

// Knight function holds all the data for a knight entity
function Knight() {
  // initialize the knight entity
  // x, y holds the current knight position (currently pre-set to 0,0)
  this.x=0;
  this.y=0;
  this.steps=0;

  // initialize variables
  this.path = [];
  this.fitness = 0;
  // the first path will start on (0, 0)
  this.path.push(createVector(this.x, this.y));
}

Now, what can a knight do? The most obvious one: Move. Let’s add a move function inside the knight. I will add 2 move function: moveForward() and traceBack(). This way, we can consistently tell the knight which move to take given the direction.

// move forward holds the possible moves of a knight in all direction
  this.moveForward = function(direction) {
    switch(direction)  {
      case 1: this.x+=1; this.y-=2; break;
      case 2: this.x+=2; this.y-=1; break;
      case 3: this.x+=2; this.y+=1; break;
      case 4: this.x+=1; this.y+=2; break;
      case 5: this.x-=1; this.y+=2; break;
      case 6: this.x-=2; this.y+=1; break;
      case 7: this.x-=2; this.y-=1; break;
      case 8: this.x-=1; this.y-=2; break;
    }
  }

  // trace back a move
  this.traceBack = function(direction) {
    switch(direction)  {
      case 1: this.x-=1; this.y+=2; break;
      case 2: this.x-=2; this.y+=1; break;
      case 3: this.x-=2; this.y-=1; break;
      case 4: this.x-=1; this.y-=2; break;
      case 5: this.x+=1; this.y-=2; break;
      case 6: this.x+=2; this.y-=1; break;
      case 7: this.x+=2; this.y+=1; break;
      case 8: this.x+=1; this.y+=2; break;
    }
  }

Genetic Algorithm Part

Now we will start the fun part! Before implementing the Genetic Algorithm into our knight, let’s set several things straight first. We need the Genetic Algorithm to:

• Create unique traits for each knight
• Evaluate the fitness of the Knight
• Breed the next generation of knights

Chromosome

In our body, we have chromosomes that holds the information for our own traits; the color of our eyes, our height, and so many other things. If the knights were to have some traits, what kind of traits should it have? In this project, I will be using the moves taken by the knights as their traits.

Let’s code it in chromosome.js

// Chromosome function holds the chromosome entity
function Chromosome(genes)  {
  // initialize variables
  // genes will hold the unique traits of the chromosome
  this.genes = [];
  // apply an existing set of genes if given one
  if(genes) {
    this.genes = genes;
  }
  else {
    // generate random genes (random moves)
    for (var i=0; i<cols*cols-1; i++)  {
        this.genes[i] = int(random(1, 9));
    }
  }
}

In chromosome.js, we are saying that the chromosome will hold an array of genes, basically dictating what moves the knight should take. If there were no genes given, the chromosome will generate a random set of genes.

Since we have the chromosome for the knights, we can implement that in our knight.js. We can tell each knight to hold a chromosome by adding a few more lines in knight.js:

//Add chromosome as an input variable
function Knight(chromosome) {set to 0,0)
  this.x=0;
  this.y=0;
  this.steps=0;

  // add a checker to either use an existing chromosome or
  // generate a new random chromosome
  if(chromosome) {
    this.chromosome = chromosome;
  }
  else {
    // initialize a new random chromosome
    this.chromosome = new Chromosome();
  }
}

We will code in a move() function that will use the gene of the current step as a move command.

There’s a problem though, the genes can give invalid commands even when there are still valid moves available. To fix this, we will apply a “repair” in the algorithm; Cycle through each possible steps to find a legal move. If we can’t find any, then the knight will move on to the next move.

Here’s what the code to be added in knight.js:

  // move the knight given its current turn
  this.move = function()  {
    // set default variables
    legal=false;
    limit = 0
    // we check if the move is either illegal or havent cycled through all of the possible moves
    // if we can't find a legal move, we continue
    while(!legal && limit++<8)  {
      this.moveForward(this.chromosome.genes[this.steps]);
      if((this.x>=0 && this.x<cols) && (this.y>=0 && this.y<cols)) {
            legal=true;
        for(var i=0; i<this.path.length; i++) {
          if((this.path[i].x==this.x) && (this.path[i].y==this.y)){
            legal=false;
          }
        }
      }
      // if the last move was illegal, attempt to trace back
      if(!legal) {
        this.traceBack(this.chromosome.genes[this.steps]);
        if(this.findForward) {
          this.chromosome.genes[this.steps] = (this.chromosome.genes[this.steps]%8)+1;
        }
        else {
          this.chromosome.genes[this.steps] = ((this.chromosome.genes[this.steps]+6)%8)+1;
        }
      }
    }
    // add the last move's coordinates to the knight's path array
    this.path[this.steps+1] = createVector(this.x, this.y);
    // increment the number of steps taken by the knight
    this.steps++;
  }

Population

After adding the ability to move for our knights, we need to start generating a population for a single generation. What makes Genetic Algorithm effective (and fun to watch) is the ability to run a mini survival of the fittest in a given population. We can see a lot of different outcomes only by changing the population size. Let’s make a function in population.js:

// Population function holds the population entity
function Population(popsize) {
  // initialize variables
  this.generation = 1
  this.knights = [];
  this.popsize = popsize;
  this.matingpool = [];

  // fill the population with knight entities
  for (var i=0; i < this.popsize; i++)  {
    this.knights[i] = new Knight();
  }

  // run function tells all of the knights to generate their moves
  this.run = function() {
    // loop for number of moves
    for(var i=0; i< cols*cols-1; i++) {
      // loop through each of the knights
      for (var j=0; j < this.popsize; j++)  {
        // tell the knight to generate a single move
        this.knights[j].move();
      }
    }
  }
}

Here, we are saying that a population accepts a size that will be used as the amount of knights to generate in one single generation. Afterwards, we can call this.run() to run all of the knights in the population.

Fitness Function

We now have a knight that can move and be given a list of moves (chromosome). To make use of those things, we will implement a way to calculate the survivability of a knight, or what we call a fitness value. In this case, the fitness function will be derived from the number of legal moves until one illegal move is found. So for example, if we encounter an illegal move at move 7 (remember that we start the count from 0), the fitness value of the knight would be 7 (7 legal moves from 0 to 6).

Let’s code this in knight.js:

  // calcFitness goes through the paths and adds the fitness value until it reaches an invalid move
  this.calcFitness = function()  {
    // default state for legal is true
    legal=true;
    this.fitness = 0;
    
    // loops through paths taken by the knight
    for(var i = 0; i<this.path.length; i++) {
        // check whether the knight is outside of the board
        if(this.path[i].x<0 || this.path[i].x>cols-1 || this.path[i].y<0 || this.path[i].y>cols-1)  {
          legal=false;
        }
        // check whether the current square has been visited before
        for(var j=0; j<i; j++)  {
          if(this.path[i].x == this.path[j].x && this.path[i].y == this.path[j].y) {
            legal=false;
          }
        }
        // return when we have found an illegal move
        if(!legal)  {
          return
        }
        // increment fitness value
        this.fitness++;
    }
  }

Evaluating Fitness

Now that all of the knights have their own separate fitness values, we can evaluate them at the end of each generation. We will create an algorithm to tell that the knights with better scores will be more likely to survive. In this example, I will only use the roulette wheel selection method. In this method, we will generate a wheel array that will store a knight N amount of times in the array. N is determined by its normalized fitness value (relative to the maximum fitness of the generation) multiplied by 100.

So, if we have 2 knights each having a fitness function of 30 and 10, the first knight will be inserted to the array 100 times, while the second knight will only be inserted 33 times.

Add this function inside population.js‘s Population function:

// evaluate function will calculate the fitness function for every knights
// evaluation results will determine the mating pool
this.evaluate = function()  {
  // initialize variables
  var maxfit=0;
  var bestKnight;

  // iterate through all of the knights in the population
  for (var i=0; i < this.popsize; i++)  {
    this.knights[i].calcFitness();
    
    // store the highest fitness
    if(this.knights[i].fitness>maxfit)  {
      maxfit=this.knights[i].fitness;
    }
  }

  // normalize fitness values
  for (var i = 0; i < this.popsize; i++) {
    this.knights[i].fitness /= maxfit;
  }

  // create a mating pool
  this.matingpool = [];

  // loop through every knight in the population
  for (var i = 0; i < this.popsize; i++) {
        // insert the knight's chromosome to the mating pool
        // n times according to how good its fitness value is
        var n = this.knights[i].fitness * 100;
        for (var j = 0; j < n; j++) {
          this.matingpool.push(this.knights[i]);
        }
      }

  // if we have found maximum fitness (all squares successfully visited)
  if(maxfit==(cols*cols))  {
    // stop the loop
    noLoop();
  }

  // add the generation count
  this.generation++;
}

Crossover & Mutation

After creating the mating pool, we will prepare the next generation’s knights by crossing over the mating pool.

Firstly, we will add another function inside chromosome.js to for crossover and mutation. The crossover will take another chromosome as an input, and will combine the genes from both chromosomes to form a new one.

The mutation gives genes a probability to “mutate”, meaning that it will turn into a random move. This is what gives the Genetic Algorithm the motivation to explore new moves.

Let’s code this in chromosome.js:

 // crossover attempts to mix the genes between 2 chromosomes
  this.crossover = function(partner) {
    var newgenes = [];
    // pick a mid divider that will determine which gene to take for the current index
    var mid = floor(random(cols*cols-1));
    for (var i=0; i<cols*cols-1; i++)  {
      if(i > mid) {
        newgenes[i] = this.genes[i];
      }
      else {
        newgenes[i] = partner.genes[i];
      }
    }
    return new Chromosome(newgenes);
  }

  // mutation will attempt to randomly alter the genes
  this.mutation = function()  {
    for (var i=0; i<this.genes.length; i++) {
      if(random(1)<0.01)  {
        this.genes[i] = int(random(1,9));
      }
    }
  }

Now in population.js, we will implement the functions that we have made by creating another function:

// selection function selects a random parent A and parent B
// from the mating pool and cross over their chromosomes together
// this action is done for the number of population
this.selection = function() {
  var newKnights = [];
  for (var i=0; i<this.popsize; i++) {
    // picks random parent candidates from the mating pool
    var parentA = random(this.matingpool).chromosome;
    var parentB = random(this.matingpool).chromosome;
    // crossover the chromosomes
    var child = parentA.crossover(parentB);
    // gives a mutation chance to the newly created knight
    child.mutation();
    // add the new knight to the array
    newKnights[i] = new Knight(child);
  }
  // replace the old population with the new one
  this.knights = newKnights;
}

Combining Everything Up

Let’s recap. We now have table.js, knight.js, population.js, and chromosome.js. I’ll also add the code to visualize the algorithm using p5js. They would look like:

// Table function holds the table entity
function Table()  {
  // show function draws the table on canvas
  this.show = function()  {
    noStroke();
    textAlign(CENTER);

    let x=0
    let y=0

    // loop through each squares and apply a checkerboard pattern
    // while also numbering each square
    for(var i=0;i<cols;i++)  {
      for(var j=0; j<cols; j++)  {
        // set the background color
        if((i+j)%2===0) fill(255);
        else fill(0);

        // draw the square
        rect((j*scl)+x,y, scl, scl);

        // set the text color & size
        if((i+j)%2===0) fill(0);
        else fill(255);
        textSize(scl/3);

        // draw the index of the square
        text(i*cols+j, (j*scl)+x+(scl/2), y+scl-(scl/2));

        // draw the x and y coordinates of the square
        textSize(scl/6);
        text("x : "+j +"  "+ "y : "+i, (j*scl)+x+(scl/2), y+scl-10);
      }
      // move to the next row
      y+=scl;
    }
  }
}

// Knight function holds all the data for a knight entity
function Knight(chromosome) {
  // initialize the knight entity
  // x, y holds the current knight position (currently pre-set to 0,0)
  this.x=0;
  this.y=0;
  this.steps=0;

  // use existing cross over parent chromosome if it does exist
  if(chromosome) {
    this.chromosome = chromosome;
  }
  else {
    // initialize a new random chromosome
    this.chromosome = new Chromosome();
  }

  // initialize variables
  this.path = [];
  this.fitness = 0;
  // the first path will start on (0, 0)
  this.path.push(createVector(this.x, this.y));
  // findForward will determine how the knight cycles possible steps to fix illegal moves
  this.findForward = boolean(Math.round(random(1)));

  // calcFitness goes through the paths and adds the fitness value until it reaches an invalid move
  this.calcFitness = function()  {
    // default state for legal is true
    legal=true;
    this.fitness = 0;
    
    // loops through paths taken by the knight
    for(var i = 0; i<this.path.length; i++) {
        // check whether the knight is outside of the board
        if(this.path[i].x<0 || this.path[i].x>cols-1 || this.path[i].y<0 || this.path[i].y>cols-1)  {
          legal=false;
        }
        // check whether the current square has been visited before
        for(var j=0; j<i; j++)  {
          if(this.path[i].x == this.path[j].x && this.path[i].y == this.path[j].y) {
            legal=false;
          }
        }
        // return when we have found an illegal move
        if(!legal)  {
          return
        }
        // increment fitness value
        this.fitness++;
    }
  }

  // move forward holds the possible moves of a knight in all direction
  this.moveForward = function(direction) {
    switch(direction)  {
      case 1: this.x+=1; this.y-=2; break;
      case 2: this.x+=2; this.y-=1; break;
      case 3: this.x+=2; this.y+=1; break;
      case 4: this.x+=1; this.y+=2; break;
      case 5: this.x-=1; this.y+=2; break;
      case 6: this.x-=2; this.y+=1; break;
      case 7: this.x-=2; this.y-=1; break;
      case 8: this.x-=1; this.y-=2; break;
    }
  }

  // trace back a move
  this.traceBack = function(direction) {
    switch(direction)  {
      case 1: this.x-=1; this.y+=2; break;
      case 2: this.x-=2; this.y+=1; break;
      case 3: this.x-=2; this.y-=1; break;
      case 4: this.x-=1; this.y-=2; break;
      case 5: this.x+=1; this.y-=2; break;
      case 6: this.x+=2; this.y-=1; break;
      case 7: this.x+=2; this.y+=1; break;
      case 8: this.x+=1; this.y+=2; break;
    }
  }

  // move the knight given its current turn
  this.move = function()  {
    // set default variables
    legal=false;
    limit = 0
    // we check if the move is either illegal or havent cycled through all of the possible moves
    // if we can't find a legal move, we continue
    while(!legal && limit++<8)  {
      this.moveForward(this.chromosome.genes[this.steps]);
      if((this.x>=0 && this.x<cols) && (this.y>=0 && this.y<cols)) {
            legal=true;
        for(var i=0; i<this.path.length; i++) {
          if((this.path[i].x==this.x) && (this.path[i].y==this.y)){
            legal=false;
          }
        }
      }
      // if the last move was illegal, attempt to trace back
      if(!legal) {
        this.traceBack(this.chromosome.genes[this.steps]);
        if(this.findForward) {
          this.chromosome.genes[this.steps] = (this.chromosome.genes[this.steps]%8)+1;
        }
        else {
          this.chromosome.genes[this.steps] = ((this.chromosome.genes[this.steps]+6)%8)+1;
        }
      }
    }
    // add the last move's coordinates to the knight's path array
    this.path[this.steps+1] = createVector(this.x, this.y);
    // increment the number of steps taken by the knight
    this.steps++;
  }

  // show function is used to display the knight's moves on the board
  // the moves will be displayed until an illegal move is encountered.
  this.show = function()  {
    legal=true;
    noStroke();
    for(var i=0; i < this.path.length; i++) {
      if(this.path[i].x<0 || this.path[i].x>cols-1 || this.path[i].y<0 || this.path[i].y>cols-1)  {
        legal=false;
      }
      for(var j=0; j<i; j++)  {
        if(this.path[i].x == this.path[j].x && this.path[i].y == this.path[j].y) {
          legal=false;
        }
      }
      if(legal)  {
        fill(0,255,0,150);
      }
      else {
        fill(255,0,0,150);
      }
      rect(this.path[i].x*scl,this.path[i].y*scl, scl, scl);
      fill(0,255,0);
      ellipse(this.path[i].x*scl+scl/2, this.path[i].y*scl+scl/2, scl/6, scl/6);
      fill(255);
      text(i+1, this.path[i].x*scl,this.path[i].y*scl, scl, scl);
    }
    strokeWeight(scl/20);
    stroke(0,255,0);
    noFill();
    beginShape();
    for(var i = 0; i < this.path.length; i++) {
      for(var j=0; j < i; j++) {
        if((this.path[i].x === this.path[j].x) && (this.path[i].y === this.path[j].y))  {
          legal=false;
        }
      }
    vertex(this.path[i].x*scl+scl/2,this.path[i].y*scl+scl/2);
    }
    endShape();
    chromosomes.html(this.chromosome.genes);
  }
}

// Population function holds the population entity
 function Population(popsize) {
   // initialize variables
   this.generation = 1
   this.knights = [];
   this.popsize = popsize;
   this.matingpool = [];
 // fill the population with knight entities
   for (var i=0; i < this.popsize; i++)  {
     this.knights[i] = new Knight();
   }
 // evaluate function will calculate the fitness function for every knights
   // evaluation results will determine the mating pool
   this.evaluate = function()  {
     // initialize variables
     var maxfit=0;
     var bestKnight;
 // iterate through all of the knights in the population for (var i=0; i < this.popsize; i++)  {   this.knights[i].calcFitness();   // choose the knight with the highest fitness   if(this.knights[i].fitness>maxfit)  {     maxfit=this.knights[i].fitness;     bestKnight = this.knights[i];   } } // normalize fitness values for (var i = 0; i < this.popsize; i++) {   this.knights[i].fitness /= maxfit; } // create a mating pool this.matingpool = []; // loop through every knight in the population for (var i = 0; i < this.popsize; i++) {       // insert the knight's chromosome to the mating pool       // n times according to how good its fitness value is       var n = this.knights[i].fitness * 100;       for (var j = 0; j < n; j++) {         this.matingpool.push(this.knights[i]);       }     } // display the best knight's movements on the board bestKnight.show(); // print the maximum fitness of the current generation stats.html("Generation " + this.generation + " maximum fitness is " + maxfit); // if we have found maximum fitness (all squares successfully visited) if(maxfit==(cols*cols))  {   // stop the loop   noLoop();   // inform that we are done   stats.html("Done with " + this.generation + " Generations"); } // add the generation count this.generation++;
 }
 // selection function selects a random parent A and parent B
   // from the mating pool and cross over their chromosomes together
   // this action is done for the number of population
   this.selection = function() {
     var newKnights = [];
     for (var i=0; i<this.popsize; i++) {
       // picks random parent candidates from the mating pool
       var parentA = random(this.matingpool).chromosome;
       var parentB = random(this.matingpool).chromosome;
       // crossover the chromosomes
       var child = parentA.crossover(parentB);
       // gives a mutation chance to the newly created knight
       child.mutation();
       // add the new knight to the array
       newKnights[i] = new Knight(child);
     }
     // replace the old population with the new one
     this.knights = newKnights;
   }
 // run function tells all of the knights to generate their moves
   this.run = function() {
     // loop for number of moves
     for(var i=0; i< cols*cols-1; i++) {
       // loop through each of the knights
       for (var j=0; j < this.popsize; j++)  {
         // tell the knight to generate a single move
         this.knights[j].move();
       }
     }
   }
 }

// Chromosome function holds the chromosome entity
function Chromosome(genes)  {
  // initialize variables
  // genes will hold the unique traits of the chromosome
  this.genes = [];
  // apply an existing set of genes if given one
  if(genes) {
    this.genes = genes;
  }
  else {
    // generate random genes
    for (var i=0; i<cols*cols-1; i++)  {
        this.genes[i] = int(random(1, 9));
    }
  }

  // crossover attempts to mix the genes between 2 chromosomes
  this.crossover = function(partner) {
    var newgenes = [];
    // pick a mid divider that will determine which gene to take for the current index
    var mid = floor(random(cols*cols-1));
    for (var i=0; i<cols*cols-1; i++)  {
      if(i > mid) {
        newgenes[i] = this.genes[i];
      }
      else {
        newgenes[i] = partner.genes[i];
      }
    }
    return new Chromosome(newgenes);
  }

  // mutation will attempt to randomly alter the genes
  this.mutation = function()  {
    for (var i=0; i<this.genes.length; i++) {
      if(random(1)<0.01)  {
        this.genes[i] = int(random(1,9));
      }
    }
  }
}

And that’s it! You’re done coding your first Genetic Algorithm! What’s left is only implementing the Genetic Algorithm. The code will run in sketch.js, with setup() only running once and loop() runs until noloop() gets called. (That’s when we have found a valid tour).

// populationSize, change this to experiment around
 var populationSize = 50;
 // number of columns
 // this also applies to row
 var cols=8;
 // variable initialization
 var scl;
 var population;
 var table;
 var stats;
 var chromosomes;
 var tourslog;
 var generations = [];
 var knightmoves = [];
 var toursdata;
 // setup is a p5js function that
 // will run only once
 function setup() {
   // create a 800x800 pixel canvas
   createCanvas(800,800);
   // set the background to black
   background(0);
   // set fill color to white
   fill(255);
 // set scale to be width of canvas divided by number of columns
   scl=width/cols;
 // initialize new table
   table = new Table();
 // initialize new population with the population size
   population = new Population(populationSize);
 // display the table
   table.show();
 // create a paragraph element
   stats = createP("Stats");
   // place the paragraph on 850, 10
   stats.position(850,10);
   // add class "stats" to the paragraph
   stats.class("stats");
   // rename paragraph element to say GENERATION 0
   stats.html("GENERATION 0");
 // create a new paragraph element
   chromosomes = createP("Chromosomes");
   chromosomes.position(850,40);
   chromosomes.class("chromosomes");
   chromosomes.html("Chromosomes");
 }
 // draw function is the p5js function
 // that will constantly loop
 function draw() {
   // run a generation of the genetic algorithm
   population.run();
 // refresh the table
   table.show();
 // evaluate the GA's generation
   // display the best candidate on the board
   population.evaluate();
 // select the candidates for the next GA generation
   population.selection();
 }

Since we are running the code from an HTML file, we will have to import the javascript files into the HTML code. Type this into your index.html:

<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8">
    <title>Knight Tour</title>
    <script src="libraries/p5.min.js" type="text/javascript"></script>

    <script src="https://www.gstatic.com/firebasejs/3.6.9/firebase.js"></script>
    <script src="sketch.js" type="text/javascript"></script>
    <script src="table.js" type="text/javascript"></script>
    <script src="knight.js" type="text/javascript"></script>
    <script src="population.js" type="text/javascript"></script>
    <script src="chromosome.js" type="text/javascript"></script>

    <style> body {padding: 0; margin: 0;} canvas {vertical-align: top;} </style>
  </head>
  <body>
  </body>
</html>

All that’s left to do is to open index.html in your browser! It should look like this:

Here’s a running example with a population size 50 (change the population size around and see what happens!):

https://editor.p5js.org/Rocksus/full/yX2ZlGZDL

Conclusion

If you have finished this project yourself, congratulations! Through this, we have learned about knight tours, using Genetic Algorithm to solve it, and using p5js to visualize the process.

This is a very simple approach using Genetic Algorithm. There are a lot of different ways to code a Genetic Algorithm, such as getting the fitness values and crossovers. Hope this has been a good introduction for you!

You can always check out the code in this github repository. In the repository, I also included a way to store all of your past tours in a firebase database.

Tags

• Javascript
• Machine Learning
• p5js