Arboles Minimax Con Poda Alfa Beta

[Helius]

 Hola,

Acabo de hacer un juego de puzzle en J2ME y para las búsquedas de la IA estoy usando Minimax con poda alfa-beta pero me va tremendamente lento en algunos móviles y buscando tan sólo en 2 niveles, si pongo más de 2 niveles tarda siglos en responder.

¿Alguien sabe algo para optimizar esto? Lo único que he conseguido hacer es que no busque en movimientos repetidos.

No se si es que estoy haciendo algo mal o es que de los móviles no me puedo esperar mucho más  :(

Saludos.

[raistlin]

 lamentablemente muchos moviles son insultantemente lentos. mi consejo es que uses solo lo necesario y trates de minimizar al maximo el area.

[Helius]

 He encontrado alguna cosa aquí http://www.fierz.ch/strategy2.htm

Pero las optimizaciones me llevan más tiempo de cálculo que lo que se ahorra el algoritmo una vez optimizado.

Voy a probar con las Hash Tables. Eso sí puede que me venga bien.

[Warchief]

 Había escrito lo de abajo, pero luego he caído en que dices que sólo 2 niveles????

Explica un poco más: tamaño del árbol de búsqueda (= calcularMovimientosPosibles()), función de evaluación, etc, porque 2 niveles son muy pocos (incluso para un minimax sin poda). Si te interesa tengo un par de códigos por ahí, bajados de inet y otro mío.

-------------
Lo que había escrito antes de reflexionar:
-------------

Utilizas ordenación previa a la poda?

Es decir, que la poda alfabeta sólo funciona bien (=suele funcionar bien) cuando antes hay un proceso de ordenación (más ligero) de los subárboles a explorar. Esa ordenación debería hacer que la búsqueda mirase antes subárboles buenos, podandado desde niveles superiores.

[Helius]

 2 niveles son muy pocos sip, pero parece que algunos móviles no pueden con más. Además estamos hablando de Java y encima J2ME.

El juego es de tipo ataxx, la funcion de evaluación es simple, (fichas_negras - fichas_blancas).

No ordeno porque me cuesta más la ordenación que lo que me pueda ahorrar. Además no se muy bien el criterio a la hora de ordenar, he utilizado la propia función de evaluación, los movimientos con más puntuación examinarlos primero pero me resulta ineficiente.

El problema creo que es que en cada turno hay demasiados posibles movimientos, unos 20 o 30 de media en este tipo de juego con el tablero que uso (9x9). Aunque ahora que lo pienso si sólo uso dos niveles serían un total de  400 a 900 posibles movimientos, no me parecen muchos para que tarde tanto, y eso sin contar la poda... no se, no se, creo que el problema puede ser la velocidad del móvil y la torpeza de Java.

Hay que tener en cuenta que cada vez que busca un nuevo movimiento tiene que:
- Mirar todos los posibles movimientos (esto tarda un pelin porque hay que recorrer el tablero y mirar las posibilidades de cada ficha)
- Crear un tablero nuevo a partir del original lo que significa hacer una copia de arrays.
- Aplicar cada movimiento a dicho tablero y llamar recursivamente

No se, de todas formas Warchief si me puedes pasar los códigos te lo agradecería por si estoy haciendo algo mal.

[fiero]

 No sé como serán de grandes esos arrays, pero te puedes evitar copiarlos cada vez que examinas una posibilidad, con lo que te puedes evitar miles de copias.

La idea sería mandar a la función minimax la situación del tablero actual + un vector conteniendo los movimientos a evaluar. En ese caso, al entrar a la función, la secuencia de ejecución sería: actualizar el tablero-> evaluar posiciones-> restaurar el tablero-> llamar recursivamente con posiciones de entrada+posiciones siguientes.

Por ejemplo, en una llamada del tercer nivel, se deberán actualizar 3 posiciones, sin embargo, con las copias del tablero, para llegar a la misma llamada, se habrían realizado 3 copias de todo el tablero.

un saludo

EDITO:

Estaba pensando que lo de antes no es lo más óptimo (me he liao). Solo habría que pasar a la siguiente llamada recursiva la siguiente posición de ficha. En este caso la secuencia sería: actualizar posicion-> evaluar posiciones-> llamar al siguiente nivel con nuevas posiciones-> restaurar posición-> salir de función recursiva

algo así  :P

[samsaga2]

 No se si podra aplicar en tu caso pero en los juegos de ajedrez lo que se hace es meter el tablero en un byte (8x8=256bits). Es un byte por tipo de pieza. Con la reduccion drastica del tamaño en memoria del tablero tambien veras una mejor de velocidad (la memoria de un movil es extremadamente lenta).

[Warchief]

 Copiar el tablero era un coste enorme. Más si lo haces por cada nivel (cada nivel que mete un movimiento tiene que hacer 1 copia por movimiento posible). Lo que yo hice es:

Un movimiento son 2 short (origen, destino) + 1 short (valor) + 4 enteros para información adicional sobre capturas.

Código [Seleccionar] Expand


class AIMove
{
// public access again to save some time
public:

/// Default constructor, use to declare useful vars
AIMove() : valid(false) { }

/// Constructor that rocks the work, use it inside the AI algorithm
AIMove(int srow, int scol, int drow, int dcol);

/// source coordinates (7 bits for 'X' and 7 for 'Y' (2^7 = 128 > max board size))
unsigned short int mSource;
/// destination coordinates (7 bits for 'X' and 7 for 'Y' (2^7 = 128 > max board size))
unsigned short int mDestination;

/// The AI has to set this boolean to true if its a valid movement
bool valid;

/// Value of the move. Better moves should have better value (for alphabeta pruning)
short int mValue;

// You could use less variables for the undo process; it is not too expensive this way,
// so i will use it (remeber is not that easy as sacrifices are allowed)
/// Undo information
TUnit undo_movedUnit;
/// Undo information
TTeam undo_movedUnitTeam;
/// Undo information
TUnit undo_takenUnit;
/// Undo information
TTeam undo_takenUnitTeam;
};


De forma que el código sería:

Código [Seleccionar] Expand


  // Apply the movement
  applyMove(board, *mList[i]);

  // Eval descendant nodes
  actualValue = minMove(board, bestMove, alpha, beta, depth+1);  // minMove o maxMove

  // Undo the movement
  undoMove(board, *mList[i]);



Investiga:
http://telefonica.net/web2/warchief/resour...inimax%20AB.zip

El mío en la carpeta 'warchief' (sólo puedo pasar el código de la ia) en c++.
Los demás en c++ excepto 1 en java, pero parece bastante tonto.

[Helius]

 Gracias, voy a ello  :)