Devolución de recursión de poda Alpha-Beta de Java Minimax

recursion artificial-intelligence

Question

Estoy tratando de implementar minimax con poda alfa-beta para un juego de damas en Java. Mi algoritmo minimax funciona perfectamente. Mi código se ejecuta con el código alfa-beta en su lugar. Desafortunadamente, cuando juego 1000 juegos contra el algoritmo minimax estándar, el algoritmo alfa-beta siempre se queda atrás en unos 50 juegos o algo así.

Dado que la poda alfa-beta no debería reducir la calidad de los movimientos, solo el tiempo que lleva lograrlos, algo tiene que estar mal. Sin embargo, saqué lápiz y papel y dibujé valores hipotéticos del nodo hoja y utilicé mi algoritmo para predecir si calculará el mejor movimiento correcto, y no parece haber ningún error lógico. Usé el árbol de este video: Alpha-Beta Pruning para rastrear mi algoritmo. Lógicamente debería tomar todas las mismas opciones y, por lo tanto, ser una implementación que funcione.

También he puesto sentencias impresas en el código (se han eliminado para reducir el desorden), y los valores se devuelven correctamente, aparece y se produce la poda. A pesar de mis mejores esfuerzos, no he podido encontrar dónde está el error lógico. Este es mi tercer intento diferente de implementar esto y todos ellos han tenido el mismo problema.

No puedo publicar el código completo aquí, es demasiado largo, así que he incluido los métodos que son relevantes para el error. No estoy seguro, pero sospecho que el problema puede estar en el método de movimiento no recursivo (), aunque no puedo encontrar un error lógico en él, así que simplemente lo estaría haciendo más, probablemente haciendo cosas. Peor más que mejor sin tener una rima o razón.

¿Hay algún truco para recuperar múltiples valores enteros de llamadas recursivas en un bucle for? Funciona bien con mis implementaciones minimax y negamax, pero la poda alfa-beta parece producir algunos resultados extraños.

@Override
public GameState move(GameState state) 
{
    int alpha = -INFINITY;
    int beta = INFINITY;
    int bestScore = -Integer.MAX_VALUE;
    GameTreeNode gameTreeRoot = new GameTreeNode(state);
    GameState bestMove = null;
    for(GameTreeNode child: gameTreeRoot.getChildren())
    {
        if(bestMove == null)
        {
            bestMove = child.getState();
        }
        alpha = Math.max(alpha, miniMax(child, plyDepth - 1, alpha, beta));
        if(alpha > bestScore)
        {
            bestMove = child.getState();
            bestScore = alpha;
        }
    }
    return bestMove;
}

private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta) 
{
    if(depth <= 0 || terminalNode(currentNode.getState())) 
    {
        return getHeuristic(currentNode.getState());
    }
    if(currentNode.getState().getCurrentPlayer().equals(selfColor))
    {
        for(GameTreeNode child: currentNode.getChildren())
        {
            alpha = Math.max(alpha, miniMax(child, depth - 1, alpha, beta));

            if(alpha >= beta)
            {
                return beta;
            }
        }
        return alpha;
    }
    else
    {
        for(GameTreeNode child: currentNode.getChildren())
        {
            beta = Math.min(beta, miniMax(child, depth - 1, alpha, beta));

            if(alpha >= beta)
            {
                return alpha;
            }
        }
        return beta;
    }
}
//Checks to see if the node is terminal
private boolean terminalNode(GameState state)
{
if(state.getStatus().equals(win) || state.getStatus().equals(lose) || state.getStatus().equals(draw))
    {
        return true;
    }
    else
    {
        return false;
    }
}

Answer 1

El 16 de marzo de 2013, sage88 preguntó:

¿Hay algún truco para recuperar múltiples valores enteros de llamadas recursivas en un bucle for? Funciona bien con mis implementaciones minimax y negamax, pero la poda alfa-beta parece producir algunos resultados extraños.

En la poda alfa beta, el único valor de salida de interés es la puntuación de un nodo: el valor final de beta en un nodo mínimo se considera para el valor alfa de su nodo máximo primario; Del mismo modo, el valor final de alfa en un nodo máximo se considera para el valor beta de su nodo mínimo primario. Por lo tanto:

La respuesta a su pregunta es el algoritmo mismo, ya que es el truco más relevante.

Dicho esto, hay dos errores en su implementación: 1) Como señaló originalmente Adrian Blackburn, está devolviendo alfa incorrectamente desde un nodo mínimo y viceversa, lo que distorsiona su precisión; 2) Está renunciando a las oportunidades de poda considerando prematuramente el alfa o beta padre en el valor del nodo actual. Esta versión corrige los valores de retorno y maximiza la poda:

private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta) {
    if (depth <= 0 || terminalNode(currentNode.getState())) {
        return getHeuristic(currentNode.getState());
    }
    if (currentNode.getState().getCurrentPlayer().equals(selfColor)) {
        int currentAlpha = -INFINITY;
        for (GameTreeNode child : currentNode.getChildren()) {
            currentAlpha = Math.max(currentAlpha, miniMax(child, depth - 1, alpha, beta));
            alpha = Math.max(alpha, currentAlpha);
            if (alpha >= beta) {
                return alpha;
            }
        }
        return currentAlpha;
    }
    int currentBeta = INFINITY;
    for (GameTreeNode child : currentNode.getChildren()) {
        currentBeta = Math.min(currentBeta, miniMax(child, depth - 1, alpha, beta));
        beta = Math.min(beta, currentBeta);
        if (beta <= alpha) {
            return beta;
        }
    }
    return currentBeta;
}

Gracias por aportar una pregunta divertida e interesante :)

Para más diversión, aquí hay una aclaración de su método move() , eliminando una llamada redundante a Math.max() :

@Override
public GameState move(GameState state) {
    GameState bestMove = null;
    int bestScore = -INFINITY;
    GameTreeNode gameTreeRoot = new GameTreeNode(state);
    for (GameTreeNode child : gameTreeRoot.getChildren()) {
        int alpha = miniMax(child, plyDepth - 1, bestScore, INFINITY);
        if (alpha > bestScore || bestMove == null) {
            bestMove = child.getState();
            bestScore = alpha;
        }
    }
    return bestMove;
}

Finalmente (aún más divertido), solo una sugerencia, un cambio de nombre de método para aclarar la intención de terminalNode() , aunque lo movería a GameState para que pueda llamarse sin parámetros:

private boolean isTerminal(GameState state) {
    //return Is.any(state.getStatus(), win, lose, draw);
    return state.getStatus().equals(win)
        || state.getStatus().equals(lose)
        || state.getStatus().equals(draw);
}

Answer 2

Noté que usted dijo que encontró el problema, pero no debería ser la poda beta minimax alfa

if it is MAX''s turn to move
  for child in children
     result = alphaBetaMinimax(child, alpha, beta)
     if result > alpha
        alpha = result
        if node is root
           bestMove = operator of child
     if alpha >= beta
        return alpha
  return alpha

if it is MIN''s turn to move
  for child in children
     result = alphaBetaMinimax(child, alpha, beta)
     if result < beta
        beta = result
        if node is root
           bestMove = operator of child
     if beta <= alpha
        return beta
  return beta

tu escribiste:

  if alpha >= beta
    return beta
return alpha

Answer 3

Para lograr las apuestas de resultados de prueba, debe implementar algún tipo de orden de movimiento. En el ajedrez suele ser de capturas o cheques. Ese tipo de movimientos tienden a cambiar la evaluación más, por lo que tienen un gran impacto en la imprenta. En las damas, podría estar tomando piedras de los oponentes o promoviendo piedras de sí mismo en el octavo rango (lo siento, no sé los términos utilizados).

Answer 4

Solo para responder a tu pregunta

¿Hay algún truco para recuperar múltiples valores enteros de llamadas recursivas en un bucle for?

Sí, en Java necesitaría pasar un objeto a la llamada a la función recursiva y luego modificar el contenido de ese objeto. Después de que la función vuelva, podrá acceder a los valores modificados.

P.ej.

class ToBeReturned {
    int returnValue1;
    int returnValue2;
    int returnValue3;
}

Answer 5

Ya solucionaste tu problema, pero el problema que encontraste es bastante común. Así que cada vez que construyas una parte del algoritmo para un agente de AI, tienes que probarlo correctamente. Entonces, una vez que su algoritmo minimax sea correcto, puede generar muchos árboles aleatorios y verificar si los resultados son los mismos. Por ejemplo, en Python puedes hacer esto de esta manera:

class Node():
    def __init__(self, data, children):
        self.data = data
        self.children = children

def generateTree(depth, branching):
    total = branching**depth
    values = [randint(-100, 100) for _ in xrange(total)]
    level = [Node(values[i], []) for i in xrange(total)]

    for _ in xrange(depth):
        total /= branching
        level = [Node(None, level[i * branching: (i+1) * branching]) for i in xrange(total)]

    return level[0], values

Ahora puedes generar un árbol con muchos árboles al azar y comparar los resultados.

tree, values = generateTree(depth, branching)
print negamax(tree, depth, 1) == alpha_beta_negamax(tree, depth, float(''-inf''), float(''inf''), 1)

No olvide que minimax y alpha-beta solo obtienen el mejor valor, mientras que lo que le interesa en un juego real es un movimiento. Es sencillo modificarlos de tal manera que puedan devolver un movimiento, pero esto depende de un desarrollador para decidir cómo se devuelve el movimiento. Esto se debe a que puede haber muchos movimientos que conduzcan a la mejor solución (puede devolver el primero, el último o el más común es encontrar todos los movimientos y devolver el aleatorio).

En su caso, el problema fue con la aleatoriedad de los valores devueltos, por lo que durante la prueba, el buen enfoque es corregir la aleatoriedad.