Explore Simple Game Algorithms with Color Walk: Part 2

In this series we are taking a look at different game algorithms using the simple game Color Walk as a sandbox for exploration and discovery. The last post was an introduction that described what Color Walk is, explained how to get it running on your own setup, and presented some brainstorming of possible algorithms to explore. This post will start digging into the simplest of those algorithms: round-robin, but first, we need to build up some tooling around the Color Walk JavaScript code to make it easier to test out our algorithms and benchmark their performance. We'll use the round-robin algorithm as a vehicle to help develop this tooling, so we have something to play with while getting the benchmark tooling up and running.

Round-Robin and the Development of Tooling

We're using Jennifer Dewalt's Color Walk code as a starting point. The JavaScript is fairly easy to understand. She builds the board from a grid of <div> elements with randomly colored backgrounds, and below the board is a set of 5 control buttons, each with the background corresponding to the color that it will remove from the board if clicked. All of the board updating and end-of-game logic is contained within the Control object, which may not be what we want once we start automating the color picking with a batch mode, but we'll get to that later.

For now, let's work on adding in support for the user to click a button that will follow the round-robin algorithm. Each time they click the button, it will remove the blocks corresponding to its current color and then switch to the next color in a cycle. To do that, we'll add another button to color_walk.html.erb below the other control buttons:

  <div id="control_container">
    <p class="btn moves score">0</p>
  </div>

  <div id="solver_container">
    <p>Round Robin</p>
  </div>

This solver_container is not actually a button, but a container in which buttons and other algorithm controls will be created, either in the HTML, or in JavaScript. The Round Robin text will identify the round-robin algorithm button for now, but I'm sure we'll be changing it to be more flexible down the road. We'll also want to give the control we add to this container the same style as the controls in control_container, so we can add its ID to color_walk.scss:

    #control_container, #solver_container {
     margin-top: 20px;
        // ...

In the future I'll assume that we all know how to add HTML elements and style them so we can focus on the algorithm code that will be added to the JavaScript. To implement the round-robin algorithm, the idea will be to display the next color that will be chosen on the round-robin button, and each time it's clicked, trigger the code that removes that color from the board and change the round-robin button to the next color in the sequence, cycling through all five colors repeatedly. To achieve this behavior, we'll need an array of the color controls, which doesn't currently exist, so we'll add it to the definitions at the top of color_walk.js:

  var blocks = [];
  var colors = ['#14b19f', '#0e274e', '#ec5257', '#6c2275', '#f9ac00'];
  var controls = [];

Then, we can add the controls to this new array as they're being created:

  makeBlocks();

  _.each(colors, function (color) {
    controls.push(new Control(color));
  });

  new Solver();

We also created our Solver button here. This will be the button that cycles through the color controls and changes color when clicked. Its creation code looks like this:

  function Solver() {
    this.index = 0;

    this.init = function() {
      var that = this;

      this.solver = $('<div>', {
        id: 'solver',
        class: 'control btn',
        style: 'background-color:' + colors[this.index]
      }).on('click', function (e) {
        that.roundRobin();
      }).appendTo('#solver_container');
    };

    this.init();

    this.roundRobin = function() {
      controls[this.index].updateGameBoard();
      this.index = (this.index + 1) % controls.length;
      this.solver.css('background-color', colors[this.index]);
    }
  }

Here we add a member variable to keep track of which color and control we're on by an array index, and then we initialize the button, giving it the background color of the current index and a click function that calls the round-robin algorithm. The roundRobin() function implements the algorithm, which is simply triggering the current control to update the game board, increment the index with wrap-around when it reaches the end of the controls, and updating the background color of the button to the new color index. I'm not sure if this will be the best way to support multiple algorithms later on, but it works and looks pretty clean for now, so we can go with it and change it later if needed.

However, one thing is still not quite right. Even though we have access to the color controls in the controls[] array, we don't yet have access to the updateGameBoard() function because it is declared as a local function in the Control object. To give access, we need to change the definition from this:

    function updateGameBoard(control)
      var color = control.color;

To this:

    this.updateGameBoard = function() {
      var color = this.color;

We can also get rid of the function parameter because we have access to this control's color through a member variable already. All that's left to fix is the other call to updateGameBoard() inside Control:

    this.init = function () {
      $('<div>', {
        class: "control btn",
        style: "background-color:" + this.color
      }).on('click', function (e) {
        that.updateGameBoard();
      }).appendTo('#control_container');
    };

Now we can test out the round-robin algorithm and see how it does by simply clicking the round-robin button as fast as we can. For the board created from an initial random seed of 1, I cleared the board in 50 moves with the round-robin algorithm. Not great. I can easily do better than this by eye-balling the board, so we should expect to do better with more complex algorithms. That's not our main concern right now, though. We have two other pressing problems to work out. First, when we restart the game, the same board appears for the next game, but we want to test out the algorithm with multiple different boards to see how it performs in general. Second, this manual mode is great for seeing the details of how the algorithm works, but it sucks for testing many boards. We want to get that batch mode working.

Finishing off Interactive Mode

The first problem of starting the next game with a new board has an easy fix, but we'll need to do some refactoring of the Control code to make it easy. That's the preferred way to add features and fix bugs, right? First refactor the code so that the change is easy, and then make the easy change. So here's the Control code, some of which we've seen already:

  function Control(color) {
    this.color = color;

    this.init = function () {
      var that = this;

      $('<div>', {
        class: "control btn",
        style: "background-color:" + this.color
      }).on('click', function (e) {
        that.updateGameBoard();
      }).appendTo('#control_container');
    };

    this.init();

    this.updateGameBoard = function() {
      var color = this.color;
      _.each(blocks, function (block) {
        if (block.isDead) {
          getNeighbors(block, color);
        }
      });

      moves += 1;
      $('.score').text(moves);
    }

    function getNeighbors(block, color) {
      var i = block.position;
      var neighbor_positions = [i - 1, i + 1, i - grid_length, i + grid_length];

      if (i % grid_length == 0) {
        neighbor_positions[0] = false;
      } else if (i % grid_length == (grid_length - 1)) {
        neighbor_positions[1] = false;
      }

      neighbor_positions = _.reject(neighbor_positions, function (pos, i) {
        if (pos < 0 || pos > grid_length * grid_height - 1) {
          return true;
        } else if (pos === false) {
          return true;
        }
      });

      checkNeighbors(neighbor_positions, color);
    }

    function checkNeighbors(positions, color) {
      _.each(positions, function (position) {
        var block = blocks[position];
        if (block.color == color && !block.isDead) {
          block.isDead = true;
          $('#block' + position).css('background-color', '#d9d9d9');
          checkIfFinished(block, color);
        }
      });
    }

    function checkIfFinished(block, color) {
      var game_continues = _.some(blocks, function (block) {
        return block.isDead == false
      });

      if (game_continues) {
        getNeighbors(block, color);
      } else {
        $('#game_over').fadeIn(300);
      }
    }
  }

Let's ignore the fact that the logic in getNeighbors() would be much simpler if the array of blocks was a 2D array, and instead look at where the game ends in checkIfFinished(). By putting the end-of-game check inside checkNeighbors(), which is inside getNeighbors(), we are checking if the game is done way more often than we need to, and it makes restarting the game with a new board more complicated because it will be buried inside a recursion. To pull the checkIfFinished() call out of checkNeighbors(), we can simply call getNeighbors() instead of checkIfFinished(), remove the call to getNeighbors() inside checkIfFinished(), and call checkIfFinished() from updateGameBoard():

    this.updateGameBoard = function() {
      var color = this.color;
      _.each(blocks, function (block) {
        if (block.isDead) {
          getNeighbors(block, color);
        }
      });

      checkIfFinished();
      moves += 1;
      $('.score').text(moves);
    }

    function getNeighbors(block, color) {
      // ...
    }

    function checkNeighbors(positions, color) {
      _.each(positions, function (position) {
        var block = blocks[position];
        if (block.color == color && !block.isDead) {
          block.isDead = true;
          $('#block' + position).css('background-color', '#d9d9d9');
          getNeighbors(block, color);
        }
      });
    }

    function checkIfFinished() {
      var game_ends = _.all(blocks, function (block) {
        return block.isDead == true;
      });

      if (game_ends) {
        $('#game_over').fadeIn(300);
      }
    }

I also refactored the logic inside checkIfFinished() to make more sense without the game_continues branch of the if statement. Now what we want to do if the game ends is reset the board instead of fading in the Game Over modal and reloading the entire page when the user clicks the new game link. To do this, we can return a boolean from checkIfFinished() and reset the board if it's true:

    this.updateGameBoard = function() {
      var color = this.color;
      _.each(blocks, function (block) {
        if (block.isDead) {
          getNeighbors(block, color);
        }
      });

      if (isFinished()) {
        makeBlocks();
      } else {
        moves += 1;
      }
      $('.score').text(moves);
    }

    // ...

    function isFinished() {
      return _.all(blocks, function (block) {
        return block.isDead == true;
      });
    }

Notice the name of checkIfFinished() changed to isFinished() to better fit its new role. Now when a game is finished, a new game starts right away by generating a new set of random blocks, and the board is different as well because the RNG seed has not been reset by a page load. We're actually getting closer to our second goal with this change. Since a new game begins as soon as the current game ends, we just have to automate the algorithm button clicks to get a batch mode working.

Extending into Batch Mode

To automate the batch mode, we'll need a couple new controls: an input box to specify the number of iterations of the game to do, and a play button to kick off the batch run. The HTML and CSS for these elements is simple, so I'll leave that to you to arrange if you're following along. I named the IDs solver_iterations and solver_play for the input box and play button, respectively. Then, the JavaScript to enable the batch mode is added to Solver():

  var iterations = 0;
  function Solver() {
    var that = this;

    this.index = 0;

    this.init = function() {
      this.solver = $('<div>', {
        id: 'solver',
        class: 'control btn',
        style: 'background-color:' + colors[this.index]
      }).on('click', function (e) {
        that.roundRobin();
      }).appendTo('#solver_container');

      $('#solver_play').on('click', function (e) {
        var iterations = $('#solver_iterations').val();
        that.run();
      });
    };

    // ...

    this.run = function _run() {
      that.roundRobin();
      if (moves === 0) iterations -= 1;
      if (iterations !== 0) setTimeout(_run, 10);
    }
  }

The lovely that assignment needed to be moved outside of this.init() so that it could be used inside this.run() as well. Inside this.init() a click handler is assigned to the #solver_play button that grabs the number of iterations specified by the #solver_iterations input box and starts the batch mode running. The this.run() function calls the round-robin algorithm and checks to see if the game is finished. If it is, then the number of iterations left to do is decremented. If there are still iterations left to do, then a timer is set to run the algorithm again in 10 milliseconds. This timer allows the board to redraw between moves so that we can see that something is actually happening during long runs and get a sense of how the algorithm is working.

Rounding out Batch Mode

The tooling is starting to look pretty good, but there's still something missing. We don't have any statistics! We can easily add some text elements to report the max, min, mean, and standard deviation of moves for the batch run that has just completed. After adding the appropriate HTML text elements, we can keep track of the moves for each game played for our statistics by pushing them into an array as each game finishes:

  var game_moves = [];
  function Control(color) {
    // ...

    this.updateGameBoard = function() {
      var color = this.color;
      _.each(blocks, function (block) {
        if (block.isDead) {
          getNeighbors(block, color);
        }
      });

      if (isFinished()) {
        game_moves.push(moves);
        makeBlocks();
      } else {
        moves += 1;
      }
      $('.score').text(moves);
    }

    // ...
  }

Then, after all of the game iterations have finished, we can calculate the statistics in Solver():

  function Solver() {
    // ...

    this.run = function _run() {
      that.roundRobin();
      if (moves === 0) iterations -= 1;

      if (iterations === 0) {
        calculate_stats();
      } else {
        setTimeout(_run, 10);
      }
    }

    function calculate_stats() {
      $('#max').text('Max: ' + _.max(game_moves));
      $('#min').text('Min: ' + _.min(game_moves));

      var sum = _.reduce(game_moves, function(a, b) { return a + b; });
      var mean = sum / game_moves.length;
      $('#mean').text('Mean: ' + Math.round(mean*100) / 100);

      var sum_squares = _.reduce(game_moves, function(a, b) { return a + Math.pow(b - mean, 2); }, 0);
      var stdev = Math.sqrt(sum_squares / game_moves.length);
      $('#stdev').text('Stdev: ' + Math.round(stdev*100) / 100);
    }
  }

The if condition for deciding to make another move in this.run() was changed around a bit to also call calculate_stats() if all of the iterations are done, and then the statistics are calculated and updated on the page. (You can take a look at my statistics series for a refresher on standard deviation.)

Notice that the game_moves array is never cleared, so if the batch mode is run multiple times, more game moves are just appended to the array, and the stats are recalculated. This behavior is okay for now because we're only able to run one algorithm, and hitting the play button multiple times allows us to see the statistics evolve over multiple batches of runs. After we add more algorithms, we'll need to clear that array and reset the RNG seed so that statistics can be accurately calculated when we switch between algorithms, but that's a task for another day. For now, I think we've made enough progress with our tooling, and we have a good foundation for testing out our different algorithms. Here's what things look like for 100 runs of the round-robin algorithm:

So this algorithm ranges in performance from about 37 to 62 moves per game, with a standard deviation of about 4.5 moves. That is a wider range than I expected, but the mean is right about where I thought it would be, falling pretty close to the moves required for the first game played in interactive mode. Next time we'll see how some of the other algorithms stack up to this baseline.

We spent a lot of time developing the tooling for testing out different algorithms for this simple game. Why spend all that time? Why not just show the code changes and move on to tackling the various algorithms? I felt that it would be instructive to see how tooling can get added to existing code in a progressive manner without completely tearing up the code and starting from scratch.

Throughout this exercise we added new features bit by bit, methodically building up to a pretty nice set of tools that enable easier evaluation of the different algorithms we're going to see. It may not have been clear how we were going to get from there to here if I just threw a description of batch mode and statistics out there and showed the code, but breaking the problem up into small, easy steps is a great way to solve programming problems. You can make more progress faster because the smaller problems are self-contained, and you can build confidence on a bunch of quick successes. It helps get you into a flow where the end goal isn't so overwhelming. If you only need to think about little changes—move these few lines of code over here, reorganize this if statement, break this code out into a function—then you make less mistakes, forget less tasks that need to be done, and get to your ultimate goal faster. Seeing that process in action is invaluable for developing it in your own skill set.

Next time we'll be doing more small changes to get algorithm switching in place and start looking at more interesting algorithms.


Article Index
Part 1: Introduction & Setup
Part 2: Tooling & Round-Robin
Part 3: Random & Skipping
Part 4: The Greedy Algorithm
Part 5: Greedy Look Ahead
Part 6: Heuristics & Hybrids
Part 7: Breadth-First Search
Part 8: Depth-First Search
Part 9: Dijkstra's Algorithm
Part 10: Dijkstra's Hybrids
Part 11: Priority Queues
Part 12: Summary