No post anterior criamos o framework básico do game e vimos (de forma bem simplificada) alguns conceitos sobre o Minimax. Neste post vamos colocar esses conceitos em prática, além de utilizar poda alfa - beta e ordenação de lances para melhorar o desempenho da engine, fundamental caso você esteja desenvolvendo para alguma plataforma mobile.
Classe MinimaxOthello
Entender essa classe é o objetivo deste tópico. O Minimax com poda alfa-beta é um desses casos onde é fácil entender o algoritmo, mas é difícil visualizar o mecanismo.
Ao longo do algoritmo, mantemos referência a variável de instância bestFound, que representa o melhor lance encontrado até então. Por ser recursivo e consumir bastante CPU, a cada lance da AI criamos uma nova Thread e esperamos run() retornar, após isso obtemos o melhor lance com getBestFound(). Repare no construtor, que precisa saber qual posição queremos analisar, qual a profundidade máxima que iremos atingir, e se queremos ou não analisar até o fim do jogo. Obviamente, analisar a árvore de posições até o fim só é possível na fase final do jogo, e o caller do algoritmo deve decidir quando isso acontece.
No começo do algoritmo, checamos se atingimos uma posição final ou a profundidade máxima. No primeiro caso, retornamos um valor evalGameOver na faixa -INFINITO < evalGameOver < INFINITO, que será positivo caso currentPlayer tenha vencido, negativo caso tenha perdido, ou zero no empate. Caso a profundidade máxima seja atingida e solve == false, retornamos o valor da posição atingida, caso solve == true, seguimos expandindo a árvore até chegar em um nó terminal.
Seguindo em frente, obtemos uma lista com os lances válidos para a posição atual e os ordenamos, logo após setar a variável eval de cada lance, com o método estático scoreMoves da classe OthelloHeuristics. Em seguida vem a parte mágica: para cada lance da lista, aplicamos esse lance na posição atual, e invocamos recursivamente o algoritmo. Ao invocar a recursão, o objeto board será alterado, e é por isso que na próxima linha desfazemos o lance com undoMove. Podiamos criar uma cópia profunda do objeto board e usar esta cópia na recursão, eliminando undoMove, mas criando milhares (ou milhões) de novos objetos a cada chamada. Nem sempre é fácil implementar undoMove, mas vale bastante a pena em termos de memória (mais tarde vamos olhar a variável calls). O algoritmo é intrincado, mas a estrutura é a mesma para qualquer aplicação. Segue a classe:
import java.util.*;
import java.util.concurrent.*;
public class MinimaxOthello implements Runnable
{
private CountDownLatch doneSignal;
private int maxDepth;
private int calls;
private OthelloMove bestFound;
private OthelloBoard board;
private static float INFINITY = Float.MAX_VALUE/1000;
private boolean solve = false;
private Comparator<OthelloMove> comparator = Collections.reverseOrder(new MoveComparator());
public MinimaxOthello (OthelloBoard board, int maxDepth, CountDownLatch doneSignal, boolean solve)
{
this.board = board;
this.bestFound = new OthelloMove();
bestFound.setPlayer(board.getCurrentPlayer());
this.maxDepth = maxDepth;
this.doneSignal = doneSignal;
this.solve = solve;
}
public OthelloMove getBestFound()
{
return this.bestFound;
}
public void run()
{
float val = minimax(board, bestFound, -INFINITY, INFINITY, 0);
System.out.println("calls: " + calls);
System.out.println("eval: " + val);
System.out.println();
doneSignal.countDown();
}
private float minimax(OthelloBoard board, OthelloMove best, float alpha, float beta, int depth)
{
calls++;
OthelloMove garbage = new OthelloMove();
int currentPlayer = board.getCurrentPlayer();
if (board.checkEnd())
{
int bd = board.countDiscs(OthelloBoard.BLACK);
int wd = board.countDiscs(OthelloBoard.WHITE);
if ((bd > wd) && currentPlayer == OthelloBoard.BLACK)
{
return INFINITY/10;
}
else if ((bd < wd) && currentPlayer == OthelloBoard.BLACK)
{
return -INFINITY/10;
}
else if ((bd > wd) && currentPlayer == OthelloBoard.WHITE)
{
return -INFINITY/10;
}
else if ((bd < wd) && currentPlayer == OthelloBoard.WHITE)
{
return INFINITY/10;
}
else
{
return 0.0f;
}
}
if (!solve)
{
if (depth == maxDepth)
return OthelloHeuristics.eval(currentPlayer, board);
}
ArrayList<OthelloMove> moves = board.getAllMoves(currentPlayer);
if (moves.size() > 1)
{
OthelloHeuristics.scoreMoves(moves);
Collections.sort(moves, comparator);
}
for (OthelloMove mv : moves)
{
board.makeMove(mv);
float score = - minimax(board, garbage, -beta, -alpha, depth + 1);
board.undoMove(mv);
if(score > alpha)
{
alpha = score;
best.setFlipSquares(mv.getFlipSquares());
best.setIdx(mv.getIdx());
best.setPlayer(mv.getPlayer());
}
if (alpha >= beta)
break;
}
return alpha;
}
}
Classe OthelloHeuristics
Apesar da simplicidade, o jogo Othello é bastante rico em termos de estratégia. Alguns conceitos encontrados no xadrez também se aplicam ao jogo: mobilidade, controle do centro, aberturas e tempo, para citar alguns.
Como sou um péssimo jogador, uma breve pesquisa me esclareceu os seguintes pontos:
- Apenas contar peças é uma péssima estratégia, quase sempre levando a derrota
- O controle das 'quinas' (corner squares) e 'bordas' (edge squares) é fundamental
- A mobilidade é fundamental
Existem outros conceitos igualmente importantes ('paridade' por exemplo) mas a lista acima já é um bom começo. As estratégias acima estão relacionadas com o conceito de 'disco estável', que são os discos que uma vez conquistados, não podem mais ser 'flipados' pelo seu adversário. Repare que ao conquistar uma quina, podemos utilizá-la como pivô para novos discos estáveis, o que geralmente garante uma boa vantagem. É claro que o seu adversário também sabe disso, e não vai te entregar as corner squares de graça, o que nos leva ao conceito de mobilidade.
Para forçar seu adversário a fazer lances ruins, devemos ter uma mobilidade superior (maior número de opções a cada jogada) e tirar proveito disso forçando o adversário a entregar uma ou mais quinas. Geralmente lances adjacentes a quina são fracos, pois levam a perda desta. As duas casas adjacentes lateralmente a uma quina são chamadas de 'C squares', e a casa diagonalmente adjacente a quina é conhecida como 'X square'.
Esses são os fatores que vamos considerar na nossa heurística, o que já garante um desempenho razoável contra um jogador mediano. Um dos fatores que não estamos levando em conta e que melhoraria muito a força da engine, são os edge patterns, ou padões da borda. Se levarmos em conta a quina, cada borda possui 310 = 59049 configurações, que geralmente são pré-calculadas e acessadas durante a avaliação da posição.
A heurística utilizada é bem simples: dependendo da fase do jogo, atribuímos pesos diferentes para cada característica abaixo:
- mobilidade
- mobilidade potencial
- corner squares
- C squares
- X squares
- número de discos
import java.util.ArrayList;
public class OthelloHeuristics
{
private static final int[] cornerIndexes = new int[]{11, 18, 81, 88};
private static final int[] xIndexes = new int[]{22, 27, 72, 77};
private static final int[] cIndexes = new int[]{12, 21, 17, 28, 71, 82, 78, 87};
private static final int[] squareValues = new int[]
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 120, -20, 20, 5, 5, 20, -20, 120, 0,
0, -20, -40, -5, -5, -5, -5, -40, -20, 0,
0, 20, -5, 15, 3, 3, 15, -5, 20, 0,
0, 5, -5, 3, 3, 3, 3, -5, 5, 0,
0, 5, -5, 3, 3, 3, 3, -5, 5, 0,
0, 20, -5, 15, 3, 3, 15, -5, 20, 0,
0, -20, -40, -5, -5, -5, -5, -40, -20, 0,
0, 120, -20, 20, 5, 5, 20, -20, 120, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
};
public static int mobility (int player, OthelloBoard board)
{
return board.getAllMoves(player).size();
}
public static int mobilityDiff (int player, OthelloBoard board)
{
return mobility(player, board) - mobility(board.getOpponent(player), board);
}
public static int potentialMobility(int player, OthelloBoard board)
{
int opponent = board.getOpponent(player);
int[] cells = board.getCells();
int mob = 0;
for (int i = 10; i < 90; i++)
{
int col = i % 10;
if (col != 0 && col != 9)
{
if (cells[i] == opponent)
{
for (Integer dir : OthelloBoard.DIRECTIONS)
{
int around = dir + i;
if (cells[around] == OthelloBoard.EMPTY && cells[around] != OthelloBoard.WALL)
{
mob++;
break;
}
}
}
}
}
return mob;
}
public static int potentialMobilityDiff(int player, OthelloBoard board)
{
return potentialMobility(player, board) - potentialMobility(board.getOpponent(player), board);
}
public static int cornerSquares (int player, OthelloBoard board)
{
int corners = 0;
int[] cells = board.getCells();
for(int i = 0; i < cornerIndexes.length; i++)
if (cells[cornerIndexes[i]] == player)
corners++;
return corners;
}
public static int cornerSquaresDiff (int player, OthelloBoard board)
{
return cornerSquares(player, board) - cornerSquares(board.getOpponent(player), board);
}
public static int badXSquares (int player, OthelloBoard board)
{
int x = 0;
int[] cells = board.getCells();
for (int i = 0; i < 4; i++)
if ((cells[cornerIndexes[i]] != player) && (cells[xIndexes[i]] == player))
x++;
return x;
}
public static int badXSquaresDiff (int player, OthelloBoard board)
{
return badXSquares(player, board) - badXSquares(board.getOpponent(player), board);
}
public static int badCSquares (int player, OthelloBoard board)
{
int c = 0;
int[] cells = board.getCells();
int corner = 0;
for (int i = 0; i < cIndexes.length; i+= 2)
{
if (cells[cornerIndexes[corner++]] != player)
{
if (cells[cIndexes[i]] == player)
c++;
if (cells[cIndexes[i + 1]] == player)
c++;
}
}
return c;
}
public static int badCSquaresDiff (int player, OthelloBoard board)
{
return badCSquares(player, board) - badCSquares(board.getOpponent(player), board);
}
public static int discsDiff (int player, OthelloBoard board)
{
int playerDiscs = board.countDiscs(player);
int opponentDiscs = board.countDiscs(board.getOpponent(player));
return playerDiscs - opponentDiscs;
}
public static void scoreMoves(ArrayList<OthelloMove> moves)
{
for (OthelloMove mv : moves)
{
mv.setEval(squareValues[mv.getIdx()]);
}
}
public static float eval(int player, OthelloBoard board)
{
float value = 0.0f;
int phase = board.getPhase();
if (phase == OthelloBoard.PHASE_OPENING)
{
value = 100 * mobilityDiff(player, board) + 100 * potentialMobilityDiff(player, board)
+ 800 * cornerSquaresDiff(player, board)
- 200 * badXSquaresDiff(player, board) - 200 * badCSquaresDiff(player, board);
}
else if (phase == OthelloBoard.PHASE_MIDGAME)
{
value = 100 * mobilityDiff(player, board) + 100 * potentialMobilityDiff(player, board)
+ 900 * cornerSquaresDiff(player, board)
- 250 * badXSquaresDiff(player, board) - 200 * badCSquaresDiff(player, board);
}
else if (phase == OthelloBoard.PHASE_ENDGAME)
{
value = discsDiff(player, board);
}
else
{
System.out.println("Erro na heuristica: fase indeterminada.");
}
return value;
}
}
Testando
Já temos as peças necessárias para criar a engine, o que nos falta é implementar um game loop e criar uma GUI simples. A classe OthelloPiece nos ajuda a desenhar as peças. Segue a classe:
import javax.swing.*;
import java.awt.*;
import java.awt.geom.*;
public class OthelloPiece
{
private int color;
private int size;
public OthelloPiece(int color, int size)
{
this.color = color;
this.size = size;
}
public void draw(Graphics g, int x, int y)
{
Color col = null;
if (color == OthelloBoard.WHITE)
col = Color.white;
else
col = Color.black;
g.setColor(col);
g.fillOval(x, y, size, size);
}
}
A classe OthelloPanel abaixo implementa a GUI e o game loop:
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.ArrayList;
import java.util.Random;
import java.util.concurrent.*;
public class OthelloPanel extends JPanel implements Runnable
{
private int cellSize;
private int pieceSize;
private OthelloBoard board = null;
private int humanColor;
private int cpuColor;
private boolean waitingInput = false;
private boolean finished = false;
public static final int HUMAN = 100;
public static final int CPU = 200;
private int lastMoveIndex;
public OthelloPanel(int cellSize, int startPlayer)
{
board = new OthelloBoard();
if (startPlayer == HUMAN)
this.humanColor = OthelloBoard.BLACK;
else
this.humanColor = OthelloBoard.WHITE;
this.cpuColor = 3 - this.humanColor;
this.cellSize = cellSize;
this.pieceSize = (int)(cellSize * 0.75);
this.setDoubleBuffered(true);
int screenSize = (2 + OthelloBoard.BOARD_SIZE) * cellSize;
this.setPreferredSize(new Dimension(screenSize, screenSize));
this.addMouseWatcher();
UIManager.put("OptionPane.noButtonText", "N\u00E3o");
UIManager.put("OptionPane.yesButtonText", "Sim");
}
private boolean isFinished()
{
return board.checkEnd();
}
private boolean isHumanTurn()
{
return humanColor == board.getCurrentPlayer();
}
private void doLogic()
{
if (isFinished())
{
finished = true;
return;
}
//verifica somente uma vez se existem lances validos
//caso existam, espera por input
//caso contrario, faz lance fantasma
if (isHumanTurn())
{
if (waitingInput)
return;
ArrayList<OthelloMove> moves = board.getAllMoves(humanColor);
if (moves.get(0).getFlipSquares() == null)
{
board.makeMove(moves.get(0));
waitingInput = false;
}
else
{
waitingInput = true;
}
}
//dispacha uma nova Thread minimax, e espera a busca terminar
else
{
int maxDepth = 6;
boolean solve = board.getPhase() == OthelloBoard.PHASE_ENDGAME;
CountDownLatch signal = new CountDownLatch(1);
MinimaxOthello AI = new MinimaxOthello(board.cloneBoard(), maxDepth, signal, solve);
new Thread(AI).start();
try
{
signal.await();
}
catch(InterruptedException exception)
{
exception.printStackTrace();
}
OthelloMove mv = AI.getBestFound();
board.makeMove(mv);
//repaint();
lastMoveIndex = mv.getIdx();
System.out.println("AI move: " + mv.getIdx());
}
}
private void doInput(int index)
{
if (isHumanTurn())
{
int[] cells = board.getCells();
if (cells[index] != OthelloBoard.EMPTY)
return;
ArrayList<Integer> flips = board.getFlips(index, humanColor);
if (flips.size() > 0)
{
OthelloMove mv = new OthelloMove();
mv.setFlipSquares(flips);
mv.setIdx(index);
mv.setPlayer(humanColor);
board.makeMove(mv);
lastMoveIndex = index;
repaint();
waitingInput = false;
}
}
}
public void startNewGame()
{
board = new OthelloBoard();
finished = false;
waitingInput = false;
lastMoveIndex = -666;
//troca cores
int temp = cpuColor;
cpuColor = humanColor;
humanColor = temp;
new Thread(this).start();
}
public void run()
{
while (! finished)
{
this.doLogic();
this.repaint();
try
{
Thread.sleep(20L);
}
catch (InterruptedException exception)
{}
}
//fim de jogo
int human = board.countDiscs(humanColor);
int cpu = board.countDiscs(cpuColor);
int empty = OthelloBoard.BOARD_SIZE * OthelloBoard.BOARD_SIZE - (human + cpu);
String msg = null;
if (human > cpu)
{
human += empty;
msg = "Voce venceu por " + human + " - " + cpu + "!";
}
else if (human < cpu)
{
cpu += empty;
msg = "Voce perdeu por " + cpu + " - " + human + "!";
}
else
msg = "Empate!";
msg += "\nDeseja jogar uma nova partida?";
int x = JOptionPane.showConfirmDialog(null, msg, "Game Over", JOptionPane.YES_NO_OPTION);
if (x == 0)
startNewGame();
}
private void drawGUI(Graphics g)
{
Graphics2D g2D = (Graphics2D) g;
g2D.setStroke(new BasicStroke(1.5f));
//cor de fundo
Color bg = new Color(0, 130, 0);
setBackground(Color.gray);
int w = OthelloBoard.BOARD_SIZE * cellSize;
int origin = cellSize;
//linhas horizontais
g.setColor(Color.black);
for (int i = 0; i < OthelloBoard.BOARD_SIZE + 1; i++)
{
g.drawLine(origin, i * cellSize + origin, origin + w, i * cellSize + origin);
}
//linhas verticais
for (int i = 0; i < OthelloBoard.BOARD_SIZE + 1; i++)
{
g.drawLine(i * cellSize + origin, origin, i * cellSize + origin, w + origin);
}
g.setColor(Color.white);
//headers
String[] headers = new String[]{"A","B","C","D","E","F","G","H"};
for (int i = 0; i < OthelloBoard.BOARD_SIZE; i++)
g.drawString(headers[i], cellSize * i + (int)(origin * 1.5), (int)(cellSize * 0.75));
//linhas
for (int i = 0; i < OthelloBoard.BOARD_SIZE; i++)
g.drawString("" + (i + 1), (int)(cellSize * 0.6), cellSize * i + (int)(origin * 1.5));
}
private void drawScore(Graphics g)
{
//score
g.setColor(Color.yellow);
g.setFont(new Font(null, Font.BOLD, 15));
int wd = board.countDiscs(OthelloBoard.WHITE);
int bd = board.countDiscs(OthelloBoard.BLACK);
g.drawString("White: " + wd, cellSize * 1, (int)(cellSize * 9.5));
g.drawString("Black: " + bd, cellSize * 8, (int)(cellSize * 9.5));
}
private void drawBoard(Graphics g)
{
int[] cells = board.getCells();
int gameCols = OthelloBoard.BOARD_SIZE;
int hiddenCols = gameCols + 2;
int mid = (cellSize - pieceSize)/2;
for (int i = hiddenCols; i < cells.length - hiddenCols; i++)
{
int col = i % hiddenCols;
int row = i / hiddenCols;
if ((col != 0) && (col != hiddenCols - 1))
{
int piece = cells[i];
if (piece == OthelloBoard.EMPTY)
continue;
OthelloPiece p = new OthelloPiece(cells[i], pieceSize);
p.draw(g, col * cellSize + mid, row * cellSize + mid);
}
}
//lance fantasma idx = -666
if (lastMoveIndex > 0)
{
g.setColor(Color.yellow);
int col = lastMoveIndex % hiddenCols;
int row = lastMoveIndex / hiddenCols;
g.drawRect(col * cellSize, row * cellSize, cellSize, cellSize);
}
}
private void drawMoves(Graphics g)
{
ArrayList<OthelloMove> moves = board.getAllMoves(humanColor);
if (isHumanTurn() && moves.get(0).getFlipSquares() != null)
{
g.setColor(new Color(0, 0, 0, 80));
for (OthelloMove mv : moves)
{
int idx = mv.getIdx();
int col = idx % 10;
int row = idx /10;
g.fillOval(col * cellSize + cellSize/2, row * cellSize + cellSize/2, cellSize/8, cellSize/8);
}
}
}
public void paintComponent(Graphics g)
{
super.paintComponent(g);
Graphics2D g2 = (Graphics2D) g;
g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
this.drawGUI(g);
this.drawBoard(g);
this.drawScore(g);
this.drawMoves(g);
}
//mouse
private void addMouseWatcher()
{
this.addMouseListener(new MouseAdapter()
{
public void mousePressed(MouseEvent e)
{
int col = e.getX()/cellSize;
int row = e.getY()/cellSize;
int index = row * (OthelloBoard.BOARD_SIZE + 2) + col;
if ((row > 0 && row < 9) && (col > 0 && col < 9))
doInput(index);
}
});
}
public static void main (String[] args) throws Exception
{
OthelloPanel panel = new OthelloPanel(60, HUMAN);
JFrame window = new JFrame("Othello");
window.getContentPane().add(panel);
window.setResizable(false);
window.pack();
window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
window.setVisible(true);
new Thread(panel).start();
}
}
Eu particularmente não consegui vencer a engine, pois como disse sou péssimo jogador. Testando contra algumas applets o desempenho foi bem convincente, perdendo apenas para os programas que utilizam inúmeros padrões pré-calculados e implementam uma heurística mais refinada. Bons jogos e até o próximo post!
Nenhum comentário:
Postar um comentário