He estado reflexionando sobre el desarrollo de un juego de lógica similar al Einstein's Puzzle , que tendría diferentes conjuntos de pistas para cada nueva repetición del juego.
¿Qué estructuras de datos usaría para manejar las diferentes entidades (mascotas, colores de casas, nacionalidades, etc.), reglas de deducción, etc. para garantizar que las pistas que proporcione apunten a una solución única?
Me está costando mucho pensar cómo hacer que las reglas de deducción jueguen con las posibles pistas; Cualquier idea sería apreciada.
logic
data-structure
puzzle
taserian
fuente
fuente
Respuestas:
Guau. Esto en realidad parece una situación en la que las redes semánticas de IA de la vieja escuela, como Richard Bartle pensó que serían importantes para el futuro de los juegos cuando escribiera Inteligencia artificial y juegos de computadora , serían útiles. Básicamente, tiene un par de listas de datos (tablas de bases de datos, lo que sea), la primera de las cuales especifica reglas sobre cómo las cosas pueden relacionarse entre sí, como:
Entonces tienes instancias de las categorías:
Estas estructuras de datos no encapsulan completamente la situación: necesita las restricciones de unicidad, y algunas de las categorías necesitan meta-reglas, como el
POSITIONmanejo de "a la derecha de", "a la izquierda de" y "siguiente a "conceptos, por ejemplo, pero la estructura del problema parece sugerirlos fuertemente.No sé si esto te llevará muy lejos, pero espero que ayude.
fuente
Mi recomendación es mirar el código de Python para problemas de satisfacción de restricciones (CSP) que se proporciona con el proyecto AIMA . Utilizan un diccionario (matriz asociativa / tabla hash) para realizar un seguimiento de las restricciones válidas. Además, hay implementaciones de varios algoritmos utilizados para resolver CSP, como min-conflict y AC3.
El código incluye un ejemplo de problema de Zebra como ejemplo, como el que se vinculó.
fuente
Esto va muy profundo en realidad. Es extraño que Wikipedia nunca lo mencione.
Lo que está buscando son pruebas muy duras que, probablemente, se puedan alcanzar con cosas como las pruebas de Fitch . Así que estamos tratando de deducir cosas de nuestros datos dados. Hay muchos constructores a prueba de Fitch que hacen mucho trabajo por ti. Pero algunos ejercicios simplemente no son a prueba.
No sé si el usuario debe hacer los cálculos. Si es así, tenga en cuenta cosas como 3SAT , que son problemas que no se pueden deshacer para el tiempo polinómico.
En cuanto a las estructuras de datos que desea utilizar, creo que desea tener algún tipo de
Ruleclase. La regla puede ser cualquier cosa, según el tipo. No hay muchas reglas en la lógica de predicados , por lo que esto se puede superar heredando (if, iff, and, or, not ...). Estas reglas solo tienen que ser evaluadas. Y lo único que puede hacer una regla es devolver verdadero o falso. Porque eso es lo que haces con la lógica de predicados. En la universidad, John Kelly me recomendó leer este libro .Volviendo a las clases: debería ver estos problemas como vería la implementación de cálculos normales con las matemáticas. ¿Qué es un
+operador? Contiene dos parámetros, que pueden ser una nueva ecuación por sí misma, o simplemente un número. Creo que tienes lo mismo con las reglas. Pueden tener nuevas Reglas como parámetro, o simplemente un booleano (llamado predicado).Espero que esto te ayude mucho, especialmente las referencias. Si quieres saber más, o si voy en la dirección equivocada, dímelo.
fuente
Ruleclase es una buena idea. El modelado de estas restricciones todavía se hace por lógica de predicados, creo.No tengo una buena respuesta, pero buscando pistas sobre el mismo tipo de problema, encontré este repositorio en github:
https://github.com/nateinaction/Zebra-Puzzle
Contiene algo de lógica para seleccionar pistas y decidir cuántas pistas necesitarías para resolver el rompecabezas.
fuente
Hay esto en resolverlo.
Por supuesto, creo que no sería demasiado difícil trabajar hacia atrás; es decir, tener una lista como esta:
Fred Red Dog
Steve Blue Cat
Bill Ballena Púrpura
Eric Cyan Dolphin
Que podría generarse fácilmente y luego formar un conjunto de reglas a partir de eso.
En cuanto al almacenamiento, ¿por qué no un conjunto de cada cosa por separado, entonces [Fred, Steve, Bill, Eric] y un conjunto de la respuesta [Fred, Red, Dog]. Luego tenga 'NOMBRE (no) OBJETO DE ACCIÓN'.
Cuando te pones a ello, ¿realmente importa una solución única? Siempre que su juego pueda dividirlos en las listas, y marque 'el set 1 no contiene Whale'.
fuente