IA para Mastermind.
Tachikomaia:
Mastermind
https://es.wikipedia.org/wiki/Mastermind
En mi caso no usaré colores sino números 0 o 1.
Creo que la solución es:
1- Generar árbol de acciones-reacciones (a las pistas).
2- Elegir código secreto.
3- Ver cuánto tarda el árbol en hallar el número dándole las pistas.
4- Ir al paso 2 hasta que no queden más códigos secretos.
5- Ir al paso 1 hasta que no queden más árboles.
El objetivo es hallar el árbol que adivine los números más rápido.
Sé que hay gente que lo ha hecho, pero por lo que he visto no he entendido.
Estoy trancado en la parte 1 :/
Gracias.
Serapis:
Ya te he indicado en más de una ocasión que tus 'problemas' suelen tener que ver frecuentemente con combinatoria y teoría de grafos. Haz el esfuerzo por aprender algo al respecto (sin quejarte de que no lo entiendes, solo inténtalo, si no lo entiendes a la primera sigue leyendo y leyendo, llega un momento que tu cabeza tiene suficientes piezas y sin darte cuenta montas el puzzle y acabas por comprender las cosas...)
Esto no puede llamarse IA, por varias razones...
- Es lo suficientemente sencillo como para resolverlo mediante grafos y más eficientemente mediante autómatas.
- El juego acaba tras 8 intentos fallidos (un IA no puede 'aprender' con solo 8 jugadas). Todavía se le podría 'enseñar' partidas (miles) tratando de que al final fuere capaz de satisfacer una solución la mayor parte de las veces. ...pero incluso así es mucho más trabajo (manual) que resolverlo por las formas antedichas.
- La IA se suele reservar para sistemas donde la complejidad se escapa humanamente al análisis, o bien aunque no escape, su resolución conlleve un tiempo (tambien) humanamente inaceptable.
Voy a darte algunas pistas... a ver si logras hacer algo (aparte de protestar).
- De entrada descarta usar unos y ceros (solo complicarás las cosas, sabiendo cuales son las reglas dle juego y que estas son finitas y de pequeño número), usa letras: siendo 8 bolas: ABCDEFGH
Una jugada como ACDG supone usar las bolas cuya letra representan en el orden en que aparecen en la jugada (apuesta). Prácticamente todos los lenguajes aceptan tratamiento de textos con caracteres y números por muy básico que sea el lenguaje.
- Como solo son 4 bolas la solución, el número de posibilidades para ordenar 4 bolas son: 1*2*3*4 = 24, es decir aún siendo 4 bolas la solución pueden estar ordenadas de 24 maneras distintas. Resulta de interés determinar el mínimo número de apuestas en que puede hallarse la solución partiendo de un fallo total de orden (más adleante alargo un poquito más este caso, es el más interesante porque a otros casos (no a todos) se llega desde éste, luego resolviendo éste, 'por el camino' resuelves aquellos).
- Tras la apuesta del jugador (en la primera de ellas), hay solo 14 resultados distintos.
es decir estos resultados son los nodos hijos del nodo raíz de un árbol.
Si las numeramos (por ejemplo para acogerlos en una enumeración, serían):
00 - 0 negras y 0 blancas (equivale a -12- (4 negras con las bolas no jugadas, es deicr la próxima apuesta usa las 4 no usadas))
01 - 1 negra
02 - 1 blanca
03 - 2 negras
04 - 2 blancas
05 - 1 negra y 1 blanca
06 - 3 negras
07 - 3 blancas
08 - 2 negras y 1 blanca
09 - 2 blancas y 1 negra
10 - 2 negras y 2 blancas
11 - 3 negras y 1 blanca
12 - 4 negras (fallan en el orden)
13 - 4 blancas (hallado, fin de partida)
14 - 3 blancas y 1 negra NOTA: que este caso nunca puede darse, se añade solo por que no parezca un olvido... y hacer notar así su caso imposible.
Supongamos que tu primera apuesta fuera: ABCD y el resultado de la apuesta es 12 (4 negras)...
Lo más razonable con el resultado es cambiar solo 2 bolas en la siguiente apuesta, por ejemplo AB--> BA (también podrías cambiar 3 bolas de sitio o las 4, pero las combinaciones de los resultados posibles son más numerosas con tales casos). Por ello ciñámonos solo a considerar un cambio de solo 2 de ellas:
El nodo 10 tendría (en este caso) como hijos nodos a:
12 - 4 negras ---> es decir sigue sin cambios, pero ahora sabemos que AB ocupan las posiciones 34 y CD las posiciones 12 (después de otra apuesta llegamos al caso 12 o 10, y con otra más al 10 (si antes no llegamos al 13 (la solución).
10 - 2 negras y 2 blancas ---> caso de que el intercambio arroje a ambas a su orden correcto. La siguiente apuesta resuelve el enigma: CD--> DC = resultado 11 (reseulto)
11 - 3 negras 1 blanca ---> A o B es blanca.
...si vas descendiendo de forma exhaustiva caso por caso, finalmente tienes una forma arbórea de explorar los resultados para dirigir la siguiente apuesta y así poder solucionarlo en el mínimo número de jugadas.
Nota que las resultados son siempre los mismos, por lo que al final se reduce a usar una y otra vez las mismas operaciones con resultados ya conocidos, donde lo que cambia es la información previa que ya hemos obtenido y que será conjugado con el nuevo resultado lo que derive a uno u otro nodo.
Asumo que el árbol incluso podría generarse en forma de Trie, donde la raíz es la solución y se alcanza siempre si el número de profundidad del nodo (actual) no es superior al número de jugadas máximas antes de dar por perdida la partida...
No me he parado a verificar si es posible ganar siempre en el númro de jugadas máximo (8), ni tengo previsto perder tiempo en ello. Creo que con el tiempo dedicado a responderte es más suficiente.
Desde el punto de vista de un autómata, habría que asignar estados con cada jugada: sugiero dotar de un valor de 5 por cada 'bola blanca' y un valor de 1 por cada 'bola negra' (nota que un valor menor de 5 para blancas dejaría en la ambigüedad el resultado, pués 4 negras suman 4). El estado final del autómata con valor '20' señalaría el estado de aceptación.
Una IA podría ser alimentado con partidas completas (jugada a jugada), recibiendo como retroalimentación precisamente el valor numérico resultante. Si el número de jugadas es lo suficientemente grande, es probable que de una forma algo más monstruosa* acabara llegando a un esquema equivalente al árbol recién descrito (* las IA habitualmente consumen mucho más recursos de memoria (mientras se los entrena), que un sistema equivalente programado de forma manual).
Si no eres capaz de programar un esquema con árboles, ni con autómatas, me temo que tampoco serás capaz de crear una IA, que suele ser más complejo.
...aunque conociéndote un poco, asumo que tienes la mala costumbre de llamar IA, a procesos que no lo son (esto ya ocurre incluso en profesionales idiotizados).
Tachikomaia:
Es muy difícil responder tu mensaje...
Cita de: Serapis en 6 Febrero 2021, 16:30 pm
Ya te he indicado en más de una ocasión que tus 'problemas' suelen tener que ver frecuentemente con combinatoria y teoría de grafos. Haz el esfuerzo por aprender algo al respecto (sin quejarte de que no lo entiendes, solo inténtalo, si no lo entiendes a la primera sigue leyendo y leyendo, llega un momento que tu cabeza tiene suficientes piezas y sin darte cuenta montas el puzzle y acabas por comprender las cosas...)
Sinceramente si es muy largo o complicado prefiero hacer otra cosa.
Citar
Esto no puede llamarse IA, por varias razones...
Bueno, no sé, pero llega a aprender algo sin que yo se lo diga.
Citar
- Es lo suficientemente sencillo como para resolverlo mediante grafos y más eficientemente mediante autómatas.
¿Cómo es con grafos y autómatas?
Citar
- El juego acaba tras 8 intentos fallidos (un IA no puede 'aprender' con solo 8 jugadas).
Puse el título de Mastermind porque es muy parecido, pero no he puesto un límite a la cantidad de intentos.
Citar
- La IA se suele reservar para sistemas donde la complejidad se escapa humanamente al análisis, o bien aunque no escape, su resolución conlleve un tiempo (tambien) humanamente inaceptable.
Al parecer soy incapaz de resolver el problema por mí mismo.
Citar
- De entrada descarta usar unos y ceros (solo complicarás las cosas, sabiendo cuales son las reglas dle juego y que estas son finitas y de pequeño número), usa letras: siendo 8 bolas: ABCDEFGH
¿Por qué dices que complico si estoy simplificando? 2 valores es más sencillo que 8. En todo caso puedo usar letras en vez de números si te parece mejor.
Citar
- Como solo son 4 bolas la solución, el número de posibilidades para ordenar 4 bolas son: 1*2*3*4 = 24
Calculo que en mi caso serían 1*2.
Citar
- Tras la apuesta del jugador (en la primera de ellas), hay solo 14 resultados distintos.
es decir estos resultados son los nodos hijos del nodo raíz de un árbol.
En mi caso son 4:
0 posiciones correctas 0 posiciones equivocadas
01
10
20
11 no puede ser creo
Citar
Si no eres capaz de programar un esquema con árboles, ni con autómatas, me temo que tampoco serás capaz de crear una IA, que suele ser más complejo.
¿Entonces esto es un autómata?
Código
actions for fotograma 1
// Situación inicial.
BaseVS = 10;
// Guardar Situación inicial.
SitID = "S"+BaseVS;
set (SitID+"VS", BaseVS);
set (SitID+"C", "Ninguno");
C = 1;
// Variables de Unsolved situaciones.
U = 0;
Us = 0;
actions for fotograma 2
// Reset Situación. Aplicación.
VS = BaseVS+C;
// ¿Sol?
if (20<VS) {
// Solución; iniciar mostrar lista.
List = C;
gotoAndPlay (4);
// Sino ¿la situación está anotada?
} else if (eval("S"+VS+"VS") == undefined) {
// No. Anotarla.
SitID = "S"+VS;
set (SitID+"VS", BaseVS);
set (SitID+"C", C);
Us = Us+1;
SitID = "U"+Us;
set (SitID+"VS", VS);
}
actions for fotograma 3
// La situación existe. ¿Modificar candidato es posible?
if (C<2) {
// Modificación de candidato.
C = C+1;
gotoAndPlay (2);
} else if (U<Us) {
// Usar Unsolveds.
U = U+1;
BaseVS = eval("U"+U+"VS");
C = 1;
gotoAndPlay (2);
} else {
// No hay Solución.
stop ();
}
actions for fotograma 5
SitID = eval("S"+BaseVS+"C");
BaseVS = eval("S"+BaseVS+"VS");
if (SitID != "Ninguno") {
List = SitID+" "+List;
gotoAndPlay (4);
} else {
stop ();
}
¿Cuales son los requisitos para que sea IA? Nota que en el título simplifiqué, en parte por no saber qué decir. ¿Lo que describí con números no lo es?
Al final has hablado bastante, gracias, pero no me ayudaste con la parte 1...
Yo a lo que he llegado por ahora es a:
Código___Árbol1___Árbol2___etc
________Tiempo que tarda el árbol en hallar el código.
Pero no sé cómo nombrar o crear a los árboles.
Serapis:
Son varias preguntas. Voy a ver si te respondo a todas sin extenderme demasiado...
Cita de: Tachikomaia en 6 Febrero 2021, 18:10 pm
Sinceramente si es muy largo o complicado prefiero hacer otra cosa.
Complicado por sí mismo no, es, pero la complejidad es algo subjetivo que depende de los conocimientos de cada uno.
Cita de: Tachikomaia en 6 Febrero 2021, 18:10 pm
Bueno, no sé, pero llega a aprender algo sin que yo se lo diga.
Nota la diferencia entre 'encontrar una solución' y 'aprender algo'.
Cita de: Tachikomaia en 6 Febrero 2021, 18:10 pm
¿Cómo es con grafos y autómatas?
Con grafos es siguiendo el camino que tracé en el mensaje anterior.
Puedes en un principio considerar un árbol, y más tarde pasar a considerar un grafo o al revés.
Nota que con grafos y árboles, la recursividad está a la orden del día. Luego el lenguaje usado debe aceptar recursividad. Es posible cambiar cualquier sistema iterativo a recursivo y viceversa pero en la práctica a veces es complicado pasar de uno a otro, en tanto que en un sistema es básicamente intuitivo. Esa lucha 'contraintuitiva' añade una capa de complejidad innecesaria e indeseable.
Para hacerlo con autómatas, necesitas conocer la teoria de autómatas... si no es como querer arreglar la maquinaria de un tren, solo porque lograste arreglar el pedal de la bici de tu sobrino.
Cita de: Tachikomaia en 6 Febrero 2021, 18:10 pm
Puse el título de Mastermind porque es muy parecido, pero no he puesto un límite a la cantidad de intentos.
Ok.. no limitarlo en prinicipio a un número de intentos no es mala idea.
Cita de: Tachikomaia en 6 Febrero 2021, 18:10 pm
Al parecer soy incapaz de resolver el problema por mí mismo.
¿Por qué dices que complico si estoy simplificando? 2 valores es más sencillo que 8. En todo caso puedo usar letras en vez de números si te parece mejor.
Calculo que en mi caso serían 1*2.
Una IA se alimenta de datos. Datos que deben sopesarse, para que se adapten. Si el número de entradas es muy escueta, el aprendizaje será complejo, no quedaría claro ni existiría una separación definida de cuando una solución responde a la lógica tras la IA, respecto de la pura causalidad (pués solo hay 4 soluciones entre la que elegir, por fuerza acertaría un 25% de las veces incluso sin ninguna 'intelgencia detrás')
... ahora pon 20 entradas y entonces incluso un 2% de aciertos será más admirable al caso que un 25% con solo 2 entradas.
Cita de: Tachikomaia en 6 Febrero 2021, 18:10 pm
¿Cuales son los requisitos para que sea IA? Nota que en el título simplifiqué, en parte por no saber qué decir. ¿Lo que describí con números no lo es?
Una IA necesita en principio ser un proceso abstracto, aunque luego pueda ser definido expresamente para un cometido único.
Una IA tiene una o más salidas, pero dichas salidas retroalimentan la entrada, sin retroalimentación no hay siquiera memoria, menos aprendizaje.
Nota que la memoria es una retroalimentación de una entrada con algo ya almacenado (una salida previa).
El aprendizaje, consiste en hacer esto mismo a muchas más capas... El aprendizaje podría verse como una simulación d ela simulación de una memoria.
Una IA requiere poder cambiar valores llamados pesos, para estabilizar como reacciona la información, esos pesos hacen una especie de compensacion distinta a diferentes entradas.
Cita de: Tachikomaia en 6 Febrero 2021, 18:10 pm
¿Entonces esto es un autómata?
actions for fotograma 1
// Situación inicial.
BaseVS = 10;
No. Para nada.
Eso es un bloque funcional de acciones.
Guarda una cierta similitud pero solo si se comprende. desde luego no en la forma de abordarlo.
Un autómata en principio se desentiende de tu problema particular, es abstracto.
Recibe un estado inicial y una secuencia y va cambiando el estado interno en función de dichas entradas y una función de evolución (llamada de transición), que dicta como cambia (a que éstado evoluciona desd eel estado actual y con el valor actual de la secuencia). A menudo suele generarse una tabla, para representar el funcionamiento de la funcion de transición.
De una forma simplificada con los datos de entrada computa qué reglas se cumplen y hacia qué estado evoluciona, para finalmente señalar si cumple o no la regla.
En realidad se requiere un autómata por cada regla, aunque finalmente pueden aunarse y simplificar el esquema.
Un autómata en este caso se encargaría de evaluar la apuesta y el número de bolas negras y blancas, y así determinar si la secuencia dada es la solución o no, podría además devolver esos estados internos de las bolas (para recibirlos en la siguiente apuesta).
Como te decía más arriba, para hacerlo con autómatas, necesitas conocer la teoria de autómatas...
No es posible enseñar en 2 o 3 párrafos algo que precisa como mínimo 50 páginas.
Cita de: Tachikomaia en 6 Febrero 2021, 18:10 pm
Al final has hablado bastante, gracias, pero no me ayudaste con la parte 1...
Yo a lo que he llegado por ahora es a:
Código___Árbol1___Árbol2___etc
________Tiempo que tarda el árbol en hallar el código.
Lamentablemente no puedo penetrar en tu cabeza.
Poner un titulo y el texto de una salida, es lo mismo que no haber hecho nada.
En mi mensaje anterior te he dado pie para sigas desde allí, con árboles. ...pero si tampoco sabes crear y usar árboles en el lenguaje que entiendes... lo que hagas o dejes de hacer, entiendas o dejes de atender, depende finalmentee de tus capacidades.
Tachikomaia:
Cita de: Serapis en 6 Febrero 2021, 20:01 pm
Nota la diferencia entre 'encontrar una solución' y 'aprender algo'.
Encontrar una solución es aprender algo.
Bueno, sigo sin saber cómo nombrar o hacer un árbol. Y usarlo.
Navegación
[#] Página Siguiente