I played with your code and there is a little to say
error
First of all, there is a mistake. I don't think your code really works for a 3x3 board. The problem is that you revert move you add to the board. You do this at the end of the newminimax47 method exactly once, even if it moves to the board inside the for loop in the method you add. This means that the method call not only calculates something, but also changes the state of the board, and the rest of the code does not expect it.
So, remove revert where it is now, and as soon as you can:
setX(x); currentScore = newminimax47(x)[0]; revert(x);
it also means you don't need the lastAdded variable.
play
It's much easier to see what happens if you really play against your own algorithm. Add a method to the State class
public void dump() { for (int y = 0; y < n; y++) { for (int x = 0; x < n; x++) { System.out.print(state[y * n + x]); } System.out.println(); } }
and the main thing in you is something like
public void play() { State s=new State(3); Scanner in = new Scanner (System.in); while (s.isGameOver().equals("Not Gameover")) { int[] options = s.getAvailableMoves(); s.dump(); System.out.println ("Your options are " + Arrays.toString(options)); int move = in.nextInt(); s.setX(move); int [] ScoreAndRecommendedMove=new int[2]; ScoreAndRecommendedMove=s.newminimax47(0); System.out.println("Score: "+ScoreAndRecommendedMove[0]+" Position: "+ ScoreAndRecommendedMove[1]); s.setO(ScoreAndRecommendedMove[1]); } s.dump(); }
and you can play against him. On a 3x3 board, this works fine for me. Unfortunately, I calculated that calculating the first move at 4x4 takes about 48 hours on my computer.
data types
Your choice of data types is often a little ... weird. If you want to remember a single character, use char instead of String . If you want to return a yes / no solution, try using boolean . There are also some parts of the program that can be replaced with less code doing the same. But that was not your question, and so on ...
algorithm
So what happened with the minimax solution to this problem? Suppose the first four movements are X5, O8, X6 O7. Another possibility is to start the game with X5, O7, X6, O8. Another one is X6, O7, X5, O8. And finally, X6, O8, X5, O7.
All four of these possibilities for the first four turns of the game lead to the same game match. But minimax does not recognize that they are the same (basically there is no memory of parallel branches), so it will calculate all four of them. And the number of calculations of each state of the board will increase rapidly if you look deeper.
The number of possible games significantly exceeds the number of possible board states. Estimate the number of games: first there are 16 possible moves, then 15, then 14, 13, ... and so on. The rough estimate is 16!, Although minimax will not have to calculate all of them, because many of them will be ready before the 16th move.
Assessment of the number of game states: each square on the board can be either empty, or X, or O. So 3 ^ 16 boards. Not all of them are really valid boards, because the number of Xs on the board can be no more than one, and then the number of Os, but still it is close to 3 ^ 16.
sixteen! possible games are approximately one and a half million times more than 3 ^ 16 possible states of the board. This means that we roughly calculate each board half a million times at a time.
The solution is to start memorizing every game that you figure out. Each time a recursive function is called, first check to see if you know the answer, and if so, just return the old answer. This is a method called memoization .
memorization
I will describe how to add memoization using already created data structures (although I do not agree with them). To perform memoization, you need a collection in which you can quickly add and quickly search. A list (e.g. ArrayList ) will not do us any good. Quickly add values, but search very slowly in long lists. There are several options, but the simplest of them is HashMap . To use the HashMap , you need to create something that represents your state, and you can use it as a key. The easiest way is to simply make a String with all the X / O / - characters that represent your panel.
So add
Map<String,int[]> oldAnswers = new HashMap<String,int[]>();
to your State object.
Then at the beginning of your newminimax47 method newminimax47 create a line that represents the state, and check if we know the answer:
String stateString = ""; for (String field : state) stateString += field; int[] oldAnswer = oldAnswers.get(stateString); if (oldAnswer != null) return oldAnswer;
Finally, when you compute a new answer at the end of newminimax47 , you must not only return it, but also save it on the map:
int[] answer = {bestScore, bestPos}; oldAnswers.put (stateString, answer); return answer;
With a note in place, I was able to play a 4x4 game against your code. The first move is still slow (20 seconds), but after that everything is calculated and very fast. If you want to speed it up, you can learn alpha beta pruning , but the improvement will not be almost the same as a memory. Another option is to use more efficient data types. This will not reduce the theoretical order of your algorithm, but it can still easily make it 5 times faster.