Hola
Hace unos días asistí en el colegio de mi hija a una charla donde debía explicar a qué me dedicaba a los chavales de su clase. Como no sabía por donde meterle mano pensé en explicarles las bases de un algoritmo típico en juegos de mesa contra un openente, el minimax. El algoritmo está suficientemente explicado en muchas páginas como: http://es.wikipedia.org/wiki/Minimax
Por ello, recordando viejos tiempos de facultad me puse a programar el minimax para el juego de las tres en raya. Dejo aquí las distintas clases generadas.
Cada clase y método están suficientemente comentados como para no necesitar añadir nada mas.
1.- Lanzador del aplicativo
package org.dune.juegos;
import java.awt.BorderLayout;
import java.awt.EventQueue;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import javax.swing.JFrame;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;
import javax.swing.JPanel;
import javax.swing.UIManager;
import java.awt.SystemColor;
public class TresR {
private JFrame frame;
/**
* Lanzador de la aplicación tres en raya
*/
public static void main(String[] args) {
EventQueue.invokeLater(new Runnable() {
public void run() {
try {
final TresR tr = new TresR();
tr.frame.setVisible(true);
} catch (Exception e) {
e.printStackTrace();
}
}
});
}
/**
* Constructor
*/
public TresR() {
//Inicializamos entorno grafico
inicializaPantalla();
}
private void inicializaPantalla() {
//Definimos la pantalla del juego
frame = new JFrame();
frame.setBackground(SystemColor.control);
frame.getContentPane().setBackground(SystemColor.control);
frame.setBounds(100, 100, 800, 600);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.getContentPane().setLayout(null);
//Definimos el contenedor del tablero
final JPanel cajaTablero = new JPanel();
cajaTablero.setBounds(12, 71, 756, 471);
cajaTablero.setBackground(SystemColor.control);
frame.getContentPane().add(cajaTablero);
cajaTablero.setLayout(new BorderLayout(0, 0));
//Definimos la barra de menú
final JMenuBar menuBar = new JMenuBar();
menuBar.setBackground(SystemColor.control);
menuBar.setBounds(0, 0, 780, 21);
frame.getContentPane().add(menuBar);
//Definimos el menú Juego
final JMenu mJuego = new JMenu("Juego");
final JMenuItem smEmpezar = new JMenuItem("Empezar");
final JMenuItem smSalir = new JMenuItem("Salir");
mJuego.add(smEmpezar);
mJuego.add(smSalir);
menuBar.add(mJuego);
//Definimos el menú ayuda
final JMenu mAyuda = new JMenu("Ayuda");
final JMenuItem smInfo = new JMenuItem("Info");
mAyuda.add(smInfo);
menuBar.add(mAyuda);
//Definimos la acción de la opción de menú Empezar
smEmpezar.addMouseListener(new MouseAdapter() {
@Override
public void mousePressed(MouseEvent e) {
//Pintamos el tablero
final Tablero pTablero = new Tablero();
cajaTablero.removeAll();
cajaTablero.add(pTablero);
frame.setVisible(true);
}
});
//Definimos la acción de la opción de menú Salir
smSalir.addMouseListener(new MouseAdapter() {
@Override
public void mousePressed(MouseEvent e) {
//Salimos del juego
System.exit(0);
}
});
//Definimos la acción de la opción de menú info
smInfo.addMouseListener(new MouseAdapter() {
@Override
public void mousePressed(MouseEvent e) {
//Pintamos la pantalla de ayuda
final Info pInfo = new Info();
cajaTablero.removeAll();
cajaTablero.add(pInfo);
frame.setVisible(true);
}
});
}
}
2.- Tablero
package org.dune.juegos;
import java.awt.Button;
import java.awt.Font;
import java.awt.GridLayout;
import java.awt.SystemColor;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.UIManager;
public class Tablero extends JPanel implements ActionListener {
private static final long serialVersionUID = -6025639950351265124L;
//Botonera que representa el tablero
final Button botonesCasillas[][] = new Button[3][3];
//Estructura de memoria con las casillas del juego
int matrizTablero[][] = new int[3][3];
//Implementación del algoritmo minimax
final MiniMax minimax;
//Indicador de turno de jugador
boolean turnoHumano;
/**
* Constructor del panel
*/
public Tablero() {
//Define el contenido del panel
setBackground(UIManager.getColor("info"));
setLayout(new GridLayout(3, 3, 0, 0));
for (int i=0; i<3; i++) {
for (int j=0; j <3; j++) {
botonesCasillas[i][j] = new Button();
botonesCasillas[i][j].setBackground(SystemColor.control);
botonesCasillas[i][j].setFont(new Font("Arial",Font.BOLD,60));
botonesCasillas[i][j].addActionListener(this);
this.add(botonesCasillas[i][j]);
}
}
//Inicializamos variables de la partida
turnoHumano = true;
//Limpia los botones del tablero
limpiaBotones();
//Iniciamos el minimax
minimax = new MiniMax(3,3);
}
/**
* Interprete de las acciones del usuario.
*/
public void actionPerformed(ActionEvent e){
//Movimiento decidido por el ordenador
Movimiento mov;
//Si el turno era del humano
if(turnoHumano==true){
//Quitamos el turno al humano
turnoHumano = false;
//Revisa qué casilla ha pulsado
for (int i=0;i<3;i++) {
for (int j=0;j<3;j++) {
//Mira si la casilla pulsada por el humaon estaba libre
if ((e.getSource()==botonesCasillas[i][j]) && (botonesCasillas[i][j].getLabel().equals(""))){
//Pone en la casilla una P
botonesCasillas[i][j].setLabel("P");
matrizTablero[i][j] = MiniMax.CASILLA_PERSONA;
//Lanza el algoritmo minimax y recoge el movimiento elegido
mov = minimax.minimax(matrizTablero);
if (mov.getPosX()!=-1 && mov.getPosY()!=-1) {
//Introducimos un retardo
retarda(500);
//Dibujamos el movimiento del ordenador
botonesCasillas[mov.getPosX()][mov.getPosY()].setLabel("O");
matrizTablero[mov.getPosX()][mov.getPosY()]=MiniMax.CASILLA_ORDENADOR;
//Si hay ganador quito el turno al humano para que no pueda mover mas
if(minimax.haGanadoJugador(MiniMax.CASILLA_PERSONA)) {
turnoHumano=false;
JOptionPane.showMessageDialog(null, "ME HAS GANADO");
} else if (minimax.haGanadoJugador(MiniMax.CASILLA_ORDENADOR)) {
turnoHumano = false;
JOptionPane.showMessageDialog(null, "JE JE JE, SIEMPRE GANO YO...");
} else {
turnoHumano = true;
}
} else {
turnoHumano = false;
JOptionPane.showMessageDialog(null, "HEMOS VUELTO A EMPATAR");
}
}
}
}
}
}
private void retarda(int milis){
try {
Thread.sleep(milis);
} catch (InterruptedException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
}
/**
* Limpia los botones del tablero
*/
private void limpiaBotones(){
for (int i=0; i<3; i++) {
for (int j=0; j <3; j++) {
botonesCasillas[i][j].setLabel("");
}
}
}
}
3.- Implementación del minimax
package org.dune.juegos;
public class MiniMax {
public static final int CASILLA_VACIA = 0;
public static final int CASILLA_PERSONA = 1;
public static final int CASILLA_ORDENADOR = 2;
private int tableroActual[][];
private int numCols;
private int numFils;
/**
* Recibe los datos del tablero de juego.
*
* @param anchura Dimensión horizontal del tablero.
* @param altura Dimensión vertical del tablero.
*/
public MiniMax(int anchura, int altura) {
super();
this.numCols = anchura;
this.numFils = altura;
this.tableroActual = new int[numCols][numFils];
}
/**
* Es el turno del ordenador y en base al tablero actual decidimos el movimiento a realizar.
*/
public Movimiento minimax(int[][] tableroParam){
this.tableroActual = tableroParam;
int posX=-1;
int posY=-1;
int aux=-9999;
int mejor=-9999;
for (int x=0;x<this.numCols;x++){
for (int y=0;y<this.numFils;y++){
if (isCasillaVacia(x,y)){
marcarCasilla(x,y,CASILLA_ORDENADOR);
aux = min();
if (aux>mejor) {
mejor=aux;
posX=x;
posY=y;
}
marcarCasilla(x,y,CASILLA_VACIA);
}
}
}
return new Movimiento(posX,posY);
}
/**
* El último jugador que marcó alguna casilla fue el ordenador, por lo que analizamos los posibles
* movimientos de la persona.
*
* Si estamos en un nodo hoja devolvemos la valoración del tablero, puede que haya ganado el ordenador
* o puede que sigamos empatados, así que hay dos posibles valores: 1 (gana el ordenador)
* y 0 (seguimos empatados).
*
* Si no es nodo hoja recorremos las casillas vacías simulando ser el jugador humano, y llamando
* a continuación al método MAX. Llamamos a MAX porque en el siguiente turno le tocará jugar a la CPU
* y nos interesa maximizar su resultado.
*/
private int min(){
if (haGanadoJugador(CASILLA_ORDENADOR)){
//Si ha ganado el ordenador devolvemos el valor del tablero
return 1;
} else if (isTableroLleno()){
//Si el tablero está lleno y no ha ganado el ordenador hemos empatado
return 0;
} else {
//Si el tablero no está lleno y no ha ganado el ordenador, recorremos todos
//los posibles movimientos restantes y los valoramos llamando a max()
int aux=9999;
int mejor=9999;
for (int x=0;x<this.numCols;x++){
for (int y=0;y<this.numFils;y++){
if (isCasillaVacia(x,y)){
marcarCasilla(x,y,CASILLA_PERSONA);
aux = max();
if (aux<mejor) {
mejor=aux;
}
marcarCasilla(x,y,CASILLA_VACIA);
}
}
}
return mejor;
}
}
/**
* El último jugador que marcó alguna casilla fue la persona, por lo que analizamos los posibles
* movimientos del ordenador.
*
* Si estamos en un nodo hoja devolvemos la valoración del tablero, puede que haya ganado la persona
* o puede que sigamos empatados, así que hay dos posibles valores: -1 (gana la persona)
* y 0 (seguimos empatados).
*
* Si no es nodo hoja recorremos las casillas vacías simulando ser el ordenador, y llamando
* a continuación al método MIN. Llamamos a MIN porque en el siguiente turno le tocará jugar al humano
* y nos interesa minimizar su resultado.
*/
private int max(){
if (haGanadoJugador(CASILLA_PERSONA)){
//Si ha ganado la persona devolvemos el valor del tablero
return -1;
} else if (isTableroLleno()){
//Si el tablero está lleno y no ha ganado la persona hemos empatado
return 0;
} else {
///Si el tablero no está lleno y no ha ganado la persona, recorremos todos
//los posibles movimientos restantes y los valoramos llamando a min()
int aux=-9999;
int mejor=-9999;
for (int x=0;x<this.numCols;x++){
for (int y=0;y<this.numFils;y++){
if (isCasillaVacia(x,y)){
marcarCasilla(x,y,CASILLA_ORDENADOR);
aux = min();
if (aux>mejor) {
mejor=aux;
}
marcarCasilla(x,y,CASILLA_VACIA);
}
}
}
return mejor;
}
}
/**
* Determina si una determinada posición del tablero está
* o no vacía.
*
* @param x. Fila de la casilla a analizar.
* @param y. Columna de la casilla a analizar.
*
* @return True cuando la casilla está vacía
*/
private boolean isCasillaVacia(int x, int y){
return tableroActual[x][y]==CASILLA_VACIA;
}
/**
* Ocupa la casilla indicada con la ficha recibida.
*
* @param x. Fila de la casilla a marcar.
* @param y. Columna de la casilla a marcar.
* @param ficha. Ficha a colocar.
*/
private void marcarCasilla(int x, int y, int ficha){
tableroActual[x][y]=ficha;
}
/**
* Determina si el tablero tiene casillas libres.
*
* @return True si hay casillas no ocupadas.
*/
private boolean isTableroLleno(){
for (int x=0;x<3;x++){
for (int y=0;y<3;y++){
if (isCasillaVacia(x,y)){
return false;
}
}
}
return true;
}
/**
* Determina si el jugador que maneja la ficha recibida
* por parámetro ha ganado la partida.
*
* @param ficha Ficha que podría haber ganado
*
* @return True cuando el jugador con la ficha recibida ha ganado.
*/
public boolean haGanadoJugador(int ficha){
//Verifica si el jugador ha ganado en las diagonales
if((tableroActual[0][0]==ficha && tableroActual[1][1]==ficha && tableroActual[2][2]==ficha)||
(tableroActual[0][2]==ficha && tableroActual[1][1]==ficha && tableroActual[2][0]==ficha)) {
return true;
} else {
//Verifica si el jugador ha ganado en una fila
for(int i=0;i<3;i++) {
if(tableroActual[i][0]==ficha && tableroActual[i][1]==ficha && tableroActual[i][2]==ficha) {
return true;
}
}
//Verifica si el jugador ha ganado en una columna
for(int i=0;i<3;i++) {
if(tableroActual[0][i]==ficha && tableroActual[1][i]==ficha && tableroActual[2][i]==ficha) {
return true;
}
}
}
return false;
}
}
4.- Clase auxiliar para manejar los movimientos
package org.dune.juegos;
public class Movimiento {
private int posX;
private int posY;
public Movimiento(int posX, int posY) {
super();
this.posX = posX;
this.posY = posY;
}
public int getPosX() {
return posX;
}
public void setPosX(int posX) {
this.posX = posX;
}
public int getPosY() {
return posY;
}
public void setPosY(int posY) {
this.posY = posY;
}
}
Muy bueno, ¿ se le puede ganar o siempre empatas contra la pc ?
ResponderEliminarHola
ResponderEliminarTampoco he jugado mucho, pero dudo que puedas ganar, el árbol es muy pequeño.
Este comentario ha sido eliminado por el autor.
ResponderEliminarel info me marca error
ResponderEliminarHola
ResponderEliminarNo se a qué te refieres...