Minimax with Alpha-Beta Pruning

The Algorithm Wiki is now using the new streamlined Tailspin visualiser UI. It is a fraction of the size of the old visualiser framework and makes use of the latest Tailspin Javascript interpreter.

To toast this I have added algorithms for minimax and minimax with alpha-beta pruning.

These were the algorithms that I implemented from Wikipedia a long time ago, only to spend hours debugging to find a ≤ was swapped for a ≥, the algorithms that started the initial experiments that became Tailspin. Wikipedia is now corrected, but the simple typo underscores the danger of code that never executes. It’s almost impossible to ensure it is accurate, and even if you do, on a wiki someone else will add a typo for you. Now you can run and execute the exact code live using Tailspin combined with a great visualisation.

Wikipedia, of course, still has a much more robust description and explanation of alpha-beta pruning. But this guarantees the code is correct and just plain a great visualisation aid to understanding the complexities of alpha-beta pruning.

Tailspin on GitHub

Tailspin is now up on GitHub and down to 57 / 11578 failures running the ES5.1 test262 test suite.

Interactive Javascript programming puzzles

Using Tailspin, a flexible and reversible Javascript interpreter, for algorithm visualisation merely scratches the surface of what it can do.

One of the more interesting opportunities is interactive learning environments. There are many online interactive Javascript websites, but all use the browser’s interpreter or server-side execution of code. Websites like Code Academy and Khan Academy do a pretty good job, but they are limited by the black-box execution of code in the browser.

By using Tailspin which provides access to the inner workings of the interpreter it is possible to expand what can be done in these online interactive coding websites.

C->A->T

Modelled on the pointer programming puzzles of Jhavé, I have used Tailspin to create a small website for interactive Javascript programming problems. Access to Tailspin’s workings during execution allows the visualise of any user supplied program as it runs, and enables them to see how their solution succeeds or fails.

Among other things it provides:

  • Live code errors and warnings
  • A range of programming puzzles
  • Automatic saving of your progress
  • Scrubbable execution of your Javascript program
  • A visualisation of your program running that shows the values and lists in your program
  • A visualisation that animates as you scrub through the program execution

Check it out here: JS problems — How will you fare?

Reversible Javascript

Stepping through code in the browser is very cool, but it can already be done with a bit of work by enabling developer mode on your browser and writing your own .html and .js files.

What you can’t do is go back in time.

Which leads me to Tailspin. It is a fully reversible, standards-compliant1, meta-circular Javascript interpreter. As well as running in the browser and allowing algorithms to be visualised, it can run code both forwards and backwards.

A reversible interpreter provides some really interesting opportunities for exploration and education. So far I have focused on algorithm visualisation where reversibility makes it possible to scrub through the execution of algorithms. This is not just fun, it transforms the experience of understanding the algorithm. You can see this used to great effect in the Algorithm Wiki and in the depth-first traversal example below. The code that is highlighted on the left-hand side is the actual code that is running.

All the visualisations on the Algorithm Wiki have been updated and support reversible execution. You can now scrub through algorithms such as Factorial, Insertion Sort or Fisher-Yates Shuffle.

I have also updated the in-browser IDE to support reversibility, so you can step backward through your own code. Even after your code has hit an exception or ended, you can step backwards into the code to see what happened.


  1. Tailspin meets more than 99% of the 11500 tests in the ECMAScript Language test262 suite. The test262 suite is the standard test suite for ES 5.1 the standardised Javascript that runs in your browser. So you can be very certain that code that runs in Tailspin works in your browser. 

Javascript in Javascript in a Wiki

A while ago I implemented an algorithm from Wikipedia. It turned out it had a subtle bug. A single less-than instead of a greater-than. Unfortunately I spent a long time finding the problem, but it did start me thinking about how to improve pseudo-code on the web.

In an interactive medium there is little reason why algorithms should still be presented as static text. Text which can not be visualised, verified or checked in any way. Algorithms are complex beasts and ensuring they are correct is tricky and understanding them takes time. Running an algorithm is essential for correctness and stepping through an algorithm is extremely helpful for comprehension.

This meshed with something a few things I had been tinkering with for a while. A full Javascript-in-Javascript interpreter, Narcissus, rewritten in continuation-passing style to allow more control over the interpretation. Using an interpreter on-top of the browser’s native interpreter allows code to be paused and controlled in ways that are impossible when running native Javascript code in the browser.

The result is Javascript code that runs in the browser but can be controlled and visualised. Code that a user can pause and step through to see the control flow. Code which is verifiable and has a much better chance of being correct. Real code not pseudo-code. Right in your web-browser. As an example here is an interpreter and visualisation which runs the Javascript code for the bubble sort algorithm:

This is pretty neat, but it is a bit more interesting taking it a bit further. On top of the Javascript interpreter I built an experimental wiki http://will.thimbleby.net/algorithms to explore making algorithms interactive on the web. It’s experimental because there are still lots of things to do and to figure out (eg. security), but I think it is very promising.

Some old Apple PR

I just rescued this from the handy Wayback Machine. It spells out some of my thinking at that point about UI design and it calls me an “Interface Master” which doesn’t hurt.

Apple PR

Scanline Flood Fill

After spending a while looking for a decent scanline flood fill algorithm and not finding one, I built my own. The above interactive example shows how both scanline and simple flood filling work. You can draw and test any of the four different flood fills to see how they compare. Once you have filled an area, clicking and holding the “Show pixels tested” button shows a “heat” map of the number of times each pixel has been tested (from green:1 to red:8).

The scanline flood fill algorithm works by scanning a line, and adding ranges on the next/previous lines to a stack. For a shape with no loops or thin walls which are filled on both sides the scanline algorithm will only test each pixel once. It achieves this by skipping testing the range of pixels that the current line was filled from.

A rough outline of the algorithm is:

  1. Add the starting range [x, y] to a stack.
  2. While there is a range to fill:
    1. Extend the current range left and right.
    2. Add new ranges on the previous and next lines that overlap the current range to the stack. Skip testing the range of pixels that the current range was created from.

This implementation is nice, clean, fast and supports 8-way (diagonal) filling. All the values needed are passed in as parameters to floodFillScanline. The test(x, y) function returns true for pixels that need filling, the paint(x, y) function paints the pixel. This function will fill all connected pixels starting from (x, y) as long as test and paint are defined over x:[0, width) and y:[0, height) and a painted pixel does not test true.

function floodFillScanline(x, y, width, height, diagonal, test, paint) {
    // xMin, xMax, y, down[true] / up[false], extendLeft, extendRight
    var ranges = [[x, x, y, null, true, true]];
    paint(x, y);

    while(ranges.length) {
        var r = ranges.pop();
        var down = r[3] === true;
        var up =   r[3] === false;

        // extendLeft
        var minX = r[0];
        var y = r[2];
        if(r[4]) {
            while(minX>0 && test(minX-1, y)) {
                minX–;
                paint(minX, y);
            }
        }
        var maxX = r[1];
        // extendRight
        if(r[5]) {
            while(maxX<width-1 && test(maxX+1, y)) {
                maxX++;
                paint(maxX, y);
            }
        }

        if(diagonal) {
            // extend range looked at for next lines
            if(minX>0) minX–;
            if(maxX<width-1) maxX++;
        }
        else {
            // extend range ignored from previous line
            r[0]–;
            r[1]++;
        }

        function addNextLine(newY, isNext, downwards) {
            var rMinX = minX;
            var inRange = false;
            for(var x=minX; x<=maxX; x++) {
                // skip testing, if testing previous line within previous range
                var empty = (isNext || (x<r[0] || x>r[1])) && test(x, newY);
                if(!inRange && empty) {
                    rMinX = x;
                    inRange = true;
                }
                else if(inRange && !empty) {
                    ranges.push([rMinX, x-1, newY, downwards, rMinX==minX, false]);
                    inRange = false;
                }
                if(inRange) {
                    paint(x, newY);
                }
                // skip
                if(!isNext && x==r[0]) {
                    x = r[1];
                }
            }
            if(inRange) {
                ranges.push([rMinX, x-1, newY, downwards, rMinX==minX, true]);
            }
        }

        if(y<height)
            addNextLine(y+1, !up, true);
        if(y>0)
            addNextLine(y-1, !down, false);
    }
}

A* shortest path in Javascript

A* is a well known and popular shortest path algorithm. With the correct heuristic it is efficient and finds the optimal solution. Here’s a fun and simple Javascript implementation that makes use of the canvas element. The code is free (public domain) for anyone to use or improve.

The above demo lets you play with the algorithm. By clicking you can add/remove walls or drag the start (blue) or end (red) nodes. The shortest route is highlighted by a red line and the searched nodes are drawn from yellow to green by distance from the start node.

The options to the right of the map control how the path is calculated. Diagonal movement is considered as the same cost as straight movement, but the tweak diagonal cost toggle adjust the diagonal cost to be slightly more expensive so that nicer looking paths are preferred. This doesn’t alter the length of the found path only the number of nodes searched and the path’s appearance.

A tie breaker can be used to decided which nodes with the same estimated cost are preferred. Preferring new nodes is a very simple and efficient tie breaker. The prefer new nodes option toggles preferring new/old nodes, if old nodes are preferred then A* performs much worse especially for empty spaces. The dot product tie breaker is a different tie breaker that chooses paths that are closer to the straight line between the start and end for equal paths.

For more information on the A* algorithm and path finding I would recommend Amit’s A* Pages.

A triptych of shortest paths

  

These were created by using A* repeatedly. Each shortest path found reduced the cost along that path, thus creating brighter yellow ‘worn’ paths. The paths are generated either using a random goal location from a fixed starting point or as part of a round trip A to random location to B.

Notes on MISC

There has been plenty of interest in MISC, that warrant some quick comments.

- The source code is now available here: MISC source (about 3000 lines of Java code and 350 of MISC). Hopefully you’ll find it useful. It might also be interesting/confusing to look at the bootstrap file.
- The mathematical operators now accept multiple operands like [+ 2 3 4 5]
- Yes I like square brackets (Smalltalk, ObjC) it saves the shift key
- Quoting is required in lamda/let because there are no special forms in MISC. This means that it is possible to write lambda, let and if etc. without macros and also to have the results of an expression provide the arguments for these functions, eg. [let [union '[a:3] '[b:4]] '[+ a b]] which is not possible to write in this fashion in Lisp, because in Lisp let is a special form and does not evaluate it’s first argument.
- Creating new things and exploring ideas are always important, which is what MISC achieves for me.