We have previously seen how we can create a fairly simple game in a short amount of time. In the closing post of the series, I mentioned one possible direction for evolving the code was adding the option to “play against the computer”, i.e. have the option for an automated player, or even two.
This is not only interesting from the coding point of view. It also allows us to explore how to code heuristics and/or “AI” into the game, compare strategies, etc.
In this post, I will describe the necessary changes made in the code in order to incorporate these bots into the game. This is not meant to be anyway authoritative source on how to write good AI for games, or how to implement it efficiently. It’s just one way to add this kind of feature.
If you want to see the end result, have a look at the deployed game instance, and follow the instructions for specifying automated players.
Enabling Automated Players
The first order of business is to facilitate introduction of AI players (“bots”). So far, the code we built was responding to mouse clicks in the browser, in other words, driven by human interaction. We’d like to allow for moves to be decided by code, and for the game to invoke such code and proceed with the game, without any human interaction.
Keeping to the spirit of the original design, we’re still building the automated players as part of the Javascript, browser-based code. We don’t want to introduce another separate runtime component to the system.
So the next two commits (6a4c509, 5489462) introduce this facility:
You can see that the setup of the AI players is done during the construction of the MancalaGame class (game.js, line 24). The requested AI player type is passed using URL parameters (index.html, lines 6,10-16) which are then parsed and used for initializing the bots. Note that the necessary player class is setup in the global PLAYER objects1. At this point we have only one type of player – SimpleAIPlayer.
The invocation of the AI player happens when responding to the player’s click (game.js, line 50). The _makeNextMoveIfCurrentPlayerIsAI function (game.js lines 53-62) simply checks that the game isn’t done, and whether the current player is an AI one. If it is, we invoke the nextMove function which is the main function in the AI player’s interface. The result of this function is simply the cell to play. The function then invokes the makeMove function, which is also used for human players from the UI.
Another small addition is the start function for the MancalaGame class (game.js, lines 42-45). Which simply tests if player one (the current player at the beginning of the game), is an AI, and makes a move. This is used to kickstart a game where the first player is a bot. The 2nd player being a bot, and further moves of the 1st player, is handled through the mechanism described above.
We Start Simple
The first implementation of a bot in this game (SimpleAIPlayer.js) is dead simple – it’s based on a very naïve heuristic: play the cell with the most cells in it. To be honest, it’s only here to serve as a straw man for testing the whole bot mechanism; there’s not a lot of wisdom in this heuristic. It can also serve as a benchmark for testing other strategies.
The implementation of the nextMove method – the only method in the bot interface – is pretty straightforward: based on the current player playing (the side parameter), simply search for the cell with the most stones on that side of the board (lines 21-26 in SimpleAIPlayer.js). Note that this strategy is deterministic – given a board state, it will always choose the same cell2. This is important when testing this, and also for testing this against other bot strategies.
Mancala Bot Wars
The next commit adds another simple AI bot player – Random AI Player, which simply picks a cell to play at random. This in itself isn’t very interesting. What is interesting3 is that now we have two types of bots, and we can run experiments on what strategy is better – we just pit the two bots against each other.
In order to do that, we’ll write some code that enables us to run the game with two bots and record the result. The next commit takes care of that:
First, you’ll note the bots.js file, which is a simple script, invoked from the command line, that simply runs several rounds of the game and writes the results to a file. Every round creates a new game instance with the chosen player types, and calls game.start. It’s a script with some parameters, nothing fancy.
In order to support this, we need to refactor the MancalaGame class a bit. Specifically, we need it to be able to run w/o UI. This means two things: the game needs to run without a UI, and delivering the results has to be decoupled from the UI as well.
This is what happens in the game.js file. In lines 3,6 you can see we add a callback to announce that the game is over, and transmit the result. This callback is used in the _gameOver method, in line 35. Note that the code for showing the game over message moved out from this class (as it should); look for it in the index.html file.
In addition, we enable the client of the MancalaGame class to pass a null value for the cnvsELID constructor parameter, which signals to us that there’s no canvas UI to be used for this game instance. The boardUI member then becomes optional (lines 8-13) and whenever we access the boardUI, we need to make sure it’s present (lines 18,41).
We now have a game that can be run without human intervention, and play out solely with bots. We can now start experimenting with different game parameters, and see what strategy plays out better.
Prime geeky goodness.
Later commits clean up the bot experiment script, and add features. We also add other types of both player, with different heuristics (e.g. greedy capture, minimax player) so we can compare more strategies.