Structures de données pour les jeux de logique / Règles de déduction / Ensemble d'indices suffisant?

11

J'ai réfléchi au développement d'un jeu de logique similaire à Einstein's Puzzle , qui aurait différents ensembles d'indices pour chaque nouveau jeu.

Quelles structures de données utiliseriez-vous pour gérer les différentes entités (animaux domestiques, couleurs des maisons, nationalités, etc.), les règles de déduction, etc. pour garantir que les indices que vous fournissez indiquent une solution unique?

J'ai du mal à réfléchir à la façon de faire jouer les règles de déduction avec les indices possibles; toute perspicacité serait appréciée.

logic data-structure puzzle taserian
la source
1
Je ne pense pas que ce serait très intéressant de jouer. Après l'avoir résolu une fois , recommencer avec des règles différentes ne serait pas très différent de jouer au sudoku.
o0 '.
4
D'un autre côté, les gens font des centaines de sudoku avant de s'ennuyer avec eux. Et si vous liez les réponses à une sorte d'action dans le monde plutôt que de simplement taper un numéro ou un nom, les gens ne se plaindront même pas que c'est du sudoku.
Cela me rappelle ce jeu: nick.com/games/series.html
CeeJay
3
Je suggérerais de jeter un œil aux jeux d' Everett Kaser - il a fait une tonne de jeux de cette nature, en particulier Sherlock qui a été inspiré par ce puzzle, mais aussi certains des autres jeux, comme Honeycomb Hotel ou son dernier jeu. , Mme Hudson . Cela pourrait vous aider à voir ce genre de chose en action.
Michael Madsen
@Joe: ce que vous dites est techniquement correct, mais l'important ici est de savoir ce que vous (il) faites. Faire un jeu de type sudoku est bien si vous savez que vous le faites, alors que cela entraînera presque certainement des résultats de merde si vous pensez que vous faites autre chose.
o0 '.

Réponses:

4

Sensationnel. Cela semble en fait être une situation où les sites sémantiques de l'IA à l'ancienne, comme Richard Bartle pensait qu'ils allaient être importants pour l'avenir des jeux lorsqu'il écrivait l'intelligence artificielle et les jeux informatiques , seraient utiles. Vous avez essentiellement quelques listes de données (tables de base de données, peu importe), dont la première spécifie des règles sur la façon dont les choses peuvent être liées les unes aux autres, comme:

a PERSON must LIVE IN a DOMICILE
a PERSON must OWN an ANIMAL
a PERSON must DRINK a BEVERAGE
a PERSON must SMOKE a CIGARETTE BRAND
a PERSON must BE OF a NATIONALITY
a DOMICILE must BE IN a POSITION
a DOMICILE must BE OF a COLOR

Ensuite, vous avez des instances des catégories:

ANIMAL: dog snail zebra fox horse
BEVERAGE: milk tea OJ coffee water
CIGARETTE BRAND: Kools Parliaments Luckies OldGold Chesterfields
NATIONALITY: Englishman Spaniard Ukrainian Japanese Norwegian
POSITION: first second third fourth fifth
COLOR: red green yellow ivory blue

Ces structures de données n'encapsulent pas complètement la situation - vous avez besoin des contraintes d'unicité, et certaines des catégories ont besoin de méta-règles, comme la POSITIONgestion des besoins "à droite de", "à gauche de" et "suivant" aux "concepts, par exemple - mais la structure du problème semble les suggérer fortement.

Je ne sais pas si cela vous mènera très loin, mais j'espère que cela vous aidera.

le chaos
la source
4

Ma recommandation est de regarder le code Python pour les problèmes de satisfaction de contraintes (CSP) fourni avec le projet AIMA . Ils utilisent un dictionnaire (tableau associatif / table de hachage) pour garder une trace des contraintes valides. En outre, il existe des implémentations de plusieurs algorithmes utilisés pour résoudre les CSP, comme les min-conflits et AC3.

Le code inclut un exemple de problème Zebra comme exemple, comme celui auquel vous avez lié.

Brandon
la source
1

Cela va très loin en fait. Étrange que Wikipedia ne le mentionne jamais.

Ce que vous cherchez, ce sont des épreuves très dures qui peuvent probablement être atteintes avec des choses comme les épreuves de Fitch . Nous essayons donc de déduire des choses de nos données données. Il existe de nombreux constructeurs à l'épreuve de Fitch qui font beaucoup de travail pour vous. Mais certains exercices ne sont tout simplement pas à prouver.

Je ne sais pas si l'utilisateur doit faire les calculs. Si c'est le cas, soyez conscient de choses comme 3SAT , qui sont des problèmes insolubles pour le temps polynomial.

Quant aux structures de données que vous souhaitez utiliser, je pense que vous voulez avoir une sorte de Ruleclasse. La règle peut être n'importe quoi, selon le type. Il n'y a pas beaucoup de règles dans les logiques de prédicat , donc cela peut être surmonté en héritant (if, iff, et, or, not ...). Ces règles doivent seulement être évaluées. Et la seule chose qu'une règle peut faire, c'est retourner vrai ou faux. Parce que c'est ce que vous faites avec les logiques de prédicat. À l'université, on m'a recommandé de lire ce livre de John Kelly .

Revenons aux classes: vous devriez voir ces problèmes comme vous verriez implémenter des calculs normaux avec les mathématiques. Qu'est-ce qu'un +opérateur? Il contient deux paramètres, qui peuvent être une nouvelle équation en soi, ou juste un nombre. Je pense que vous avez la même chose avec les règles. Ils peuvent avoir de nouvelles règles comme paramètre, ou simplement un booléen (appelé prédicat).

J'espère que cela vous aide beaucoup, surtout les références. Si vous voulez en savoir plus ou si je vais dans la mauvaise direction, dites-le moi.

Marnix
la source
Le problème n'est pas simplement des preuves dans la logique des prédicats sur un modèle fini (et minuscule!), Ou j'aurais répondu plutôt que de mettre une prime. Le but n'est pas de résoudre le problème - le but est de faire automatiquement le problème, et d'une manière intéressante.
@Joe Le problème, même pour un petit ensemble, serait toujours le problème 3SAT. Si vous ne créez que des ET et des OU, cela pourrait conduire à des choses qui ne sont pas satisfaisantes, donc je pense qu'il serait très difficile de simplement générer un puzzle aléatoire. Le puzzle doit contenir au moins quelques restrictions. Parfois, le raisonnement en arrière pourrait être la réponse (avoir une solution, laisser les choses de côté)
Marnix
La logique générale des prédicats est en fait plus difficile que 3SAT; cependant, les algorithmes de preuve modernes sont vraiment très bons dans la pratique. En plus de cela, générer simplement un modèle, un puzzle et vérifier une solution peut être fait en temps linéaire - l'astuce consiste à s'assurer que les contraintes fournies produisent une solution unique et découvrable.
@Joe y a-t-il donc des contraintes dont nous pouvons être certains pour créer ce puzzle? La question était toujours: quelle infrastructure de données utiliser. Donc je pense toujours que la Ruleclasse est une bonne idée. Je pense que la modélisation de ces contraintes se fait toujours par une logique de prédicat.
Marnix
0

Je n'ai pas de bonne réponse, mais à la recherche d'indices sur le même type de problème, j'ai trouvé ce référentiel sur github:

https://github.com/nateinaction/Zebra-Puzzle

Il contient une certaine logique pour sélectionner les indices et décider du nombre d'indices dont vous auriez besoin pour résoudre le puzzle.

Vegar
la source
-1

Il y a ceci pour le résoudre.

Bien sûr, je pense qu'il ne serait pas trop difficile de travailler en arrière; c'est avoir une liste comme celle-ci:

  • Fred Red Dog

  • Steve Blue Cat

  • Bill Purple Whale

  • Eric Cyan Dolphin

Qui pourrait être facilement généré, puis créer un ensemble de règles à partir de cela.

En ce qui concerne le stockage, pourquoi pas un ensemble de chaque chose distincte, donc [Fred, Steve, Bill, Eric] et un ensemble de réponses [Fred, Red, Dog]. Ensuite, indiquez «NAME does (not) ACTION OBJECT».

En fin de compte, une solution unique est-elle vraiment importante? Tant que votre jeu peut les diviser en listes, et cochez «l'ensemble 1 ne contient pas de baleine».

Le canard communiste
la source
2
L'astuce est que vous voulez que le problème soit toujours difficile. Si les règles que vous générez admettent 90% des combinaisons possibles comme réponses valides, ce n'est plus un casse-tête intéressant.
Je suppose que c'est un point valable - mais la solution n'est-elle pas simplement de réduire le nombre d'indices donnés?
The Communist Duck
1
Non. La sous-spécification est plus susceptible de conduire à de nombreuses conclusions valables. Une surspécification est susceptible de conduire à une conclusion très évidente. Un bon puzzle logique évite les deux.
Ah oui, j'ai raté ça d'une façon ou d'une autre. J'essaierai d'ajouter une meilleure solution si je peux en penser une.
The Communist Duck
Joe: Exactement avec votre premier commentaire. Un puzzle qui vous permet de brouiller des indices bon gré mal gré n'est pas tant un puzzle qu'un projet artistique de jardin d'enfants.
taserian