(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 |
The comments on this website require the use of JavaScript. Perhaps your browser isn't JavaScript capable or the script is not being run for another reason. If you're interested in reading the comments or leaving a comment behind please try again with a different browser or from a different connection.