tic tac toe en utilisant alpha beta prunning en Java

Question

Je suis en train de jouer au tic tac toe en utilisant itératif Alpha-Beta prunning, J'ai une seconde limite pour un mouvement, mais pour une raison quelconque, il ne fonctionne pas bien.

I modifié le code alpha-bêta régulière donc au lieu de retourner alpha ou bêta, elle retourne un état (ce qui est la carte avec le prochain mouvement)

Chaque fois que je crée les enfants mettre à jour leur profondeur.

Mais encore une fois pour une raison quelconque, je continue à perdre et je vois que mon alpha beta ne voit pas le meilleur coup à faire.

Voici mon code:

La boucle extérieure:

while (watch.get_ElapsedMilliseconds() < 900 && d <= board.length * board[0].length - 1) 
     { 
      s = maxiMin(beginSt, d, watch); 
      if (s.getNextMove().getIsWin() == true) 
      { 
       break; 
      } 
      d++; 
     } 
     return new location(s.getNextMove().getRow(), s.getNextMove().getCol()); 

La version bêta alpha:

public State maxiMin(State s, int depth, Stopwatch timer) 
    { 
     if (s.getDepth() == 7) 
     { 
      Console.WriteLine(); 
     } 
     if (timer.get_ElapsedMilliseconds() > 850 || s.getDepth() == depth || goalTest(s.getBoard()) != 0) 
     { 
      s.evaluationFunc(line_length, PlayerShape); 
      s.setAlpha(s.getEvaluation()); 
      s.setBeta(s.getEvaluation()); 
      return s; 
     } 
     LinkedList<State> children = createChildren(s, true); 
     // No winner, the board is full 
     if (children.get_Count() == 0) 
     { 
      s.evaluationFunc(line_length, PlayerShape); 
      s.setAlpha(s.getEvaluation()); 
      s.setBeta(s.getEvaluation()); 
      return s; 
     } 
     while (children.get_Count() > 0) 
     { 
      State firstChild = children.get_First().get_Value(); 
      children.RemoveFirst(); 
      State tmp = miniMax(firstChild, depth, timer); 
      int value = tmp.getBeta(); 
      if (value > s.getAlpha()) 
      { 
       s.setAlpha(value); 
       s.setNextMove(tmp); 
      } 
      if (s.getAlpha() >= s.getBeta()) 
      { 
       return s; 
      } 
     } 
     return s; 
    } 

    public State miniMax(State s, int depth, Stopwatch timer) 
    { 
     if (s.getDepth() == 7) 
     { 
      Console.WriteLine(); 
     } 
     if (timer.get_ElapsedMilliseconds() > 850 || s.getDepth() == depth || goalTest(s.getBoard()) != 0) 
     { 
      s.evaluationFunc(line_length, PlayerShape); 
      s.setAlpha(s.getEvaluation()); 
      s.setBeta(s.getEvaluation()); 
      return s; 
     } 
     LinkedList<State> children = createChildren(s, false); 
     // No winner, the board is full 
     if (children.get_Count() == 0) 
     { 
      s.evaluationFunc(line_length, PlayerShape); 
      s.setAlpha(s.getEvaluation()); 
      s.setBeta(s.getEvaluation()); 
      return s; 
     } 
     while (children.get_Count() > 0) 
     { 
      State firstChild = children.get_First().get_Value(); 
      children.RemoveFirst(); 
      State tmp = maxiMin(firstChild, depth, timer); 
      int value = tmp.getAlpha(); 
      if (value < s.getBeta()) 
      { 
       s.setBeta(value); 
       s.setNextMove(tmp); 
      } 
      if (s.getAlpha() >= s.getBeta()) 
      { 
       return s; 
      } 
     } 
     return s; 
    } 

Est-ce que appriciate bien si quelqu'un peut me dire si quelque chose ne va pas. Je soupçonne peut-être quelque chose à voir avec le fait que je retourne "s" au lieu de l'alpha bêta ordinaire qui renvoie l'évaluation mais je n'ai pas réussi à trouver l'erreur.

Merci à l'avance,

Lena

Answer 1

Tout d'abord tic-tac-toe est un jeu très simple, et je crois qu'il est résoluble avec un code beaucoup plus simple, surtout parce que nous savons qu'il ya toujours un lien option et le nombre total d'états est inférieur à 3^9 (y compris symétrique et de nombreux états impossibles).

En ce qui concerne votre code, je crois que l'un de vos problèmes est que vous ne semblez pas augmenter votre profondeur dans les appels récursifs.

vous avez également beaucoup de problèmes de mauvais style dans votre code, vous avez séparé miniMax et MaxiMin en deux fonctions bien qu'elles soient fondamentalement les mêmes. vous parcourez une collection en supprimant des éléments plutôt que d'utiliser for-each ou un itérateur (ou même un itérateur d'int).