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. Havvy

    Somebody should pit browsers against each other using this! It’d be an amusing experience.

    It’d help if the game was multiplayer, but manually moving pieces around would work too.

    Reply
    1. dvander Post author

      It doesn’t handle end-game too well, at least against other programs I found they’d end up just moving the last pieces around and not trying to win. So probably that would happen :|

      Reply
  2. Frederick Polgardy

    This is bizarre, because I’ve literally been doing the same thing. I’m not doing nearly the amount of timing-based AI as you are – just a basic minimax algo with a bottom-out depth of about 6 moves, and a heuristic I stumbled upon 15 years ago that works surprisingly well. I’ll have to take a look at your algorithm and see how mine fares against it. I’m just starting to do some tweaks.

    Let me know what you think!

    http://sustainablecode.github.com/checkers-js

    Reply
  3. Slapo

    I ran the Fast checkers benchmark in Firefox Beta 7, Opera 11 beta build 1111, Chrome 9.0.587.0 and Safari 5.0.3 (7533.19.4).
    Firefox: 5010/sec (this goes down a bit on page reload to 4818/sec or similar)
    Opera: 9272/sec (goes up on page reload)
    Chrome: 3043/sec (stays roughly the same on page reload)
    Safari: 8846/sec (stays roughly the same on page reload)

    I got numbers like those repeatedly.
    This is on Windows XP on Intel Core2 Duo [email protected] GHz, an Intel IGP Q965.

    Reply
  4. Mario Radeke

    I’m typically to blogging and i actually recognize your content. The article has actually peaks my interest. I am going to bookmark your site and maintain checking for brand spanking new information.

    Reply
  5. Jerrell Goggins

    obviously like your web site but you have to check the spelling on quite a few of your posts. Many of them are rife with spelling problems and I find it very bothersome to tell the truth nevertheless I will definitely come back again.

    Reply
  6. Roselia

    Muchas gracias por esta información, porque es justo lo que necesitaba saber sobre este tema tan sutil, que usualmente es difícil de encontrar en la web.

    Reply
  7. Bernarda Ragazzo

    Hi there I am so glad I found your website, I really discovered you by accident,while I was researching on Aol for something else, However I am below now and https://small-games.pro/football-master-hack-cheat-tool/ Right here now and also would jujst like to claim joys for a remarkable message aand a all rounded amazing blog (I also enjoy the theme/design), I don’t have time to search it all at the minute I have book-marked it and also added in your RSS feeds, so when I have time I will bbe back to find out more, Please do keep up the great work.work

    Reply
  8. Cordell

    I do not usually comment much on the web, but this time, I have to say that this reading has amazed me. A sincere thank you! By writing to us, that we are constantly seeking answers ;)

    Reply
  9. 86Aline

    I see you don’t monetize your page, don’t waste your traffic, you can earn extra
    bucks every month because you’ve got high quality
    content. If you want to know how to make extra money, search for: best adsense
    alternative Wrastain’s tools

    Reply
  10. Romaine Deangelus

    Thank you a lot for providing individuals with remarkably splendid opportunity to discover important secrets from this site. It’s always very sweet and stuffed with fun for me personally and my office peers to visit your blog at the very least 3 times a week to learn the latest tips you will have. Of course, I’m at all times happy with the beautiful ideas you give. Certain 3 facts in this posting are honestly the finest I’ve had.

    Reply
  11. Cletus

    Excellent message packed with beneficial ideas! My web site is actually reasonably brand new and I am actually likewise possessing a hard time getting my visitors to leave opinions.

    Reply
  12. Angelica

    Hello there I am actually thus delighted I found your blog post, I definitely found you accidentally, while I was actually viewing on google.com for another thing, Anyways I am actually right here right now as well as could just like to claim give thanks to for a significant article and also a all round engaging website. Please perform maintain the magnum opus.

    Reply
  13. Wilfred Finton

    I only reached this amazing internet site not long ago. I was actually caught with the part of resources you have actually acquired here. Significant fingers up for bring in such remarkable weblog webpage!

    Reply
  14. Phillip

    I consider why the other specialists of this sector do not understand this. You must continue your writing. I’m positive, you have a substantial readers’ base already!

    Reply
  15. produits de luxe

    I’ve recently started a site, the information you offer on this site has helped me tremendously. Thanks for all of your time & work. “The inner fire is the most important thing mankind possesses.” by Edith Sodergran.

    Reply
  16. suba me

    O1jDCR Your style is so unique in comparison to other people I have read stuff from. I appreciate you for posting when you have the opportunity, Guess I all just book mark this site.

    Reply
  17. Maryalice Sandager

    Awesome blog! Do you have any recommendations for aspiring writers? I’m planning to start my own blog soon but I’m a little lost on everything. Would you recommend starting with a free platform like WordPress or go for a paid option? There are so many choices out there that I’m totally overwhelmed .. Any suggestions? Thanks!|

    Reply
  18. 루비맞고

    Thank you, I’ve just been searching for info about this subject for ages and yours is the greatest
    I’ve discovered so far. However, what about the conclusion? Are you positive about the source?

    Reply
  19. 라스베가스 호텔 예약

    Hmm it seems like your blog ate my first comment (it was super
    long) so I guess I’ll just sum it up what I wrote and say, I’m thoroughly enjoying
    your blog. I as well am an aspiring blog blogger but I’m still new
    to everything. Do you have any suggestions for novice blog writers?

    I’d certainly appreciate it.

    Reply
  20. Anonymous

    If some one needs expert view regarding blogging and site-building then i recommend him/her to pay a visit this web site, Keep up the good work.

    Reply
  21. Anonymous

    I was curious if you ever thought of changing the structure of your blog?
    Its very well written; I love what youve got to say. But maybe you could a little more in the way of content so people could connect with it
    better. Youve got an awful lot of text for only having one or 2 pictures.
    Maybe you could space it out better?

    Reply
  22. https://www.kgxcf5p77.online

    Excellent site you have here but I was wanting to know if you knew of any discussion boards that cover the same
    topics talked about in this article? I’d really like to
    be a part of community where I can get suggestions from other experienced people that share the same interest.
    If you have any suggestions, please let me know. Thanks!

    Reply

Leave a Reply

Your email address will not be published.