Explore Simple Game Algorithms with Color Walk: Part 1

A few years ago, Jennifer Dewalt did a project where she created 180 websites in 180 days, one every day for half a year, to learn how to program. These "websites" were actually web pages within one website, but the plan and the execution were still quite amazing. I watched on and off as she created page after page, learning all about web development in the process. One page in particular caught my interest: the simple game called Color Walk.

In this game there's a 20x30 grid of colored blocks in five different colors. The top left block is blank, and there are five colored buttons to choose from. Click a button, and the blank space will expand by removing the adjacent colored blocks corresponding to the button clicked. The goal is to clear the board in as few clicks as possible.

Color Walk by Jennifer Dewalt

It's a simple game, to be sure, but I was fascinated by it. I would play it and think about what the best strategy would be to clear the board in the fewest moves. Would a greedy algorithm be best, should I try to pick the color that would maximize the perimeter of the blank space, or would a full search be possible? The possible strategies are numerous. It was just complex enough that I would tire of computing different strategies by hand, but I kept the idea tucked in the back of my mind to try to tackle the game with algorithms.

It's about time to explore these different strategies and start messing around with some code. This game provides a perfect sandbox for trying out different algorithms and hopefully learning some things in the process. If you want to try out the game, here's Jennifer's original website, and if you want to follow along, the code is available at her Github repo. You can clone her repo and get the Rails app up and running to experiment yourself.

Get Color Walk Running

Getting this old Rails app running in full is not too easy, since Rails has come a long way since 2013. It's not necessary to get all 180 pages running, though, just the Color Walk page. I didn't want to install Rails 3.2, but I have Rails 4.2 installed, so I created a new app in that version and copied in the Color Walk page and assets. Luckily, Color Walk doesn't use much of anything other than the basic Rails configuration, so just copying that page in worked alright. First, create a new controller for the page:

$ rails generate controller ColorWalk index

Then copying these files into the project should work:

• Copy app/views/color_walk/game/index.html.erb to app/views/color_walk/index.html.erb
• Copy app/assets/stylesheets/color_walk_game.css.scss to app/assets/stylesheets/color_walk.css.scss
• Copy app/assets/javascripts/websites/color_walk_game.js to app/assets/javascripts/color_walk.js
• Copy vendor/assets/javascripts/underscore.js to vendor/assets/javascripts/underscore.js
• Remove app/assets/javascripts/color_walk.coffee since it won't be needed

A few file changes are also necessary. First, add this to config/initializers/assets.rb:

Rails.application.config.assets.precompile += %w( underscore.js color_walk.css )

Then, add this to app/views/layouts/application.html.erb:

<%= javascript_include_tag 'underscore.js' %>

Add this to the end of app/assets/javascripts/color_walk.js to make the JavaScript run on the page load:

$(document).on('ready page:load', function() {
  colorWalk();
});

And in the same file, add the function randomInt() before makeBlocks(), since it was defined in some library but is too simple to go searching for:

  function randomInt(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
  }

Change the first line of app/assets/stylesheets/color_walk.css.scss because the old CSS selector won't work:

body .color_walk_game {

And finally, remove the render line from app/views/static_pages/color_walk.html.erb and wrap everything in a <div class="color_walk_game">:

<div class="color_walk_game">
  <div id="wrapper">
    <div id="gameboard"></div>
  </div>

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

  </div>

  <div class="modal" id="start">
    <div class="inner_modal">
      <p class="close">X</p>
      <h1>Color Walk</h1>
      <p>You start in the upper left corner of the gameboard at the grey square. Use the buttons to take over neighboring squares of the same color. The goal is to clear the field in as few moves as possible.</p>
    </div>
  </div>

  <div class="modal" id="game_over">
    <div class="inner_modal">
      <h1>Awesome!</h1>
      <p>You cleared the field in <span class="score"></span> moves.</p>
      <%= link_to "Play Again", @color_walk %>
    </div>
  </div>
</div>

Whew. At this point, you should be able to start the Rails server and find the game in a browser at http://localhost:3000/static_pages/color_walk. Now, what are we going to do with it?

The Plan

The idea is to explore various algorithms for finding the least number of moves required to clear a board while getting a sense of how each algorithm works. We'll create an interactive mode where the algorithm can provide hints or recommendations for the user to select the next color for each move, and a batch mode where the algorithm will automatically run through and solve a number of boards on its own, reporting how many moves it took to clear each board. The interactive mode is useful for exploring and understanding each algorithm, while the batch mode will help assess the performance of each algorithm over multiple runs.

A third review mode would also be desirable where the algorithm runs automatically, but at a slow enough speed that the viewer can see the flow of how the board is cleared. This mode would show how the algorithm behaves as it's running, providing further insight and improving intuition about the algorithm.

With this idea of the interfaces we're going to build worked out, we should come up with some ideas of possible algorithms that we're going to explore. Going through a brainstorming exercise will generate a list of ideas to work from, and the free-form thinking will be good for understanding the space of possible algorithms that we can use. For starters, a couple of simple algorithms jump to mind that would establish a baseline of performance that more complex algorithms should aim to beat: round-robin and random choice.

The round-robin algorithm would cycle through, picking each color in sequence regardless of the state of the board. This algorithm is so simple that it can already be done in interactive mode without any additional coding. Just select each color in a cycle until the board is cleared and see how many moves it required. A batch mode of this algorithm is also conceptually easy to implement with a loop.

A random choice algorithm requires slightly more code and computation since it will be choosing a random color for each move, excluding the color just picked, but it is still relatively simple to implement. Later algorithms would certainly have to consistently beat either of these two dead-simple algorithms. Otherwise, it would be more efficient to use the round-robin or random choice algorithm to clear the board and forgo all of the extra calculation.

An immediately obvious improvement on either basic algorithm would be to exclude colors that would not clear additional blocks from the board. It is legal in the game to pick a color that has no blocks adjoining the cleared area, and it counts as a move, so skipping these color choices for the round-robin algorithm or not allowing them in the random choice algorithm would obviously improve the move count.

If we want to avoid colors that would not remove any blocks, maybe we can take that to the other extreme and choose the color that would remove the most blocks on each move. This reasoning leads to the greedy algorithm, another relatively simple algorithm to implement. On each move, we will count how many blocks would be removed for each color, and choose the color that removes the most blocks to see if that results in the least moves to clear the board.

Maybe the greedy algorithm is too short-sighted, though. It's easy to imagine cases where choosing a less plentiful color on the current move will open up more blocks of another color for the next move. We'll call such an algorithm that looks one move ahead to find the color choice that maximizes the available blocks of any one color for the next move the greedy-look-ahead algorithm. This algorithm could be extended to any number of moves, so looking ahead one move would be a greedy-look-ahead-1 algorithm, looking ahead two moves would be a greedy-look-ahead-2 algorithm, and so on.

What if maximizing the number of blocks cleared on each move isn't as important as opening space deep in the board as fast as possible? We could devise an algorithm that focuses on finding paths deep into the board. Such an algorithm would require more thought to implement, but it could perform quite well. We could call it the deep-path algorithm. A related algorithm would be one that maximizes the perimeter of the cleared space on each move. The larger the perimeter is, the deeper the cleared area would extend into the board. We can call this algorithm the max-perimeter algorithm.

The algorithms thought up so far should be making us think about the structure of the move choices through the course of the game, and how each color choice results in a branching of subsequent choices. The total set of move choices can be arranged in a graph with each node being a color choice, and edges from a node branch to the color choices on the next move. The value of each node could be the number of blocks cleared, the increase in perimeter, or some other measurement. This move graph suggests a number of shortest-path algorithms including: depth-first-search (DFS), breadth-first-search (BFS), A*-search, and Dijkstra's Algorithm.

These graph algorithms should trigger the question, "Can we calculate an optimal solution to this problem?" I.e. can we search the entire move graph, or do we have to truncate the search? Well, having played many games, I've found that it's relatively difficult to get less than 30 moves by just estimating the best color choice on each move, but it should be possible on most boards. On the other hand, on my first attempt with the round-robin algorithm, I got 53 moves. That means that a move graph is about 30-55 moves deep, and with five color choices, it branches by four on each move. By the time we're looking 30 moves in, we're searching through 4³⁰, or 1.15*10¹⁸ moves. That's not quite as bad as chess, but most algorithms are going to be pretty slow by the time they're searching through that many moves. Also, storing such a large graph in memory becomes a significant problem. An optimal solution is probably not possible, and if it is, increasing the board size would still cripple the faster algorithms.

That's okay, though. That makes our evaluation of different algorithms more interesting because we're not just looking for an algorithm that can find the optimal solution and be done. We need to evaluate the performance of these algorithms both in least number of moves and the time it takes to find that set of moves. We will also be learning how to organize the game code and structure the algorithms for better performance, so we'll hopefully improve our programming skills throughout this process.

To recap, we've come up with this list of algorithms so far:

1. Round-Robin
2. Random Choice
3. Round-Robin with skips
4. Random Choice with skips
5. Greedy
6. Greedy-Look-Ahead-n
7. Deep-Path
8. Max-Perimeter
9. DFS
10. BFS
11. A* Search
12. Dijkstra's Algorithm

That's a decent list to start with, and we'll likely come up with more heuristics to try as we explore these algorithms. The first thing we'll want to do before we start trying out algorithms is remove some of the randomness of the game board setup. Each time the game starts, the blocks are randomly assigned colors, but that makes for some difficult algorithm testing because we're not comparing apples to apples.

To force the game to create the same board each time (or the same series of boards once we've got a batch mode running), we would normally provide a fixed seed to the random number generator. JavaScript doesn't have that feature, so we'll have to roll our own RNG. It turns out that sending sequential integers to the sine function and moving far enough down the string of digits in the result actually produces a decently uniform distribution of random decimals. The code is simple enough:

  var seed = 1;
  function random() {
    var x = Math.sin(seed++) * 10000;
    return x - Math.floor(x);
  }

  function randomInt(min, max) {
    return Math.floor(random() * (max - min + 1)) + min;
  }

We multiply by 10,000 to get rid of the first four digits in the result. These digits will tend to clump around 0.9999 and 0.0000, which would bias the RNG so we discard them. With this modification, the game will generate the same board every time, and when we add the batch mode to generate a series of boards, it will generate the same series of boards every time. Then we can compare the results of running different algorithms without needing to run a huge number of boards to smooth out statistical variations.


Now that we have a working web page that generates the same board each time it loads, we have something that we're ready to experiment with. Next time we'll create the batch and review modes and start exploring some of the simpler algorithms to see what's possible for solving Color Walk with basic strategies. Then we can move on to the more complex 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