Generating Game Trees using Depth- and Breadth-First Search

In a previous post I described how to visualize game trees using D3.js. Now I'll present two animations of the creation of the game tree using two of the most common tree traversal algorithms: depth-first search and breadth-first search.

Depth-First Search

Breadth-First Search

If you want to jump straight to the source code, here it is:

Depth-First Search (DFS)

The main idea of the depth-first search algorithm is that it starts from the root of the tree and tries to go quickly as far from as possible. Here is the DFS function that is called on every iteration of the animation loop (until the tree is fully traversed):

var depthFirstIteration = function(node) {
    if (!node) {
        return;
    }
    var moves = node.game.moves();
    // go to parent node
    if (!moves.length || (node.children && node.children.length === moves.length)) {
        return depthFirstIteration(node.parent);
    }
    else {
        if (!node.children) {
            node.children = [];
        }
        var child = {
            game: node.game.copy().move(node.children.length),
            parent: node,
            id: nodes.length
        };
        node.children.push(child);
        return child;
    }
};

And here is the depth-first search animation:

Breadth-First Search

On the other hand, the idea of breadth-first search is to start at the root node and explore the tree level by level, visiting all siblings before visiting any children. Here is the BFS function that is called on every iteration of the animation loop (until the tree is fully traversed):

var breadthFirstIteration = function() {
    if (queue.length > 0) {
        var node = queue.shift();
        if (node.parent != node) {
            if (!node.parent.children) {
                node.parent.children = [];
            }
            node.parent.children.push(node);
        }
        var moves = node.game.moves();
        for (var i = 0; i < moves.length; i++) {
            queue.push({
                game: node.game.copy().move(i),
                parent: node,
                id: counter++
            });
        }
        return node;
    }
};

And here is the breadth-first search animation:

And that's it! In the next blog post I'll show how to add the Minimax values to the game nodes. The Minimax value indicates whether the game position is a win, loss or draw for the player whose turn it is, and finding that value is the goal of most game-playing algorithms.


comments powered by Disqus