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 e bastante rico em termos de estrategia. Alguns conceitos encontrados no xadrez tambem se aplicam ao jogo: mobilidade, controle do centro, aberturas e tempo, para citar alguns. Como sou um pessimo jogador, uma breve pesquisa me esclareceu os seguintes pontos: Apenas contar pecas e uma pessima estrategia, quase sempre levando a derrota O controle das 'quinas' (corner squares) e 'bordas' (edge squares) e fundamental A mobilidade e fundamental Existem outros conceitos igualmente importantes ('paridade' por exemplo) mas a lista acima ja e um bom comeco. As estrategias acima estao relacionadas com o conceito de 'disco estavel', que sao os discos que uma vez conquistados, nao podem mais ser 'flipados' pelo seu adversario. Repare que ao conquistar uma quina, podemos utiliza-la como pivo para novos discos estaveis, o que geralmente garante uma boa vantagem. E claro que o seu adversario tambem sabe disso, e nao vai te entregar as corner squares de graca, o que nos leva ao conceito de mobilidade. Para forcar seu adversario a fazer lances ruins, devemos ter uma mobilidade superior (maior numero de opcoes a cada jogada) e tirar proveito disso forcando o adversario a entregar uma ou mais quinas. Geralmente lances adjacentes a quina sao fracos, pois levam a perda desta. As duas casas adjacentes lateralmente a uma quina sao chamadas de 'C squares', e a casa diagonalmente adjacente a quina e conhecida como 'X square'. Esses sao os fatores que vamos considerar na nossa heuristica, o que ja garante um desempenho razoavel contra um jogador mediano. Um dos fatores que nao estamos levando em conta e que melhoraria muito a forca da engine, sao os edge patterns, ou padoes da borda. Se levarmos em conta a quina, cada borda possui 310 = 59049 configuracoes, que geralmente sao pre-calculadas e acessadas durante a avaliacao da posicao. A heuristica utilizada e bem simples: dependendo da fase do jogo, atribuimos pesos diferentes para cada caracteristica abaixo: mobilidade mobilidade potencial corner squares C squares X squares numero de discos Observe que na fase final do game consideramos apenas o numero de discos, ja que a busca ocorre ate uma posicao finalizadora ser alcancada. A mobilidade potencial conta o numero de casas vazias com pelo menos uma peca