Multi-threading in JavaScript(Part-2)

Game on

What I’m talking about here is the code required to understand the rules of a game, which can then evaluate situations and tactics in order to try to beat you at that game. Complicated stuff.

To illustrate, I’m going to look at a project I’ve been developing on the side for a little while. By “little while” I mean three years, the majority of which was spent at a plateau where the game theoretically worked, but was too intense to use … until I thought of this approach. The game is a competitive puzzle based around color- and shape-matching.

To summarize: you make your way across the board by adjacent shape- and color-matching. For example, if you start on, say, a green triangle—then you can move to any other triangle, or any other green shape. Your objective is to reach the crystal in the middle, then take it to the other side of the board, while your opponent tries to do the same. You can also steal the crystal from your opponent.

So, we have logical rules determining movement and we can also see tactics emerging. For example, to avoid having your opponent reach the crystal, or stealing it from you—you might select a move that blocks them, or try to finish at a place they can’t reach.

The work of the computer is to find the best move for any given situation, so let’s have a look at that process in summary pseudo-code:

function compute() { var move = null; move = tactic1(); if(!move) { move = tactic2(); } if(!move) { move = tactic3(); } if(move) { doit(); } else { pass(); } }

We evaluate a tactic, and if that gives us a good move then we’re done; otherwise we evaluate another tactic, and so on, until we either have a move, or conclude that there isn’t one and we have to pass.

Each of those tactic functions runs an expensive process, as it has to evaluate every position on the board, as well as potential future positions, possibly many times each in light of various factors. The example only has three tactics, but in the real game there are dozens of different possibilities, each one expensive to evaluate.

Any one of those evaluations individually is fine, but all of them together, run consecutively, make for an overly intense process that freezes the browser.

So what I did was split the main code into discreet tasks, each of which is selected with a switch statement, and iterated over using an asynchronous timer. The logic of this is not a million miles away from those Choose Your Own Adventure books I used to have as a kid, where each task concludes with a choice of further tasks, all in real time, until we reach the end:

This code is significantly more verbose than the original, so if reducing code size were the only imperative, this would clearly not be the way to go.

But what we’re trying to do here is create an execution environment with no ceiling, that is, a process that doesn’t have an upper limit in terms of complexity and length; and that’s what we’ve done.

This pattern can be extended indefinitely, with hundreds or even thousands of tasks. It might take a long time to run, but run it will, and as long as each individual task is not too intense, it will run without killing the browser.

A Path of No Return

The strength of this approach is also its major weakness: since the inner function is asynchronous, we cannot return a value from the outer function. So, for example, we cannot do this (or rather, we can, but there would be no point):

function checksomething() { var okay = false; var i = 0, limit = 100, busy = false; var processor = setInterval(function() { if(!busy) { busy = true; if(condition) { okay = true; } if(++i == limit) { clearInterval(processor); } busy = false; } }, 100); return okay; }

That checksomething() function will always return false because the inner function is asynchronous. The outer function will return before the first iteration of the inner function has even happened!

This next example is similarly pointless:

if(++i == limit) { clearInterval(processor); return okay; }

We’re out of the scope of the outer function, therefore we’re unable to return from it; that return value disappears uselessly into the ether.

What we can do here is take a leaf out of Ajax coding techniques, and use a callback function (which in this example I’m calling “oncomplete”):

function checksomething(oncomplete) { var okay = false; var i = 0, limit = 100, busy = false; var processor = setInterval(function() { if(!busy) { busy = true; if(condition) { okay = true; } if(++i == limit) { clearInterval(processor); if(typeof oncomplete == 'function') { oncomplete(okay); } } busy = false; } }, 100); }

So when we call checksomething(), we pass an anonymous function as its argument, and that function is called with the final value when the job is complete:

checksomething(function(result) { alert(result); });

Elegant? No. But robustly functional? Yes. And that’s the point. Using this technique, we can write scripts that would otherwise be impossible.

Do Androids Dream of Silicon Sheep?

With this technique in our kit, we now have a means for tackling JavaScript projects that were previously way out of the realm of possibility. The game I developed this pattern for has fairly simple logic, and hence a fairly simple brain, but it was still too much for conventional iteration; and there are plenty of other games out there that need a good deal more clout!

My next plan is to use this technique to implement a JavaScript Chess engine. Chess has a huge range of possible scenarios and tactics, leading to decisions that could take an extremely long time to calculate, far longer than would have been feasible without this technique. Intense computation is required to create even the most basic thinking machine, and I confess to being quite excited about the possibilities.

If we can pull off tricks like this, who’s to say what’s possible? Natural language processing, heuristics … perhaps we have the building blocks to develop Artificial Intelligence in JavaScript!