Visualizing Game Trees with D3.js

D3.js is a JavaScript library for data visualization. It allows direct inspection and manipulation of the DOM, but is intended solely for data visualization. D3 is proving to be very versatile and powerful, thanks to the technologies upon which it is based: JavaScript, SVG, and CSS. In so doing, D3 takes full advantage of the capabilities of the modern browser.

In this post I will show how to use D3.js to visualize game trees using Mauler, the abstract strategy games framework that I described in a previous post. The full source code used for this blog post is in this Gist.

What is a game tree?

In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. Here is a figure of a game tree in which the root node is a Tic-Tac-Toe game position and the first player, X, is about to move next:

Being able to visualize game trees like this one is very useful to analyze the possible moves and outcomes to make better decisions. For example, in this figure we can see that:

  • There are three possible moves for X.
  • There are 10 game positions that can be potentially reached from the current position.
  • There are five leaf nodes, which means five possible endgame positions.
  • The outcomes for the five endgame positions are:
    • Two wins for X.
    • One win for .
    • Two draws.
  • If we assume perfect play by the second player, only the move to the middle-bottom square guarantees a win for the first player.

Even in a trivial example like this, it is much easier to make these observations with a corresponding visualization of the game tree. Also, in the case of more complex examples, data visualization allows us see patterns or trends that we might have missed otherwise.

Now let's walk through, step by step, how to visualize game trees with Javascript, SVGs and D3.

Drawing the Tic-Tac-Toe game board

First of all, we need to create an instance of a Tic-Tac-Toe game position. I'll be using the Tic-Tac-Toe implementation from Mauler:

var ticTacToe = new TicTacToe({
    board: [['O', 'X', 'O'],
            ['O', 'X', ' '],
            [' ', ' ', 'X']]
});

Next, define the dimensions and colors for the board:

var boardLength = 150,
    squareLength = Math.floor(boardLength / 3),
    bgColor = "rgb(255, 219, 122)",
    gridColor = "rgb(229, 197, 110)",
    crossColor = "rgba(231, 76, 60, 1.0)",
    noughtColor = "rgba(41, 128, 185,1.0)";

Now we can create the SVG and set its dimensions. For convenience, a d3 selection of the <svg> element will be stored in the svg variable:

var svg = d3.select(document.createElement("svg"))
                .attr("width", boardLength)
                .attr("height", boardLength);

Fill the background using an SVG <rect> element:

svg.append("rect").attr({
    "x": 0,
    "y": 0,
    "width": boardLength,
    "height": boardLength,
    "fill": bgColor,
    "stroke": "none"
});

Draw the grid using a <rect> element for the border and <line> elements for the grid:

// border
svg.append("rect").attr({
    "x": 0,
    "y": 0,
    "width": boardLength,
    "height": boardLength,
    "fill": "none",
    "stroke": gridColor,
    "stroke-width": Math.floor(lineWidth * 2)
});
// lines
for (var i = 1; i < 3; i++) {
    // vertical
    svg.append("line").attr({
        "x1": squareLength * i,
        "y1": 0,
        "x2": squareLength * i,
        "y2": boardLength,
        "stroke": gridColor,
        "stroke-width": lineWidth
    });
    // horizontal
    svg.append("line").attr({
        "x1": 0,
        "y1": squareLength * i,
        "x2": boardLength,
        "y2": squareLength * i,
        "stroke": gridColor,
        "stroke-width": lineWidth
    });
}

Draw the Xs and s:

var scale = d3.scale.ordinal()
                    .domain([0, 1, 2])
                    .rangeRoundBands([0, boardLength], 1, 0.5);

var drawCross = function(row, col) {
    var cellSize = squareLength / 4,
        crossLineWidth = squareLength / 10;
    svg.append("line").attr({
        "x1": scale(col) - cellSize,
        "y1": scale(row) - cellSize,
        "x2": scale(col) + cellSize,
        "y2": scale(row) + cellSize,
        "stroke": crossColor,
        "stroke-width": crossLineWidth
    });
    svg.append("line").attr({
        "x1": scale(col) - cellSize,
        "y1": scale(row) + cellSize,
        "x2": scale(col) + cellSize,
        "y2": scale(row) - cellSize,
        "stroke": crossColor,
        "stroke-width": crossLineWidth
    });
};

var drawNought = function(row, col) {
    svg.append("circle").attr({
        "cx": scale(col),
        "cy": scale(row),
        "r": squareLength * 0.3,
        "fill": noughtColor
    });
};

for (var row = 0; row < 3; row++) {
    for (var col = 0; col < 3; col++) {
        var cellType = ticTacToe.cell(row, col);
        if (cellType === "CROSS") {
            drawCross(row, col);
        } else if (cellType === "NOUGHT") {
            drawNought(row, col);
        }
    }
}

And now we have a full SVG implementation of the Tic-Tac-Toe board! For convenience, from now on we will assume a drawTicTacToe(game) function that returns a new <svg> element based on the given Tic-Tac-Toe game.

Generate the tree

The next step is to automatically generate the tree that we want to visualize. The tree will have the following structure:

var tree = {
    game: ticTacToe,
    children: [{
        game: game,
        children: [{
            game: nextGameState1
        }]
    }, {
        game: nextGameState2
    }]
};

Every node in the tree has a game property that represents the current game state, and the children is an optional property that has the list of possible game states that can be reached by making each of the legal moves. To generate the game tree we will start creating the root node:

var root = {
    game: ticTacToe
};

Now we will create a simple depth-first search (DFS) algorithm to generate the tree from a given node:

var depthFirstTreeGenerator = function(node) {
    var moves = node.game.moves();
    if (moves.length > 0) {
        node.children = [];
        for (var i = 0; i < moves.length; i++) {
            var newGameNode = { game: node.game.copy().move(i) };
            node.children.push(newGameNode);
            depthFirstTreeGenerator(newGameNode);
        }
    }
};

And we just have to pass the root node to the DFS algorithm to generate the full tree:

depthFirstTreeGenerator(root);

Visualize the game tree

Now that we have the game tree that we want to visualize, and a drawTicTacToe(game) function that returns a new <svg> of the game, we can finally draw the tree. Here is the code to visualize the tree with D3:

var margin = { top: 50, right: 30, bottom: 60, left: 30 },
    width = 675 - margin.left - margin.right,
    height = 400 - margin.top - margin.bottom,
    nodeSize = 85,
    edgeWidth = 2,
    treeBgColor = "#eeeeee",
    edgeColor = "#666666";

var diagonal = d3.svg.diagonal().projection(function(d) { return [d.x, d.y]; });

var svg = d3.select(svgElem)
            .append("svg")
            .attr("width", width + margin.left + margin.right)
            .attr("height", height + margin.top + margin.bottom)
            .attr("style", "background-color: " + treeBgColor)
            .append("g")
            .attr("transform", "translate(" + margin.left + ", " + margin.top + ")");

var tree = d3.layout.tree().size([width, height]);

tree.separation(function() {
    return 2;
});

var nodes = tree(root);

var nodeMargin = nodeSize / 3.4;

svg.selectAll("path")
    .data(tree.links(nodes))
    .enter().append("path")
    .attr("d", diagonal)
    .attr("fill", "none")
    .attr("stroke", edgeColor)
    .attr("stroke-width", edgeWidth);

svg.selectAll("g.node-group")
    .data(nodes)
    .enter()
    .append("g")
    .attr("class", "node-group")
    .attr("transform", function(d) {
        return "translate(" + (d.x - nodeMargin) + ", " + (d.y - nodeMargin) + ")"
    });

// Draw nodes
svg.selectAll(".node-group")
    .each(function(node) {
        svgView.model = node.game;
        svgView.svg = d3.select(this);
        svgView.render();
    });

// Resize game nodes
svg.selectAll(".node-group")
    .attr("transform", function() {
        return this.getAttribute("transform") + " scale(0.6)";
    });

Examples

Here are a few examples of game trees of different sizes generated with this script. At two plies:

At three plies:

At four plies:

And that's it! You can find the full source code used for this blog post in this Gist.

Summary

In this blog post I showed how we can use D3.js to visualize game trees using the game of Tic-Tac-Toe. The code used here would work for any other abstract strategy game as long as it follows the Mauler interface. In the next blog posts I'll show how to visualize game tree search algorithms (i.e. Minimax, Alpha-Beta Pruning, Monte-Carlo Tree Search) to play abstract strategy games.


comments powered by Disqus