elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Ejemplo de Minimax: 3 en raya
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Ejemplo de Minimax: 3 en raya  (Leído 14,915 veces)
ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Ejemplo de Minimax: 3 en raya
« en: 15 Enero 2012, 23:32 pm »

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
  1. #include <iostream>
  2. #include <vector>
  3. #include <string.h>
  4. using namespace std;
  5.  
  6. int M[3][3];
  7.  
  8.  
  9. int fila[] = {0, 2, 2, 2, 1, 1, 1, 0, 0, 0};
  10. int col[] = {0, 0, 1, 2, 0, 1, 2, 0, 1, 2};
  11.  
  12. int incf[] = {0, 1, 1, -1};
  13. int incc[] = {1, 1, 0, 1};
  14.  
  15. int check() {
  16.    for (int i = 0; i < 3; ++i) {
  17.        for (int j = 0; j < 3; ++j) {
  18.            for (int d = 0; d < 4; ++d) {
  19.                string s;
  20.                int f = i, c = j;
  21.                for (int h = 0; h < 3; ++h) {
  22.                    if (f < 0 or f >= 3 or c < 0 or c >= 3) break;
  23.                    s += char(M[f][c] + '0');
  24.                    f += incf[d];
  25.                    c += incc[d];
  26.                }
  27.                if (s == "111") return 1;
  28.                else if (s == "222") return 2;
  29.            }
  30.        }
  31.    }
  32.    return -1;
  33. }
  34.  
  35. void draw() {
  36.    for (int i = 0; i < 50; ++i) cout << endl;
  37.    for (int i = 0; i < 3; ++i) {
  38.        for (int j = 0; j < 3; ++j) {
  39.            if (M[i][j] == 0) cout << "  ";
  40.            else if (M[i][j] == 1) cout << " X";
  41.            else cout << " O";
  42.            if (j != 2) cout << " |";
  43.        }
  44.        cout << endl;
  45.        if (i != 2) cout << "------------" << endl;
  46.    }
  47. }
  48.  
  49. int rec(int &x, int &y, int torn) {
  50.    int best = -2;
  51.    int z, t;
  52.    for (int i = 0; i < 3; ++i) {
  53.        for (int j = 0; j < 3; ++j) {
  54.            if (M[i][j] != 0) continue;
  55.            M[i][j] = torn;
  56.            if (check() == torn) {
  57.                x = i;
  58.                y = j;
  59.                M[i][j] = 0;
  60.                return 1;
  61.            }
  62.            int aux = rec(z, t, (torn == 1)?2:1);
  63.            if (aux == -2 or aux == 0) {
  64.                if (best < 0) {
  65.                    best = 0;
  66.                    x = i;
  67.                    y = j;
  68.                }
  69.            }
  70.            else if (aux == -1) {
  71.                if (best < 1) {
  72.                    best = 1;
  73.                    x = i;
  74.                    y = j;
  75.                    M[i][j] = 0;
  76.                    return best;
  77.                }
  78.            }
  79.            else if (aux == 1) {
  80.                if (best < -1) {
  81.                    best = -1;
  82.                    x = i;
  83.                    y = j;
  84.                }
  85.            }
  86.            M[i][j] = 0;
  87.        }
  88.    }
  89.    return best;
  90. }
  91.  
  92. void tira_pc() {
  93.    int x, y;
  94.    int aux = rec(x, y, 1);
  95.    M[x][y] = 1;
  96. }
  97.  
  98. void tira_jug() {
  99.    int pos = -1;
  100.    while (pos < 1) {
  101.        cin >> pos;
  102.        if (pos < 1 or pos > 9) pos = -1;
  103.        else if (M[fila[pos]][col[pos]] != 0) pos = -1;
  104.    }
  105.    M[fila[pos]][col[pos]] = 2;
  106. }
  107.  
  108. int main() {
  109.    memset(M, 0, sizeof(M));
  110.    int win = -1, torn = 0;
  111.    int qtt = 0;
  112.    draw();
  113.    while ((win = check()) < 0 and qtt < 9) {
  114.        if (torn == 1) tira_pc();
  115.        else tira_jug();
  116.        torn = 1 - torn;
  117.        draw();
  118.        ++qtt;
  119.    }
  120.    if (win == 1) cout << "Gana el ordenador" << endl;
  121.    else if (win == 2) cout << "Ganas tu" << endl;
  122.    else cout << "Empate" << endl;
  123. }

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.


En línea

m0rf


Desconectado Desconectado

Mensajes: 828


BACK!


Ver Perfil
Re: Ejemplo de Minimax: 3 en raya
« Respuesta #1 en: 16 Enero 2012, 00:01 am »

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!!


En línea

Si todos fuéramos igual de inteligentes no existiría la mediocridad porque no podríamos apreciarla. Aprecias la mediocridad?
ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Ejemplo de Minimax: 3 en raya
« Respuesta #2 en: 16 Enero 2012, 17:57 pm »

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.
En línea

m0rf


Desconectado Desconectado

Mensajes: 828


BACK!


Ver Perfil
Re: Ejemplo de Minimax: 3 en raya
« Respuesta #3 en: 16 Enero 2012, 23:27 pm »

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.
En línea

Si todos fuéramos igual de inteligentes no existiría la mediocridad porque no podríamos apreciarla. Aprecias la mediocridad?
cappa_daniel

Desconectado Desconectado

Mensajes: 1


Ver Perfil
Re: Ejemplo de Minimax: 3 en raya
« Respuesta #4 en: 20 Abril 2015, 23:24 pm »

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?
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
3 en raya en batch
Scripting
The Shadow 0 1,814 Último mensaje 16 Febrero 2008, 00:06 am
por The Shadow
4 en raya
Programación C/C++
vaXy 5 8,233 Último mensaje 18 Marzo 2011, 20:56 pm
por anonimo12121
3 en raya Help
Programación C/C++
safkevin 3 4,168 Último mensaje 11 Mayo 2010, 05:09 am
por Og.
Si un dvd se raya... « 1 2 »
Hardware
Nu|kEr32 18 11,615 Último mensaje 22 Agosto 2010, 03:59 am
por Nu|kEr32
[Aporte] Tres en raya con minimax
Programación C/C++
0xFer 9 5,099 Último mensaje 25 Mayo 2015, 22:02 pm
por Stakewinner00
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines