Proxy Inverso: abril 2014

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;
    }
}

Proxy Inverso

Páginas

sábado, 26 de abril de 2014

Tres en raya (minimax)

jueves, 24 de abril de 2014

Gnome 3 (gnome-shell) gestión varios monitores