Jogo da Velha

• Camada de modelo com implementação de AI para jogo da velha utilizando o algoritmo minimax
• Ótima referência: http://ai-depot.com/articles/minimax-explained/

Anotações

• Finalmente entendi o algoritmo minimax, basicamente funciona da seguinte forma: a partir do estado atual do jogo, deve se criar uma árvore do jogo contendo todas as possíveis jogadas. É atribuído uma nota para cada jogada que indica o quão bom é aquele movimento para se ganhar o jogo (função heurística). Por exemplo, podemos atribuir a nota 1 se AI ganhar, 0 se empatar e -1 se perder. Desta forma, na vez do AI jogar, dentre as possíveis jogadas, deve-se pegar o ramo com a maior nota obviamente para ter mais chances de ganhar. Já, no nodo da vez do jogador, deve se pegar o ramo com a pior nota prevendo que ele fará a melhor jogada.

• Obs.: "Deste modo para um problema que não se conhece qual e' o melhor caminho em busca de uma solução, define-se uma função heurística que acredita-se levara a esta solução"

Código Fonte

package javaapplication186;

/**
 *
 * @author leonardo
 */
public class Model2 {

    // 1 2 4 8 16 32 64 128 256
    int b1;
    int b2;
    private int[] winCombinations = {7, 56, 73, 84, 146, 273, 292, 448};

    public void start() {
        b1 = b2 = 0;
    }

    public void play(int x, int y) {
        b1 = b1 | (int) Math.pow(2, x + y * 3);
    }

    public void playAI() {
        b2 = b2 | minimax(b1, b2, 0, 1);
    }

    private int minimax(int b1, int b2, int p, int j) {
        Integer v = null;
        int bestMove = 0;
        int b = b1 | b2;
        for (int i = 1; i <= 256; i *= 2) {
            if ((b & i) != i) {
                int b1c = (j == 0) ? (b1 | i) : b1;
                int b2c = (j == 1) ? (b2 | i) : b2;
                int pv = 0;
                pv = (j == 0 && checkW(b1c)) ? -1 : pv;
                pv = (j == 1 && checkW(b2c)) ? 1 : pv;
                pv = (pv != 0) ? pv : minimax(b1c, b2c, p + 1, (j + 1) % 2);
                if (v == null || (j == 0 && pv < v) || (j == 1 && pv > v) 
                        || (j == 0 && pv == v && System.nanoTime()%2==0) 
                        || (j == 1 && pv == v && System.nanoTime()%2==0)) {
                    v = pv;
                    bestMove = i;
                }
            }
        }
        return (p == 0) ? bestMove : ((v == null) ? 0 : v);
    }

    public boolean checkW(int b) {
        boolean win = false;
        for (int winCombination : winCombinations) {
            win = win || ((b & winCombination) == winCombination);
        }
        return win;
    }
    
}