Porting Score4 to Javascript: The Browser Wars

  

 
   
  submit to programming reddit
 

(July 2011)

A Javascript port of my Score4 AI engine

For the TL;DR crowd: A couple of weeks ago I implemented the AI Minimax algorithm, in order to play a game called Score4/ConnectFour. Below you will find my Javascript port of that code: just click with the mouse on any column you wish, thus dropping green chips in the board. The goal is to form a line of four green ones - the computer will be trying to form a line of 4 red ones.
 
Your browser does not support the canvas element... Use Firefox or GoogleChrome or Opera.

to restart the game...

Minimax in Javascript - run browser, run!

A couple of weeks ago I implemented the AI Minimax algorithm, and then used it to play the Score4/ConnectFour game.

I wrote the code in both functional (OCaml/F#) and imperative (C#/C++) styles, and got different speed results from each one of them. Naturally, C/C++ was the fastest one by far: more than 5 times faster that the next best performer (OCaml). People from Reddit and Hacker News joined in, with implementations in Python, Java, Go, Haskell and D(!). I placed all the code on Github, so it is easy to compare the various implementations and see how the code works.

And today, the thought occured to me: what about Javascript, the language of the Web?

At first I was reluctant; at the depth I made the comparison (AI looking 7 moves ahead), compiled languages needed 4-5 seconds to make a move... wouldn't Javascript take a lot longer, thus making the whole effort futile?

Turns out I was wrong: The Javascript engines in modern browsers are *amazing*, to say the least. The JIT-compilation makes Javascript code run almost at the same speed as compiled languages!

It took me 2 hours to do the porting (most of which was spent reading the canvas APIs). I kept the default depth checking at level 7, and then, using my trusty Phenom II/3GHz at work, I tested it with the 5 most popular browsers. The Minimax engine (which you can test yourself above, just click on the middle column) - reports how much time it takes to make a move. This is what I got:

Google Chrome 12.0.742.1222.147 seconds
Internet Explorer 9.0.8112.16421  4.007 seconds
Safari 5.1 (7534.50)4.754 seconds
Opera 11.50 (build 1074)5.016 seconds
Firefox 5.0.17.328 seconds

Time it takes to make a move at depth level 7 from various browsers
 
To me... that was unexpected. OK, everybody knows that Chrome is REALLY fast - but I was under the impression that Firefox is very fast, too... I also knew that IE has improved a lot, but I didn't realize by how much!

Apparently, my code is a tough cookie :-) You can use "View/Source" to check it out - it is basically a line-by-line translation of the C/C++ version, since (a) that was the fastest one, and (b) if you use imperative constructs, Javascript can "mirror" C quite well.

Perhaps it's the recursive calls of minimax that Firefox doesn't like - I don't know. But feel free to join the fight, and find ways to make the code run faster - the Javascript implementation (i.e this page!) is now part of my GitHub repos :-)

Enjoy!

Update, August 3: Apparently, the new engine coming up in Firefox will run just as fast as Chrome.

Update, August 7: Since Firefox is not yet up to speed, and browsers/CPUs in mobile phones are even slower, I added auto-detection of mobile browsers, and set the depth level to (a) 5 for mobiles, and (b) to 6 for normal, desktop machines.

Nomen est omen...  main(O){10<putchar(6^--O?84-(31&0x20558400>>5*O):10)&&main(2+O);}
 
My CV  About me  Back to homepage Last update on: Fri Mar 15 14:31:35 2013 (Valid HTML, Valid CSS)