conecta 4 con inteligencia artificial

[minoskum]

Hola .. mi problema es el siguente:
necesito hacer una clase para la uni de un jugador de conecta 4 con un método que realice una jugada no aleatoria osea que busque la victoria o el empate..
Para esto me dijeron que tenia que usar un árbol donde en cada nodo tengo un tablero con cada movimiento que pueda hacer el otro jugador ...pero no lo veo muy claro..
he visto x otros foros que para esto se usa el metodos min max ..pero no tengo ni idea de como hacerlo.
El tablero es de 6x7 y bueno pongo los métodos que ya tengo..por si s interesa..

public abstract String nextMove(); //que es el que necesito

public abstract boolean validMove(int player, String move); //que verifica que se elige una columna valida y no este llena.

public abstract boolean doMove(int player, String move); //realiza el movimiento

public abstract int winner(); //devuelve el ganador ,quien consiga 4 en linea