Función de evaluación para TicTacToe

Bueno. Pues resulta que en Sistemas Inteligentes nos mandaron implementar una función de evaluación (una heurística) para el tres en raya por el algoritmo Alfa-Beta. Ésta se usaría cuando limitaramos el tiempo de respuesta a cosas ínfimas como 1ms (pues de otra forma tendría tiempo para desarrollar un MiniMax y ésto no tendría sentido.

Ésta vez (a diferencia de las demás) publicaré todo el código previo únicamente para descargar. No para molestar sino porque son varias clases extensas.

Antes de nada debo avisar de que éste código tiene un dueño que no tiene nada que ver con el blog (excepto mi algoritmo). Por ésto mismo debo mencionar las librerías AIMA (Artificial Intelligence: A Modern Approach) que son las dueñas del código original. Aquí os pongo el proyecto y su .jar para importar.

Os cuento lo que pedía el profesor... Resulta que la clase que hace la búsqueda de forma iterativa (la clase IterativeDeepeningAlphaBetaSearch.java) tiene una función de evaluación que siempre devuelve 0.5, lo que hace que coja elementos al azar si no son terminales (me refiero a elementos pero recordad que estamos hablando de un árbol en Alfa-Beta).
Para ello dijo que lo que podíamos hacer era contar (en un estado determinado) las posibles soluciones (sin contar los empates) que podía haber y restarle a las del primero las del segundo para obtener el número "evaluación". El programa ya se encargará de usarlo como crea conveniente. Solo tenemos que buscar la función eval y arreglarla. Tenemos que implementarle algo así:

Espero que haya quedado claro... xP

Aquí tenéis la clase que hemos modificado para tener la solución.
Y aquí resuelto el código. Hemos modificado la clase IterativeDeepeningAlphaBetaSearch. Dentro de ésta hemos cambiado la función eval (solo el return) y hemos creado otras funciones que nos han ayudado a calcularlo todo. Espero que lo disfruteis pues me ha costado unas 15h sacarlo todo. (Lo que os he explicado es más o menos lo que me explicaron a mi. Ni como está formada la class STATE, ni la class PLAYER. Todo lo que descubrí lo hice por mi propia cuenta toqueteando).

Os cuento que la base de mi solución ha sido encontrar otra forma de dar la solución. Simplificando lo que hago es (tras ver que state era una string con forma de matriz que se iba actualizando con X y O) pasarla a 0, 1 y -1 y ver que me daba las mismas soluciones que como lo había pedido el profesor. Pongo foto explicativa:

Y ya sin más dilación, el trozo de código en el que he trabajado ;)

 protected double eval(STATE state, PLAYER player) {
  if (game.isTerminal(state)) {
   return game.getUtility(state, player);
  } else {
   maxDepthReached = true;
   return this.heuristic(state, player);
  }
 }
 
 private double heuristic(STATE state, PLAYER player) {
  
  System.out.println(state);
  
  int [][] tabla = tabla(state);
  for (int i = 0; i < 3; i++){
   for (int j = 0; j < 3; j++) {
    System.out.print(tabla[i][j] + " ");
   }
   System.out.println();
  }
  System.out.println();
  
  int heuristica = sumaColumnas(tabla)+sumaDiagonales(tabla)+sumaFilas(tabla);
  
  return heuristica;
 }
 
 private int[][] tabla(STATE state) {
  int[][] tb = {{5,5,5},{5,5,5},{5,5,5}}; //Por si hay algún fallo al introducir, que cante.
  Scanner sc = new Scanner(state.toString());
  sc.useDelimiter(" ");
  int acumulador = 0;
  while(sc.hasNext()) {
   String c = sc.next();
   
   switch (c) {
   case "-": case "\n-": tb[acumulador/3][acumulador%3] =  0;break;
   case "X": case "\nX": tb[acumulador/3][acumulador%3] =  1;break;
   case "O": case "\nO": tb[acumulador/3][acumulador%3] = -1;break;
   }
   
   acumulador++;
  }
  
  return tb;
 }

 
 /* Lo que hago es dar un valor de 1 al jugador que va primero y -1 al que va segundo.
  * El primero (por el algoritmo) intentará maximizar el resultado y el segundo, minimizarlo.
  * 
  * Por esto mismo cambio las X por 1 y las O por -1
  * Sumo el resultado de las diagonales, horizontales y verticales y me da lo mismo que si buscara
  * cuantas posibilidades de victoria y derrota tengo libres. ^^
  * 
  */
 
 private int sumaColumnas(int[][] table) {
  int suma = 0;
  for (int i = 0; i < 3; i++) {
   suma = suma + table[0][i];
   suma = suma + table[1][i];
   suma = suma + table[2][i];
  }
    
  return suma;
 }
 
 private int sumaFilas(int[][] table) {
  int suma = 0;
  for (int i = 0; i < 3; i++) {
   suma = suma + table[i][0];
   suma = suma + table[i][1];
   suma = suma + table[i][2];
  }
    
  return suma;
 }
 
 private int sumaDiagonales(int[][] table) {
  int suma = 0;
  for (int i = 0; i < 3; i++) {
   suma = suma + table[i][i]; //Diagonal normal
   suma = suma + table[i][i];
   suma = suma + table[i][i];
  }

   suma = suma + table[0][2]; //Diagonal inversa
   suma = suma + table[1][1];
   suma = suma + table[2][0];
  
    
  return suma;
 }
 

Si tenéis alguna duda no dudéis en preguntar. Espero seguir viéndoos por aquí.

Saludos ;)