les chiffres et les lettres sur Spectrum 48K

[Xavier]

Salut,
Tu compliques tout... car ton code doit être réverssible.
Donc usine à gaz sur Spectrum.
Commence plutôt par les chiffres... car je pense qu'il ne faut pas traiter les lettres en tant que lettre...
Mais faire un codage type calcule matriciel sur les lettres utilisées.
Tu gagneras beaucoup de temps si cryptes des mots en pré-programmation.
Tu peux aussi voir du cotê des machines crées pour l'occasion!
Mais, tes 30k me semblent très juste.

[gilles]

visiblement des messages ont été perdus...
Xavier, dans le jeu il y a deux aspects.
La recherche pour vérification pour le joueur et la recherche d'une solution pour l'adversaire simulé par le ZX.
Le dico est à utiliser pour les 2 phases et ce n'est pas la vérification qui posera le plus de problème de perf mais bien la recherche d'une solution. Donc c'est le parcours qui est à optimiser, on ne peut pas utiliser toutes les combinaisons possibles car il y en a trop sur 9 lettres (5.429.503.678.976) ce qui exclue la table de hash. (par contre cette méthode est efficace en vérification).

[phil-nellier]

Salut,
Tu compliques tout... car ton code doit être réverssible.
Donc usine à gaz sur Spectrum.
Commence plutôt par les chiffres... car je pense qu'il ne faut pas traiter les lettres en tant que lettre...
Mais faire un codage type calcule matriciel sur les lettres utilisées.
Tu gagneras beaucoup de temps si cryptes des mots en pré-programmation.
Tu peux aussi voir du cotê des machines crées pour l'occasion!
Mais, tes 30k me semblent très juste.

Merci de ton avis , mais..
1) j'ai volontairement choisi une machine de faible capacité pour voir s'il était possible malgré tout d'implémenter quelque chose de performant (justement le contraire d'une usine à gaz)
2) ta proposition me semble très inadaptée au problème, d'autant que j'ai déjà la réponse en terme de performance, la routine et le dictionnaire sont opérationnels, la recherche de mot prend moins de 10 secondes, et la vérification encore moins. Pourquoi chercher midi à 14 heures ?
3) quant aux chiffres, puisque je crois que nous avons fait à peu près le tour de la question LETTRES, je pense ouvrir un fil parallèle, celui-ci commence a être un peu lourd pour être parcouru dans le détail

Pour conclure, le résultat est là, il reste certainement des optimisations à effectuer, mais à la marge en ce qui concerne les lettres.
Par exemple, en restant sur une compression statique, il est sans doute possible d'associer à chaque code non pas une désinence mais un groupe de désinences fonctionnant ensemble.
Pour les désinences que j'ai choisies, c'est difficile à envisager, quoique faisable pour féminin et féminin pluriel (e et es) ce qui permet de gagner un emplacement, mais malheureusement ça s'arrête là.

Ou alors il faudrait choisir des désinences autres, comme la série "(eu)x, (eu)se, (eu)ses" pour des mots racine tels que joyeux, heureux.. ou encore "(on), (on)ne, (on)nes" pour des mots comme baron, ovation,.. L'optimisation serait alors dans le choix des désinences les plus payantes. En cherchant bien, je pourrais peut-être améliorer le taux de compression, mais ce n'est pas dit, car importe beaucoup le nombre de mots racines pouvant s'employer avec chaque désinence (préfixe et/ou suffixe) ou série de désinences.

[gilles]

as-tu le dictionnaire complet au format texte non compressé et déployé (avec toutes les fin de mot valides)? je testerai bien l'hypothèse de la compression générique de 26 ensembles par la première lettre.
Peut-être en C sur du thomson, le 6809 à 1MHz étant assez proche du Z80 en perfs.

[phil-nellier]

as-tu le dictionnaire complet au format texte non compressé et déployé (avec toutes les fin de mot valides)? je testerai bien l'hypothèse de la compression générique de 26 ensembles par la première lettre.
Peut-être en C sur du thomson, le 6809 à 1MHz étant assez proche du Z80 en perfs.

Intéressante proposition Gilles !
Je n'ai pas le dictionnaire déployé, mais je dois pouvoir le fabriquer assez facilement, à condition d'envoyer depuis l'émulateur du spectrum les mots recomposés ligne par ligne sur le périphérique imprimante puis de transférer le tout en pdf. La question est surtout, pour ton usage, de la manière de te fournir les mots.
Par exemple (DE)[RE)TOURNE(ES)(S)(E)(R), puis à la ligne suivante un autre mot et ses désinences.
ou mot composé par mot composé
TOURNE
DETOURNE
RETOURNE
TOURNEES
TOURNES
etc..
dis-moi comment tu vois les choses...

[phil-nellier]

A propos, pour ceux qui voudraient tester l'efficacité du codage actuel, tant pour les chiffres que pour les lettres, je vous livre le programme de jeu complet en son état actuel :

Cliquer sur le lien ci après => les chiffres et les lettres

L'interface est des plus simples de manière à laisser autant de place que possible au code et au dictionnaire..

Bon jeu

[gilles]

quelle que soit la forme je m'adapterai. a la limite je peux même repartir du dico non déployé mais ce serait un peu plus long, tout dépend si le code est documenté ou non.

[gilles]

je pense à une autre option pour optimiser.
Puisque l'ordi cherche à avoir le meilleur score, autant parcourir d'abord les mots de 9 lettres, puis les 8 et ainsi de suite. (ou peut être d'abord 8 puis s'il reste du temps les 9)
on peut donc avoir 2 axes de découpe par lot, première lettre et taille.
Pour simuler un comportement plus "humain" on peut volontairement limiter le parcours pour les 9 et 8 lettres.

[C.Ret]

[...]
1) il y a bien génération automatique des combinaisons : l'algorithme cherche d'abord les préfixes, puis essaie d'ajouter un suffixe, en testant la longueur de mot obtenue. Enfin, si aucune de ces combinaisons ne fonctionne, il teste successivement les suffixes seuls. Cela implique de n'entrer que des combinaisons valides. Par exemple, pour le mot DORMI, on pourrait coder le préfixe EN et le suffixe ES, mais cela ne marcherait pas car si le mot combiné ENDORMIES est valide, ce n'est pas le cas de DORMIES sans préfixe. On devra donc arbitrer et choisir ou le préfixe, ou le suffixe mais pas les deux.

Merci, cela répond parfaitemetn à mes interrogations. Très astucieux cette façon de coder suffixes et préfixes et cela effectivement permet de bien compresser le dictionnaire, tout en restant parfaitemet cohérant avec son utilisation.
La recherche ne consiste-elle pas à trouver le mot le plus long ?

2) toutes les combinaisons sont essayées, car vu le temps de traitement de la totalité du dictionnaire (7 à 8 s) il est inutile de chercher à optimiser la recherche

Je dois avouer, que je ne programme en général qu'en BASIC sur mes vieilleries 8 bit, alors, parcourir 4000 mots en 7 à 8 s, je ne m'attendais pas à ce que ce soit aussi rapide ! En général, j'utilise des fichiers et les lecteur Commodore sont particulièremetn (peu) véloce. ALors parcourri 4000 RECORDS prend le temps nécessaire.
C'est pour cela que j'aime ces machines, on a le temps de comrpendre ce qui ce passe.

Donc effectivement à ce rythme, il n'est pas besoin de se compliquer le vie et le code avec une méthode de recherche sophistiquée. Même si cela est tentant.

Comme Gilles, ci-dessus, je suis tenté par un algorithme de recherche combinant optimisation de la recherche et compression des données. En particulier, je craignais que la recherche soit lente, et qu'il faille développer une stratégie, comme par exemple regrouper les mots en fonction des lettres qu'il ne contiennent pas (pour limiter le nombre d'échecs lors du test de composition du mot par rapport au tirage (avec et sans ses préfies)), et comme déployer un arbre complet à partir des 26 lettres de l'alphabet est monstueux, j'envisagais de n'utiliser qu'un nombre restreint de lettres clefs, mais en les sélectionnant en fonction du contenu du dictionnaire, afin de maximiser les chances que le premier mots ou les premiers mots acceptables soient aussi ceux qui auront le plus de chance de faire le score maximal. C'est à dire en basant la recherche sur les lettres contenues dans les mots les plus longs; pourquoi utiliser des bits pour coder une branche du dictionnaire qui ne contient pas de lettre stratégique et qui de toute façon ne permettra pas de bon score ?
Mieux vaut d'abord parcourrir les branches proposant les lettres des mots les plus longs.

En plus, cette idée d'évaluer l'importance stratégique d'une lettre, peut aussi avoir un rôle dans le tirage; l'ordinateur demandera une "voyelle" ou une "console" en connaissance de cause et non plus au hazard !


Dans les bases de données spectrales que je manipule chaque jour, il y a par spectres plussieurs millions de canaux et il faut bien compresser car aucun disque dur ne serait capable de mémoriser tout cela et les recherches de 'patterns spectraux' (en français de motif spectral) prendraient des heures. Mais, bien malin serait le spectroscopiste capable de dire quelle partie des spectres est importante, comment et où palcer les points clefs de la base.
Nous laissons donc faire le calcul, en fait la méthode de compression analyse l'ensemble des spectres par des méthodes d'analyses factorielles afin d'en déduire les "axes de symètries", se sont en fait des vecteurs qui permettent de reconstruire 95% de la base de données à, partir d'uniquement une quinzaines des 'profils types'. C'est la base de l'analyse discriminante; en quelques calculs simples, les spectres sont décomposés en combinaison de figures spécifiques.

C'est impressionnant, l'incorporation d'un nouvel échantillon de spetres dans la base prends maintenant environ une heure de calculs, car l'ordinateur doit tout recalculer et restructurer entièrement la base de données (et encore, il y a quinze ans, au début de ma thèse cela prenait une nuit dans une centre de calcul !). Par contre, l'identification d'un spectres soumis à analyse ne prend que quelques secondes (comme dans les feuilletons du NCIS ou des Experts Manhatan- mais sans l'interface graphique qui défile - le seul truc qui s'affiche c'est la liste des compoosés, un coefficient de correlation et un seuil de confiance) C'est sûr que c'est moins spectaculaire qu'à la TV, mais tout aussi efficace.

Pour notre petit dico, on peut utiliser le même principe; c'est l'analyse du dictionnaire qui dicte les lettres à utiliser en priorité. Le nombre qui serait effectivement pris en compte sera dicté par les contraintes d'espace mémoire afin d'optimiser le codage. C'est cette même analyse qui donnerait aussi le score maximal théorique pour chaque lettres (voyelles ou consonnes), ou même pour chaque combinaison de voyelles et consonnes. D'où l'idée de ne plus tirer au hazard celles-ci quand c'est à l'ordinateur de choisir, mais bien de tenter de multiplier les chances de victoire en recherchant les combinaisons fructueuses (celles présentent dans les mots les plus longs du dico) si l'ordinateur se sent fort, ou au contraire en les évitant (si l'ordinateur craint que cela ne donne l'avantage à son adversaire) !


Mais comme la recherche est rapide, c'est peut-être inutile de chercher à associer ces aspects stratégie de recherche ou de jeu avec le codage et la compression du dictionnaire. Ce peut être deux aspects diffèrents du programme.

Dans le même ordre d'idée, au lieu d'imposer les suffixe et préfixes au dictionaire, on peut aussi demander au Spectrum de déterminer quel serait le jeux de suffixes et préfixes qui permettraient la meilleure compression du dictionnaire. Et ensuite de reconstruire un dictionnaire compressé optimisé. Comme pour mes spectres, l'ajout d'un certains nombre de mots peut conduire à revoir la définition des codes des préfixes et suffixes. Mais peut importe, si l'on a automatisé la chaine de compression...
Très vite le système va converger vers un système de codage stable, car plus il y a d'individus dans la base, moins l'ajout d'un nouveau membre aura de chance de remettre en question les comptages. Car contrairement aux spectres que j'obtient au laboratoire, les mots n'ont que quelques lettres, alors qu'un spectre a plusieurs millions de canaux, donc l'ajout d'un seul spectre fait entrer dans ma base beaucoup plus de bruit que d'information, la méthode de compression spctrale est donc très instable, car les individus (de l'odre de plusieurs milliers) ne sont rien fasse aux millions de canaux qui sont potentiellemet autant de source de bruit. (Pour moi, bruit est l'opposé d'un signal ou d'une information, car c'est à partir des signaux contenus dans mes spectres que je les interpréte chimiquement et moléculairement.)

[phil-nellier]

quelle que soit la forme je m'adapterai. a la limite je peux même repartir du dico non déployé mais ce serait un peu plus long, tout dépend si le code est documenté ou non.

Bon, j'ai mis un peu de temps à trouver le moyen de générer un fichier exploitable, (les caractères du spectrumm sont mal compris par les outils d'océrisation)
Mais le voilà enfin disponible en téléchargement sur le lien suivant :

dictionnaire déployé

Séparation simple des mots par des espaces.
Au total 147000 octets sans les espaces (et peut-être quelques retours chariot intempestifs) contre 28490 dans la version compressée exploitée en environnement spectrum, donc effectivement un taux de compression de 80 %, obtenu par la méthode décrite plus haut complétée par l'utilisation des cinq codes non exploités par l'alphabet parmi ceux qui n'utilisent que les 5 premiers bits (décalage appliqué sur la lettre E quand elle existe sur un mot, 5 décalages possibles donnent 5 suffixes supplémentaires (TTE/S, NE/S, UX, MENT,RIE/S). Gain pas très important en fait, mais faisant grapiller encore un bon millier de mots supplémentaires.

Je profite de ce message pour répondre aux observations pertinentes de plusieurs sur l'optimisation de la recherche : effectivement le dictionnaire est classé par ordre décroissant de taille des mots racines, même si ce n'est pas indispensable car en langage machine, l'algorithme balaie tout le dictionnaire en quelques secondes (li faut un bon quart d'heure en Basic !)

[phil-nellier]

Je dois avouer, que je ne programme en général qu'en BASIC sur mes vieilleries 8 bit, alors, parcourir 4000 mots en 7 à 8 s, je ne m'attendais pas à ce que ce soit aussi rapide ! En général, j'utilise des fichiers et les lecteur Commodore sont particulièremetn (peu) véloce. ALors parcourri 4000 RECORDS prend le temps nécessaire.
C'est pour cela que j'aime ces machines, on a le temps de comrpendre ce qui ce passe.

c'est aussi un vrai plaisir pour moi

Donc effectivement à ce rythme, il n'est pas besoin de se compliquer le vie et le code avec une méthode de recherche sophistiquée. Même si cela est tentant.

En plus, cette idée d'évaluer l'importance stratégique d'une lettre, peut aussi avoir un rôle dans le tirage; l'ordinateur demandera une "voyelle" ou une "console" en connaissance de cause et non plus au hazard !

là je diverge ! l'objectif pour moi n'est pas de permettre à la machine de tricher, mais de lui donner les meilleurs moyens d'être efficace justement sans tricher. Car j'ai déjà vu ce genre de développement, un peu facile.. D'ailleurs le programme propose un mode sans tirage aléatoire, les lettres sont choisies par l'utilisateur

Dans les bases de données spectrales que je manipule chaque jour, il y a par spectres plussieurs millions de canaux et il faut bien compresser car aucun disque dur ne serait capable de mémoriser tout cela et les recherches de 'patterns spectraux' (en français de motif spectral) prendraient des heures. Mais, bien malin serait le spectroscopiste capable de dire quelle partie des spectres est importante, comment et où palcer les points clefs de la base.
Nous laissons donc faire le calcul, en fait la méthode de compression analyse l'ensemble des spectres par des méthodes d'analyses factorielles afin d'en déduire les "axes de symètries", se sont en fait des vecteurs qui permettent de reconstruire 95% de la base de données à, partir d'uniquement une quinzaines des 'profils types'. C'est la base de l'analyse discriminante; en quelques calculs simples, les spectres sont décomposés en combinaison de figures spécifiques
Pour notre petit dico, on peut utiliser le même principe; c'est l'analyse du dictionnaire qui dicte les lettres à utiliser en priorité. Le nombre qui serait effectivement pris en compte sera dicté par les contraintes d'espace mémoire afin d'optimiser le codage. C'est cette même analyse qui donnerait aussi le score maximal théorique pour chaque lettres (voyelles ou consonnes), ou même pour chaque combinaison de voyelles et consonnes. D'où l'idée de ne plus tirer au hazard celles-ci quand c'est à l'ordinateur de choisir, mais bien de tenter de multiplier les chances de victoire en recherchant les combinaisons fructueuses (celles présentent dans les mots les plus longs du dico) si l'ordinateur se sent fort, ou au contraire en les évitant (si l'ordinateur craint que cela ne donne l'avantage à son adversaire) !

très intéressant, cette approche des bases de donnée spectrales : en fait, lors de la constitution du dictionnaire, on s'aperçoit vite qu'après avoir balayé les mots les plus juteux en terme de compression, le nombre d'anagrammes augmente rapidement, et on est alors obligé de se rabattre sur des mots plus complexes et uniques,. C'est un profil en cloche, et on est très vite limité.

[C.Ret]

là je diverge ! l'objectif pour moi n'est pas de permettre à la machine de tricher, mais de lui donner les meilleurs moyens d'être efficace justement sans tricher. Car j'ai déjà vu ce genre de développement, un peu facile.. D'ailleurs le programme propose un mode sans tirage aléatoire, les lettres sont choisies par l'utilisateur

Loin de moi l'idée de "tricher", mais il y a longtemps que je n'ai plus suivi ce jeu à la télé.
Pour le tirage des lettres, le candidat doit-il toujours indiquer 'consonne' ou 'voyelle' ?

http://www.ina.fr/video/I11026231/premi ... nt.fr.html


Ou aors est-ce par aleternance, chacun des deux joueur devant indiquer s'il souhaite une 'consonne' ou une 'voyelle'.

Je partiat du principe que choisir judicieusement l'une ou l'autre, faiait partie de la stratégie du jeu; un bon équilibre permettant des mots plus longs et plus facile à trouver (ce qui peut aussi favoriser l'adversaire), et un déséquilibre risquant de limiter la longueur du mot mais qui pourrait cependant être plus dificile à trouver (notons que là aussi il faut tenir compte de l'habileté de son adversaire).

[phil-nellier]

là je diverge ! l'objectif pour moi n'est pas de permettre à la machine de tricher, mais de lui donner les meilleurs moyens d'être efficace justement sans tricher. Car j'ai déjà vu ce genre de développement, un peu facile.. D'ailleurs le programme propose un mode sans tirage aléatoire, les lettres sont choisies par l'utilisateur

Loin de moi l'idée de "tricher", mais il y a longtemps que je n'ai plus suivi ce jeu à la télé.
Pour le tirage des lettres, le candidat doit-il toujours indiquer 'consonne' ou 'voyelle' ?
http://www.ina.fr/video/I11026231/premi ... nt.fr.html
Ou alors est-ce par aleternance, chacun des deux joueur devant indiquer s'il souhaite une 'consonne' ou une 'voyelle'.
Je partiat du principe que choisir judicieusement l'une ou l'autre, faiait partie de la stratégie du jeu; un bon équilibre permettant des mots plus longs et plus facile à trouver (ce qui peut aussi favoriser l'adversaire), et un déséquilibre risquant de limiter la longueur du mot mais qui pourrait cependant être plus dificile à trouver (notons que là aussi il faut tenir compte de l'habileté de son adversaire).

Oui, c'est par alternance que chacun choisit consonne ou voyelle.
Le choix est effectivement capital dans la stratégie. Il est évident que dans le cas exposé ici, l'ordinateur qui ne dispose pas de beaucoup de place pour son dictionnaire devrait privilégier les voyelles, car la plupart des mots sont issus de développements par préfixes et suffixes utilisant des voyelles. Je n'ai pas incorporé un tel algorithme mais cela devrait pouvoir se faire, sans tricher !

[Xavier]

Code : Tout sélectionner

#     LE COMPTE EST BON.
#       DE G.BARTHEL
#  ®®®®®®®®®®®®®®®®®®®®®®®®
#     MIS EN MEMOIRE PAR
#           XAVSNAP
#  ®®®®®®®®®®®®®®®®®®®®®®®®
#
# UTILISEZ VB81 XUR OU ZXTOKEN
# POUR COMPILER CE PROGRAMME.
#
#   ordi‘œ NUMERO 4 PAGE 49
#
#          -=OoO=-
#
1 SLOW
2 LET X=1
3 DIM B(6)
4 DIM G(6)
5 DIM A(6)
6 DIM H$(6,1)
7 DIM H(6)
8 DIM I(6)
9 PRINT AT 5,2;"DONNEZ LES 6 CHIFFRES ?"
10 FOR N=1 TO 6
20 INPUT B(N)
25 PRINT AT 7+N*2,5;"*>";B(N);
30 NEXT N
35 CLS
50 PRINT AT 5,2;"LE CHIFFRE A TROUVER ?"
53 INPUT C1
55 CLS
56 FAST
57 FOR O=1 TO 6
58 DIM E(20)
59 LET Q=1
61 FOR P=1 TO 6
62 LET A(P)=B(P)
63 NEXT P
65 LET C=C1
80 FOR N=O TO 6
90 FOR M=1 TO 6
95 IF A(M)=0 OR N=M THEN GOTO 130
115 LET E=(C-A(N))/A(M)
118 IF E=INT E THEN GOSUB 4000
120 IF E=INT E THEN GOTO 1000
122 LET E=(C+A(N))/A(M)
123 IF E=INT E THEN GOSUB 4000
125 IF E=INT E THEN GOTO 2000
130 NEXT M
140 NEXT N
141 LET X=1
142 CLS
143 GOTO 5000
145 NEXT O
150 PRINT AT 5,2;"NON JE NE TROUVE PAS"
155 STOP
160 PRINT AT 0,2;"LE COMPTE EST BON."
161 FOR N=1 TO X-1
162 PRINT AT 18-(N*2),5;G(N);H$(N);H(N);"=";I(N)
163 NEXT N
165 PRINT AT 2,10;C1
168 PRINT AT 20,3;
170 FOR N=1 TO 6
180 PRINT B(N);" * ";
190 NEXT N
200 COPY
210 STOP
1040 LET B=E*A(M)
1050 LET D=B+A(N)
1052 IF A(N)=0 THEN GOTO 1065
1053 LET G(X)=B
1054 LET H$(X)="+"
1055 LET H(X)=A(N)
1056 LET I(X)=D
1062 LET X=X+1
1065 IF E=1 THEN GOTO 1080
1066 LET G(X)=E
1067 LET H$(X)="X"
1068 LET H(X)=A(M)
1069 LET I(X)=B
1075 LET X=X+1
1080 LET C=E
1090 LET A(N)=0
1100 LET A(M)=0
1150 IF E=1 THEN GOTO 160
1200 GOTO 80
2000 LET B=E*A(M)
2010 LET D=B-A(N)
2011 LET G(X)=B
2012 LET H$(X)="-"
2013 LET H(X)=A(N)
2014 LET I(X)=D
2030 GOTO 1062
4000 FOR P=1 TO 20
4010 IF E=E(P) THEN GOTO 130
4020 NEXT P
4500 RETURN
5000 IF Q=20 THEN GOTO 145
5010 LET E(Q)=C
5020 LET Q=Q+1
5030 GOTO 61
6000 REM ----------------------
6010 REM (C)G.BARTHEL ET ORDI-5
8020 REM    LE COMPTE EST BON

[phil-nellier]

A propos du "compte est bon"
je connais ce programme paru il y a nombre d'années sur Ordi 5, et que j'avais testé. Hélas, il ne teste qu'une infime partie des possibilités, n'utilise pas non plus tous les signes d'opération, et s'il s'avère performant pour du Basic (car le temps imparti et la lenteur de calcul du Basic Sinclair ne permettent pas mieux) c'est tout relatif et loin d'être probant. L'assembleur est le seul moyen d'obtenir du Spectrum une réelle efficacité dans cet exercice.

A propos Xavier, j'avais ouvert un fil spécifique pour "le compte est bon", ce serait peut-être bien d'y aller voir, j'y explique l'algorithme que j'emploie.