tic tac toe utilizando alpha beta en

Question

Estoy tratando de jugar tic tac toe usando iterativo Alpha-Beta, Tengo un segundo límite para un movimiento pero por alguna razón no funciona bien.

he modificado el código alfa-beta regular de modo en lugar de devolver alfa o beta, devuelve un estado (que es el tablero con el siguiente movimiento)

Cada vez que crear niños I actualizar su profundidad.

Pero de nuevo por alguna razón sigo perdiendo y veo que mi beta alfa no ve el mejor movimiento para hacer.

Aquí está mi código:

El bucle externo:

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 alfa-beta:

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; 
    } 

appriciate mucho si alguien me puede decir si algo está mal. Sospecho que tal vez tiene algo que ver con que estoy devolviendo "s" en lugar de la versión alfa beta que devuelve la evaluación, pero no pude encontrar el error.

Gracias de antemano,

Lena

Answer 1

En primer lugar tic-tac-dedo del pie es un juego muy simple, y creo que es solucionable con un código mucho más sencillo, sobre todo porque sabemos que siempre hay un empate opción y el número total de estados es menor que 3^9 (incluidos los estados simétricos y muchos imposibles).

En cuanto a su código, creo que uno de sus problemas es que no parece aumentar su profundidad en las llamadas recursivas.

También tiene muchos problemas de estilo incorrecto en su código, ha separado miniMax y MaxiMin en dos funciones, aunque son básicamente las mismas. itera sobre una colección eliminando elementos de ella en lugar de usar for-each o un iterador (o incluso un int iterator).