Align 4 Retrospective: Writing a Multi-Threaded Game in JavaScript

I recently published my Align 4 game on CodePen. Simply put, it’s a Connect Four clone that you play against the computer. Before I say more, go play it.

Align 4 v3 screenshot

History

This is the third incarnation of this game that I have written. I made the first one a full decade ago (!) as a Windows app written in C++. Then I made the second one a few years ago using JavaScript and HTML5 canvas. And here’s the third one, still JavaScript, but more awesome.

The AI

The AI uses the minimax algorithm to pick its moves. It’s pretty standard stuff in game theory and works really well for this sort of game, where the win condition and the moves you are allowed to make are well defined.

In a nutshell, the computer is simply navigating a huge tree of potential moves. It looks at all the moves it could make, then every set of moves you could make in response, then every set of moves it could… You get the idea. The difficulty controls how many turns ahead it will look. It’s n+1, so on diffuculty 5 it’s looking 6 moves out. After evaluating all these potential moves, it picks the most promising branch and makes the corresponding move.

Sometimes, after the AI makes a move, it’ll show a message about “feeling saucy”. This happens when it evaluates a branch and realizes that it can win no matter what you do. Likewise, when you see a message about being “unsure”, that means the AI knows you can definitely win — assuming you play the right moves.

Web Worker

This was my first true multi-threaded JavaScript app. By default, JavaScript apps are single-threaded. All code runs in the main UI thread. One unfortunate effect of this is that if you have computationally expensive code running (in this case, evaluating a huge tree of potential moves), nothing else happens until the code is done. And I’m not just talking about the JavaScript. DOM elements can’t be added, CSS animations freeze, user clicks are not responded to. Basically, your browser tab locks up. No good!

And that’s where web workers come in. A web worker lets you run some JavaScript in a separate thread. So I put all the heavy AI stuff in a web worker, leaving my main thread free and responsive.

One caveat of using a web worker is that it must be in a separate file. The file is also subject to CORS security policies. You can try to work around the separate file requirement with creative use of Blobs, but IE10+ will treat them as cross-origin, so you’re kind of screwed there. Ultimately, my solution for publishing this on CodePen was to create 2 pens, one for the UI and another for the web worker.

Animation

I used a fair bit of animation to make interacting with the chips feel more natural. I calculate positioning offsets in code, and I scale the duration of the drop animation with however many rows the chip has to drop, but besides that all animations are done in CSS. This provides much better performance than jQuery tweening. There are no real “physics” to speak of, just liberal use of ease-in/ease-out to roughly emulate acceleration due to gravity.

Oh, and one huge tip: put backface-visibility: hidden on animated elements. This will solve some flickering problems and will fix the initial stutter with delayed animations.

Tips

I have playtested hundreds (thousands?) of games against the AI. Here are a few tips to help you win:

  • Don’t bother with obvious wins. The AI won’t not notice. It’ll block you every time.
  • The trick is to trap the AI. Set up situations where you create two winning moves at once, so the AI can only block one. Or set up a situation where if the AI did block you, it would create another winning move for you on top of the chip it just dropped.
  • Controlling the center of the board is more valuable than dropping chips along the edges.
  • Play defensively. Of course you want to block the AI getting four chips in a row, but blocking three chips in a row makes the board safer.
Inline Block, Working as Intended Gradient Animation Trick