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!
As informações sobre os anexos são confidenciais e destinados exclusivamente ao destinatário você.
ResponderExcluirAs informações sobre os anexos são confidenciais e destinados exclusivamente ao destinatário você.
ResponderExcluir