créer un scrabble contre ordinateur

Question

bonjour à toutes et tous


quelques questions à tous les champions de la programation.


Je suis en train d'essayer de faire un jeu de scrabble, le jeu jeu en solitaire ,les points, la vérification des solutions ça ça va!


Mais ce qui deviens très difficilec'est lorsque je veux que l'ordinateur donne toutes les solutions possible.


J'ai bien réussi à le faire mais gros , très gros problème c'est que le temps de réflexion de l'ordinateur devient très long au fur et à mesure que la partie se déroule.


Je voudrais votre avis d'abord est ce que le language VB est il approprié pour ce genre de logiciel? Et pourquoi, lequel le mieux approprié?(de toutes manières je ne connais que celui là!)


Et mon autre question serait plus sur le raisonnement à avoir:


là je parcours tout le plateau à la recherche des cases non vides!à partir de cette case je note toutes les cases qui pourraient rentrer dans un mot sur cette ligne, je les ajoute à celle du chevalet, j'en cherche tous les anagrames possibles, et à partir des dictionnaires classés je cherche les mots qui correspondent aux anagrames, une fois un mot trouvé je vérifie qu'il s'inscrit bien sur le plateau (surtout dans les mots croisés qu'il génère) et comptabilise les points réalisés. je fait cette opération pour presque toutes les cases , ligne par ligne, puis colonne  par colonne. De plus il faut vérifier si on peut juxtaposé des mots, pour celà il faut vérifier à chaque case pleine soit devant soit dessus soit derrière soit dessous si on peut juxtaposé un mot fabriqué à partir des lettres du chevalet. Tout ceci deviens très long !!!! Mais aucune solution ne m'échappe de la plus pettite à la plus longue et de la plus simple à la plus tordue.


Je n'ai vu qu'un logiciel jouant contre l'ordinateur "DzWords 2.0" vraiment pas mal, je n'ai pas testé toute une partie mais prometteur. problème je n'ai pas le code source pour comprendre comment il a fait.


Je serais preneur de toute aide.




 


merci àtous d'avance

jmfmarques · Answer

Bonjour,

Si la base de données (ton "dictionnaire") est complète, ce qu'il te faut tout simplement "bûcher", c'est la syntaxe des SQL. Cette syntaxe peut utiliser les caractères jokers, les lettres à imposer, celles à refuser, l'emplacement forcé d'une ou de plusieurs lettres, la longueur forcée du mot, etc.... de sorte à n'extraire de ta base que les mots correspondants à ces critères.
Une requête pouvant inclure des ET et des OU imbriqués, elle te conduira à une pu à plusieurs solutions (si elles existent)...
Ce qui ne va pas, par contre, c'est faire ce que tu fais, c'est à dire le contraire : chercher des anagrammes et vérfier s'ils correspondent à un mot (car là oui, c'est long, bien évidemment).
Voilà donc : bûche la syntaxe des requêtes.

BruNews · Answer

marco, jette un oeil ici:
AIDE AUX MOTS CROISES (WIN32)
http://www.cppfrance.com/code.aspx?ID=31892

Tu auras une "idée" de solution pour le moteur des mots (recherche, classement, insertion), c'est très proche de celui que j'avais fourni pour un scrabble. Tu constateras qu'il faut un certain travail pour obtenir du performant, autant dire de suite que ça exclut VB ce genre d'exercice, il faut accéder à la mémoire quand on veut des perfs.

ciao...
BruNews, MVP VC++

jmfmarques · Answer

Oui...
En gardant toutefois à l'esprit que, contrairement aux mots-croisés, on a entre les mains des lettres à utiliser.

BruNews · Answer

Combiner les lettres est infiniment plus rapide que parser des milliers de mots.

Il convient toujours de rappeler que les langages ont différentes cibles, ça évite aux gens de perdre leur temps.

ciao...
BruNews, MVP VC++

jmfmarques · Answer

Bonjour Brunews (tu as probablement raison),

Mis à part ce choix de langage et de méthode, j'ai pour notre ami une petite suggestion de nature à rendre le programme moins puissant que le joueur, au début, mais de plus en plus fort ensuite....

L'idée, je le dis de suite, n'est pas de moi. Elle est celle d'un collègue ayant développé une application SCRABBLE...

Principe : l'ordinnateur n'a au début qu'une quantité limitée de mots valides en mémoire (il est donc encore "faible"...)
A chaque étape du jeu : tout mot accepté comme valide vient enrichir sa base de données.
De cette manière :
1) le joueur est confronté à un adversaire de plus en plus fort
2) le développeur voit sa tâche d'alimentation de la base de données considérablement allégée

BruNews · Answer

oui oui, l'idée est fort juste pour ce qui est du réglage de la puissance de "réflexion" de l'ordi.

Par contre ça induit de gérer 2 bases et de les synchroniser au fur et à mesure, encore du code performant à prévoir.

ciao...
BruNews, MVP VC++

cs_MPi · Answer

J'ai aussi travaillé sur un jeu de Scrabble avec un dico, je pense, complet...
Mais encore, un dico de Scrabble est différent des dicos de langue française...
Celui que j'ai réussi à créer est plutôt un dico de langue française... il me semble...ça fait longtemps...

Mais j'en suis au même point que Marco. Comment faire pour créer un algorithme rapide, côté ordinateur...(?)

J'ai un jeu de Scrabble créé par UBI Soft qui permet 10 niveaux, un peu comme certains jeux d'échecs ... C'est assez époustouflant de le voir aller et créer des mots collés à d'autres et former 5 mots différents avec quelques lettres déjà placées, et le tout en une fraction de seconde... Quelle est donc la formule magique ? quel est la base de ce calcul ? Faut-il être un mathématicien de premier ordre ?

Et comment alors définir un niveau d'efficacité de calcul basé sur autre chose que l'apprentissage du logiciel lui-même (?) Comment permettre un calcul plus ou moins complexe pour être facile à battre ou imbattable (?)

N'étant pas mathématicien, moi-même, je pense que tout est là... une logique mathématique... mais laquelle ???

Le principe de ma base de données est 2 champs: les anagrammes et les mots possibles.
Dans mon esprit, ça ne peut pas être plus simple, mais peut-être que je me trompe totalement ?

Marco, je pense que tu es sur la bonne voie, mais lors du placement de mots par l'ordi, je pense que tu devrais t'attarder à certains endroits de la "plaque de jeu" plutôt que de tout parcourir... Et peut-être même, pendant que le joueur pense à son coup, l'ordi devrait penser à ses stratégies selon ce qui est déjà placé. Est-ce qu'on parle alors de multi-threading ? Bon je suis fatigué et vais me coucher ... Bon matin à vous, les français, ici c'est la nuit...

MPi

cs_MPi · Answer

Après une nuit trop courte ..., j'en suis venu à me demander si le jeu commercial que j'ai n'utilisait pas 2 programmes (?)

Un qui sert de jeu
Un autre qui sert seulement à rechercher des mots à placer pendant que l'utilisateur s'amuse à placer, déplacer ses lettres,...

Ce qui m'a fait penser à ça, c'est que lorsqu'on joue normalement, l'ordi ne met que très peu de temps à "riposter" avec son mot. Par contre, il y a une option "indice" qui demande à l'ordi de trouver un mot à placer avec nos propres lettres et là, c'est un peu plus long ... il y a un temps de réflexion de quelques secondes de plus.

Comme VB6 ne gère pas le multi-threading, je pense que l'option d'un deuxième programme pourrait être intéressant. Reste à savoir comment gérer tout ça...(?)

MPi

cs_marco62118 · Answer

Merci à tous de vous intéresser, je suis franchement content qu'on puisse aider les autres comme ça!!!!

d'abord Brunews , je me doute bien que le VB n'est pas le programme idéal, j'avais déjà vu qu'en C++ on pouvais faire des choses plus rapide, peut être une des fonctions en plus, mais je n'y connait rien en C++ et je crois déjà assez difficile à se mettre à un language.Je suis allez voir le lien que tu donnes et malheureusement les commentaires ne m'ont pas encouragé à lire et à essayer de comprendre ta programation qui plus est en C++, domage....
à jmfmarques Je crois qu'il faut utiliser les deux car sur le chevalet tout de même sept lettres on a aucune idée des mots faisables, et c'est surtout intéressant lorsqu'on veut juxtaposé un mot aux mots déjà écrit sur le plateau.
Donc ma recherche de solution se décompose en deux recherches de conception différente:
 la première conception: pour les mots juxtaposés, (répété qutre fois devant dessus dessous derrière), 
premièrement avec chaque lettre du chevalet vérifie que cette lettre peut être juxtaposé à un endroit bien défini,devant derrière dessus dessous d'une lettre donnée du plateau
deuxièment avec les 7 lettres du chevalet recherche des anagrames faisables , à partir de là recherche de tous les mots existants (cette recherche est faite une seule fois en début de coup et enregistré dans un tableau) cette recherche est assez rapide. j'ai créé des dictionnaires de 2 à 15 lettres avec 2 champs l'anagrame et le mot ( pour rejoindre ce que dissait MPI) 
troisièment avec la lettre juxtaposé , sa position dans les mots trouvés c'est de vérifier que ce mot peut bien s'insérer, que tous les mots croisés qu'il génére sont valides et dans la foulée calculée les points, le tout mis dans un tableau temporaire de solutions .
la deuxième conception : c'est pour créer des mots dans le sens horizontal et vertical, c'est là que c'est plus complexe et plus long et que certainement les requêtes SQL sont certainement intéressantes. Mais je ne connais absolument pas les requêtes SQL! 
donc moi je travaille ligne par ligne ou colonne par colonne, j'ajoute toutes les lettres ( jusqu'à la taille faisable d'un mot exemple d'une ligne  : 4 lettres , 3cases vides, 1 lettre ,5 cases vides, 2lettres, ma première recherche ne pourra se faire qu'avec les 4 lettres 3vides1lettres et les 7 lettres du chevalet donc 12 lettres avec les 4 première obligatoires, à partir de là recherche d'anagrame et de mots faisables puis vérification que ces mots s'insére bien sur le plateau et encore une fois que les mots croisés générés existent bien.
Comme tu le dits ,j'éduque mon ordinateur , premièrement j'ai inscrit dans chaque case au fur et à mesure qu'on joue et on écrit des mots sur le plateau, le nbre de cases vide horizontalement ou verticalement ou la case se trouve, les mots qui se trouvent immédiatement au voisinage de la case, avec leur points. Et je vais en plus essayer d'incrire dans les cases aux extrémités de mots si on peut encore rajouter des lettres devant ou derrière ces mots.
à MPI: Je ne pense pas qu'il existe une solution mathématique Et j'ai bien pensé à faire travailler l'ordinateur pendant que le joueur déplace des lettres ou réfléchit mais là je ne sais comment. Je crois que ça peut être un sujet de discusion suplémentaire.
Il serait peut être intéressant de poursuivre en commun cette recherche

encore merci à vous

cs_MPi · Answer

En fait, l'idée d'un deuxième programme ou d'un deuxième thread serait de créer des mots possibles pendant que l'utilisateur joue son tour. Ces mots pourraient être inscrits dans un fichier ou dans la base de données et annulés s'il y a placement de lettres dans une des régions visées. Ceci ayant pour but d'accélérer le coup de l'ordi ...

Mais je connais les contraintes de vérifications, calculs, validations,... et c'est assez tordu comme expérience informatique...

Je pense aussi qu'il faut éviter les pièges, c'est-à-dire de prendre une direction qu'on croit logique en passant à côté de pistes plus simples, mais qu'on oublie ou qu'on ne voit plus à force de se concentrer sur autre chose... C'est pourquoi j'ai laissé le jeu de côté en espérant me réveiller un matin en criant Eureka !

Mais je vais suivre ce post avec intérêt

MPi

Créer un scrabble contre ordinateur

10 réponses

Votre réponse