So recently, I was given a coding assignment to create a Tic-Tac-Toe game, following some parameters. I was given full design freedom, but was tasked with emphasizing good coding structure/organization, algorithm use, and simplicity. There were also three types of strategies to design, including a player who tries to always win, one who always tries to tie, and one who plays randomly. It was a good assignment to test to see how far I’ve developed in these past several months. In retrospect, I think I did a respectable job. I ended up using lots of design patterns I hadn’t used before. It’s hard to say whether I’ve surpassed where I was when I left for law school, but taking my programming seriously has definitely elevated me quickly compared with where I was just a few months ago. In any case, here is a summary of the project with code available on my github (https://github.com/rocketegg/Projects/tree/gh-pages/Tic-Tac-Toe):
TIC-TAC-TOE prompt
1. A short description of how you approached the problem including design tradeoffs and future improvements.
I approached the problem from more of a design angle than for sheer performance. Tic-tac-toe is a simple game, so even though many checking run in O(n^2) and take linear memory, this shouldn’t impede performance from a practical sense. It makes the source code more readable as well. I refrained from programming in a way that would box one in to a simple 3×3 grid. For example, the checks for whether the tic-tac-toe game has a winner could theoretically all be run in constant time since there are at most 8 winning configurations.
Thus, it was my decision to focus more on extensibility so that any part of the program can be improved (as in the real world, based on time and requirement constraints). For example, players can easily be created by implementing the “Player.java” class. Each player has an associated chooseMove() method to implement, which returns a move based on a type of strategy. Following the strategy design pattern, strategies are also easily created and extensible as well. Thus, the win strategy is comprised on several substrategies (not all broken out into classes for simplicity sake) of deciding if there is a winning move to take, a losing move to block, choosing the optimal move, etc.
In this way, future improvements could easily be made by adding strategies and employing them as part of the broader Win/Tie/Random strategies. One rule I did not have time to implement was a rule based on creation of a “fork” or a situation in which two possible winning scenarios are created so that the opponent is guaranteed a loss. Alongside that strategy would be the counterpart strategy of blocking a fork from forming.
2. Working java code with instructions on how to run it.
To run the java code, simply download and build the code and execute the application. The main class instantiates a menu which should be self-explanatory. I focused less on making this menu pretty, however doing so would not be difficult (just time-consuming).
3. A description of the algorithm used including the strengths and weaknesses.
As stated above, the algorithms are simple for the sake of readability. They could be improved in numerous ways. For instance, comparing win states for rows/columns could be done in constant time by doing 8 comparisons each based on a particular win configuration. Alternatively, one could create a string to represent a game board: e.g. “XXO|OXO|OXO” could represent the positions in snaking order. Then arithmetic based on a character array could be done to save memory and computation time. Finally (but not comprehensively), one could implement the algorithm using a depth-first-search algorithm. One thought I had was to implement the algorithm using DFS which would search for each possible win scenario given a board configuration. There wouldn’t be too many since board states in tic-tac-toe are often “forced” by needing to block an opponent’s winning position. A stack would be kept given the moves for the particular win scenario currently being followed by the DFS algorithm. When an opponent moves, the algorithm would recompute the win scenarios and choose another one to follow. I implemented a similar algorithm in my code (also available in my github at https://github.com/rocketegg/Practice/tree/master/src/solver) to solve the “peg jumping” game that is common in many bars.
UPDATE: I’ve since implemented the minimax algorithm as a strategy for solving Tic-Tac-Toe. It was an interesting task, but very hard to debug. The logic is complex (especially with alpha-beta pruning), but it’s extensibility is fantastic. One hiccup I encountered when developing the algorithm was the scoring mechanism. Using just a default -1, 0, and 1 for “O” wins, “Tie game” or “X” wins turned out to be a bad decision (or one that rendered teh minimax strategy nearly useless) because the computer would evaluate a losing strategy that could eventually win (e.g. where the opponent could just immediately win) with the same weight as an immediate win (both have a 1 max value). This turns out to be a common problem with minimax algorithms in general. Thus, I had to tweak the scoring mechanism to take account of the depth of the recursive call. In any case, here is the minimax strategy :
private BestMove chooseMinimaxMove(TicTacToeBoard board, String side) {
int bestScore;
GridCell bestMove = null;
String otherSide = side.equals("X") ? "O" : "X";
if ((bestScore = TicTacToeBoardExaminer.getScore(board, side, depth)) != TicTacToeBoardExaminer.NO_WINNER_YET) {
return new BestMove(null, bestScore);
}
ArrayList<GridCell> possibleMoves = TicTacToeBoardExaminer.getAllOpenMoves(board, side);
if (side.equals("X")) { //Player's turn
bestScore = -11;
} else { //Opponent's turn
bestScore = 11;
}
BestMove b = null;
for (GridCell move : possibleMoves) {
board.update(move);
GridCell undoMove = new GridCell(move.getRow(), move.getCol(), true, " ");
b = chooseMinimaxMove(board, otherSide, depth+1);
board.update(undoMove);
if (side.equals("X")) { //player turn
if (b.getScore() > bestScore) {
bestScore = b.getScore();
bestMove = move;
}
} else if (side.equals("O")){ //opponent turn
if (b.getScore() < bestScore) {
bestScore = b.getScore();
bestMove = move;
}
}
//Simple Pruning
if (bestScore == TicTacToeBoardExaminer.maxWinScore(side)) {
return new BestMove(bestMove, bestScore);
}
}
return new BestMove(bestMove, bestScore);
}
}
/**
* Just a wrapper class to hold a gridcell and a score
* @author Gamer
*
*/
private class BestMove {
private GridCell move;
private int score;
public BestMove(GridCell move, int score) {
this.move = move;
this.score = score;
}
public GridCell getMove() {
return move;
}
public int getScore() {
return score;
}
}
Additionally, as part of the minimax strategy, it’s really important to have a good scoring strategy with well-defined limits. Here is what I implemented:
/**
* Returns a score (if possible) based on a board configuration and
* if you are the side
* Depth n - means that 10 is the max score - if the game is over on the first move
* otherwise, if there is a winning board, subtract the depth because it potentially
* opens up to a loss
* Scores:
* 10 - n: side has won, n is depth
* -10 + n: other side has won, where n is depth
* 0: is tie
* 100: No winner yet
*
* @param board
* @param side
* @return
*/
public static int getScore(TicTacToeBoard board, String side, int depth) {
if (sideHasWon(board, "X"))
return PLAYER_WIN - depth;
else if (sideHasWon(board, "O"))
return OPPONENT_WIN + depth;
else if (board.getAllOpenCells().size() == 0 && side.equals("X"))
return TIE;// - depth;
else if (board.getAllOpenCells().size() == 0 && side.equals("O"))
return TIE;// + depth;
else
return NO_WINNER_YET;
}
4. Any alternate approaches considered.
See above.
5. A test suite that measures that probability of each of the computer based opponents winning when pitted against one another.
I don’t have a fully-fledged test suite, however from the game menu, one can test n-games based on differing players (read: strategies). For example, one can test the win strategy against the tie strategy (i.e. Champ vs Toby) n-number of times. The results for 1000 games range at roughly about 250 games won for Champ, 0 games won for Toby, and the rest tied. One could easily translate this into roughly a 25% win rate when pitted against Toby. When pitted against the random strategy, this win rate creeps to about 90% with a 9% tie rate and about a 1% loss rate. In computing each of these statistics, the player who starts the game is rotated back and forth.
6. Anything else you think would be valuable.
I have extensively documented my source code so that it is easier to read. The main classes that one should look at are the TicTacToeGame class which encapsulates an entire game and the Player and Strategy classes to see how the logic is implemented in the backend. I would be happy to answer any other questions about my approach.
Code and Codes 