O algoritmo minimax Tic-Tac-Toe não funciona com placas 4x4
Então, eu estou trabalhando neste projeto há 3 semanas. Consegui fazer com que a função minimax funcionasse cedo para uma placa 3x3, no entanto, começaram a surgir problemas quando tentei usá-la para uma placa 4x4, ou seja, erros de espaço na pilha Java. Desde então, com a ajuda da remoção do Alpha beta, consegui reduzir o número de chamadas minimax necessárias dentro da função minimax de aprox. 59000 a 16000 a 11000 e, finalmente, a 8000 chamadas (isso pressupõe uma chamada minimax inicial para uma placa com um slot já preenchido). O problema agora, no entanto, é que o método continua sendo executado em jogos 4x4. Ele simplesmente continua se chamando sem parar, sem erros, sem resultado, nada. Teoricamente, a meu ver, minha função deveria funcionar para tamanhos arbitrários de placas, o único problema era a memória. Agora, desde que reduzi bastante a ganância de memória da minha função, esperava que funcionasse. Bem, isso acontece para o 3x3. No entanto, não é para o 4x4. Uma breve explicação sobre o que a função faz: A função retorna uma matriz de tamanho 2 contendo o próximo movimento mais favorável dentre todos os próximos movimentos possíveis, juntamente com a pontuação que se espera obter com esse movimento. O sistema de pontuação é simples. +10 para uma vitória O, -10 para uma vitória X e 0 para um empate. A função é obviamente recursiva. Dentro dele, você encontrará certos atalhos que reduzem o número de chamadas necessárias para si. Por exemplo, se for a vez de X e a pontuação retornada for -10 (que é a melhor pontuação possível para X), saia do loop, ou seja, pare de observar outros movimentos potenciais desse estado. Aqui está o código para a classe State:
private String [] state; //Actual content of the board
private String turn; //Whose turn it is
private static int n; //Size of the board
public State(int n) {
state = new String[n*n];
for(int i = 0; i < state.length; i++) {
state[i] = "-";
}
State.n = n;
}
public int[] newminimax47(int z) {
int bestScore = (turn == "O") ? +9 : -9; //X is minimizer, O is maximizer
int bestPos = -1;
int currentScore;
int lastAdded = z;
if(isGameOver() != "Not Gameover") {
bestScore= score();
}
else {
int i = 0;
for(int x:getAvailableMoves()) {
if(turn == "X") { //X is minimizer
setX(x);
currentScore = newminimax47(x)[0];
if(i == 0) {
bestScore = currentScore;
bestPos = x;
if(bestScore == -10)
break;
}
else if(currentScore < bestScore) {
bestScore = currentScore;
bestPos = x;
if(bestScore == -10)
break;
}
}
else if(turn == "O") { //O is maximizer
setO(x);
currentScore = newminimax47(x)[0];
if(i == 0) {
bestScore = currentScore;
bestPos = x;
if(bestScore == 10)
break;
}
else if(currentScore > bestScore) {
bestScore = currentScore;
bestPos = x;
if(bestScore == 10)
break;
}
}
i++;
}
}
revert(lastAdded);
return new int [] {bestScore, bestPos};
}
Funções complementares usadas por newminimax47 ():
isGameOver ():
public String isGameOver() {
if(n == 3) {
//Rows 1 to 3
if((state[0] != "-") && (state[0] == state[1]) && (state[1] == state[2]))
return (state[0] == "X") ? "X Won" : "O Won";
else if((state[3] != "-") && (state[3] == state[4]) && (state[4] == state[5]))
return (state[3] == "X") ? "X Won" : "O Won";
else if((state[6] != "-") && (state[6] == state[7]) && (state[7] == state[8]))
return (state[6] == "X") ? "X Won" : "O Won";
//Columns 1 to 3
else if((state[0] != "-")&&(state[0] == state[3]) && (state[3] == state[6]))
return (state[0] == "X") ? "X Won" : "O Won";
else if((state[1] != "-") && (state[1] == state[4]) && (state[4] == state[7]))
return (state[1] == "X") ? "X Won" : "O Won";
else if((state[2] != "-") && (state[2] == state[5]) && (state[5] == state[8]))
return (state[2] == "X") ? "X Won" : "O Won";
//Diagonals
else if((state[0] != "-") && (state[0]==state[4]) && (state[4] == state[8]))
return (state[0] == "X") ? "X Won" : "O Won";
else if((state[6] != "-") && (state[6] == state[4]) && (state[4] == state[2]))
return (state[6] == "X") ? "X Won" : "O Won";
//Checking if draw
else if((state[0] != "-") && (state[1]!="-") && (state[2] != "-") && (state[3]!="-") &&
(state[4] != "-") && (state[5] != "-") && (state[6] != "-") && (state[7] != "-") &&
(state[8] != "-"))
return "Draw";
else
return "Not Gameover";
}
else {
//Rows 1 to 4
if((state[0] != "-") && (state[0] == state[1]) && (state[1] == state[2]) && (state[2] == state[3]))
return (state[0] == "X") ? "X Won" : "O Won";
else if((state[4] != "-") && (state[4] == state[5]) && (state[5]==state[6]) && (state[6] == state[7]))
return (state[4] == "X") ? "X Won" : "O Won";
else if((state[8] != "-") && (state[8] == state[9]) && (state[9]==state[10]) && (state[10] == state[11]))
return (state[8] == "X") ? "X Won" : "O Won";
else if((state[12] != "-") && (state[12] == state[13]) &&(state[13] == state[14]) && (state[14] == state[15]))
return (state[12] == "X") ? "X Won" : "O Won";
//Columns 1 to 4
else if((state[0] != "-") && (state[0] == state[4]) && (state[4] == state[8]) && (state[8] == state[12]))
return (state[0] == "X") ? "X Won" : "O Won";
else if((state[1] != "-") && (state[1] == state[5]) && (state[5] == state[9]) && (state[9] == state[13]))
return (state[1] == "X") ? "X Won" : "O Won";
else if((state[2] != "-") && (state[2] == state[6]) && (state[6] == state[10]) && (state[10] == state[14]))
return (state[2] == "X") ? "X Won" : "O Won";
else if((state[3] != "-") && (state[3] == state[7]) && (state[7] == state[11]) && (state[11] == state[15]))
return (state[3] == "X") ? "X Won" : "O Won";
//Diagonale
else if((state[0] != "-") && (state[0] == state[5]) && (state[5] == state[10]) && (state[10] == state[15]))
return (state[0] == "X") ? "X Won" : "O Won";
else if((state[12] != "-") && (state[12] == state[9]) && (state[9] == state[6]) && (state[6] == state[3]))
return (state[0] == "X") ? "X Won" : "O Won";
//Pruefe ob Gleichstand
else if((state[0] != "-") && (state[1] != "-") && (state[2] != "-") && (state[3]!="-") &&
(state[4] != "-") && (state[5] != "-") && (state[6] != "-") && (state[7] != "-") &&
(state[8] != "-") && (state[9] != "-") && (state[10] != "-") && (state[11] != "-") &&
(state[12] != "-") && (state[13] != "-") && (state[14] != "-") && (state[15] != "-"))
return "Draw";
else
return "Not Gameover";
}
}
Por favor, desculpe a franqueza do método isGameOver (), ele apenas verifica o estado do tabuleiro (ou seja, Win, Draw, Game not Over)
O método getAvailableMoves ():
public int[] getAvailableMoves() {
int count = 0;
int i = 0;
for(int j = 0; j < state.length; j++) {
if(state[j] == "-")
count++;
}
int [] availableSlots = new int[count];
for(int j = 0; j < state.length; j++){
if(state[j] == "-")
availableSlots[i++] = j;
}
return availableSlots;
}
Esse método simplesmente retorna uma matriz int com todos os próximos movimentos disponíveis (em relação ao estado atual) ou retorna uma matriz vazia se nenhuma movimentação estiver disponível ou se o jogo terminar.
O método score ():
public int score() {
if(isGameOver() == "X Won")
return -10;
else if(isGameOver() == "O Won")
return +10;
else
return 0;
}
setO (), setX () e revert ():
public void setX(int i) {
state[i] = "X";
turn = "O";
lastAdded = i;
}
public void setO(int i) {
state[i] = "O";
turn = "X";
lastAdded = i;
}
public void revert(int i) {
state[i] = "-";
if(turn == "X")
turn = "O";
else
turn = "X";
}
Meu método principal fica assim em um jogo 3x3:
public static void main(String args[]) {
State s = new State(3);
int [] ScoreAndRecommendedMove = new int[2];
s.setX(8);
ScoreAndRecommendedMove = s.newminimax47(8);
System.out.println("Score: "+ScoreAndRecommendedMove[0]+" Position: "+ ScoreAndRecommendedMove[1]);
}
Neste jogo, X iniciou o jogo com um movimento na posição 8. O método neste caso retornará
Score: 0 Position: 4
Significa que o movimento mais promissor de O está na posição 4 e, no pior dos casos, produzirá uma pontuação de 0 (ou seja, um empate).
A imagem a seguir tem como objetivo dar uma idéia de como funciona o newminimax47 (). Nesse caso, nosso estado inicial (quadro) recebe o número 1. Nota: Os números indicam a precedência na criação dos estados considerados. 1 foi criado antes de 2, 2 foi criado antes de 3, 3 foi criado antes de 4 e assim por diante.
Nesse cenário, a pontuação e a posição retornadas ao estado 1 serão
Score: 0 Position: 6
vindo do estado 8.
Nota: O código que você vê são apenas trechos da classe State real. Esses trechos por si só devem permitir que você recrie e brinque com a função newminimax47 sem problemas (pelo menos para 3x3). Quaisquer erros que você possa encontrar não são realmente erros, eles simplesmente não foram incluídos nos trechos que eu copiei aqui e o código deve funcionar sem eles. A variável lastAdded nas funções setO e setX, por exemplo, não está incluída nos trechos aqui, mas acabei de perceber que você não precisa dela para poder trabalhar com a função minimax, para que você possa comentar isso.