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 showed how to implement one of the simplest algorithms I could think of, round-robin, and how to develop some tooling around the game so that we can quickly run through multiple iterations in a batch mode and see statistics on the run. This post will start exploring some more algorithms, and we'll start needing to think about how to improve the algorithms so they aren't so naive.
Adding the Second Algorithm
The first thing we need to do to add a second algorithm into the mix is add an ability to change the algorithm type, both within the UI and in the code when running the solver. The UI addition is easy. All we need to do is replace the "Round Robin" text with a
<select> tag that includes the
<option> tags for each algorithm choice we'll support. Right now that will be "Round Robin" and "Random Choice," since a random algorithm will be another simple algorithm that will be quick to implement. I also gave the
<select> tag an ID of
solver_type, so it can easily be accessed from the code.
The code changes are a little more extensive than the UI. We'll start with adding an event handler to update the solver state when the algorithm changes. For that addition we can add this code to the
Solver.init() function:
$('#solver_type').change(function () {
switch (this.value) {
case 'roundrobin':
that.solverType = that.roundRobin;
break;
case 'random':
that.solverType = that.randomChoice;
break;
default:
that.solverType = that.roundRobin;
break;
}
game_moves = [];
seed = 1;
makeBlocks();
});
This code adds a change event handler to the
#solver_type select box, and sets the
Solver.solverType property to the function we want to use for the algorithm chosen. This is one of the lovely features of JavaScript (as opposed to C++). Passing functions around is easy because they are first-class citizens in the language. No need for special syntax here, and when we want to call the algorithm we've chosen, it will be as simple as
that.solverType(). To finish off the handler, we need to restart the game board by setting the
seed back to its starting value and recreating the blocks on the board. We also need to clear out the
game_moves so that the statistics get calculated for one algorithm at a time.
We should also set an initial value for the
solverType so that it's ready to go when the page loads, and we can stick that near the bottom of
Solver, after the definition of the algorithms:
function Solver() {
// ...
this.roundRobin = function() {
// ...
}
this.solverType = this.roundRobin;
Now we need to call this new
solverType() function instead of the
roundRobin() function in the click handler for the interactive mode control:
this.solver = $('<div>', {
id: 'solver',
class: 'control btn',
style: 'background-color:' + colors[this.index]
}).on('click', function (e) {
that.solverType();
}).appendTo('#solver_container');
And we need to make sure to also call it in the
run() function:
this.run = function _run() {
that.solverType();
// ...
}
At this point the round-robin algorithm should work again, if it is selected, but the random choice algorithm will not work because we haven't defined it, yet. That task is simple enough:
this.randomChoice = function() {
controls[this.index].updateGameBoard();
this.index = randomInt(0, controls.length - 1);
this.solver.css('background-color', colors[this.index]);
}
We merely had to replace the index update code in
roundRobin() with some new code that gets a random index. It should be obvious that future algorithms will follow this same structure, so we should be able to pull out the first and last lines of this function into its own function that can be shared between all of the algorithms. Let's make a new function called
runAlgorithm() that updates the game board, calls the currently configured algorithm, and updates the color of the solver control button:
this.runAlgorithm = function() {
controls[this.index].updateGameBoard();
this.solverType();
this.solver.css('background-color', colors[this.index]);
}
this.roundRobin = function() {
this.index = (this.index + 1) % controls.length;
}
this.randomChoice = function() {
this.index = randomInt(0, controls.length - 1);
}
This change simplifies each of the algorithm functions. We also need to remember to change the two
solverType() calls to be
runAlgorithm() calls. Now we have things nicely cleaned up and adding future algorithms should be easy, at least from the standpoint of adding in the scaffolding of each new algorithm. Some of the algorithm code itself could still be challenging.
Notice how this architecture came about naturally. I didn't spend a lot of time trying to plan out the perfect set of functions ahead of time. I added things incrementally, and as optimization and organizational changes became obvious, I did them. Too much planning and design runs the risk of architecting the code into a dead end, making it difficult to add new features to a code base that has become too complicated with twists and turns that form a maze of objects and function calls. I much prefer taking a path of least resistance, paying attention to where the code is leading, and making incremental improvements that organize and support the code for the problem it is attempting to solve.
Some programmers may balk at the use of a switch statement to decide which algorithm to use, but it's not as bad as it seems. Switch statements get cumbersome when there are multiple switch statements operating on similar objects with similar structure strewn throughout the code. These switch statements all have to be updated whenever another item is added to the list of possible cases. If you ever find yourself updating multiple switch statements when adding a new option or feature, that's the time to think about how to reorganize that code into a class hierarchy so that most of the switch statements can be eliminated. Most of the time, you'll still need one switch to create the objects from the correct classes, but one should be enough. I don't expect to need more than this one switch statement for the different types of algorithms, so I think it's fine.
Getting back to this new random choice algorithm, let's see how it performs:
Wow, that is much worse than round-robin was. The average number of moves is 30 moves higher than round-robin, and the standard deviation is twice as big. Here's a comparison of the two algorithms:
| Round Robin | Random Choice |
| Min | 37 | 60 |
| Mean | 48.3 | 80.2 |
| Max | 62 | 115 |
| Stdev | 4.5 | 10.5 |
It's also apparent when watching the algorithm run that it behaves differently. It sometimes appears to get stuck, pausing for a moment before continuing to clear blocks. It also seems to leave some colors of blocks behind for a while while it clears others. Both of these behaviors are caused by the randomness of the algorithm. It appears to pause when it repeatedly picks the same color more than once, and certain colors will appear to get left behind if the algorithm happens to not pick them for an extended sequence of moves. Not picking one color for a long time may not be much of an issue, but picking the same color multiple times in a row is definitely contributing to this algorithm's poor performance. We should start looking at how to improve that behavior.
Improving Random Choice with Skipping
The immediate problem of picking the same color more than once in a row is fairly easy to solve. We can add a new algorithm type to the drop-down selector with the option value of "random-skip," and then add a case to the switch statement for it:
$('#solver_type').change(function () {
switch (this.value) {
case 'round-robin':
that.solverType = that.roundRobin;
break;
case 'random':
that.solverType = that.randomChoice;
break;
case 'random-skip':
that.solverType = that.randomChoiceWithSkipping;
break;
default:
that.solverType = that.roundRobin;
break;
}
Then all we have to do to fill in the randomChoiceWithSkipping() function that implements the algorithm is check each random integer that's created for the index, and while the candidate index is the same as the current one, generate a new candidate, like so:
this.randomChoiceWithSkipping = function() {
i = randomInt(0, controls.length - 1);
while (this.index === i) {
i = randomInt(0, controls.length - 1);
}
this.index = i;
}
This optimization makes a marked improvement in the algorithm's performance:
Everything has improved, with the average number of moves being reduced by 17 moves, and the standard deviation being reduced by nearly 3 moves. However, this is still substantially worse than the round-robin algorithm, and that's likely because of how the random choice algorithm picks colors differently than round-robin. Because it's possible that the next random color that's chosen was the same as one picked in the recent past, it's more likely that the chosen color doesn't remove any more blocks, or at least very few. The round-robin algorithm guarantees that at least the next color will be the least recently picked color, and it's likely that more blocks of that color will be exposed for removal by the time the color comes around again.
We aren't going to consider optimizing the number of blocks removed on each color choice quite yet. That's getting into a different kind of algorithm, but we can look at not picking a color that will not remove any blocks on the current move. That would still be a random algorithm with skipping, and it seems like it would further improve the random choice algorithm. We're kind of going for the most non-wasteful random algorithm we can think of here, while still keeping it as random as possible.
So how do we check that the candidate random color removes at least one block? The current code doesn't lend itself well to this check because the tasks of finding blocks to remove, removing those blocks, and incrementing the move count all happen together in the same base function call. There's no way to easily check for a color without also doing the rest of the work of updating the game board. Luckily, there's a fairly simple way to get what we want by adding a function and threading a conditional parameter through the function calls for updating the blocks. I can imagine that at some point we're going to want to separate out those search and update tasks because later algorithms are going to do a deeper, more complex search of the board, but by then we'll also want to change the data structure for the blocks. That's a bigger change to the code that isn't really necessary, yet, so let's stick with the simple workaround for now.
To implement the simple workaround, we want to create a function that does most of what
Control.updateGameBoard() does, except for the updating the game board part. Instead of searching for blocks of a certain color adjacent to grey blocks and removing them, we want to search for blocks of a certain color adjacent to grey blocks and return whether a match was found. To do this check, we can start by updating the algorithm to do what we want it to do, and then fill in the details as we go:
this.randomChoiceWithSkipping = function() {
do {
this.index = randomInt(0, controls.length - 1);
} while (controls[this.index].checkGameBoard(true) === false);
}
Now instead of checking if the new control index is the same as the last one, we want to check if the game board has a match on the color of the new control index. If it doesn't, we'll pick a new index. That change allows us to simplify the code a bit because we don't have to remember the old index anymore. So what does
Control.checkGameBoard() do? It basically does what the start of
Control.updateGameBoard() does, but with an extra conditional parameter so that it will know to stop on the first match:
function Control(color) {
// ...
this.updateGameBoard = function() {
this.checkGameBoard(false);
if (isFinished()) {
game_moves.push(moves + 1);
makeBlocks();
} else {
moves += 1;
}
$('.score').text(moves);
}
this.checkGameBoard = function(only_check) {
var match = false;
var color = this.color;
_.each(blocks, function (block) {
if (block.isDead) {
match = match || getNeighbors(block, color, only_check);
}
});
return match;
}
Because
Control.checkGameBoard() does nearly the same thing as the beginning of
Control.updateGameBoard(), we can call it from
Control.updateGameBoard() as well, but with
only_check = false so that the search will run through every block and update the game board as it goes. Within
Control.checkGameBoard(), we've added a variable to keep track of if there was a match, and return that value at the end of the function. We also pass the
only_check conditional along to
getNeighbors() so that we can use it where we're going to need it.
You've probably noticed that this code is a little wasteful in that it does not return on the first match found. It will continue searching through the rest of the grey blocks even after finding a match. While that's probably less efficient, there is a reason for it. I'm still working from the assumption that we're going to want to completely change the method of searching for colors later on because the current method will prove to be too slow. I don't want to do that change until I need to, though, so I'm doing the simplest thing that will work here without changing too much code. It's still fast enough for these simple algorithms, and I have a hunch that if we change things to return immediately on a match, we'll be changing it back in the near future for the greedy algorithm. Let's move on to the changes to
getNeighbors():
function getNeighbors(block, color, only_check) {
// ...
return checkNeighbors(neighbor_positions, color, only_check);
}
function checkNeighbors(positions, color, only_check) {
var match = false;
_.each(positions, function (position) {
var block = blocks[position];
if (block.color == color && !block.isDead) {
if (only_check) {
match = true;
return;
}
block.isDead = true;
$('#block' + position).css('background-color', '#d9d9d9');
getNeighbors(block, color, only_check);
}
});
return match;
}
The only change in
getNeighbors() is the call at the end to
checkNeighbors() by adding the
only_check argument. Most of the real changes are inside
checkNeighbors(). We add a variable here to again keep track of whether a match was found or not, and inside the if block that finds a match, if we're returning on the first match, we set the match-tracking variable to true and return. Note that because of how the
_.each() function works, this only returns from the current iteration of the loop, bypassing the code that updates the game board, but not returning from
checkNeighbors(). The rest of the neighbors are still checked, and any other matches would also return from the loop iteration function before updating the game board. Since we also call
getNeighbors() inside this loop, we need to pass along
only_check for the other blocks that will be searched. The same argument as before for not changing the code too much applies here, so we just loop through all the neighbors and return whether or not a match was found at the end.
The enhanced skipping should now be working, so let's give it a whirl:
Things have improved yet again! Now we're getting pretty close to the performance of round-robin, as we can see in the following table:
| Round Robin | Random Choice | Random with Skipping |
| Min | 37 | 60 | 43 |
| Mean | 48.3 | 80.2 | 53.1 |
| Max | 62 | 115 | 64 |
| Stdev | 4.5 | 10.5 | 4.5 |
The fact that random choice with skipping is still slightly worse than round-robin probably means that the least-recently-used behavior of round-robin is slightly more optimal than just picking a color at random. This is good. We now have two reasonable baselines for comparing against future algorithms. We do have one more improvement we can make, however.
Improving Round-Robin
Clearly, now that we can skip colors that aren't worth choosing in random choice because they won't remove any blocks, we can do the same thing with round-robin. This is an easy addition, and it should improve round-robin's performance somewhat. To add this algorithm, we can create another menu choice, add it to the switch statement, and add this algorithm code:
this.roundRobinWithSkipping = function() {
do {
this.index = (this.index + 1) % controls.length;
} while (controls[this.index].checkGameBoard(true) === false);
}
The new algorithm simply checks if the new index has a color match, and if not, it moves on to the next index until it does find a match. How much of an improvement do we get?
Not as much as I was expecting, but it's still an improvement. Let's look at all of the results:
| Round Robin | RR with Skipping | Random Choice | Random with Skipping |
| Min | 37 | 37 | 60 | 43 |
| Mean | 48.3 | 46.9 | 80.2 | 53.1 |
| Max | 62 | 59 | 115 | 64 |
| Stdev | 4.5 | 4.1 | 10.5 | 4.5 |
We shaved 1.4 moves off of the average, 3 moves off of the max, and 0.4 moves off of the standard deviation, showing that the distribution tightened up somewhat. I'll bet most of the improvement by not picking dead colors in round-robin came from the beginning and the end of games, when there are most likely to be less useful colors to pick from.
Now we should have a good idea of what to expect from future algorithms. A normal game with haphazard choices of colors will result in about 50 moves, if we at least take care to not pick a color that won't remove any blocks. Picking a color that was not picked recently is also generally better than picking a color totally at random. The goal for the rest of the algorithms is to do better than this, much better. We should also start to get an idea of what a reasonable lower bound is for the number of moves in a typical game, and thus, what a well-played game looks like. We'll start down that path next time with the greedy algorithm, and see where that takes us.
Article IndexPart 1: Introduction & SetupPart 2: Tooling & Round-RobinPart 3: Random & SkippingPart 4: The Greedy AlgorithmPart 5: Greedy Look AheadPart 6: Heuristics & HybridsPart 7: Breadth-First SearchPart 8: Depth-First SearchPart 9: Dijkstra's AlgorithmPart 10: Dijkstra's HybridsPart 11: Priority QueuesPart 12: Summary
