RAE-Tic Tac Toe

• Download RAE-TicTacToe.zip - 1 MB

Introduction

It was developed with Visual Studio 2012, it will work with the Express version too. It uses the .NET Framework in the version 3.5. It runs on Windows XP or higher. I used C# and WPF.

The goal from Tic Tac To is get three markers of the own color in a line: vertical, horizontal or diagonal. The player with the white color makes the first move.

I first thought about creating a search tree for the moves and using the Min-Max algorithm. There are a lot of implementations from Tic Tac Toe but I didn't look at them and created my own solution. I found that's enough to just select the best move for the player and computer by classifying each move. The computer should be unbeatable.

The Game class contains the game logic, and the Board which is a 3x3 Array of FieldValue. The Rank enum contains the levels for ranking.

public enum FieldValue { blank = 0, white, black
                    , nextMove      // To display the computed move while visualizing a test;
};
public enum Rank {
    wins=6,
    blocksWin=5,
    winsOnNextMove=4,
    canWinOnNextMove=3,
    canWinInTwoMoves=2,
    winNotPossible=1,
    undefined=0
}
class Game {
    public FieldValue[,] Board = new FieldValue[3, 3];
...}    

The Move command of Game iterates about all cells in the Board and returns the Move with the highest ranking.

public class Move {
public int X, Y;
public FieldValue Color;
public Rank RankI;
 ...}
public Move Move(FieldValue fv, ref Move maxMove) {
    if (fv == FieldValue.blank) throw new ArgumentOutOfRangeException(MethodBase.GetCurrentMethod().Name);
    maxMove = null;
    Move currentMove = null;
    for (int y = 0; y <= Board.GetUpperBound(0); y++) {
        for (int x = 0; x <= Board.GetUpperBound(1); x++) {
            currentMove = RankMove(x, y, fv);
            if (currentMove != null && currentMove.RankI > 
                (maxMove == null ? Rank.undefined : maxMove.RankI))
                maxMove = currentMove;
        }
    }
    return maxMove;
}     

RankMove moves from the current cell in all directions and fills the corresponding DirectionMove.

class DirectionMove: Move {
public int SequenceLength;
public bool CanExpand;
public DirectionMove(int x, int y, FieldValue color, int sequenceLength, bool canExpand)
    : base(x, y, color, Rank.undefined) {
    SequenceLength = sequenceLength;
    CanExpand = canExpand;
}
private DirectionMove moveLeft(int x, int y, FieldValue fv) {
    if (fv == FieldValue.blank) throw new ArgumentOutOfRangeException(MethodBase.GetCurrentMethod().Name);
    int hits = 0;
    bool canExpand = false;
    int i = 0;
    for (i = x-1; i >= 0; i--) {
        if (Board[y,i] == fv) {
            hits++;
        } else {
            break;
        }
    }
    if (HasColor(i, y, FieldValue.blank)) {
        canExpand = true;
    }
    return new DirectionMove(x, y, fv, hits, canExpand);
}

private DirectionMove moveRight(int x, int y, FieldValue fv) {
    if (fv == FieldValue.blank) throw new ArgumentOutOfRangeException(MethodBase.GetCurrentMethod().Name);
    int hits = 0;
    bool canExpand = false;
    int i = 0;
    for (i = x + 1; i <= 2; i++) {
        if (Board[y,i] == fv)
            hits++;
        else break;
    }
    if (HasColor(i, y, FieldValue.blank)) {
        canExpand = true;
    }
    return new DirectionMove(x, y, fv, hits, canExpand);
}       

In SequenceLength, it collects how many cells of the own color are found in the direction of the DirectionMove. Additionally, it collects in canExpand if it can expand in this direction.

In RankMove, the SequenceLength of opposite directions are summed up and accumulated in ExpandForSequenceLength. blankBlankNeighbours is used to determine when you have a sequence length of 1: if you can reach the goal of three markers in one direction.

public Move RankMove(int x, int y, FieldValue fv){
    if (Board[y, x] != FieldValue.blank) return null;
    int[] ExpandForSequenceLength = new int[3] { 0,0,0};
    
    DirectionMove first = moveLeft(x, y, fv);
    DirectionMove second = moveRight(x, y, fv);
    if (first.SequenceLength + second.SequenceLength == 2) 
    { // If we have a sequence of 3 CanExpand doesn't matter
        ExpandForSequenceLength[first.SequenceLength + second.SequenceLength] 
        += Math.Max(1,(first.CanExpand ? 1 : 0) + (second.CanExpand ? 1 : 0));
    }else{
    ExpandForSequenceLength[first.SequenceLength + second.SequenceLength] 
    += (first.CanExpand ? 1 : 0) + (second.CanExpand ? 1 : 0);
    }
  ...
    int blankBlankNeighbours = BlankBlankNeighbours(x, y);
    int sequenceLength = 0;
    if (ExpandForSequenceLength[2] > 0) {
        sequenceLength = 2;
    } else if (ExpandForSequenceLength[1] > 0) {
        sequenceLength = 1;
    }
    Rank rank = Classify(sequenceLength + 1, ExpandForSequenceLength[sequenceLength], blankBlankNeighbours);
    return new Move(x, y, fv, rank);
}        

The public entry point to make a Move is the Game method public Move Move(FieldValue fv) which the GUI calls relaying over the Controller.The routine decides if the Move of the computer or player should be returned as next Move. If the player can finish on the next Move, it sets the Rank blocksWin. In Classify, the Move gets a rank by a simple classification.

public Move Move(FieldValue fv) {
    Move res = null;
    if (fv == OwnColor) {
        Move ownMove = Move(fv, ref MaxOwnMove);
        Move playerMove = Move((fv == FieldValue.white) ? FieldValue.black : FieldValue.white, ref MaxPlayerMove);
        if (ownMove.RankI >= playerMove.RankI) {
            res = ownMove;
        } else {
            res = playerMove;
            res.Color = OwnColor;
            if (playerMove.RankI == Rank.wins) {
                res.RankI = Rank.blocksWin;
            }
        }
        // Move to center is fine
        if (Board[1, 1] == FieldValue.blank) {
            if (res.RankI <= Rank.canWinOnNextMove) {
                res = new Move(1, 1, OwnColor);
            }
        }
    } else throw new ApplicationException("Move can only be called with the color for the computer");
    return res;
    
private Rank Classify(int sequenceLength, int canExpand,  int blankBlankNeighbours) {
   if (sequenceLength <= 0) throw new ArgumentOutOfRangeException(MethodBase.GetCurrentMethod().Name);
   if (sequenceLength >= 3) return Rank.wins;
   if (sequenceLength >= 2 && canExpand >= 2) return Rank.winsOnNextMove;
   if (canExpand == 0) return Rank.winNotPossible;
   if (sequenceLength >= 2 && canExpand >= 1) return Rank.canWinOnNextMove;
   return Rank.winNotPossible;
}    

Test

 class Tests {
    public Game TestResult = null;
    public Move MoveResult;
    [Test]
    public void TryThree_Horizontal() {
        Game game = new Game();
        game.Board[0, 0] = game.PlayerColor;
        game.Board[0, 1] = game.PlayerColor;
        game.Board[2, 1] = game.PlayerColor;
        game.Board[1, 0] = game.OwnColor;
        game.Board[1, 1] = game.OwnColor;
        
        Move move = game.Move(game.OwnColor);
        game.Board[move.Y, move.X] = FieldValue.nextMove;
        TestResult = game;
        MoveResult = move;
        Assert.AreEqual(new Move(2, 1, game.OwnColor), move);
    }
    ...
    [Test]
    public void WinsOnNextMove_CornerVerticalAndHorizontal() {
        Game game = new Game();
        game.Board[1, 0] = game.PlayerColor;
        game.Board[1, 1] = game.PlayerColor;
        game.Board[2, 1] = game.PlayerColor;
        game.Board[1, 2] = game.OwnColor;
        game.Board[0, 1] = game.OwnColor;
        
        Move move = game.Move(game.OwnColor);
        game.Board[move.Y, move.X] = FieldValue.nextMove;
        TestResult = game;
        MoveResult = move;
        Assert.AreEqual(Rank.winsOnNextMove, move.RankI);
        Assert.AreEqual(new Move(2, 0, game.OwnColor), move);
    }

The tests should be easy to read. TestResult and MoveResult are set for displaying the Test. The ShowTests method of the Controller class uses reflection to invoke and display the tests.