Ejemplo de Minimax: 3 en raya

[ghastlyX]

Esta tarde con un amigo ha salido el tema por cosas de la conversación y le he desafiado a ganar al 3 en raya (Tic-tac-toe) a una IA que hiciera para el ordenador. Tras unos 15 minutos, os dejo el código que he hecho, puesto que considero que puede ser interesante la parte del minimax para aquellos que no hayan hecho nunca uno. Los gráficos son cutres y por consola, puesto que no era el objetivo del programa hacer una interfaz bonita.

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int M[3][3];


int fila[] = {0, 2, 2, 2, 1, 1, 1, 0, 0, 0};
int col[] = {0, 0, 1, 2, 0, 1, 2, 0, 1, 2};

int incf[] = {0, 1, 1, -1};
int incc[] = {1, 1, 0, 1};

int check() {
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int d = 0; d < 4; ++d) {
                string s;
                int f = i, c = j;
                for (int h = 0; h < 3; ++h) {
                    if (f < 0 or f >= 3 or c < 0 or c >= 3) break;
                    s += char(M[f][c] + '0');
                    f += incf[d];
                    c += incc[d];
                }
                if (s == "111") return 1;
                else if (s == "222") return 2;
            }
        }
    }
    return -1;
}

void draw() {
    for (int i = 0; i < 50; ++i) cout << endl;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (M[i][j] == 0) cout << "  ";
            else if (M[i][j] == 1) cout << " X";
            else cout << " O";
            if (j != 2) cout << " |";
        }
        cout << endl;
        if (i != 2) cout << "------------" << endl;
    }
}

int rec(int &x, int &y, int torn) {
    int best = -2;
    int z, t;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (M[i][j] != 0) continue;
            M[i][j] = torn;
            if (check() == torn) {
                x = i;
                y = j;
                M[i][j] = 0;
                return 1;
            }
            int aux = rec(z, t, (torn == 1)?2:1);
            if (aux == -2 or aux == 0) {
                if (best < 0) {
                    best = 0;
                    x = i;
                    y = j;
                }
            }
            else if (aux == -1) {
                if (best < 1) {
                    best = 1;
                    x = i;
                    y = j;
                    M[i][j] = 0;
                    return best;
                }
            }
            else if (aux == 1) {
                if (best < -1) {
                    best = -1;
                    x = i;
                    y = j;
                }
            }
            M[i][j] = 0;
        }
    }
    return best;
}

void tira_pc() {
    int x, y;
    int aux = rec(x, y, 1);
    M[x][y] = 1;
}

void tira_jug() {
    int pos = -1;
    while (pos < 1) {
        cin >> pos;
        if (pos < 1 or pos > 9) pos = -1;
        else if (M[fila[pos]][col[pos]] != 0) pos = -1;
    }
    M[fila[pos]][col[pos]] = 2;
}

int main() {
    memset(M, 0, sizeof(M));
    int win = -1, torn = 0;
    int qtt = 0;
    draw();
    while ((win = check()) < 0 and qtt < 9) {
        if (torn == 1) tira_pc();
        else tira_jug();
        torn = 1 - torn;
        draw();
        ++qtt;
    }
    if (win == 1) cout << "Gana el ordenador" << endl;
    else if (win == 2) cout << "Ganas tu" << endl;
    else cout << "Empate" << endl;
}

Se juega con los números:
7 8 9
4 5 6
1 2 3

El ordenador juega con X, el jugador humano con O. Empieza jugando el humano, aunque todo esto son detalles que se arreglan cambiando una o dos líneas.

[m0rf]

Interesante lo de la teoria de la decisión y el algoritmo de toma de decisiones minimax, conoces alguno más o este es el más utilizado o lo has elegido por algo en especial?

Saludos, realmente interesante nunca he tocado este tema.

PD: Empate siempre xD!!

[ghastlyX]

Minimax lo que hace informalmente es considerar todos los casos que se pueden dar desde donde estás y en base a esto, elegir el movimiento que te lleve a un resultado mejor asumiendo que el contrario hará el movimiento que más te perjudique.

El problema de minimax es que el árbol de estados que crea es muy grande para juegos más complejos, pero con el 3 en raya hay pocos y lo puede calcular entero, de manera que el ordenador juega de forma perfecta, por eso he programado un minimax.

A la hora de programarlo no es complicado, es un pequeño backtracking. La idea es probar todos tus posibles movimientos y recursivamente hacer que haga lo mismo tu rival. En función de lo que retorne tu rival, elegirás la opción que mejor te vaya.

Si se deja acabar minimax, la jugada es perfecta. El problema es que no todos los juegos como ya he dicho lo permiten (puesto que necesitaría demasiado tiempo, por ejemplo con el ajedrez) y lo que se hace cuando se usa minimax en estos juegos es realizar diferentes tipos de podas para así conseguir un movimiento suficientemente bueno.

[m0rf]

A más es solo para juegos con dos jugadores por lo que vi en wikipedia.

A ver si me animo un dia de estos ha hacer un pequeño juego con este metodo para probarlo.

Gracias por aclarar sobre para que sirve minimax.

Saludos.

[cappa_daniel]

amigo la verdad soy nuevo en esto de programar pero  me podrías ayudar en explicar el código la verdad me perdí en algunas puntos. lo podrías subir comentado el codigo?