No post anterior criamos o framework basico do game e vimos (deforma bem simplificada) alguns conceitos sobre o Minimax.Neste post vamos colocar esses conceitos em pratica, alem de utilizar podaalfa - beta e ordenacao de lances para melhorar o desempenhoda engine, fundamental caso voce esteja desenvolvendo para alguma plataformamobile.Classe MinimaxOthello Entender essa classe e o objetivo deste topico. O Minimax com poda alfa-beta e um desses casos onde e facil entender o algoritmo, mas e dificil visualizar o mecanismo. Ao longo do algoritmo, mantemos referencia a variavel de instancia bestFound, que representa o melhor lance encontrado ate entao. Por ser recursivo e consumir bastante CPU, a cada lance da AI criamos uma nova Thread e esperamos run() retornar, apos isso obtemos o melhor lance com getBestFound(). Repare no construtor, que precisa saber qual posicao queremos analisar, qual a profundidade maxima que iremos atingir, e se queremos ou nao analisar ate o fim do jogo. Obviamente, analisar a arvore de posicoes ate o fim so e possivel na fase final do jogo, e o caller do algoritmo deve decidir quando isso acontece. No comeco do algoritmo, checamos se atingimos uma posicao final ou a profundidade maxima. No primeiro caso, retornamos um valor evalGameOver na faixa -INFINITO < evalGameOver < INFINITO, que sera positivo caso currentPlayer tenha vencido, negativo caso tenha perdido, ou zero no empate. Caso a profundidade maxima seja atingida e solve == false, retornamos o valor da posicao atingida, caso solve == true, seguimos expandindo a arvore ate chegar em um no terminal. Seguindo em frente, obtemos uma lista com os lances validos para a posicao atual e os ordenamos, logo apos setar a variavel eval de cada lance, com o metodo estatico scoreMoves da classe OthelloHeuristics. Em seguida vem a parte magica: para cada lance da lista, aplicamos esse lance na posicao atual, e invocamos recursivamente o algoritmo. Ao invocar a recursao, o objeto board sera alterado, e e por isso que na proxima linha desfazemos o lance com undoMove. Podiamos criar uma copia profunda do objeto board e usar esta copia na recursao, eliminando undoMove, mas criando milhares (ou milhoes) de novos objetos a cada chamada. Nem sempre e facil implementar undoMove, mas vale bastante a pena em termos de memoria (mais tarde vamos olhar a variavel calls). O algoritmo e intrincado, mas a estrutura e a mesma para qualquer aplicacao. 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