Software Engineer Explore Uncomplicated Game Algorithms Amongst Coloring Walk: Business Office 7

We're continuing to explore dissimilar game algorithms using the uncomplicated game last post we took a deep dive into other heuristics that could live used instead of the obvious maximize-the-number-of-blocks-removed approach together with works life that the obvious choice is genuinely hard to beat. After looking at diverse heuristics, it's fourth dimension nosotros fill upward inwards some gaps inwards our exploration of algorithms yesteryear looking at a span of primal graph algorithms: breadth-first search (BFS) together with depth-first search (DFS). These algorithms are the 2 basic ways to search for something inwards a graph of nodes (or vertices) connected yesteryear edges, together with a graph is just what nosotros receive got when nosotros line out all possible motility choices alongside each node representing a motility together with edges connecting sequential moves. We'll focus on BFS for this post.

Before We Begin, H5N1 Bug Fix

Before nosotros start looking into BFS, nosotros should brand some minor changes to the code to improve its performance. The implementation of the greedy look-ahead (GLA) algorithm that we've implemented a põrnikas that is non affecting correctness, but it is slowing the search downward considerably. Here is the code inwards its sub-optimal state:

    this.greedyLookAhead = function() {       var max_control = _.max(controls, function(control) {         if (control.checkGameBoard(1, that.metric) === 0) {           supply 0;         }         supply greedyLookAheadN(2);       });       this.index = max_control.index;     }      role greedyLookAheadN(move) {       supply _.max(_.map(controls, function(control) {         var matches = control.checkGameBoard(move, that.metric);         if (matches === 0 || motility >= max_moves) {           supply matches;         }         supply greedyLookAheadN(move + 1);       }));     }

The occupation is hiding inwards the if conditional inwards greedyLookAheadN(). The see alongside this if disceptation is that if nosotros didn't divulge whatsoever matching blocks on this motility or we've reached the desired search depth, together with therefore nosotros should goal the search of this branch of moves. However, matches is non the number of matches on the electrical current move, but of all matched blocks on all moves upward to this search depth. It volition exclusively potentially live null on the foremost telephone phone to greedyLookAheadN(), but non whatsoever subsequent recursive calls! That behaviour makes the look-ahead search perform slow at the goal of the game because it's trying to search through moves beyond when the board is already cleared. That's how I noticed the problem.

Another improvement that tin easily live made is to non search for blocks for a motility that nosotros already made on the preceding move, i.e. don't pick the same motility twice inwards a row. The previously discussed if status would goal the search on the duplicate motility when it's fixed, but exclusively later on searching for matches together with finding no additional matches. We tin skip the superfluous search yesteryear detecting when we're repeating the previous move. The fixes to the code involve passing the previous motility together with previous matches into greedyLookAheadN() therefore that they tin live compared alongside the electrical current motility together with matches, respectively:

    this.greedyLookAhead = function() {       var max_control = _.max(controls, function(control) {         var matches = control.checkGameBoard(1, that.metric);         if (matches === 0) {           supply 0;         }         supply greedyLookAheadN(2, control, matches);       });       this.index = max_control.index;     }      role greedyLookAheadN(move, prev_control, prev_matches) {       supply _.max(_.map(controls, function(control) {         if (control === prev_control) {           supply 0;         }         var matches = control.checkGameBoard(move, that.metric);         if (matches === prev_matches || motility >= max_moves) {           supply matches;         }         supply greedyLookAheadN(move + 1, control, matches);       }));     }

With these changes, the algorithm correctly cuts off the search of a particular motility branch when no additional matches are found, or when the motility is the same every bit the previous move. The speed-up is to a greater extent than than a element of 3, therefore it was good worth the trouble. Even though we're moving on from the greedy algorithm, it was worth finding together with correcting this põrnikas because we'll live using similar logic to determine where to search inwards the side yesteryear side span algorithms. We wish to acquire it right therefore the searching volition live every bit fast every bit possible. Now let's start excavation into the details of BFS.

Theoretical BFS

BFS is i of 2 primal ways to search a graph. We could live searching for a specific node value, searching for a maximum or minimum, or searching for something else based on node values. In our case, we're searching for the end-of-game status where the board is cleared of blocks. The BFS algorithm is conceptually rattling simple: search the electrical current node, together with therefore search that node's kid nodes, together with therefore search those children's kid nodes, together with therefore on until nosotros divulge what we're looking for.

If nosotros recall of the graph every bit a tree alongside the electrical current node at the root, together with therefore we're searching all nodes inwards the tree inwards social club from those closest to the root to progressively deeper levels of the tree. To acquire a amend visual movie of the process, let's assume we've arranged the motility choices inwards Color Walk inwards the shape of a tree, together with nosotros receive got 3 colors to pick from instead of five. Each motility would consist of a choice betwixt 2 colors, since nosotros would never pick the same color twice inwards a row. H5N1 tree depicting 3 moves that were searched alongside BFS would await similar this:

The motility choices are blue, red, together with yellow, together with nosotros just picked bluish every bit our terminal move, therefore it is the root of the tree. Our choices for the side yesteryear side motility are together with therefore ruddy or yellow, together with each grade of the tree doubles inwards size compared to the grade earlier it. The numbers inwards each node present the social club that the nodes volition live searched alongside BFS. The squeamish affair nigh this algorithm is that if we're searching for something specific, every bit nosotros are for the end-of-game condition, together with therefore nosotros know every bit shortly every bit nosotros divulge the foremost node alongside that status that nosotros tin halt searching. That node resides at the grade alongside the to the lowest degree number of moves to hit that state. We know this fact because we've searched each grade of the tree inwards social club from the grade of the foremost motility to the grade of the foremost motility works life that completes the game. That agency we've works life an optimal solution.

Not everything is therefore nice, though. In reality this tree volition live enormous. It grows exponentially, together with nosotros are dealing alongside a base of operations of 4 instead of 2. If nosotros assume the average game volition receive got at to the lowest degree thirty moves, that agency we'll receive got to search 4³⁰ = 2⁶⁰ nodes earlier finding the shortest sequence of moves to goal the game. Even if nosotros could stand upward for each node alongside a unmarried byte of information (which nosotros most sure can't), the tree would request over an exabyte of storage to concord it. If instead nosotros generated the nodes nosotros needed to search on the fly, together with nosotros assume it took a microsecond to generate together with banking corporation check each node (highly optimistic, especially for JavaScript), it would receive got 36,560 years to search the tree. Assuming the minimum number of moves is less doesn't tending much. Reducing to 25 moves soundless results inwards almost 36 years of searching. None of this is feasible. The tree is just besides big.

We request a way to cutting this tree downward to size, together with to do it, nosotros tin usage our sometime friend greedy. The see is that the GLA algorithm works pretty well, together with it's relatively fast. We tin run alongside it for some number of moves at the foremost of the game to receive got some reasonably optimal path into the motility tree. Then switch to the BFS algorithm to divulge the optimal sequence of moves from that betoken forward.

The number that nosotros request to resolve alongside this approach is when do nosotros switch to the BFS algorithm? We don't wish to switch besides early, or it volition soundless receive got a crazy long fourth dimension to divulge the optimal path. We don't wish to switch besides late, or it volition live practically useless to receive got switched algorithms at all. It's also hard to tell when we're getting to a greater extent than or less the end, at to the lowest degree alongside the information available at the fourth dimension we're trying to decide. The best number of moves we've seen therefore far has varied from 25 to xl over 100 random boards, therefore if nosotros picked a fixed motility number of, say, twenty to switch over to BFS, nosotros could soundless live searching on the social club of 4²⁰ nodes on some boards earlier finding the optimal path.

If instead nosotros tried looking at how many blocks are left together with created a threshold for when to switch, nosotros would encounter some other problem. Sometimes i or to a greater extent than colors of blocks are non chosen for a long time, creating a large number of blocks of the same color that rest on the board until to a greater extent than or less the end, when they are wiped out alongside a unmarried move. At that betoken nosotros would all of a abrupt live besides to a greater extent than or less the goal of the game for BFS to live useful. This behaviour doesn't give all of the time, either, compounding the occupation of choosing an adequate threshold.

What nosotros request is a way to attempt for BFS, but to bail on it if it's taking besides long. We tin start alongside GLA, together with croak along to a rubber number of moves, similar 18. Then nosotros tin attempt using BFS for some reasonable number of nodes, together with if nosotros divulge the end-of-game condition, great. If nosotros don't divulge it, together with therefore we'll run GLA for some other motility together with attempt BFS again. The combined execution of both algorithms volition live slower than running GLA yesteryear itself, but hopefully we'll divulge a to a greater extent than optimal sequence of moves. Now that nosotros receive got a excogitation of action, nosotros tin start implementing the BFS algorithm. We'll start yesteryear adding it to the listing of algorithms together with adding its illustration to the switch disceptation of algorithms:

  role Solver() {     // ...      this.init = function() {       // ...        $('#solver_type').change(function () {         switch (this.value) {          illustration 'bfs':             that.solverType = that.bfsWithGla;             that.metric = areaCount;             break;           default:             that.solverType = that.roundRobin;             break;         }          // ...       });     }      // ...      this.bfsWithGla = function() {       if (moves < eighteen || bfs() === false) this.greedyLookAhead();     }   }

The metric that we'll usage is the i for GLA, together with it'll live the normal area-maximizing heuristic. We'll request a dissimilar i for BFS, together with it volition live the metric that checks if we've reached the end-of-game condition. We tin top it into the Control.checkGameBoard() role straight from inside bfs(), which allows us to laid the code upward similar it is above.

The if status to usage GLA is straightforward, together with just similar it was described: if at that spot receive got been less than eighteen moves or BFS fails, together with therefore run GLA for some other move. The details of bfs() acquire to a greater extent than complex, therefore let's receive got a await at what a basic BFS algorithm looks similar foremost together with pick it apart:

    role bfs() {       var nodes = addNodes(new Queue(), 1, null);       spell (nodes.getLength() > 0) {         var node = nodes.dequeue();          if (node.control.checkGameBoard(node.depth, endOfGame)) {           supply true;         }          nodes = addNodes(nodes, node.depth + 1, node.control);       }        supply false;     }

Here are the primal pieces of BFS, but this code is non all that nosotros volition request to acquire things working. It's the essence of the BFS algorithm, starting alongside creating a queue to concord the pending nodes that volition live checked every bit nosotros search through the motility tree. (The queue library used hither is the uncomplicated Queue.js.) The tail node of the queue volition live taken off together with checked, together with to a greater extent than nodes volition live added to the queue spell checking the dequeued node for the search condition. The spell loop does these steps every bit just described. It dequeues a node from the queue, checks if the motility associated alongside that node causes an end-of-game condition, together with adds the electrical current node's children to the queue if the goal isn't found. If the goal status is found, the search is cutting off early on yesteryear returning true from bfs(), notifying the calling role that the goal was found. If the queue e'er gets completely empty, nosotros know we've searched the entire motility tree, together with nosotros tin supply false to signal that fact.

The usage of a queue keeps the nodes inwards social club every bit BFS searches through the motility tree. The possible moves later on the electrical current motility are added to the queue first, together with and therefore each of those moves are taken off the queue inwards social club together with inspected. If the goal status isn't found, each of those moves' kid moves are added to the queue, inwards order. This procedure ends upward alongside each grade of moves beingness added to the queue inwards succession until either the search runs into the goal status or the entire tree has been searched.

Practical BFS

The BFS algorithm every bit it stands has some problems, though. First, it doesn't do anything to bound the length of the search, therefore if nosotros switch to BFS on the 18th move, many boards volition goal upward searching effectively forever. We request to bound the search somehow. Second, nosotros tin do amend than only returning truthful when nosotros divulge the goal condition. Since nosotros know what moves produced the ending, nosotros tin only do those moves right away together with live done. Last, nosotros request some way for each node to maintain runway of which moves led to that particular node. It's clear from the code that a node volition receive got information nigh which command was used for its motility together with its depth inwards the tree, but non a total tape of the moves taken to acquire to that node. We request that information attached to the nodes, together with nosotros tin do it yesteryear maintaining an array of motility numbers, called markers, that we'll utter over inwards a moment. First, hither is what the augmented bfs() code looks like:

    role bfs() {       var nodes = addNodes(new Queue(), 1, null);       var still_adding_nodes = true;       spell (nodes.getLength() > 0) {         var node = nodes.dequeue();         markers = node.markers;          if (node.control.checkGameBoard(node.depth, endOfGame)) {           doMarkedMoves();           supply true;         }          if (still_adding_nodes) {           nodes = addNodes(nodes, node.depth + 1, node.control);           still_adding_nodes = nodes.getLength() < 16384;         }       }        supply false;     }

We'll tackle the additions inwards order. The search is easily express yesteryear limiting the size of the queue. Every fourth dimension a node is searched unsuccessfully, upward to iv to a greater extent than nodes volition live added to the queue. If nosotros halt adding nodes later on the queue size hits a threshold, together with therefore the algorithm volition naturally run downward together with halt every bit the remainder of the nodes inwards the queue are searched alongside no novel additions. This behaviour is achieved through the still_adding_nodes flag together with if condition. Once the queue reaches a size of 16384 or more, still_adding_nodes volition live laid to false together with no to a greater extent than nodes volition live added.

H5N1 threshold of 16384 allows for nigh vii levels of moves to live searched. The squeamish affair nigh limiting the search inwards this way is that if nosotros create upward one's heed to trim out some motility choices earlier adding them to the queue, the algorithm volition automatically search deeper into the tree inwards the same amount of search time. Limiting the search yesteryear grade would require a alter to the threshold if nosotros wanted to search deeper, together with it would receive got to search the entire side yesteryear side level. Remember that grade size grows exponentially. By limiting the queue size, nosotros could create upward one's heed to partially search the terminal search grade if it was besides big. Alternatively, nosotros could bound the search yesteryear run fourth dimension together with acquire the added do goodness that if nosotros could improve the checkGameBoard() performance, the algorithm would automatically search deeper every bit well.

The 2nd improver to the code, doMarkedMoves() is pretty self-explanatory at this level. We'll acquire into the details if it later on describing the markers array for keeping runway of moves for each node.

The markers array is basically the marked holding from each Block object consolidated into i array for easy, compact copying to each node inwards the motility tree. (See component subdivision 4 for how the marked holding works.) We could re-create the entire blocks array for each node, but the bulk of the information inwards a block never changes during a search. Only the marked holding would change, therefore nosotros tin line it out together with arrive its ain markers array that mirrors the blocks array. To brand this change, nosotros tin add together markers at the top level:

function colorWalk() {   var blocks = [];   var clusters = [];   var markers = [];    // ...

Then nosotros request to alter every instance of <block_reference>.marked to markers[<block_reference>.position] throughout the code where <block_reference> is whatsoever reference to a Block object. With that alter made, nosotros tin brand a re-create of the markers array when nosotros add together novel nodes to the queue, preserving the motility sequence to acquire to that node inside the re-create of the array. Then nosotros tin restore the markers array alongside the i inwards the node that gets dequeued each fourth dimension through the spell loop. The dequeue activity is shown inwards the bfs() role above, together with the enqueue activity is shown inwards the addNodes() function:

    role addNodes(nodes, depth, prev_control) {       var markers_dup = markers.slice();       _.each(controls, role (control) {         if (control !== prev_control) {           nodes.enqueue({markers: markers_dup, depth: depth, control: control});         }       });        supply nodes;     }

You'll notice that nosotros don't brand a re-create for every node. One re-create is plenty for all kid nodes every bit a grouping because the checkGameBoard() role volition handgrip resetting the markers array for each kid node, every bit long every bit they're siblings. It doesn't receive got plenty information to do the same affair for kid nodes that are cousins (where the kid nodes' parents are siblings or related fifty-fifty farther upward the tree). We also top inwards the command associated alongside the raise node therefore that nosotros don't needlessly add together a node for the same command that nosotros just used to acquire hither inwards the foremost place.

Now that nosotros know how to add together together with take nodes from the queue, let's await at how nosotros tin usage the markers array to divulge the sequence of moves taken to clear the board when the end-of-game status is found:

    role doMarkedMoves() {       var move_sequence = markers.slice();       var motility = 1;       var i = _.indexOf(move_sequence, move);       spell (i > 0) {         var command = _.findWhere(controls, {color: blocks[i].color});         control.updateGameBoard();         motility += 1;         i = _.indexOf(move_sequence, move);       }     }

First, nosotros request to brand a re-create of the markers array because each fourth dimension updateGameBoard() is called, it's going to alter the markers array. Next, nosotros divulge the index of a block marked alongside the motility number of 1. Any block volition do. Then, nosotros catch the command that matches the color of the block works life together with usage that command to update the game board. Finally, nosotros increment to the side yesteryear side motility together with divulge its block's index. This procedure repeats until nosotros can't divulge the side yesteryear side motility inwards the markers array, together with yesteryear together with therefore the board should live cleared.

Performant BFS

At this betoken the code works, but there's a problem. The foremost span of iterations seem to run okay, nigh 10 seconds each on my machine, but each iteration speedily starts taking longer. It isn't besides many iterations inwards earlier each i is taking upwards of v minutes to complete. Not long later on that, the computer programme crashes alongside an out-of-memory error. We seem to receive got a retention leak, together with it evidently has something to do alongside creating tens of thousands of node objects. Somehow the garbage collector is non reclaiming all of that memory.

After doing some research together with much pondering, I recall the occupation stems from having a pointer to an object exterior of a compass (the markers array) together with to a greater extent than pointers to the same object at sure times inwards multiple levels of nested compass (in bfs() together with Queue()). The GC can't tell when nodes receive got no to a greater extent than pointers to them, therefore their retention is non freed, creating the retention leak. The way to develop this leak is to explicitly laid the pointers to null when they are no longer used:

    role bfs() {       var nodes = addNodes(new Queue(), 1, null);       var still_adding_nodes = true;       spell (nodes.getLength() > 0) {         var node = nodes.dequeue();         markers = null;         markers = node.markers;          if (node.control.checkGameBoard(node.depth, endOfGame)) {           doMarkedMoves();           supply true;         }          if (still_adding_nodes) {           nodes = addNodes(nodes, node.depth + 1, node.control);           still_adding_nodes = nodes.getLength() < 16384;         }          node.markers = null;       }        supply false;     }

Here both markers together with node.markers are laid to null explicitly, together with this remedy seems to receive got fixed the leak at to the lowest degree plenty to acquire through a batch run of 100 iterations of the algorithm. There soundless seems to live an number alongside the GC because iterations regularly receive got thirty seconds or more, but it was practiced plenty to consummate a run. Maybe an implementation of Queue that was to a greater extent than specific to this problem—one that created the correctly sized array together with exclusively laid the values of each node to reuse nodes instead of creating together with deleting them—would live to a greater extent than retention efficient. It would live an interesting occupation to explore to a greater extent than fully together with acquire from, but nosotros request to motility on together with reckon how this BFS algorithm performs.

The completed run of 100 iterations, using a GLA depth of 5, came upward alongside these results:

The results await promising, but let's compare it to a selection of the other algorithms:

Algorithm	Min	Mean	Max	Stdev
RR alongside Skipping	37	46.9	59	4.1
Random alongside Skipping	43	53.1	64	4.5
Greedy	31	39.8	48	3.5
Greedy Look-Ahead-2	28	37.0	45	3.1
Greedy Look-Ahead-5	25	33.1	41	2.8
Max Perimeter	29	37.4	44	3.2
Max Perimeter Look-Ahead-2	27	35.0	44	2.8
Perimeter-Area Hybrid	31	39.0	49	3.8
Deep-Path	51	74.8	104	9.4
Path-Area Hybrid	35	44.2	54	3.5
Path-Area Hybrid Look-Ahead-4	32	38.7	45	2.7
BFS alongside Greedy Look-Ahead-5	26	32.7	40	2.8

The BFS algorithm just barely squeaks out a victory over the GLA-5 algorithm on average together with on the maximum. It's i motility longer than GLA-5 on the minimum. This slight win came at a toll of significantly reduced speed, however, every bit the BFS algorithm runs considerably slower than GLA-5. It is, later on all, running GLA-5 for most of each iteration, together with exclusively finishing off alongside BFS to divulge the end-of-game condition.

Even if nosotros didn't brand pregnant improvements alongside the BFS algorithm, nosotros did acquire a number of things. We learned how to implement a BFS algorithm using a queue, together with that the basic see is fairly simple. Theoretically, BFS volition give an optimal solution to the occupation of finding a minimum sequence of moves for Color Walk, but the exponential growth of the motility tree presents an insurmountable occupation for a pure BFS algorithm inwards practice. To brand BFS tractable, nosotros request to start alongside a good, fast algorithm similar GLA to cutting downward the tree size earlier switching to BFS. Finally, using BFS to augment GLA tin brand incremental improvements to the performance, but it's non a slam dunk because of pregnant costs inwards run time. Next fourth dimension we'll explore the other primal graph search algorithm, depth-first search, together with reckon what problems nosotros request to overcome there.


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

Share this post