Part 1: Preparing for Santa and Krampus
Santa Tac Toe is a JavaScript port of a game I created when working as a teaching assistant for a course in AI. We had a team project where groups would create AI controlled players for the game of Amazons. Our summer terms are condensed to two months with double the lecture and lab time. To help students start their AI, I wrote a simple Tic Tac Toe game in Java to demonstrate recursive AIs. The advantage here is the search tree is so small that things like alpha-beta pruning and techniques for scoring a position are not covered so they would still need to figure those out themselves but would still have a starting point. This approach will be covered in part 2. A popular technique for games, largely due to Alpha Go, is Monty Carlo Tree Search. While I didn’t want to do a full MCTS AI, in Part 3 we look at the starting point for this technique. Finally, in Part 4 we will make everything pretty by creating the GUI for the game.
As most of my personal projects tend to be small, I tend to rely a bit too much on manual testing. This is not a bad thing, but as projects get larger and more people are involved, automated testing makes more sense. One of the trendy test driven development methods is red/green testing, which does sound like a good idea but has its detractors. The idea is you write a test first and after it fails, you write the code to make it pass the test. For code where it is easy to write automated tests, I am using Jasmine to write tests. For user interface and animation related stuff, I am still largely going to rely on manual testing, but as problems here will quickly be apparent this shouldn’t be too bad of a compromise. I do need to find a decent GUI testing suite but am not sure such a beast actually exists. For those of you interested in my test code, it is in the repository.
The board
is simply an array of numbers, set up as a single dimensional array stored as
shown in the figure above. Numbers were chosen instead of characters due to
being faster. An alternative approach would be to store the board as a string,
but strings are immutable in JavaScript. Altering a string creates a new one,
and if you are replacing the old string then it gets garbage collected. To aid
debugging, the constructor takes a string representation of the board and can
create a string representation for logging or other debugging tasks.
Setting and
getting tiles is trivial enough. The key method here is the getGameState()
method which fills out the TTTState class with information about the current
state of the board. Simply put, the game can be in progress, the X player
(Santa) could have won, the O player (Krampus) could have won, or there are no
more moves so the game ends in a tie (Cat). For win conditions, the line that
forms the win is necessary so a way of checking lines on the board is needed.
The checkLine
method assumes the starting location is correct for the direction being checked
as this is meant for internal use. All that needs to be done is to check if
three tiles all contain the same non-empty value and return true if they are. Because
we are storing the value in an array, we can use steps to find the appropriate
locations. Horizontal lines step at +1, vertical lines step at +3, diagonal
step at +4 for right diagonals and +2 for left diagonals.
checkLine(x,y,direction) {
let index = x + y * 3;
let startTile = this.board[index];
if (startTile === TTTConsts.EMPTY)
return false;
let offset = TTTConsts.LINE_OFFSETS[direction];
return (this.board[index+offset] === startTile) &&
(this.board[index+offset+offset] === startTile);
}
With this
we can work out the state of the game. We start by assuming the game is in
progress. We then quickly check to see if the board is full. If so, we know
there is either a win or a tie, so set the state to tie but continue checking
to see if it is actually a win. Each of the possible horizontal and vertical
wins are checked using the checkLine method above. Finally we check the two
diagonal moves.
getGameState() {We now have the basics for the game but need players. As we are focusing on AI players, we will start with the easiest possible AI player, one that makes moves at random. When called, this agent simply picks a tile at random, then we see if that is a valid tile and if not move to the first open tile.
this.gameState.state = TTTConsts.PLAYING;
// potential tie check
let tie = true;
for (let i = 0; i < 9; ++i)
if (this.board[i] === TTTConsts.EMPTY)
tie = false;
if (tie)
this.gameState.state = TTTConsts.TIE;
// win check
for(let i = 0; i < 3; ++i) {
if (this.checkLine(i,0,TTTConsts.VERTICAL))
this.gameState.setWinLine(this, i,0,TTTConsts.VERTICAL);
if (this.checkLine(0,i,TTTConsts.HORIZONTAL))
this.gameState.setWinLine(this, 0,i,TTTConsts.HORIZONTAL);
}
if (this.checkLine(0,0,TTTConsts.RIGHT_DIAGONAL))
this.gameState.setWinLine(this, 0,0,TTTConsts.RIGHT_DIAGONAL);
if (this.checkLine(2,0,TTTConsts.LEFT_DIAGONAL))
this.gameState.setWinLine(this, 2,0,TTTConsts.LEFT_DIAGONAL);
return this.gameState;
}
We now have the basics for the game but need players. As we are focusing on AI players, we will start with the easiest possible AI player, one that makes moves at random. When called, this agent simply picks a tile at random, then we see if that is a valid tile and if not move to the first open tile.
class AIPlayer {
constructor(playerID) {
this.playerID = playerID;
}
findNextFreeIndex(board, startIndex = 0) {
let index = -1;
let nextIndex = startIndex
do {
if (board.getTileByIndex(nextIndex) === TTTConsts.EMPTY)
index = nextIndex;
nextIndex = (nextIndex+1)%9;
} while ((index === -1) && (nextIndex !== startIndex));
return index;
}
getNextMove(board, playerToMove= TTTConsts.EMPTY) {
return this.findNextFreeIndex(board, Math.floor(Math.random() * 9));
}
}This random
player will be expanded upon for our Monty player in part 3, but next we want
to look at the traditional recursive AI, which we will do in the next part.
