No post anterior implementamos o cliente Tetris e testamos sua funcionalidade. Na segunda parte da série, daremos início a parte realmente interessante: AI. Para começar, a classe TetrisAgent será discutida em detalhes, já que os agentes serão a população alvo do algoritmo. Além disso iremos implementar duas classes que definem habilidades importantes: listar os lances possíveis e avaliar as posições resultantes.
Classe TetrisAgent
Essa é a classe base de nossa AI, e representa um jogador de Tetris. Três variáveis de instância são definidas: genes, clearedRowsArray e fitness. A habilidade de cada agente é expressa através de seus genes, onde cada slot da array genes corresponde ao peso atribuído a determinada característica da grade. Sabemos por experiência que determinados padrões da grade resultam em maiores chances de efetuar pontos, ou menores chances de game over.
No nosso caso, a array genes corresponde ao peso de 7 características distintas: 3 delas são consideradas básicas e 4 são menos óbvias. Dentre as básicas temos: número de linhas feitas, altura máxima da pilha e número de buracos não conectados. As outras são: número de buracos conectados, número de blocos acima de buracos, número de poços e nivelação da grade. Para efeito de testes, setamos genes com valores arbitrários entre 0 e 1, mas fique a vontade para alterar esses valores e observar o efeito no desempenho do agente. Como comentado acima, os valores finais serão determinados pela GA.
Nossa tarefa consiste em determinar o melhor agente possível, ou seja, quais são os valores de genes que resultam no maior número médio de linhas removidas? Durante a execução da GA, cada agente jogará uma sequência de n games aleatórios, onde a sequência de peças em cada um dos n games será fixada semeando-se o gerador numérico. Em outras palavras, todos os agentes enfrentarão os mesmo jogos, o que nos permite balancear o efeito de um agente ruim receber uma sequência boa de peças, ou um agente bom receber uma sequência ruim de peças. A variável fitness quantifica as definições acima, e será calculada como a média de linhas removidas durante os n games.
Finalmente, temos a variável clearedRowsArray, que irá armazenar o número de linhas removidas em cada jogo. Repare que estamos utilizando uma ArrayList sincronizada, pois como comentado no post anterior, cada game será executado em uma Thread separada, e também sabemos que o mesmo agente será compartilhado por n Threads. O problema em utilizar uma ArrayList padrão surge ao invocar agent.clearedRowsArray.add(linhas): caso duas Threads se esbarrem nesse método, uma ConcurrentModificationException seria lançada, terminando o programa.
Os métodos definidos são simples: eval recebe uma array com a configuração da grade, e utiliza os métodos estáticos da classe BoardEvaluator para avaliar a posição. A interface Comparable é implementada, nos permitindo ordenar agentes facilmente, o que será útil mais adiante. O método estático randomAgent simplesmente cria um novo agente e seta seus genes com valores randômicos entre 0 e 1. Por fim, cloneAgent retorna um novo objeto com os mesmos genes do agente que invoca o método. Segue a classe TetrisAgent:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
public class TetrisAgent implements Comparable
{
float[] genes = new float[]{ 0.6f, 0.3f, 0.05f, 0.1f, 0.1f, 0.1f, 0.2f};
List<Integer> clearedRowsArray = Collections.synchronizedList(new ArrayList<Integer>());
float fitness;
public float eval(int[][]board)
{
float sum = 0.0f;
sum += genes[0] * BoardEvaluator.clearedRows(board);
sum -= genes[1] * BoardEvaluator.pileHeight(board);
sum -= genes[2] * BoardEvaluator.countSingleHoles(board);
sum -= genes[3] * BoardEvaluator.countConnectedHoles(board);
sum -= genes[4] * BoardEvaluator.blocksAboveHoles(board);
sum -= genes[5] * BoardEvaluator.countWells(board);
sum -= genes[6] * BoardEvaluator.bumpiness(board);
return sum;
}
public int compareTo(Object obj)
{
if (obj instanceof TetrisAgent)
{
TetrisAgent other = (TetrisAgent) obj;
if (this.fitness > other.fitness)
return 1;
else if (this.fitness < other.fitness)
return -1;
}
return 0;
}
public static TetrisAgent randomAgent()
{
TetrisAgent agent = new TetrisAgent();
Random random = new Random();
for (int i = 0; i < agent.genes.length; i++)
agent.genes[i] = random.nextFloat();
return agent;
}
public TetrisAgent cloneAgent()
{
TetrisAgent cloneAgent = new TetrisAgent();
for (int i = 0; i < this.genes.length; i++)
cloneAgent.genes[i] = this.genes[i];
return cloneAgent;
}
}
Classe BoardEvaluator
Esta classe define métodos estáticos, utilizados pelo agente para avaliar determinada configuração da grade. Os métodos clearedRows, pileHeight e countSingleHoles retornam o número de linhas removidas, a altura máxima, e o número de buracos, respectivamente.
O método countConnectedHoles retorna o número de buracos conectados, ou seja, buracos adjacentes são contados apenas uma vez. O método blocksAboveHoles retorna a quantidade de blocos que se encontram acima de buracos.
O método countWells retorna o número de poços, ou seja, regiões onde somente a peça do tipo I pode ser encaixada sem deixar buracos. Por fim, bumpiness calcula a nivelação da grade, observando as diferenças de altura entre colunas adjacentes. Com exceção de clearedRows, admitimos que todas as características avaliadas contribuem para o deterioramento da posição, por isso o sinal negativo. Segue a classe BoardEvaluator:
public class BoardEvaluator
{
public static int clearedRows(int[][] board)
{
int cleared = 0;
int columns = board[0].length;
for(int y = 0; y < board.length - 1; y++)
{
boolean ok = true;
for(int x = 1; (x < columns - 1) && ok; x++)
if(board[y][x] == 0)
ok = false;
if(ok) cleared++;
}
return cleared;
}
public static int pileHeight(int[][] board)
{
int columns = board[0].length;
for(int y = 0; y < board.length - 1; y++)
{
for(int x = 1; x < columns - 1; x++)
{
if(board[y][x] != 0)
return board.length - 1 - y;
}
}
return 0;
}
public static int countSingleHoles(int[][] board)
{
int holes = 0;
int columns = board[0].length;
for (int j = 1; j < columns - 1; j++)
{
boolean swap = false;
for (int i = 0; i < board.length - 1; i++)
{
if (board[i][j] != 0)
swap = true;
else
{
if (swap)
holes++;
}
}
}
return holes;
}
public static int countConnectedHoles(int[][] board)
{
int holes = 0;
int columns = board[0].length;
for (int j = 1; j < columns - 1; j++)
{
boolean swap = false;
for (int i = 0; i < board.length - 1; i++)
{
if (board[i][j] != 0)
swap = true;
else
{
if (swap)
holes++;
swap = false;
}
}
}
return holes;
}
public static int blocksAboveHoles(int[][] board)
{
int blocks = 0;
int cols = board[0].length;
for(int c = 1; c < cols - 1; c++)
{
boolean swap = false;
for (int r = board.length - 2; r >= 0; r--)
{
if (board[r][c] == 0)
swap = true;
else
{
if (swap)
blocks++;
}
}
}
return blocks;
}
public static int countWells(int[][] board)
{
int cols = board[0].length;
int wells = 0;
//da segunda até a penultima coluna
for (int col = 2; col < cols - 2; col++)
{
for (int row = 0; row < board.length - 1; row++)
{
if ((board[row][col - 1] > 0) && (board[row][col + 1] > 0) && (board[row][col] == 0))
wells++;
else if (board[row][col] > 0)
break;
}
}
//primeira coluna
for (int row = 0; row < board.length - 1; row++)
{
if ((board[row][1] == 0) && (board[row][2] > 0))
wells++;
else if (board[row][1] > 0)
break;
}
//ultima coluna
for (int row = 0; row < board.length - 1; row++)
{
if ((board[row][cols - 3] > 0) && (board[row][cols - 2] == 0))
wells++;
else if (board[row][cols - 2] > 0)
break;
}
return wells;
}
public static float bumpiness(int[][] board)
{
int cols = board[0].length;
int[] heights = new int[cols - 2];
for(int x = 1; x < cols - 1; x++)
{
for(int y = 0; y < board.length - 1; y++)
{
if(board[y][x] != 0)
{
heights[x - 1] = board.length - 1 - y;
break;
}
}
}
float bmp = 0.0f;
for (int i = 0; i < cols - 3; i++)
{
float diff = Math.abs(heights[i] - heights[i + 1]);
bmp += diff;
}
return bmp;
}
} //fim da classe BoardEvaluator
Classe TetrisMove
Objetos dessa classe representam um lance que pode ser feito, dado determinada peça e board. Os campos position e rotation representam a posição em que a peça será encaixada e a rotação, respectivamente. O campo eval representa a qualidade deste lance, de acordo com a avaliação do agente. Segue a classe TetrisMove:
public class TetrisMove
{
Point position = new Point(0, 0);
int rotation;
float eval;
public TetrisMove(){}
public TetrisMove(Point p, int rot )
{
this.position = p;
this.rotation = rot;
}
}
Classe MoveSearcher
Outra classe com métodos estáticos, mas desta vez a idéia é listar todos os lances possíveis, retornando o melhor. O código de getValidMoves parece complicado, mas é bem simples: (i) movemos a peça o máximo possível para a esquerda e (ii) fazemos um drop, adicionando o lance resultante na lista. (iii) Voltamos a peça verticalmente para o topo e movemos para a direita. Os processos (ii) e (iii) são repetidos até ser impossível mover para direita, quando passamos para a próxima rotação e repetimos a partir de (i).
Repare que o agente é passado como argumento, e o método eval do objeto TetrisAgent é invocado. Outro detalhe importante é o método removePiece da classe TetrisBoard, queé utilizado para desfazer o lance, logo após efetuar o drop. O método getBestMove simplesmente invoca getValidMoves e retorna o lance com maior eval. Segue a classe MoveSearcher:
import java.util.ArrayList;
public class MoveSearcher
{
public static ArrayList<TetrisMove> getValidMoves (TetrisBoard board, TetrisPiece piece, TetrisAgent agent)
{
ArrayList<TetrisMove> moves = new ArrayList<TetrisMove>();
Point originalPosition = new Point(piece.position.x, piece.position.y);
for (int i = 0; i < 4; i++)
{
piece.rotation = i;
int startY = piece.position.y;
while (board.canMoveLeft(piece))
piece.moveLeft();
do
{
while(board.canMoveDown(piece))
piece.moveDown();
board.updateBoard(piece);
float eval = agent.eval(board.board);
TetrisMove tempMove = new TetrisMove();
tempMove.eval = eval;
tempMove.position.x = piece.position.x;
tempMove.position.y = piece.position.y;
tempMove.rotation = piece.rotation;
moves.add(tempMove);
board.removePiece(piece);
piece.position.y = startY;
if (! board.canMoveRight(piece))
{
break;
}
else
{
piece.moveRight();
}
} while(true);
piece.position = originalPosition;
}
return moves;
}
public static TetrisMove getBestMove (TetrisBoard board, TetrisPiece piece, TetrisAgent agent)
{
TetrisMove best = null;
ArrayList<TetrisMove> moves = getValidMoves(board, piece, agent);
for(TetrisMove move : moves)
{
if (best == null)
best = move;
else if (move.eval > best.eval)
best = move;
}
return best;
}
} //fim da classe MoveSearcher
Classe AIGame
Essa classe define o game loop da AI, nos permitindo visualizar o agente jogando. Como comentado anteriormente, durante a execução da GA, cada agente será compartilhado por n Threads diferentes, onde cada Thread representa um game com uma sequência fixa de peças. Veja a figura abaixo:
No post anterior, implementamos a classe GamePanel, que permite a execução de um game em uma Thread separada, aceitando input do teclado. Nest post, AIGame irá herdar de GamePanel e sobrescrever o método run.
Olhando um pouco adiante, sabemos que a qualidade de cada agente será quantificada tomando-se a média do número de linhas removidas em n games. Ou seja, para calcular esse valor, devemos nos certificar de que todas as Threads deste agente tenham finalizado a execução. A classe CountDownLatch, do pacote java.util.concurrent, nos permite fazer essa sincronia facilmente. Como estamos testando apenas um agente, não há necessidade de sincronia, e a variável doneSignal será null por enquanto. A variável cleared representa o número de linhas removidas ao fim do jogo.
O override do método run é simples: Consultamos MoveSearcher para obter o melhor lance, passando como argumentos a grade, uma cópia da peça e o agente. Atualizamos o estado do game de maneira similar ao método da superclasse, mas aqui incrementamos a variável cleared a cada linha removida. Fazemos a Thread dormir por um pequeno intervalo de tempo, o que permite uma renderização mais suave.
Em caso de game over, atualizamos a variável clearedRows do agente e invocamos doneSignal.countDown, sinalizando que esta Thread finalizou seu trabalho. Esse mecanismo ficará claro no próximo post, mas por enquanto não faz diferença, afinal doneSignal é null por enquanto. Segue a classe AIGame:
import java.util.Random;
import javax.swing.*;
import java.awt.*;
import java.util.concurrent.*;
import java.io.*;
public class AIGame extends GamePanel
{
private CountDownLatch doneSignal;
private boolean doSleep = false;
TetrisAgent agent = new TetrisAgent();
int cleared = 0;
public AIGame(int r, int c, int bs, int seed, CountDownLatch signal)
{
this(r, c, bs, seed, false);
this.doneSignal = signal;
}
public AIGame(int r, int c, int bs, int seed, boolean doSleep)
{
super(r, c, bs, seed);
this.doSleep = doSleep;
}
public AIGame(int r, int c, int bs, boolean doSleep)
{
super(r, c, bs);
this.doSleep = doSleep;
}
public void run()
{
fallingPiece = randomPiece();
while (!gameOver)
{
if (board.canMoveDown(fallingPiece))
{
TetrisMove bestMove = MoveSearcher.getBestMove(board, fallingPiece.clonePiece(), agent);
fallingPiece.position = bestMove.position;
fallingPiece.rotation = bestMove.rotation;
board.updateBoard(fallingPiece);
}
else
{
board.updateBoard(fallingPiece);
cleared +=board.checkCompleteRows();
addNewPiece();
}
if (doSleep)
{
try
{
Thread.sleep(20L);
}
catch(InterruptedException ex){}
}
repaint();
}
agent.clearedRowsArray.add(cleared); //acessado por varias threads!
if (doneSignal != null)
doneSignal.countDown();
}
} //fim da classe AIGame
Testando o agente
Chegou a hora de testar a estrutura da AI, colocando um agente para jogar. Lembrando que o agente teve seus genes hard-coded na classe TetrisAgent, você pode alterar esses valores manualmente ou simplesmente usar ai.agent = TetrisAgent.randomAgent(), e testar um agente randômico. Segue a classe TestAgent:
import javax.swing.*;
import java.awt.*;
public class TestAgent
{
public static void main (String[] args)
{
JFrame f = new JFrame();
int rows = 20, cols = 10, block = 32;
boolean sleep = true; //para atualizar o panel
AIGame ai = new AIGame(rows, cols, block, sleep);
ai.setBackground(Color.black);
f.add(ai);
f.pack();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.setResizable(false);
f.setVisible(true);
new Thread(ai).start();
}
}
No próximo post iremos implementar a GA e observar a evolução dos agentes. Caso esteja curioso, substitua os genes por esses valores (na ordem): 0.95856917f, 0.08560386f, 0.9476838f, 0.58525276f,0.0291457f, 0.18112998f, 0.17345366f e execute o programa algumas vezes. Até a próxima!
Nenhum comentário:
Postar um comentário