Organizando los directorios donde guardo todos mis proyectos, he encontrado dos juegos que hice hace ya catorce años: el 3 en raya y Dernier. Lamentablemente no puedo ver el código fuente de ninguno de los dos porque están compilados con QuickBASIC. Recuerdo que programé estos dos juegos a base de un sinfín de ifs anidados, ya que por aquel entonces no tenía ni idea de lo que era el algoritmo MiniMax. El resultado me convenció durante un tiempo ya que, a pesar de todo, eran juegos imbatibles, pero enseguida entendí que utilizando este sistema de programación nunca podría hacer un juego más complejo, como las damas o el ajedrez.

Ahora me he propuesto realizar, a modo de primera práctica con Silverlight, una versión renovada de estos dos juegos. Aprovechando estos días de inicio de año en los que estoy de vacaciones y tomándome un respiro en los estudios del MCTS, he comenzado la implementación del «apasionante» 3 en raya, en esta ocasión haciendo uso del algoritmo MiniMax con dos optimizaciones (poda alpha-beta y límite de profundidad).

Esta primera versión que he subido no incluye ningún comentario en el código, si dispongo de más tiempo comentaré las partes del código más interesantes, e implementaré las otras variantes de MiniMax para poder comparar las mejoras de rendimiento que se obtienen. El código fuente de la solución se puede descargar en el enlace que pongo al final de esta entrada.

El proyecto tiene dos clases principales (Board y IAGame). La clase Board contiene los métodos para saber si una partida ha finalizado (GameEnded) y tiene ganador (GetWinner) o está empatada (IsTie), y para saber los posibles movimientos a partir de una situación de tablero dada (GetAllowedMovements). La clase IAGame *contiene la implementación del algortimo _MiniMax con las distintas optimizaciones.

Para los interesados exclusivamente en el código del algoritmo MiniMax, aquí dejo mi implementación del método recursivo en C#.

public Movement MiniMaxBasic(Board board, int player) 
{ 
    if (board.GetWinner() != 0 || board.IsTie()) 
    { 
        Movement mov = new Movement(); mov.Value = board.GetWinner();

        return mov;
    }
    else
    {
        int[] successors = board.GetAllowedMovements(true);
        Movement best = null;
    
        foreach (int successor in successors)
        {
            Board successorBoard = (Board)board.Clone();
            successorBoard.SetMove(successor, player);
            Movement tmp = MiniMaxBasic(successorBoard, -player);
    
            if (best == null || (player == -1 && tmp.Value < best.Value) || (player == 1 && tmp.Value > best.Value))
            {
                tmp.Position = successor;
                best = tmp;
            }
        }
        return best;
    } 
}

Este método —como se puede ver— no tiene ninguna optimización en la generación del árbol de búsqueda, en el código completo están las otras dos implementaciones del algoritmo con poda alpha-beta y profundidad de búsqueda.

Actualización (11/Nov/09): Para aquellos que no tengáis Blend, he añadido un nuevo enlace para descargar el código fuente de un ejemplo de aplicación de consola. Este código permite jugar una partida contra el ordenador utilizando 3 variantes del algoritmo MiniMax.

Descargas

ConsoleTicTacToe.zip
SilverlightTicTacToe.zip