JavaScript Checkers

I’ve been itching to write some JavaScript, so a few days ago I threw together a Checkers game that uses only HTML5 and JS. It’s got a simple AI that terminates after three seconds. The faster your browser can run JavaScript, the smarter the AI will be.

For example, here is Firefox 4 Beta (blue) versus Firefox 3 (red) – it happens that Firefox 4 is roughly 10X faster at this program, and soundly defeated its predecessor:

Firefox 4 Beats Firefox 3 at Checkers

The algorithm for the AI is UCT, a form of Monte-Carlo Tree Search. The idea is to estimate the likelihood of winning from a position by simulating hundreds or thousands of random games. UCT helps prune the search space by quickly eliminating bad positions.

While writing the source for this, I tried to turn off the part of my brain that said, “Hey! I know Firefox version x.y.z might be slow or fast at feature X.” That turned out to be okay, but it was harder to avoid general knowledge about JavaScript engines. I ended up with three variations:

  • Fast Checkers, which has manual inlining, manual strength reduction, hardcoded constants, and other gross stuff. Pieces and positions are represented via packed integers.
  • Slow Checkers, which removes manual inlining, strength reduction, and baked-in constants. Here, the additional overhead is extra memory accesses and function calls.
  • OO Checkers, which is the same as “slow”, except represents pieces as objects instead of packed integers. Here, an additional overhead is object allocation.

Performance seems uniform across most browsers. Below I’ve recorded the number of games each browser could simulate per second. Higher is better. Note – this chart is totally unscientific, and random simulations are affected by the behavior of Math.random().

Fast Checkers Slow Checkers OO Checkers
Firefox 4 Beta 14035 9018 9100
IE9 PP6 14579 8234 8067
Opera 11 Alpha 13165 8178 8749
Safari 5 12442 8045 8700
Chrome 9 Canary 4160 2060 2343

And – because why not – I ran them on my Droid 2 as well.

Fast Checkers Slow Checkers OO Checkers
Fennec 2b3pre 338 170 220
Android Browser 185 93 114
Opera Mobile 166 112 126

Since I’m pretty bad at web development, and don’t write JavaScript (sans test-cases) nearly as much as I should, this was an amusing experience. I kept making some really dumb mistakes, one repeatedly:

Select All Code:
Game.prototype.player = function () {
    return this.board.player;
}
...
var player = game.player;
if (player == x) { ...

And wondering why “player” showed as a function in the developer console. I probably should have used ES5 getters. A few other language features would have made the experience a little nicer – but nothing so much as real modules. I tried to emulate good encapsulation with closures, but it’s just not the same. And it doesn’t seem like any engine is smart enough yet to propagate constants through closures (which is one difference between the “fast” and “slow” variants).

Using developer tools for the first time was also an interesting experience. Firefox 4 and Chrome can debug code with a reasonable slow-down, but IE9 became over 100X slower; presumably it cannot debug with the JIT yet. I used Firebug until I needed single-stepping (we didn’t have that working in JägerMonkey for Beta 7), and then bounced over to Chrome – both proved really invaluable. I think my days of calling alert() are over.

Anyway, it was fun writing this, and I’m glad that I can write something computationally expensive and have it be fast everywhere. If and when time permits I may try a more stimulating game like Go.

110 thoughts on “JavaScript Checkers

  1. gta 5 mobile

    The original 3 series ran until December of 2003 in Japan before being licensed
    for English-language release. That is the most important message
    the magic of friendship really wants to send. However as the latest version of Minecraft continues to be releasing, then Notch created a survival mode – a mode which created a brimming with it.

    Reply
  2. Myra Caire

    Hello,

    TIRED OF WAITING FOREVER TO EARN A PROFIT ONLINE ?

    My name is Myra Caire and I’m talking about a new way to generate quick traffic and sales in ANY niche with ZERO video/website creation, ZERO paid advertising/SEO.

    I’ve recently tried this product but quickly decide to write this review because I know this is exactly what you are looking for your bailopan.net

    No Previous Skills Or Experience Required. You can literally be a COMPLETE Newbie and Get RESULTS with just 5 minutes of actual “work”..

    SEE FULL REVIEW: http://bit.ly/36OJXNh

    Kind Regards,
    Myra Caire

    Reply
  3. yaltavesti.com

    There are many top marketers available with lists
    of below ten thousand that make additional money
    than some of those with lists of hundreds of thousands.
    Without being consistent your audience would turn away especially if they do not hear from you for
    some time. I recommend re-setting qualitative goals once
    every 2-3 months, more frequently if you’re growing rapidly.

    my blog squas (yaltavesti.com)

    Reply
  4. Ayana Tjepkema

    May I simply just say what a relief to discover somebody that genuinely knows what they’re talking about on the web. You definitely know how to bring a problem to light and make it important. A lot more people must read this and understand this side of the story. I was surprised you’re not more popular since you most certainly have the gift.|

    Reply
  5. Inez Loveless

    Good day

    I just checked out your website bailopan.net and wanted to find out if you need help for SEO Link Building ?

    If you aren’t using SEO Software then you will know the amount of work load involved in creating accounts, confirming emails and submitting your contents to thousands of websites.

    With THIS SOFTWARE the link submission process will be the easiest task and completely automated, you will be able to build unlimited number of links and increase traffic to your websites which will lead to a higher number of customers and much more sales for you.

    IF YOU ARE INTERESTED, We offer you 7 days free trial
    ==> http://bit.ly/Robot_Submitter

    Kind Regards,
    Inez Loveless ! Business Development Manager

    Reply

Leave a Reply

Your email address will not be published.