AI mastermind

LioNHearT #1 May '09

C++

buenas de nuevo. creo que esta será la ultima pregunta que os haga (o eso espero).

sigo con el proyecto del mastermind. hablando con el profesor, me ha dicho la manera de programar la estrategia. la idea es la siguiente:

crear una tabla con todos los numeros posibles de 4 cifras diferentes entre el 0 y 9999(1234 , 1345, etc...). a partir de aqui, el ordenador me dira una de esas cifras y si no es la acertada, la borrará. a partir de aqui, borrará los numeros de la tabla que no cumplan con los muertos (nº acertados en posicion correcta) y heridos (nº acertados en posicion incorrecta) que yo le diga. por ejemplo:

-nº pensado:1234
-nº maquina:3478

-muertos=0
-heridos=2

como no es el nº, la maquina borrará este numero de la tabla y todos aquellos que no cumplan esta condición. entonces como puedo hacer esto? porque la idea mas o menos la entiendo, pero no tengo ni papa de como programarlo... :S

que se os ocurre?

espero vuestra respuesta, que hasta ahora me han sido de mucha ayuda.

gracias anticipadas!!

Dod-Evers #2 May '09

Lo de rellenar el array, fácil, no?

Y luego tienes que recorrer el vector y mirar cada uno de los valores. Para quitar números tendrás que ir haciendo módulo de los valores.

LioNHearT #3 May '09

si si el array es facil. pero como puedo saber el tamaño del array? es decir, cuantos numeros de 4 digitos diferentes hay?

y luego lo de borrar numeros, como lo podria hacer?

esto me recuerda al programa este de 20p, el de adivinar lo que es tio, creo que la idea es la misma de la maquina esa que sale xDD

Poisonous #4 May '09

combinaciones con repeticion cogidas de 4 en 4?

JuAn4k4 #5 May '09

de 0000 a 9999 no es muy dificil saber el tamaño del array... 10.000 de 0 a 9999

Que te dice muertos=0

pues cojes el indice

indice = (numeroCon0Muertos %1000)*1000;

y recorres los 999 posiciones de esa cifra.

Es decir, si has dicho el 3201 y sale muertos 0.

recorres desde 3000 a 3999 y los eliminas

lo mismo para la 2ª cifra
indice = 900 , eliminas desde el 900 al 999 y luego 1900 al 1999 , 2900 al 2999 , 3900 al 3999 .... hasta 9900 al 9999

lo mismo para la tercera cifra

0000 al 0009
0100 al 0109
..
hasta
9900 al 9909

y lo mismo para la ultima cifra

No se me ocurre eliminar nada con heridos > 0 ni muertos > 0.
con heridos = 0 eliminas un porron.

PD: El vector es un vector de booleano ( Verdadero o Falso ) V = Puede ser , F = No puede ser.

elkaoD #6 May '09

En realidad la tabla tiene 10987 posibilidades (9987 si no pueden ser números menores de 1000, es decir, si no puede salir el 0423.)

Yo lo que haría sería tener un array de 4 chars como un mapa de bits (10 bits) e iría seteando los bits a 1 y a 0 dependiendo de las posibilidades, pero a veces tengo ideas tontas xD

LOc0 #7 May '09

A ver si lo he entendido.

Si tú piensas el 1234 y la máquina te dice el 3789. Resulta que:

muertos: 0

heridos: 1

¿Entonces te cargas todos los números de 4 cifras que no tengan AL MENOS una de las 4 cifras de 1234?

Si pienso el 1256 y salen:

muertos: 2

heridos: 0

¿Te cargas todos los números que no tengan AL MENOS 2 cifras iguales (en valor y posición) que 1256?

Si te salen muertos y heridos pues haces la dos cosas al mismo tiempo. Y repites hasta tener los 4 muertos (o hasta que no te quede más que un número sin tachar).

Parece MUY buen sistema (es la estrategia del mítico juego de mesa Quién es quién.)...

A la hora de implementarlo yo tiraría de un array bool de 10000 elementos inicializados a TRUE. Hazte una funcioncilla que te convierta un int en un int array[4] para tener las cifras siempre a mano y poder hacer las comprobaciones. Un contador int de 0 a 9999 y a ¡jugar!

Salu2

PD: no me había fijado en #1, que sólo querías generarte los números con las 4 cifras distintas. En ese caso #6 para variar lleva razón y la dimensión son P(10,4) = 10!/(10-4)! = 10987 (El problema es que si quieres indexar la tabla por el propio número necesitas una de 10101010. Dicho de otro modo, el 5243 por ejemplo, ¿qué posición ocupa en la lista de 1098*7?)

LioNHearT #8 May '09

lo de #6 es cierto, el tamaño lo consegui sacar anoche jejeje. pero ahora me surge otra duda: tengo esta funcion que genera un nº aleatorio de 4 cifras diferentes:

    int  aleatori (){
     int x,un,dec,cent,mil;
     bool genera=false;
     srand(time(NULL));
     while(!genera)
     {
     un=rand()%10;
     dec=rand()%10;
     cent=rand()%10;
     mil=rand()%10;
     if (
      (un!=dec && un!=cent && un!=mil) &&
      (dec!=cent && dec!=mil) &&
      (cent!=mil)
        )
       {
       genera=true;
       x = mil*1000 + cent*100 + dec*10 + un;
       }
       }
     return x;
     }

la cuestion es que llenare la tabla de estos valores. pero como hago para que no me los repita?

lluego lo de #7 tiene muy buena pinta pero... como podria hacerlo?porque tiene pinta de bastante cacao...

espero vuestras respuestas. 1000 gracias!!!

elkaoD #9 May '09

Estoy haciéndolo como dice #7, usando la técnica del "Quién es quién" (Al final deseché la idea del mapa de bits.) Está casi terminado, pero sospecho que por heurística puede ir mucho mejor.

EDIT: Hecho, me lo resuelve en una media de 14 o 15 intentos sin heurística, jugando 1000 partidas distintas en 2.2 segundos.
EDIT2: Bajada la media a 12 intentos.
EDIT3: 11 intentos, creo que ya voy a empezar a meter la heurística xD #8 toma mi código por si te sirve de algo. http://kaod.pastebin.com/f4982f682

LOc0 #10 May '09

#9

Hay un caso que creo que no has considerado y puede optimizar un poquillo. Cuando SÓLO hay heridos, puedes cargarte todos los números que tengan alguna cifra en la misma posición que el elegido.

En cuanto a la heurística podrías darle prioridad a los números restantes. Si te sale un número con muertos, después de hacer el borrado oportuno de candidatos, vuelve a recorrer la tabla y dale "prioridad" a aquellos que compartan cifras y hueco con el elegido. Sería interesante tener la tabla de posibles ordenada por prioridad en vez de generar un número aleatorio en cada iteración para ir preguntando al usuario empezando por el primero no descartado. (La primera vez obviamente necesitas generar uno aleatorio). La prioridad puedes sumarla en función del número de cifras-hueco que comparte el número con el elegido. De todas formas, una media de 11 lo veo bastante, bastante bueno.

Y una cosilla de implementación. En vez de la tabla de [10][10][10][10] podrías hacerte un array de [1098*7] y rellenarlo al inicio con todos los números entre 0 y 9999 que no tienen cifras repetidas. De esta forma, no tendrás que generar un número aleatorio de 4 cifras distintas, sino uno entre 0-5040 y cogerlo del array (si está libre). Eso sí, pierdes el poder indexar por número, pero una vez tengas la posición del array (tp es muy grande) ya es ir incrementando uno a uno. (Además que creo que sería mejor tener ese array ordenado por prioridad y empezar a buscar uno libre por arriba que "preguntar" aleatoriamente pistas al usuario).

Y de momento poco más. Ojalá tuviera más tiempo, pero mañana tengo un examen importantísimo que me medio juego la carrera. Me he metido para desconectar...

Salu2

JuAn4k4 #11 May '09

#6 De lo que hablais es de no poder repetir numeros, si pienso el 2230 que?

LioNHearT #12 May '09

estoy con #10, tengo que hacer esa tabla[1098*7] y rellenarla con todos los numeros de 4 cifras diferentes entre 0 y 9999. y es lo que hago. entonces la idea es que la maquina irá borrando los numeros que no cumplan con los muertos y heridos dichos, hasta quedarse con 1 numero, que sera la solucion, y en el caso de que no se quede con ningun numero, la maquina sabra que hemos hecho trampa. pero la cuestion es, como hacer para que no me repita ningun numero? porque uso la funcion generada que os puse mas arriba y creo que con eso me repetira numerots

elkaoD #13 May '09

#10, lo he hecho de esta forma porque así me puede resultar más fácil aplicar heurística a la elección del número. En un principio estaba hecho como dices tú, pero me pareció más cómodo poder acceder a los números por cifras.

Una media de 11 no está mal, la verdad, pero creo que se podría mejorar aunque fuera un poquito. Lo de las prioridades lo pensaré, pero había pensado en lugar de por prioridades, hacer un sistema de memoria para la IA, que recuerde el número que probó y cuántos muertos y heridos tenía, aparte de un array que vaya guardando los números que salen como posibles heridos (Por esto lo del array de 101010*10.)

#11 si piensas el 2230 no estás aplicando las reglas que #1 impuso así que... xD

EDIT: He bajado la media a 9 intentos, muchas gracias por avisarme del caso que me faltaba LOc0 Eso sí, ahora de repente no entiendo por qué funciona sin fallos mi código, no debería funcionar...
EDIT2: ¡8 intentos y vuelvo a entender mi código! xD Con una pequeña modificación 7 intentos, pero se dispara el tiempo de cálculo porque tira más de rand. http://kaod.pastebin.com/f3b1783a5 (Para el modo rápido hay que quitar el comment de //#define FAST)

Por cierto, en los intentos solo cuento los fallidos, así que en realidad antes eran 12 intentos creo.

LioNHearT #14 May '09

#13 por lo que veo has usado una tabla de 4 columnas, no? es que esto no puedo usarlo, solo nos dejan tablas de 1 x 1... se podria adaptar?

por lo de la heuristica no te preocupes, no me interesa que sea demasiado inteligente tampoco, con que piense me es suficiente xD

elkaoD #15 May '09

#14, sí, un array unidimensional de 10000 elementos y si por ejemplo quieres acceder a lo que sería mi tabla[6][2][3][4], en tu caso sería tabla[61000+2100+3*10+4]

Lo de la heurística lo hago por placer, me molan las chorraditas pequeñas de este estilo para programar xD De los proyectos grandes siempre me canso porque acabas debuggeando más que pensando o haciendo movidas aburridas de cara al usuario como comprobación de errores. Esto son pequeños retos que divierten (Al menos a mí xD) si te lo tomas en plan juego.

LioNHearT #16 May '09

entonces con poner la array de esa fora ya me funcionaria correctamente?

elkaoD #17 May '09

Pues no sé, supongo que sí, pero recomiendo que no copies y pegues sino que intentes entender un poco como funciona el código (He intentado explicar lo que es más ilegible) y hacerlo a tu manera. En #13 está el link de la última versión. Tú mira solo la función ia() a partir de donde pone // AQUI COMIENZA LA IA DE VERDAD que es la parte que te interesa. El resto olvídate porque creo que ya lo tienes hecho, sólo te falta adaptar la IA a tu programa.

LioNHearT #18 May '09

si si, si mi intencion era hacerlo, mas que nada era para saber si puedo seguir los pasos. bueno el finde me liare con el y si no entiendo algo lo comunico por aqui jejeje.

gracias!

Usuarios habituales