It started as a joke to brand a game where the user would be Firefox and the object of the game would be to beat Internet Explorer. My friend Ken Saunders and I first looked for programs that we could reuse and adapt for our little project. However each script we looked at was deficient or buggy. Neither did the existing games play very well, and a game without a real challenge is quick to bore. Sometimes the code was so badly written that it was difficult to adapt it for our purpose and hard to fix the most glaring bugs. That's really when I decided it would be easier to write my own checkers program and do it right from scratch. I think I succeeded and made one of the better checker games on the web. It became a serious program that went well beyond the browser war joke that it was intended for.
The original version of this checkers game was developed in 2006. It has been upgraded several times since, with improvements to the AI engine and the addition of new features. Building it was an enjoyable and educational experience.
One of the first decisions to make was the choice of rules by which the game should be played, as there are in fact several alternative sets of rules for the game of checkers. The ones I used for this game are based on the rules for American checkers or British draughts. The main reasons for this is that these are the most widely used rules internationally, and that they are actually easier to implement than most of the other rulesets.
The game is entirely written in JavaScript (with HTML and CSS for presentational purposes). However client-side JavaScript was not originally intended to build complicated programs in a web client. It was intended to execute quick and simple tasks on a web page, the maximum time a JavaScript program could run was therefore limited to a few seconds. (There is a way to work around that restriction, which is of course needed for a game like this.)
However, I had never been a fan of browser plugins, like Flash or Java to build browser based applications like games. They required, and most still do, the installation of extra software by the user, software that doesn't always work well across different platforms. JavaScript on the other hand is available to all out of the box, it's also a standardized programming language, which should result in less compatibility issues. In 2006, building a whole browser based game in JavaScript was an idea whose time had not yet come. However by 2011 the idea had become accepted especially in the Mozilla community. Efforts by browser vendors to speed up JavaScript and add new capabilities will surely lead to us seeing more browser based applications written in JavaScript over the coming years, mostly at the expense of Flash.
Building the game's core user interface (UI) was pretty straight forward. All we do is swap images in a grid that represents the playing board. We make it interactive by reacting to where the player clicks. A black square is also an image, that happens to force the board to keep its size and shape.
Pop-up messages are actually layers that are made visible when needed, while other elements of the page are changed on the fly by the JavaScript program.
As with any game where you play against the computer an artificial intelligence (AI) engine must be built to make the computer's decision. The AI engine consists of two important parts. The first is calculating a value for a given board (depending on the positions held by each player) and the second is going through all the possible moves to select the best move.
Going through all the possible moves is the more straight forward part to implement. To keep the game moving at an acceptable pace we have to limit the number of steps ahead that the AI engine will look. This limit is also what makes it possible for a player to win against the computer. Generally the more pieces there are on the board the more moves need to be checked, strictly speaking this is not always true but nevermind. Conversely with less pieces on the board the number of moves to calculate diminishes. That is if you look the same number of steps ahead. We use this fact to look ahead further when there are fewer playing pieces on the board.
For each possible move the AI engine will calculate the value of the resulting board. It will then select the move that leads to the best new board value for itself. If there are several moves that lead to the same new board value it will randomly select one of the moves. This is one reason why two similar boards rarely develop the same way, which also makes the game less predictable and more interesting.
However instead of memorizing all the possible best moves and selecting one at the end I developed a little algorithm to select the next move without memorizing more than one move. It works like this: when a move leads to a board with a value identical to a previously calculated move, the program randomly selects between the new move or the old one, depending on how many moves lead to the same value. I.e. if it's the second such move it will select the new one with 50% probability, if it's the third with 33.33%, if it's the fourth with 25%, etc... If a new move leads to a better value than any before it the counter gets reset and the algorithms starts over for this new best value.
Tricks like these help reduce memory use and speed up algorithms to make games more responsive. They often require a little bit more thought than the straight forward solutions but they are worth it.
Once I had developed the best move selection algorithm it turned out that the actual strategy pursued by the program depends entirely on the way one calculates the value of a board. It took a lot of playing around with the way to calculate the value of a board position. I ran into things like the computer committing suicide to prevent a player from crowning a piece. This happens if a king is worth more than two times what a normal playing piece is worth.
Moving pieces forward to the king row in order to get crowned, is done by giving a piece a little more value as it approaches the king row. As a result the computer tries to move it's own pieces forward while trying to prevent yours from moving forward.
Additionally, you want to defend the first row a bit (where your opponent can get his pieces crowned). To do this the valuation algorithm gives the first row a higher value than the second row.
The position of kings is valued differently of course, as you want to try to pin down your opponent's kings to the side and avoid being pinned down yourself. Therefore kings have more value in the center of the board. The computer will try to keep its own kings in the center while pushing yours to the side.
Picking a good board valuation scheme was clearly the crucial part of making the game work, it involved a lot of trial and error, it was more an art than it was programming.
Support for languages is built into the code, every bit of text is taken from a language file. Each language has one file that contains all the strings of text. This turns out to be a much more flexible solution than the usual practice of replacing text in the source code as that requires the maintenance over different versions of the software, whereas now there is only program to maintain. Additionally the language can be changed on the fly without restarting a game.
There is still a whole list of ideas for improvements and new features for the checkers game. Unfortunately that all costs a lot of time and time is scarce. However many improvements have already been made and features added.
Enjoy playing the checkers game!
Otto de Voogd - e-mail
