Othello e Minimax com poda alpha beta - parte 1

Olá pesssoal, tudo bem?
Nesse post vamos aplicar o famoso Minimax com poda alfa-beta, um dos meus algoritmos preferidos. Como aplicação, não queria escolher algo tão simples como Tic-Tac-Toe, nem tão complexo como xadrez. Foi aí que eu descobri o jogo Othello, também conhecido como Reversi.

Nosso objetivo é criar uma engine simples, mas que jogue de maneira convincente. O interessante no Othello é que o jogo ainda não foi 'resolvido' computacionalmente, pelo menos no tabuleiro padrão 8 x 8. Além disso é extremamente simples de aprender, e as estratégias básicas são fáceis de codificar. Caso não conheça o jogo, visite o link acima e tente algumas applets, depois volte aqui!

Minimax

A idéia básica do Minimax é minimizar a perda máxima, ou caso você seja otimista, maximizar o ganho mínimo. Para isso, a partir de determinada posição, geramos a árvore com todas as posições possíveis até determinada profundidade. Em seguida, percorremos essa árvore de baixo para cima, escolhendo os lances que maximizam nossos ganhos e lembrando que o nosso oponente fará o mesmo. Como temos um jogo de soma-zero , sob nosso pontos de vista o oponente irá minimizar seus ganhos, daí vem o nome.

Se você já jogou xadrez contra uma engine forte, é fácil perceber esse mecanismo de 'ganho mínimo' em ação. Ao fazer um lance fraco ou anti-posicional, vemos como a engine pouco a pouco nos força a uma posição inferior, mesmo quando nos defendemos corretamente (minimizamos nossa perda máxima). Ao fazer um lance realmente ruim, o nosso score cai abruptmente e o da engine aumenta a mesma quantia, e não é incomum um mate em 15 ou mais lances ser anunciado: provavelmente você foi pego pela poda alfa-beta!

Poda alfa-beta

Voltando ao exemplo do xadrez, como uma engine consegue determinar quase que instantaneamente uma situação de mate em 10, por exemplo? A resposta é simples: otimizações. O alpha-beta pruning, ou poda alfa-beta, é uma das otimizações que podem ser aplicadas ao Minimax, com o objetivo de reduzir o tempo de busca. Outra otimização que funciona junto com a poda alfa-beta é a ordenação de lances. No exemplo do mate em 10, são essas duas técnicas trabalhando junto que fazem a engine ser tão eficiente.

Para entender como isso funciona, imagine o seguinte: é a sua vez de mover e você tem 20 lances disponíveis. Ao analizar a árvore do primeiro lance (A), percebemos que ele nos dá uma vantagem decisiva em todas as variantes. Ao analizar o segundo lance disponível (B), percebemos que este pode ser imediatamente neutralizado pelo adversário. Obviamente não vale a pena continuar expandindo a árvore do lance B, pois sabemos que podemos fazer melhor com A. Ou seja, os nós provenientes de B não serão expandidos, e assim ganhamos tempo de execução. A ordenação de lances acelera esse processo, colocando os lances mais promissores para serem avalidados primeiro. Para codificar esse mecanismo o algoritmo mantém duas variáveis, alpha e beta, que representam os melhores scores atingidos pelos jogadores até então.

Heurística

Como vimos acima, precisamos de um método para decidir se uma determinada posição é vantajosa ou não. No nosso caso, as estratégias básicas do Othello já nos garantem uma engine razoável. Geralmente o nível de sofisticação e a força de uma engine refletem a complexidade da heurística utilizada. O programa Logistello, por exemplo, contém milhares de variáveis e padrões pré-calculados, além de utilizar técnicas estatísticas e A.I. para refinar parâmetros.

Após implementar o framework básico do nosso programa, você pode facilmente extender a heurística, tomando o cuidado de testar cada nova função separadamente. Outra idéia é criar um pequeno framework para testar a força do programa, o ideal seria utilizar uma engine superior como adversária. A maioria das engines de xadrez adotam o protocolo UCI para se comunicar com uma GUI. No nosso caso, Othello Engine Protocol parece ser a solução.

O código

Vamos começar definindo a estrutura básica do jogo, criando as classes OthelloBoard e OthelloMove. Na parte de AI, a classe MinimaxOthello é responsável por executar o algoritmo em uma Thread separada, e a classe OthelloHeuristics define métodos para avaliar a 'qualidade' de determinada posição. Finalmente, criamos uma GUI para testar a engine. Mãos a obra!

Classe OthelloBoard

Essa classe define apenas 4 variáveis de instância: emptyCells, phase, currentPlayer e cells. A variável phase nos diz em qual fase do jogo estamos (abertura, meio-jogo ou final) e será utilizada na hora de avaliar a posição, pois cada fase exige uma estratégia diferente. A array cells representa as casas do tabuleiro 8 x 8, e será interpretada como uma array 10 x 10, onde as 2 linhas e colunas extras irão facilitar a listagem de lances possíveis. Por fim, currentPlayer representa o jogador que tem a vez, e emptyCells nos diz quantas casas estão vazias.

Os métodos makeMove e undoMove serão utilizados no Minimax para gerar a árvore de posições, evitando criar milhares de cópias do objeto OthelloBoard que será passado ao algoritmo. O método getAllMoves retorna uma lista com todos os lances possíveis para determinado jogador, iterando sobre as células e invocando getFlips para cada casa vazia. Para checar um possível fim de jogo, checkEnd verifica se não existem mais casas vazias, ou se nenhum dos jogadores possui lances válidos.

O restante do código são getters, setters, ou métodos triviais como cloneBoard. É fundamental entender como lidamos com a situação em que um jogador não possui lances disponíveis: getAllMoves retorna um lance 'vazio', que é processado normalmente dentro de makeMove ou undoMove, assim não precisamos tratar deste caso especial ao implementar o algoritmo. Segue a classe:

import java.util.*;

public class OthelloBoard
{
   public static final int BLACK = 1;
   public static final int WHITE = 2;
   public static final int EMPTY = 0;
   public static final int WALL = 5;
   public static final int BOARD_SIZE = 8;
   public static final int[] DIRECTIONS = { -11, -10, -9, -1, 1, 9, 10, 11}; 
   public static final int PHASE_OPENING = 100;
   public static final int PHASE_MIDGAME = 200;
   public static final int PHASE_ENDGAME = 300;
    
   private int emptyCells;        
   private int phase;
   private int currentPlayer = BLACK;
   private int[] cells = new int[(BOARD_SIZE + 2) * (BOARD_SIZE + 2)];
 
   public OthelloBoard()
   {
        this.currentPlayer = BLACK;
  
        cells[44] = WHITE;
        cells[55] = WHITE;
        cells[45] = BLACK;
        cells[54] = BLACK;        
        
        emptyCells = BOARD_SIZE * BOARD_SIZE - 4;
        
        for (int i = 0; i < cells.length; i++) 
        {
            int col = i % 10;
            int row = i / 10;
            
            if (col == 0 || col == 9)
                cells[i] = WALL;
            if (row == 0 || row == 9)
                cells[i] = WALL;
        }
        
        phase = PHASE_OPENING;                            
   }
    
    public void toogleCurrentPlayer()
    {
        currentPlayer = getOpponent(currentPlayer);
    }
                
    public void setEmptyCells(int emp)
    {
        this.emptyCells = emp;
    }

    public boolean checkEnd()
    {
        boolean endGame = false;
        
        if (emptyCells == 0)
            endGame = true;
        else if ((getAllMoves(BLACK).get(0).getFlipSquares() == null) && 
                 (getAllMoves(WHITE).get(0).getFlipSquares() == null))
        {
            endGame = true;
        }                
        
        return endGame;
    }
    
    public OthelloBoard cloneBoard()
    {
        OthelloBoard b = new OthelloBoard();
        for (int i = 0; i < this.cells.length; i++)
            b.cells[i] = this.cells[i];
        
        b.phase = this.phase;
        b.currentPlayer = this.currentPlayer;
        b.emptyCells = this.emptyCells;        
        
        return b;
    }
        
    public int getEmptyCells()
    {
        return this.emptyCells;
    }
    
    public int getPhase()
    {
        return this.phase;
    }
    
    public int getCurrentPlayer()
    {
        return this.currentPlayer;
    }
    
    public int getOpponent(int player)
    {
        return 3 - player;
    }

    public int[] getCells()
    {
        return this.cells;
    }
       
    public ArrayList<OthelloMove> getAllMoves(int player)
    {
        ArrayList<OthelloMove> moves = new ArrayList<OthelloMove>();
        
        for (int i = 10; i < 90; i++) 
        {
            int col = i % 10;
            
            if (col != 0 && col != 9)            
            {
                if (cells[i] == EMPTY)
                {
                    ArrayList<Integer> flips = getFlips(i, player);                    
                    if (flips.size() > 0)
                    {
                        OthelloMove mv = new OthelloMove();
                        mv.setFlipSquares(flips);
                        mv.setIdx(i);                        
                        mv.setPlayer(player);
                        moves.add(mv);
                    }
                }
            }
        }                                     
        
        if (moves.size() == 0)
        {
            OthelloMove mv = new OthelloMove();
            mv.setPlayer(getOpponent(player));
            moves.add(mv);
        }
        return moves;
    }
    
    public ArrayList<Integer> getFlips(int idx, int player)
    {        
        int opponent = getOpponent(player);
        ArrayList<Integer> flips = new ArrayList<Integer>();
                      
        for (Integer dir : DIRECTIONS)
        {
           int distance = 1;
           int tempIdx = idx;
                        
           while (cells[tempIdx += dir] == opponent)            
               distance++;
                                                
           if ((cells[tempIdx] == player) && (distance > 1)) 
           {               
               while (distance-- > 1)
               {                    
                   tempIdx -= dir;
                   flips.add(tempIdx);
               }                            
           }            
         }
        return flips;
    }
    
    public void updatePhase()
    {
        if (emptyCells > 45)
            phase = PHASE_OPENING;
        else if(emptyCells < 15)
            phase = PHASE_ENDGAME;
        else 
            phase = PHASE_MIDGAME; 
    }
    
    public void makeMove (OthelloMove move)
    {                    
        int player = move.getPlayer();        
        ArrayList<Integer> flips = move.getFlipSquares();
        
        if (flips != null)
        {                                   
            int idx = move.getIdx();                    
            cells[idx] = player;
            for (Integer flip : flips)
                cells[flip] = player;        
                                  
            emptyCells--;    
            this.updatePhase();           
        }
        this.toogleCurrentPlayer();                    
     }
    
    public void undoMove (OthelloMove move)
    {                    
        int player = move.getPlayer();        
        ArrayList<Integer> flips = move.getFlipSquares();
        int opponent = getOpponent(player);
        
        if (flips != null)
        {
            int idx = move.getIdx();
                        
            cells[idx] = EMPTY;
            for (Integer flip : flips)
                cells[flip] = opponent;
            
            emptyCells++;                                         
            this.updatePhase();
        }
        this.toogleCurrentPlayer();                    
    }
    
    public int countDiscs(int player)
    {
        int discs = 0;
        for (int i = 10; i < 90; i++) 
        {
            int col = i % 10;
            
            if (col != 0 && col != 9)
            {
                if (cells[i] == player)                
                    discs++;                
            }            
        }
        return discs;
    }
}

Classe OthelloMove

Além das informações necessárias para fazer e desfazer um lance, definimos a variável de instância eval, que é utilizada pela classe MoveComparator para ordenar os lances. Segue a classe:

import java.util.*;

public class OthelloMove
{
    private ArrayList<Integer> flipSquares;
    private int idx;
    private int player;
    private int eval;
    
    public ArrayList<Integer> getFlipSquares()
    {
       return flipSquares;
    }

    public void setEval(int eval)
    {
        this.eval = eval;
    }

    public int getEval()
    {
        return this.eval;
    }

    public int getPlayer()
    {
        return this.player;
    }

    public void setPlayer(int player)
    {
        this.player = player;
    }

    public int getIdx()
    {
       return idx;
    }

   public void setFlipSquares(ArrayList<Integer> flipSquares)
   {
       this.flipSquares = flipSquares;
   }

   public void setIdx(int idx)
   {
       this.idx = idx;
   }
}

/* classe auxiliar */
class MoveComparator implements Comparator<OthelloMove>
{
    public int compare(OthelloMove move1, OthelloMove move2)
    {
        if (move1.getEval() > move2.getEval())
            return 1;
        else if (move1.getEval() < move2.getEval())
            return -1;
        else 
            return 0;
    }

}

Na segunda parte desta série vamos implementar as classes restantes e ver testar a engine. Até mais!