Minimax method for Tic Tac Toe

Question

I have this program for minimax tic tac toe

import java.io.*;
import java.util.*;
public class TicTacToe implements Serializable {
    String state; //State of the board such as 1, 2, 3, 4, 12, 13, etc.
    Integer score; //Score for that state
    static ArrayList <TicTacToe> States; //AllCombinations
    static final long serialVersionUID = -5036364614491205547l; 
    static String board = "41532"; //Represents the state of the board, in this case, first player put his piece in fourth spot, then second at first, etc. 
    public static void minimax (int start, int end, int start1, int end1, int operation) { //Start and end is where a specific size state can be found, I have comments in the bottom. For example 0-8 is only states with size 1, 81-584 is size 3.
        
        ArrayList <Integer> scores = new ArrayList <> ();
        for (int i = start; i <= end; i++) { //Start looking in array list where only a specific size state exists
             if(States.get(i).state.substring(0, board.length()).equals(board) && States.get(i).score == null) {  //Check if that state has the board state in its current state and if it has score
                 for (int j = start1; j <= end1; j++) { //Check one size higher state 
                    if(States.get(j).state.substring(0, States.get(j).state.length() - 1).equals(States.get(i).state)) { //If it also has the board state, add the score to a list
                        scores.add(States.get(j).score);
                    }
                 }
             }
            if(!scores.isEmpty()) {
                if(operation == 0) {
                    States.get(i).score = Collections.max(scores); //Get max
                } else {
                    States.get(i).score = Collections.min(scores); //Get min
                }
                scores.clear();
            }
        }
    }
    public static void main (String [] args) throws IOException {
        try {
            FileInputStream readData = new FileInputStream("States.txt");
            ObjectInputStream readStream = new ObjectInputStream(readData);

            States = (ArrayList<TicTacToe>) readStream.readObject(); //Get states and size from file
            readStream.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
        minimax(221625, 421191, 421192, 549063, 0); //So for example, I am going through all states of size 8 and using the minimax method, I am assigning scores based on scores of a state that's size 9, a terminal state
        minimax(73449, 221624, 221625, 421191, 1); //Then size 7 scores from size 8
    }
}
//0-8 Size one states
//9-80 Size two states
//81-584
//585-3608
//3609-18728
//18729-73448
//73449-221624
//221625-421191
//421192-549063 Size nine states

So basically this is my implementation of a minimax method, it starts from terminal states that are size nine and assigns it to states that are size eight if they don't have a score already. Then from score eight to seven. I had a different method but they are both slow when the board is empty. I need it to be far quicker, any suggestions or better data structures. The file it reads it from has states in ascending order so like 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, etc.

Answer 1

Here are some comments on various aspects of your program.

Readability

The structure of your code makes it difficult to understand. Let me point out a few aspects:

• Instead of well-formatted Javadoc documentation comments, you often write very long comment lines, by far exceeding typical screen widths.

• You don't follow Java Naming Conventions, e.g. States looks like a class name (starts with uppercase), but is a field.

• The operation parameter can only be 0 or 1, and doesn't stand for something you want to do calculations with. So instead of an integer, make it an enum with cases MIN and MAX. Then you no longer need to remember which value stands for the MIN operation, 0 or 1.

• Your indentation looks like done manually (and you did that quite well!), but any modern IDE or Java-enabled editor can do that automatically for you.

• state.substring(0, board.length()).equals(board) can be replaced by state.startsWith(board), improving both readability and speed.

Data Structures

States

You have a linear static ArrayList <TicTacToe> States; list. You know that this list is subdivided into parts, by the size. In your code, you have to remember "magic numbers", where in your list one size begins and ends. You could better use a two-dimensional list, as in List<List<TicTacToe>> where the first (outer) index denotes the size, and the second one counts through the TicTacToes with this size.

String state

You chose to represent a state as a String growing step by step, adding a digit for the location where a player placed his mark. If you see a tic-tac-toe board, you can't know (and you don't care) how the players arrived at that situation. So, your "state" isn't really a state, but the path how the players arrived at that state, meaning that a single board situation is repeated many times in your States list.

Changing that would mean to more or less start over with a completely new program. I don't know if you are willing to do that.

Relationship between states

You need to know which state is a successor of a smaller-sized state. For this, you do a linear search through all states with the correct size (your for (int j = start1; j <= end1; j++) loop). For any given state, there cannot be more successors than it has free locations, so e.g. a size-8 state only has one successor, but your loop searches some 120000 states, wasting a lot of time.

Various approaches could improve that:

• Create a states data structure that explicitly lists the successor states with every given state.

• Instead of reading a list of all states from a file, construct the states as needed, e.g. by having a constructSuccessors() method inside the TicTacToe class that constructs exactly the handful of states that can follow after this one.

Design

Design your program before you start coding it. Have clear idea (a "contract") in mind (or better: written down) what you want a part of your program to do before you start writing that piece of code. This contract should be specific enough that you can decide the code's correctness based on the contract.

Example

You introduce a minimax() method. What do you want it to do?

• Compute some value? That should become its return value.
• Change some data? That's what your implementation does, it sets the score fields of some TicTacToe states found in the States static field. A contract needs to be more specific than that:
  • Which states get new scores? All states having one size? A specific, give state? I'll assume it is "all states having one size".
  • How do you define the correct new score? This seems to be the min or max of its successor's scores.

What should I supply to the method?

• As I want it to set the scores of all states with one size, I need to somehow supply the size, and the most direct way would be to have a size method parameter. Then, for the given States data structure, it would become the method's responsibility to translate that to the start and end indices needed.

• The minimax method can be asked to either set a score as either the minimum or the maximum of its successor's scores. So it should get a parameter deciding that, like your operation parameter. As I said, I'd only change that from int to an enum.

Performance

The typical performance advice is:

• Develop your program for maximum readability.
• Check whether you have a performance problem (you did that, and stated that you have a problem).
• Use a profiler to find out where your program spends its time ("hot spot").
• Either find a local optimization for the hot spot or a different algorithm.
• Check whether the change improved the performance.