Je ne suis actuellement pas satisfait de l'IA que je programme. L'IA est censée obtenir le meilleur score pour chaque coup dans un plateau 3x3 (TicTacToe).
Les scores possibles sont -1 (Lose), 0 (Tie) et 1 (Win).
Tout d'abord, la méthode makeTurn () est appelée, qui appelle ensuite la méthode contenant l'algorithme miniMax.
private int calcScore(Button[][] currentBoard, int depth, boolean isMax) { // MiniMax Algorithm, calculating score for each branch via recursive execution
int score;
if (AIcheck.checkWin()) {
return (Util.getInstance().getTurnCounter() % 2) == 0 ? 1 : -1;
} else if (AIcheck.checkTie()) {
return 0;
}
int bestScore = isMax ? Integer.MIN_VALUE : Integer.MAX_VALUE;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (currentBoard[i][j].getText().equals("")) {
if (isMax) {
currentBoard[i][j].setText("O");
} else {
currentBoard[i][j].setText("X");
}
score = calcScore(currentBoard, depth + 1, !isMax);
currentBoard[i][j].setText("");
bestScore = isMax ? Math.max(bestScore, score) : Math.min(bestScore, score);
}
}
}
return bestScore;
}
public void makeTurn(Button[][] currentBoard) { // Calculating best move using miniMax algorithm
AIcheck = new Check(currentBoard);
int bestScore = Integer.MIN_VALUE;
int[] bestMove = new int[2];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (currentBoard[i][j].getText().equals("")) {
currentBoard[i][j].setText("O");
int score = calcScore(currentBoard, 0, false);
System.out.println(score);
currentBoard[i][j].setText("");
if (score > bestScore) {
bestScore = score;
bestMove = new int[]{i, j};
}
}
}
}
Board.getInstance().getField(bestMove[0], bestMove[1]).performClick();
}
I J'utilise isMax pour déterminer si c'est le tour du maximiseur ou non, ainsi que turnCounter% 2 pour déterminer à quel tour du joueur c'est, car ils se relaient.
Pourtant, l'IA n'empêche toujours pas ma victoire, il semble que ça passe simplement d'un champ à l'autre, au lieu de choisir le champ optimal. Comment pourrais-je mettre en œuvre correctement l'algorithme miniMax? Merci beaucoup!
Exemple:
[] | [] | []
[] | [] | []
[X] | [] | []
[O] | [] | []
[] | [] | []
[X] | [] | []
[O] | [] | []
[] | [] | []
[X] | [] | [X]
[O] | [O] | []
[] | [] | []
[X] | [] | [X]
[O] | [O] | [X]
[] | [] | [] p>
[X] | [] | [X]
[O] | [O] | [X]
[O] | [] | []
[X] | [] | [X]
[O] | [O] | [X]
[O] | [X] | [] Je gagne, cela montre aussi comment l'IA semble simplement prendre la prochaine place (de gauche à droite)
[X] | [] | [X]
3 Réponses :
Je pense que le problème est cette ligne dans calcScore()
// this will always evaluate to false
if (currentBoard[i][j].getText().equals("")) {
Vous ne calculez le score que si le tableau est vide, mais vous le définissez toujours à "0" avant d'appeler la fonction, donc le bloc de code pour cela ne sera jamais exécuté.
makeTurn () est similaire, mais je suppose que vous effacez les tableaux entre les tours? Sinon, vous devez également le mettre à jour.
Modifier: dans la fonction principale:
currentBoard[i][j].setText("O");
int score = calcScore(currentBoard, 0, false);
dans calcScore:
if (currentBoard[i][j].getText().equals("")) {
À ma compréhension, l'algorithme prend un tour, (ici: réglez-le sur "O") et calcule ensuite la qualité de cette étape en appelant récursivement l'algorithme miniMax pour chaque tour individuel. De cette façon, il obtient le meilleur tour et si c'est le cas, il annule chaque tour qu'il a pris et prend le meilleur tour calculé précédemment.
Il y a un problème avec votre attribution bestScore . Pour chaque case vide, vous faites ceci:
int bestScore = isMax ? Integer.MIN_VALUE : Integer.MAX_VALUE;
Si vous le calculez comme ceci, vous vous retrouverez toujours avec les mêmes scores, ce qui pourrait être la raison pour laquelle il ne sélectionne que la case vide suivante. Dans un algorithme minimax, vous avez besoin d'un moyen d'attribuer différentes valeurs de score pour chaque mouvement afin que vous puissiez trouver le meilleur mouvement par comparaison. Dans une partie d'échecs ou quelque chose de similaire, ces scores sont généralement donnés à travers des heuristiques. Puisque votre jeu est beaucoup plus simple, cela devrait être plus facile. Une solution simple peut être d'attribuer un score différent à chaque état du plateau et vous pouvez simplement sélectionner les mouvements qui mènent à cet état souhaité. Vous pouvez facilement le faire car le nombre de ces états est très limité dans votre jeu.
Mais est-ce que je n'attribue pas à bestScore une autre valeur plus bas dans la boucle imbriquée pour?
Je pense que le problème est de savoir comment déterminer qui a gagné dans calcScore . Vous utilisez Util.getInstance (). GetTurnCounter () , mais vous ne semblez pas mettre à jour le compteur dans les appels récursifs. Vous pouvez à la place simplement utiliser depth% 2 ou isMax pour cela:
if (AIcheck.checkWin()) {
return isMax ? -1 : 1;
}
C'est utile, merci, mais malheureusement, cela n'a pas résolu le problème dans son ensemble. :(
@ M0e que signifie "ne pas régler le problème dans son ensemble"? Avez-vous toujours pu gagner avec ce changement?
Oui, mais j'ai trouvé l'erreur. L'algorithme en lui-même est correct (comme je le pensais, d'où ma confusion) mais checkWin () était faux et aussi ce que vous avez mentionné. Puisque je n'aurais pas pu le faire sans votre correction, je marquerai votre réponse comme correcte. Merci!