Tic_Tac_Toe_against the computer Using MiniMax algorithm when the computer's turn with 4*4 board it's not playing as well?

Question

I'm building a tic_tac_toe (board) game against AI computer player in java, i wrote a MiniMax algorithm for the computer. the width of the board can change like 3*3 OR 4*4. and

when i run the game with 3*3 board the computer player working very well, but when i tried 4*4 board, the computer player doesn't work it's just taking a lot of time in his turn and then nothing just waiting until i stop the game. And here is a screen shoot what's happening.

and here is the MiniMax algorithm that i wrote:

private Pair<Integer, State> maxMove(State b) {
        if(b.isWin('X') || b.isFinished())
            return new Pair<>(b.eval('X'), b);
        else{
            int max = -222, temp;
            Pair<Integer, State> p = null;
            for (State s : b.allNextMoves('O')){
                temp = minMove(s).getKey();
                if (temp > max){
                    max = temp;
                    p = new Pair<>(s.eval('X'), s);
                }
            }
            return p;
        }
    } 


private Pair<Integer, State> minMove(State b) {
        if(b.isWin('O') || b.isFinished())
            return new Pair<>(b.eval('O'), b);
        else{
            int min = 222, temp;
            Pair<Integer, State> p = null;
            for (State s : b.allNextMoves('X')){
                temp = maxMove(s).getKey();
                if (temp < min){
                    min = temp;
                    p = new Pair<>(s.eval('O'), s);
                }
            }
            return p;
        }
    }

And the eval function is to evaluate the grid, i just make it sample to follow, and here is the func :

 public int eval(char player) {
  if (isWin(player))
            return -1;
        else
            return 0;
    }

any one knows why that's happening?

Edit

the allNextMoves(char c) function will take this board and try to find all possible moves for this board by find the first empty char in the board and put the 'X' or 'O' it depends on the player's turn,and return the list of new boards, and here is the code.

public List<State> allNextMoves(char player) {
        List<State> nextBoards = new LinkedList<>();
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < width; j++) {
                if (board[i][j] == ' ') {
                    State nextBoard = new State(this);
                    nextBoard.play(i, j, player);
                    nextBoards.add(nextBoard);
                }
            }
        }
        return nextBoards;
    }

Answer 1

The reason that the minimax algorithm does not respond is that with a 4x4 grid the number of boards to visit is much, much greater.

First, I see that your algorithm will continue the search until there is a win or a draw, meaning that lots of search paths will fill the board completely. After your first move, there are 15 turns left, where for each turn there are respectively 15, 14, 13, ... 1 alternative moves to choose from. So there are close to 15! board states to visit. It is a bit less because of the (unforced) wins that will be found, but still, 15! is a good rough estimation of the size.

In a 3x3 board, that number is only 8!

Compare the two numbers:

 8! =            40 230  
15! = 1 307 674 368 000

So the search in a 4x4 board will take about 30 million times more time than in a 3x3 board.

How to solve?

Several measures can be taken, and they can be combined. This is not a complete list, but a list of things I would work on, in that order:

1. Limit the search depth

You need to stop the search when the search depth is getting too large. There are several ways on how to decide when to stop:

• at a fixed, predefined search depth
• when a minimum, fixed search depth is reached, and when the current state is "quiet", i.e. there are no direct threats to win.

Evaluation function

When you limit the search, you need an evaluation function that will give a value of a state without searching deeper. This will be some heuristic value. For instance, it could count the number of lines that a player could still win on (if the opponent would not play well) and offset it against the same number from the opponents view.

2. Use lookup table

The same board state can be reached via different move-paths. For instance, if both players exchange their first move with their second move, you get to the same board state.

Also, several states map to each other by mirroring along the X, Y or diagonal axes.

By maintaining a hashtable of previously evaluated states, which also manage mirroring aspects, you can avoid doing a search, that essentially is duplicate.

3. Alpha Beta pruning

The pruning done by an alpha-beta algorithm will not affect the result. It gives the same result as a minimax algorithm.

4. Perform best moves first

In the extreme case, the current board may be one move away from a win, but if it is the last move that is considered, a lot of time is lost searching out the other moves. So, if you can first order the moves in such a way the that most promising moves are done first, you will gain time: the alpha beta pruning will then be much more effective.

You can rank moves by whether they are on a line occupied with "many" opponent pieces, or when that doesn't make a distinction, deal with center and corner moves first, as they can partake in more solutions than border moves.

5. Killer moves

If after a certain move you find that a reply is a life-saver, or a key-move towards a forced win, then it might pay off to try that same reply first when instead of the initial move an alternative move is played.