# Minimax implementation of tic tac toe

I have the following working tic tac toe program. Someone said it's a convoluted mess and I'm looking for pointers on how to clean it up.

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Random;
import java.util.Arrays;

public class Shortver{
private static final int boardRowDim = 3;
private static final int boardColDim = 3;
private String[][] board;
private String playerName;
private String playerMark;
private String computerMark;
private boolean humanGoes;
private boolean winner;
private boolean draw;
private int gameTargetScore;
private boolean output = false;
private boolean toSeed = false;
private ArrayList<Integer> availableMoves;

public Shortver(String name, boolean whoGoesFirst){

availableMoves = new ArrayList<Integer>();
board = new String[boardRowDim][boardColDim];

for (int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
board[i][j] = ((Integer)(double2single(i,j))).toString();
}
}
playerName = name;
humanGoes = whoGoesFirst;
playerMark = "X";
computerMark = "O";
gameTargetScore = 15;
if(!humanGoes){
playerMark = "O";
computerMark = "X";
gameTargetScore = - 15;
}
winner = false;
draw = false;
}

public static void main(String[] args)throws Exception{
System.out.println("\u000C");

Scanner kboard = new Scanner(System.in);

String name = kboard.next();
name = capitalize(name);

System.out.print("\n\n          X's go first. " + name + ", please enter your mark ('X' or 'O')");
String mark = kboard.next().toUpperCase();
boolean whoPlaysFirst = (mark.equals("X")) ? true : false;

Shortver myGame = new Shortver(name,whoPlaysFirst);

myGame.playGame(kboard);
}

public void playGame(Scanner kboard)throws Exception{

Integer move = null;
boolean goodMove;
String kboardInput = null;
Scanner input;
int[] cell2D = new int[2];
Random random = new Random();
int nextComputerMove;

if(toSeed){
board = seedBoard();
availableMoves = seedAvailable(board);
int x = 0;
int o = 0;
for(int i = 0; i < 3;i++){
for(int j = 0;j < 3;j++){
if(board[i][j].equals("X"))x++;
else if(board[i][j].equals("O"))o++;

}
}

if((x - o) == 1) humanGoes = true;
else if((x - o) == 0) humanGoes = false;
else{
System.exit(0);
}

System.out.println("humangoes = " + humanGoes + x + o);
}

while(!winner && !draw){
goodMove = false;
drawBoard(board);

if(!humanGoes && availableMoves.size() < 9){
}

if(humanGoes){
while(!goodMove){
kboardInput = kboard.next();
input = new Scanner(kboardInput);
if(input.hasNextInt()){
move = input.nextInt();
if(move == 99){
System.out.println("You found the secret exit code");
System.out.println("bye");
System.exit(0);
}
goodMove = checkMove(move);
if(!goodMove)System.out.println("          WARNING: Incorrect input, try again");
}else{
System.out.println("          WARNING: Incorrect input, try again");
}
}
cell2D = single2Double(move);
board[cell2D[0]][cell2D[1]] = playerMark;

}else{

String[][] currentBoard = new String[boardRowDim][boardColDim];
currentBoard = copyBoard(board);

ArrayList<Integer> currentAvailableMoves= new ArrayList<Integer>();
currentAvailableMoves = copyAvailableMoves(availableMoves);

//System.out.println(System.identityHashCode(currentAvailableMoves));

int[] bestScoreMove = new int[2];

bestScoreMove = findBestMove(currentBoard,currentAvailableMoves,true,0,kboard);

move = availableMoves.get(availableMoves.indexOf(bestScoreMove[1]));

cell2D = single2Double(move);
board[cell2D[0]][cell2D[1]] = computerMark;
}

humanGoes = humanGoes ? false:true;

availableMoves = updateAvailableMoves(move,availableMoves);

if (Math.abs(score(board)) == 15) winner = true;
if (availableMoves.size() == 0) draw = true;

if(winner || draw){
drawBoard(board);
}

if(score(board) == gameTargetScore)System.out.println(playerName + " you are too good for me. \n" +
"Congratulations you won!!\n\n");
else if(score(board) == -gameTargetScore)System.out.println("IWONIWONIWONohboyIWONIWONIWON");
else if(draw)System.out.println("Good game. It's a draw!");

}
}

public void drawBoard(String[][] someBoard){

String mark = " ";
Integer row,col;
String type;

for( int i = 0;i < 15; i++){
System.out.print("          ");
for (int  j = 0; j < 27; j++){

mark = " ";
if(i==5 || i == 10)mark = "-";
if(j==8 || j == 17)mark = "|";

row = i/5;
col = j/9;

type = someBoard[row][col];

if(type == "X"){
if( ((i%5 == 1 || i%5 == 3) &&
(j%9 == 3 || j%9 == 5)) ||
(i%5 == 2 &&
j%9 == 4))mark = "X";
}else if(type == "O"){
if( ((i%5 == 1 || i%5 == 3) &&
(j%9 == 3 || j%9 == 4 || j%9 == 5)) ||
((i%5 == 2) &&
(j%9 == 3 || j%9 == 5))) mark = "O";
}else{
if( i%5 == 2 && j%9 == 4){
mark = ((Integer)(row * 3 + col)).toString();
}
}
System.out.print(mark);
}
System.out.println();
}
System.out.println("\n\n\n");
}

public boolean checkMove(Integer move){

boolean goodMove = false;

for(Integer available : availableMoves){
if (available == move) goodMove = true;
}

return goodMove;
}

public int score(String[][] newBoard){

int row;
int newCol;
int score = 0;
for (int strategy = 0; strategy < 8; strategy++){
score = 0;
for (int col = 0; col < 3; col++){
if(strategy < 3){  //rows
row = strategy ;
newCol = col;
}else if (strategy < 6){ //cols
row = col;
newCol = strategy - 3;
}else{//diag
int diag = strategy - 6;
row = col - 2 * diag * (col - 1);
newCol = col;
}
if(newBoard[row][newCol].equals("X")){
score+=5;
}else if(newBoard[row][newCol].equals("O")){
score+=-5;
}
}
score = (Math.abs(score)== 15) ? score : 0;
if(Math.abs(score) == 15) break;
}

return score;
}

public String[][] copyBoard(String[][] originalBoard){
String[][] duplicateBoard = new String[boardRowDim][boardColDim];
for (int i = 0;i < boardRowDim; i++){
for(int j = 0; j < boardColDim; j++){
duplicateBoard[i][j] = originalBoard[i][j];
}
}
return duplicateBoard;
}

public String[][] updateBoard(Integer move, String mark, String[][]oldBoard){
String[][] currentBoard = new String[boardRowDim][boardColDim];
int[] cell2D = new int[2];

currentBoard = copyBoard(oldBoard);
cell2D = single2Double(move);
currentBoard[cell2D[0]][cell2D[1]] = mark;

return currentBoard;
}

public ArrayList<Integer> copyAvailableMoves(ArrayList<Integer> originalAvailableMoves){
ArrayList<Integer> duplicateAvailableMoves = new ArrayList<Integer>();
for(int i = 0; i < originalAvailableMoves.size();i++){
}
return duplicateAvailableMoves;
}

public ArrayList<Integer> updateAvailableMoves(Integer move, ArrayList<Integer> oldAvailableMoves){
ArrayList<Integer> currentAvailableMoves = new ArrayList<Integer>();
currentAvailableMoves = copyAvailableMoves(oldAvailableMoves);
currentAvailableMoves.remove(move);
return currentAvailableMoves;

}
public String[][] seedBoard(){
String[][] sampleBoard ={{"0","O","X"},{"X","4","O"},{"6","7","X"}};
//String[][] sampleBoard ={{"X","O","O"},{"3","4","X"},{"6","7","8"}};
return sampleBoard;
}

public ArrayList<Integer> seedAvailable(String[][] seedBoard){
ArrayList seedMoves = new ArrayList<Integer>();
int index = -1;
for(int i = 0; i < 3;i++){
for (int j = 0; j < 3; j++){
if(!seedBoard[i][j].equals("X") && !seedBoard[i][j].equals("O")){
index = i*3 + j;
}
}
}

return seedMoves;

}

public int[] findBestMove(String[][] currentBoard, ArrayList<Integer> currentAvailableMoves,boolean currentComputerMoves,int depth,Scanner kboard){
ArrayList<Integer> simulateAvailableMoves = new ArrayList<Integer>();
String[][] simulateBoard = new String[boardRowDim][boardColDim];

int[] scoreMove = new int[2]; //return array with score and associated move
int[] cell2D = new int[2];        //array holding i and j of board to place Mark (X or O)
int computerTargetScore = (computerMark.equals("X")) ? 15:-15;

int[][] scoreMoveAvailable = new int[currentAvailableMoves.size()][2];
Integer simulateMove = null; //current move inside loop

Boolean simulateComputerMoves = null;

for(int  i  = 0; i < currentAvailableMoves.size(); i++){
scoreMoveAvailable[i][0] = 0; //score
scoreMoveAvailable[i][1] = -1; // square 0 - 8
}

for (int i = 0; i <  currentAvailableMoves.size() ;i++){

simulateAvailableMoves = copyAvailableMoves(currentAvailableMoves);
simulateBoard = copyBoard(currentBoard);
simulateComputerMoves = currentComputerMoves;

simulateMove = simulateAvailableMoves.get(i);

simulateAvailableMoves = updateAvailableMoves(simulateMove,simulateAvailableMoves);
cell2D = single2Double(simulateMove);

if(simulateComputerMoves){

simulateBoard[cell2D[0]][cell2D[1]] = computerMark;

simulateComputerMoves = false;

if(score(simulateBoard) ==  computerTargetScore || simulateAvailableMoves.size() == 0){
scoreMove[0] = score(simulateBoard);
scoreMove[1] = simulateMove;

}else{
depth++;

scoreMove = findBestMove(simulateBoard,simulateAvailableMoves,simulateComputerMoves,depth,kboard);
}
}else{

simulateBoard[cell2D[0]][cell2D[1]] = playerMark;

simulateComputerMoves = true;

if(score(simulateBoard) == (-computerTargetScore) || simulateAvailableMoves.size() == 0){
scoreMove[0] = score(simulateBoard);
scoreMove[1] = simulateMove;

}else{
depth++;

scoreMove = findBestMove(simulateBoard,simulateAvailableMoves,simulateComputerMoves,depth,kboard);

}
}

scoreMoveAvailable[i][0] =  scoreMove[0] ;
scoreMoveAvailable[i][1] =  simulateMove;

}

int[] bestScoreMove = new int[2];
bestScoreMove[0] = scoreMoveAvailable[0][0];  //set bestScoreMove to first element in arraylist
bestScoreMove[1] = scoreMoveAvailable[0][1];

if( (currentComputerMoves && computerMark.equals("X") ) || (!currentComputerMoves && computerMark.equals("O") ) ) {

for (int i = 0; i < scoreMoveAvailable.length;i++){
if(scoreMoveAvailable[i][0]  > bestScoreMove[0]){
bestScoreMove[0] = scoreMoveAvailable[i][0] ;
bestScoreMove[1] = scoreMoveAvailable[i][1];
}

}
}else{

for (int i = 0; i < scoreMoveAvailable.length;i++){
if(scoreMoveAvailable[i][0]  < bestScoreMove[0]){
bestScoreMove[0] = scoreMoveAvailable[i][0] ;
bestScoreMove[1] = scoreMoveAvailable[i][1];
}

}

}

return bestScoreMove;

}

/*
* just some static methods to help make things easy
*/

System.out.println("u000C          Welcome to TicTacToe\n" +
"        where you can match wits\n" +
"          against the computer\n" +
"(the real challenge is making it a draw)\n");
}

/*
* the next 2 methods convert the index of a double array to a single array
* and the index of a single array to a double array
*/
public static int double2single(int row, int col){
int singleCell = 0;
singleCell = boardRowDim * row + col;
return singleCell;
}

public static int[] single2Double(int cell){
int[] cell2D = new int[2];

cell2D[0] = cell / boardColDim;
cell2D[1] = cell % boardColDim;

return cell2D;
}

public static String capitalize(String word){
word = word.substring(0,1).toUpperCase() + word.substring(1);
return word;
}

}

• I wrote this for my high school class where we are using blueJ. I can use eclipse too – DCR Jun 5 at 21:17
• Well, I've done some stuff in SAS, html, css, javascript, c, and php but I'm not really an expert at any of them – DCR Jun 5 at 21:20
• It's visible in the code that you implemted something else before :-) That's why I ask. – Thomas Weller Jun 5 at 21:21
• I hope that's a good thing. I did the CS50 edX course from Harvard a few years ago – DCR Jun 5 at 21:22

Sorry, but that someone is probably right. At the same time, thanks for being thus brave and asking on how to improve here.

It's not so simple to give feedback in such a scenario, since there are so many details that go "wrong". Since you tagged this for beginner, I'll focus on things that will benefit you most as well as things you can easily adapt. You might want to apply some of these to see how your code becomes more and more readable.

### Designing

When thinking about the software (don't forget to do that before coding), write down some sentences in prose English that describe the game. Let me give an example:

TicTacToe is a game played by two players. They play on a square 3x3 sized board. In an alternating manner, player 1 puts an X onto a cell and player 2 puts an O onto a cell. Only one sign is allowed per cell. The game ends when the first player has 3 contiguous of his own signs in any direction (horizontal, vertical, diagonal)

Find the subjects in these sentences. Each one is a candidate for a class. We have Game, Player, Board, Cell, Sign, Direction.

Next, find out what each of these could be doing (methods) and what data it needs to do that (members). Game might hold the rules, e.g. alternating the players and ending the game. Player could have the name of the player and the sign and perhaps a statistic of wins versus looses. Board might not do a lot, but it needs to hold the data (empty cells, full cells, size). Sign is just X or O - perhaps not enough to recitify a class. Direction could hold masks for all 8 ways to get a win.

It'll be a long way to go from the current code to 4 classes. This really is a hint for your next project or a complete rewrite.

### IDE

Use a real IDE. It's clearly visible that your IDE (BlueJ) did not help you write good code.

A good IDE will give you hints about

• unused variables
• unnecessary imports
• typos
• redundant initializers
• simplification of boolean expressions
• invalid String comparisons
• prefer primitive types
• move assignments to declaration
• join declaration and assignment
• replace for loops by foreach loops

I'll not go into details with any of these, because it's usually not necessary to do a review on those, because the IDE does the review for me (or you).

You can learn a lot from the hints of the IDE alone. And it will make review easier for us.

In this review, I'll tell you a bit about IntelliJ.

### Size of the class

Your code has 450 lines. Some people would say it's ok and fits the rule of 30. Others, including me, would like to see classes with about 200 lines. Assuming that this code would split up evenly with the 4 classes mentioned in the designing chapter, that's ~ 110 lines each. That would be great!

Why does size matter? If a method is very long, it does probably more than one thing. If a class is too big, it likely has too many reasons for change.

One file (which is one class in Java) is often the smalles unit a developer needs to read in order to understand something. Reading and understanding 450 lines is a lot and I'd better not be interrupted during that time.

What can easily be separated here?

A Main class which only contains the main() method. Some call it Application or Program. You could also name it TicTacToe. That main() method will wire up all other parts, so it does integration work.

How would you do that? Don't do it manually. Assuming IntelliJ as the IDE, right click the main method and choose Refactor / Move. Then enter Main as the class name and ignore the fact that it's red. The class will be created when you click Refactor.

The method drawBoard() seems to do drawing only. You could move it to a Board class.

The method capitalize() is used in main() only. It can be moved to the Main class.

Applying all the IDE suggestions will reveal dead code at this point:

boolean toSeed = false;
if(toSeed){
...
}


You can get rid of 22 lines (5%) immediately.

How would you do that? Don't do it manually. Click on the condition. Press Alt+Enter to access the quick tip light bulb. Choose Remove if statement.

You'll then find that updateBoard() and seedBoard() and seedAvailable() are unused. Similar, use Remove unused method. Again 30 lines (6%) less reading.

Also: delete all commented code without thinking.

### Naming

What is Shortver? Is that in contrast to Longver?

Do you see how class names TicTacToe, Game, Player and Board tell me so much more about what the program is about in comparison to Shortver?

Example: at what time do I figure out what the code is about? In line 440, the code mentions the term "TicTacToe" for the first time. Usually people read top to bottom, so that's very late.

How would you rename that? Don't do it manually. Right click the class name Shortver, choose Refactor / Rename and give it at least a slightly better name, following the 6 steps of naming.

### Too many empty lines

Use empty lines for separating things. Using empty lines you can create paragraphs. Paragraphs will help the reader understand what code belongs together and where something new starts.

Like

/*
* just some static methods to help make things easy
*/


Hopefully every method in your code does something useful and makes things easier.

### Size of methods

You can reduce the size of methods by extracting smaller methods. Example:

if(score(board) == gameTargetScore) {
System.out.println(playerName + " you are too good for me. \n" +
"Congratulations you won!!\n\n");
} else if(score(board) == -gameTargetScore) {
System.out.println("IWONIWONIWONohboyIWONIWONIWON");
} else if(draw) {
System.out.println("Good game. It's a draw!");
}


That would make an excellent method printGameEndMessage().

How would you do that? Don't do it manually. Mark all of these lines, right click, choose Refactor / Extract / Method.

Another example:

        if(humanGoes){
...
}else{
...
}


The code inside the if block would make up a method humanMove() and the code in the else block goes into computerMove().

That way, you end up with a short 30 line method playGame().

### Bugs

In drawBoard(), you're doing string comparison with the == operator. IMHO this only accidentally works due to string interning. The correct way is to use .equals().

To me that was an indicator that you might have been a on Java and you have probably worked with a language before that allowed string comparisons with ==. (I asked both questions in the comments)

### Magic numbers

When we find numbers in code that don't have a name, we call them "magic numbers", because they don't have an explanation.

If the number 3.14 is in your code without the name pi, do you know that should be pi or it's just 3.14000?

One of these methods is drawBoard(). All that i and j and numbers... Which one is a column, which one is a line? But then there is row and col, argh ...!

Rename i to consoleRow, j to colsoleColumn, row to boardRow, col to boardColumn.

Change 15 to 3*5. Change 27 to 3*9. This will make it more clear that we still have a 3*3 board. Change 10 to 2*5. Change 8 to 9-1. Change 17 to 2*9-1.

That way you have less different numbers and it's easier to guess their meaning.

### Conclusion

After about 2 hour of working on your code, I slowly begin to understand what it does.

I reduced from 460 lines of code to 28 + 53 + 275 = 357 lines (in 3 classes).

At this point I would need a few more advanced changes, since I need to remove duplicate code. I still don't understand the 80 lines method findBestMove().

So, that's pretty bad for a simple game like TicTacToe - but hey, I probably wrote worse code when I was your age. Nothing to worry about. Keep on learning. Keep on asking. Embrace feedback. Do pair programming.

• Thomas, this was really helpful, thank you. I will rewrite and repost, – DCR Jun 6 at 14:16