Making Santa-Tac-Toe part 2 of 4

 Part 2: Solving Using a Tree

With the basic game class that was created in the last part, we are ready to create a better player to play against. This is where the computer can have an advantage over us humans as they can examine many more moves per second than we can. This allows more exploration of the possible moves, and with a simple game like Tic-Tac-Toe, can even explore all the possible moves when deciding what move they wish to make. How is this possible? When you think about a game, it can be represented as a tree structure as shown in the image below.

The first move has nine options. The second has 8 options for each of the 9 boards. The third move has 7 options for each of the 72 boards and so on. The total number of board configurations is 9!, which is 9 factorial or 9x8x7x6x5x4x3x2x1 for a grand total of 362,880. As each move leads to a set of other moves, the game can be represented as a tree. The AI then just hast to start on the node of the tree representing the current state of the board then find the move most likely to win. There is one problem, namely that the opponent also wants to win.

We need to be able to pick the best move to make for the computer while also assuming that the opponent will always pick the best move that they can. This may sound like a problem, as what happens if the opponent doesn’t pick the best move? The answer is that the AI will still be in a good position, possibly even able to win the game faster by taking advantage of the mistake. Still, if you are using some of the pruning techniques we will be discussing, this could be a problem as the AI may not have stored information about that move and will have to search from scratch.

The basic approach then is to recursively search the tree taking the best move from whoever the current player is.  As the opponent winning is bad for us, we will invert the score from the opponent so will weigh the moves that the opponent wins as an undesirable position for us. This is implemented as a recursive pair of methods.  ScoreTiles simply takes a board and scores each possible move on the board by calling scoreTile. ScoreTile checks to see if a particular tile is a valid move and if so if that move will result in a win. If the move is not an immediate win or tie, we need to look at the next moves in the game taking the highest score from that and inverting it. This recursion will repeat until a winning or tie move is reached.

scoreTiles(board, curPlayer) {
    let scores = [];

    for (let i = 0; i < 9; ++i) {
        if (board.getTileByIndex(i) === TTTConsts.EMPTY) {
            scores.push(this.scoreTile(board, i, curPlayer));
        } else
            scores.push(TTTConsts.INVALID_MOVE);
    }

    return scores;
}

scoreTile(board, index, curPlayer) {
    if (board.getTileByIndex(index) !== TTTConsts.EMPTY) return TTTConsts.INVALID_MOVE;
    this.testBoard.clone(board);
    this.testBoard.setTileByIndex(index, curPlayer);
    let winState = (curPlayer === TTTConsts.X) ? TTTConsts.X_WON : TTTConsts.O_WON;
    let state = this.testBoard.getGameState();
    if (state.state === TTTConsts.PLAYING) {
        // recurse
        let rboard = new TTTBoard();
        rboard.clone(this.testBoard);
        let opponent = (curPlayer === TTTConsts.X) ? TTTConsts.O : TTTConsts.X;
        let scores= this.scoreTiles(rboard, opponent);
        let highIndex = 0;
        for (let i = 1; i < 9; ++i)
        if (scores[highIndex] < scores[i])
            highIndex = i;
        return -scores[highIndex];
    }
    return (state.state === winState) ? 1 : 0;
}

The getNextMove API call then simply calls the ScoreTiles for the existing move and picks the move with the highest score.

getNextMove(board, playerToMove = TTTConsts.EMPTY) {
    let scores = this.scoreTiles(board, playerToMove);
    console.log(scores)
    // return best move
    let highIndex = 0;
    for (let i = 1; i < 9; ++i)
        if (scores[highIndex] < scores[i])
            highIndex = i;
    return highIndex;
}

The search tree for Tic-Tac-Toe is a small enough tree that we can fully explore it, but what if it is not? More complicated games may not allow for us to search the entire tree in a reasonable timespan. For these games we need to come up with a different way of scoring the state of the board. This will be game specific, but one approach I would consider if there is not a good way of finding a weight for the board would be to recurse to the desired end depth and then simply do a series of random games and return a score based on how many wins occurred. Limiting the depth that you search also is a way to reduce the difficulty of the game.

To speed up searching, there are ways of pruning the search tree. If you assume that your opponent will always take the winning move if it is available, you can stop searching for an opponent move once there is a winning move available. This may not sound like much but can reduce the search by a surprising amount. 

One of the new and highly effective ways of picking moves is the use of the Monty Carlo Tree Search algorithm. We will not be implementing the full algorithm but will do the starting point and explain the algorithm in the next part.

Making Santa-Tac-Toe part 1 of 4

 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.

Making Knight's Tour Part 4 of 4

 Part 4 of 4: Hamiltonian paths and circuits

When it comes to math, I do wish that I had done more math courses. I do not consider myself a math expert, though I use it all the time and feel it is important to at least understand the concepts. When it comes to Knight’s Tour, graph theory is the mathematical topic of choice for understanding what is going on. A graph is simply a set of vertices (often called nodes by programmers) connected by edges. The game can be represented as a graph with each tile of the board being a vertex and the paths that the knight can take being the edges. The image below shows this.

When travelling through the nodes, the sequence of vertices visited is a walk. If the vertices of the walk are all distinct then you have a path. There is a special path which is made up of all vertices in the graph known as a Hamiltonian path. When you think about it, any solution to the game is a Hamiltonian path.

There is another concept in graph theory called a circuit. The idea here is that you have a path but the last vertex of the path connects to the first vertex of the path to form a cycle. Taken to the extreme, if the circuit visits every vertex once (except the starting vertex) then you have a Hamiltonian circuit. In Knight’s Tour, if the last node in a solution is an L move away from the starting location, then you have a Hamiltonian Circuit. This is a very special solution to the puzzle as you have effectively found two solutions for each tile (going in either direction is fine). Finding a Hamiltonian Circuit is not difficult as you only need to add a constraint to the solver such that it can only take the L leading to the starting location if it is the last move. This will take a very long time as there are many valid solutions that will fail. Once you have found a Hamiltonian circuit, however, creating a solver that will use it is trivial.

Once you know the path, you can simply store that as an array of next tiles.

"hamiltonian": [10,11, 8,18,19,20,12,22,

                25, 3, 4, 5, 2, 7,31,21,

                 1, 0,28,29,14, 6,39,13,

                 9,40,43,42,34,35,15,46,

                17,16,44,45,26,47,23,54,

                57,24,36,37,27,30,63,62,

                33,32,56,61,58,59,60,38,

                41,51,48,49,50,55,52,53]

The solver can then simply look up the next move in the circuit.

class KTHamiltonianSolver extends KTSolver {

    constructor(game) {

        super(game);

    }



    reset() {

        this.game.restartGame();

    }



    nextMove() {

        let curTile = this.game.lastKnightTile;

        let target = KT.hamiltonian[curTile];

        this.game.addKnight(target);

    }



}

This may seem like cheating, and it sort of is, but using a precalculated solution is actually particularly useful for solving larger puzzles. Larger puzzles can be broken down into several smaller puzzles. If you have solutions that start at one edge and another edge, you can chain the puzzles together to solve larger puzzles without incurring the exponential growth that trying to solve the complete puzzle would incur. This is known as divide and conquer.

So, how do the different solvers compare? The table below shows how all four solvers did for each of the possible starting locations. Note that I only went to 10 billion steps. I also used a C++ version of the solvers so they ran much faster. 

Making Knight's Tour part 3 of 4

 Heuristics

When you get right down to it, solving the knights tour is simply a search of really large tree.  The biggest problem is that if you take a wrong path then you end up wasting a large amount of time before you realize your mistake and come back track back up to where a viable solution can exist. The obvious solution to this is not to make bad mistakes, but how do you determine if a choice is a good choice or not? Human brains partially solve this problem by employing what is known as heuristics. The idea here is instead of doing complicated calculations the brain will look for shortcuts that usually, though not always, lead to the correct solution. With NP problems heuristics can be a very good way of solving the problems in a reasonable amount of time if you can find an appropriate heuristic.

Creating a heuristic is not a simple task. Usually several different techniques are tried to find out if any of them work with smaller versions of the problem set. The technique can then be applied to larger problems to see if they still work. Often we will start by looking at several versions of the problem and seeing if there's any pattern that can be found. The easiest way of finding a heuristic is to look at what other people have discovered and using their heuristic, but that requires an existing heuristic to already exist. Knight's tour is very popular with mathematicians so several heuristics have been devloped.

For Knights tour the Warnsdorff's heuristic is the heuristic that dominates. This is a quite simple heuristic. The idea is that for each potential move you look at the number of moves that tile will have once you have moved there and selecting the tile that has the least moves available. As you can see by the figure below, each of the tiles that we can move to has a certain number of moves attached to it, but there is also a tie. There are several approaches that can be taken for dealing with ties, so I went with a clockwise order of searching tiles and taking the clock position as the tie-breaker.

One of the things that continually came up when researching this heuristic was that when there was a tie that would quite often be where the problem with the solution was. This would mean that tide tiles would be a good candidate for a faster backtracking method. For this reason I updated the reset function to also include an indication of whether there was a tie at particular decision tree node. 

reset() {
    for (let i = 0; i < 64; ++i) {
        this.game.tiles[i].step = 0;
        this.game.tiles[i].tiebreaker = false;
    }
}

 The heart of this Huristic is the counting method. This simply looks to see if the tiles currently occupied with the night and if so returns negative one. The negative one is very important as it is possible at the very end of the game that a valid tile will have zero moves as it will be the only tile available to be moved into. We simply count all the possible moves making sure that we do not count the move back to our source tile.

countTargetMoves(target, source) {

    if ((target < 0) || (target >= 64))
        return -1;  // NOTE invalid is -1 not zero as last move will be 0 moves!!!

    if ( ! this.game.tiles[target].checkIfAllowedMove(target, source) )
        return -1;

    if (this.game.tiles[target].moveNumber !== KT.NO_MOVE)
        return -1;

    let moveCount = 0;
    for (let t = 0; t < KT.knightTileOffsets.length; ++t) {
        let knight = target + KT.knightTileOffsets[t];
        if ((knight === source) || (knight < 0) || (knight >= 64))
            continue;

        let knightXAdjust = Math.abs( (knight % 8) - (target % 8) );
        let knightYAdjust = Math.abs( Math.floor(knight / 8) - Math.floor(target / 8) );

        if ( ((knightXAdjust+knightYAdjust) === 3) &&
            (this.game.tiles[knight].moveNumber === KT.NO_MOVE) )
            ++moveCount;
    }
    return moveCount
}

 Sadly, my fast backtrack method was never tested but has been implemented here for reference. I know it was not used for reason that will become clear once the algorithm is ran. The idea behind fast backtracking is that you do not backtrack a single step but backtrack multiple steps to a decision point you know it is faulty. As we know that the tiles that have multiple tile entries are potential problem areas, this is a good point to do a fast backtrack too.

fastBacktrack() {
    let curTileIndex = this.game.lastKnightTile;
    if (curTileIndex === this.game.firstKnightTile) return;
    let curTile = this.game.tiles[curTileIndex];

    this.game.undoMove();
    curTile.step = 0;
    curTile.tiebreaker = false;

    if ( ! this.game.tiles[this.game.lastKnightTile].tiebreaker)
        this.fastBacktrack();

}

 

The next move method seems a lot more complicated than it really is. The big problem that we have is that step is no longer linear as steps may be taken in totally different orders. To get around this problem, we are treating each bit of the step variable as one of the paths that we can take. If the bit is set then we know that path is either not available or has been tried already. To loop over the bits, we simply create a mask variable which we set to 1 to indicate the first bit. The left shift operator, which is represented using <<, is used to shift that one to the appropriate bit position. If the value of step is 255 then we know that all these steps have been tried and can do a backtrack. If moves are still available we simply loop over all the bits and find the lowest count from the moves that are remaining. The lowest move is then the move that we make. As it is simple enough to also do forward checking, we will call the is game still winnable method to do a forward checking step even though this is not required as part of the heuristic.

    nextMove() {
        let curTile = this.game.lastKnightTile;
        let step = this.game.tiles[curTile].step;
        let tiebreaker = this.game.tiles[curTile].tiebreaker;
        if (step === 255) {
//            this.game.undoMove();
//            step = 0;
            return this.fastBacktrack();
        } else {
            let mask = 1;
            let index = 0;
            let lowest = -1;
            let lowestCount = 9;
            let lowestMask = 0;
            while (mask < 256) {
                if ((step & mask) === 0) {
                    let target = curTile + KT.knightTileOffsets[index];
                    let targetMoves = this.countTargetMoves(target, curTile);
//                    console.log(`target ${target} has ${targetMoves}`);
                    if (targetMoves < 0)
                        step |= mask;
                    else if (targetMoves < lowestCount) {
                        lowest = target;
                        lowestCount = targetMoves;
                        lowestMask = mask;
                    } else if (targetMoves === lowestCount) {
                        tiebreaker = true;
                    }
                }
                mask <<= 1;
                ++index;
            }
            if (lowestMask > 0) {
                step |= lowestMask;
                this.game.addKnight(lowest);
                if ( ! this.game.isGameStillWinnable() ) {
                    this.game.undoMove();
//                    console.log("Early backtracking!");
                }
            } else
                console.log("No move found???")
        }
        this.game.tiles[curTile].step = step;
        this.game.tiles[curTile].tiebreaker = tiebreaker;
    } 

Running with this Heuristic proved to be very efficient. as it turns out, the heuristic solver is able to find the solution in 63 steps for all of the possible starting locations. With the performance we are getting using this heuristic we are done, so why is there another solver in the game? My exploration of Knight’s Tour would not be complete without looking at circuits and larger boards.