(July 2011)
A Javascript port of my Score4 AI engine
| Update, September 2015: Complete re-write in TypeScript/React. Four years after I wrote this post, I found the time to port it to TypeScript/React, with configurable depth search and an arguably better looking interface. |
| 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. |
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.122 | 2.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.1 | 7.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.
| Index | CV | Updated: Sat Oct 8 12:33:59 2022 |