• Sábado 25 de Octubre de 2014, 11:23

Autor Tema:  Implementación de algoritmo MINIMAX en Othello (Reversi)  (Leído 565 veces)

genisuf

  • Nuevo Miembro
  • *
  • Mensajes: 2
    • Ver Perfil
Implementación de algoritmo MINIMAX en Othello (Reversi)
« en: Sábado 16 de Febrero de 2013, 07:54 »
0

Publicidad 
Hola foro. Como verán es mi primer posteo aquí y es debido a que no he podido encontrar qué es lo que esta fallando en este algoritmo. Espero alguien pueda darme una mano con este problema.
Resulta que estoy implementando una función con la estrategia MINIMAX para el juego Reversi en la que quedaría almacenado en la variable coordenadas (posee dos enteros, posx y posy) llamada "chosen_move" el movimiento del jugador 2 que le traiga más beneficio a la larga (depende la profundidad) . Para que puedan ayudarme debo suponer que ya saben como funciona MINIMAX, en este caso particular voy alternando la variable "color" entre 1 y 2 según a quien le toque jugar en cada nivel. La función ganancia (que anda bien ya está comprobado) resta 1 por cada ficha blanca y suma 1 por cada ficha negra en el tablero (hay casillas especiales en la que varía la constante), por lo que maximizo con las negras (jugador automático) y minimizo con las blancas (jugador manual).
La función hijos crea una lista con las coordenadas de las posibles jugadas para un determinado color en una configuración del tablero. También comprobé que ande bien dicha función, así como las de "realizar jugada".

El problema es que si elijo como profundidad máxima un número muy grande (ej: 50, o 60000 si gusta), el juego responde rápidamente. Sabiendo que la profundidad máxima para que explore el árbol completo en un tiempo computacional razonable es 6, esto me hace sospechar que cuando genera los hijos de las blancas en realidad la lista esta vacía, es decir, la función corta rápidamente al preguntar "if (hijos.empty())".

A su vez, los movimientos que va realizando las fichas negras son correctos hasta cierta jugada en la que coloca la ficha en una posición en la que no come nada (algo que no es permitido en el juego). Sin embargo, la función que corrobora si una posición es válida para que juegue un determinado color esta comprobado que anda correctamente, lo que concluye a que en realidad ese movimiento es uno que debió realizar el jugador blanco, o el mismo negro en una jugada más a futuro. Esto último me lleva a nuevamente a que pasa algo extraño con la variación de "color" de un nivel a otro, pero no estoy seguro de donde puede venir el error.

Si alguien leyendo el código puede darse cuenta que es lo que estoy haciendo mal estaría muy agradecido, ya que me he estado quemando los pelos con esta función ya hace unos días y no puedo encontrar que es lo que estoy haciendo mal.


Código: [Seleccionar]
void JugAutomatico::MINIMAX2(int & color, int & prof, int & chosen_score, coordenadas & chosen_move, Tablero &T)
{
    if (prof == 5)
    {
        chosen_score = T.ganancia();
    }
    else
    {
        list<coordenadas> hijos;
        obtener_hijos(color,hijos,T);
        if (hijos.empty())
        {
            chosen_score = T.ganancia();
        }
        else
        {
            int best_score;
            coordenadas best_move;
            int the_score=0;
            prof = prof+1;
            if (color == 1)
                int enemigo = 2;
            else
                int enemigo = 1;
            if (color == 1)
            {
                best_score = 8000;
            }
            else
            {
                best_score = -8000;
            }
            list<coordenadas>::iterator it = hijos.begin();
            while (it != hijos.end())
            {
                Tablero aux;
                aux.operator =(T);
                coordenadas the_move = *it;
                aux.realizar_jugada(color,the_move.posx,the_move.posy);
                MINIMAX2(enemigo,prof,the_score,the_move,aux);
                if (color == 1)
                {
                    if (the_score < best_score)
                    {
                        best_score = the_score;
                        best_move.posx = the_move.posx;
                        best_move.posy = the_move.posy;
                    }
                }
                else
                {
                    if (the_score > best_score)
                    {
                        best_score = the_score;
                        best_move.posx = the_move.posx;
                        best_move.posy = the_move.posy;
                    }
                }
                it++;
            }
            chosen_score = best_score;
            chosen_move.posx = best_move.posx;
            chosen_move.posy = best_move.posy;
        }
    }
}

genisuf

  • Nuevo Miembro
  • *
  • Mensajes: 2
    • Ver Perfil
Re:Implementación de algoritmo MINIMAX en Othello (Reversi)
« Respuesta #1 en: Domingo 17 de Febrero de 2013, 05:18 »
0
Ya lo solucione, gracias de todas formas