Misez p'tit Optimisez n°91 : balade du cavalier

[C.Ret]

Merci Maître Marge, ces précisions m'étaient nécessaires, je n'avais pas vu quelques subtilités, je suis en pleine séquence diatomique de Stern-Brocot pour le moment et mon HP-15C me sert bien à tenter de proposer un code décent pour une HP-65.

Mais, je vais certainement plus tarder à essayer ton code sur mon HP-15C et vérifier sa vélocité.

Il me faut aussi trouver un échiquier de belle allure comme celui que tu montres sur ta photo, je crois que pendant mes prochains déplacements et villégiatures, il y a de quoi faire sensation dans le lobby des hôtels et sur les terrasses des cafés avec un beau plateau, quelques jetons et un cavalier (blanc, noir ou assorti au plateau, peu importe), il y a de quoi faire fureur.

Vivement que nous puissions à nouveau nous croiser lors d'un mini-pockétiquaire, il va falloir penser à organiser une compétition de Rösselsprung :

.

[Marge]

Merci Maître Marge, ces précisions m'étaient nécessaires [...]

C'est bien trop d'honneur, votre honneur, merci !

Mais, je vais certainement plus tarder à essayer ton code sur mon HP-15C et vérifier sa vélocité.

Tu seras probablement déçu, c'est très lent. J'ai entré le code et le chronométrerai, on doit avoisiner les 45 secondes à une minute par coup.

Il me faut aussi trouver un échiquier de belle allure comme celui que tu montres sur ta photo, je crois que pendant mes prochains déplacements et villégiatures, il y a de quoi faire sensation dans le lobby des hôtels et sur les terrasses des cafés avec un beau plateau, quelques jetons et un cavalier (blanc, noir ou assorti au plateau, peu importe), il y a de quoi faire fureur.

Si tu savais... et tu vas savoir : j'ai acheté ce bel échiquier ici au début de l'année, les pièces étaient proposées avec, je ne les ai pas prises et j'ai choisi de m'en procurer de plus belles début mars... en Inde : je les attends toujours, bien sûr, et on comprend facilement pourquoi, cependant la direction de la poste indienne a décidé que les colis supérieurs à un certain poids ne bougeraient plus, et je n'ai donc pas de pièces adéquates...

Vivement que nous puissions à nouveau nous croiser lors d'un mini-pockétiquaire, il va falloir penser à organiser une compétition de Rösselsprung.

En effet, cet isolement commence à peser, chacun se sent comme un cavalier sur un échiquier déserté... Mais ça viendra !

[Marge]

« Saisissant sa scie, Sissa s'assit sans un sou. »

C'est amusant comme ce présent défi m'a tout le temps rappelé ce faux challenge du nombre de grains de blé de 2015 (comme le temps passe vite !)...

Tout ça pour vous dire qu'après ce programme - et probablement quelques adaptations prochaines, il me tarde de savoir comment la 67 et la 97 se comportent en comparaison de la 15C -, je lèverai sacrément le pied sur les MPO pour revenir à mon jeu de cartes. Je crois m'être démontré que je n'aimais pas lâcher les os qu'on me donne à ronger, cela me suffit.

Je tiens à remercier ledudu pour cet ultime amusement en regrettant qu'il en soit venu à vendre toute sa collection de Casio au point de ne pouvoir proposer qu'une résolution sur TI-57 (ce qui, plaisanterie mise à part, devrait être possible dans un rectangle 3 par 5 ou 3 par 6).

@+

[ledudu]

Je tiens à remercier ledudu pour cet ultime amusement en regrettant qu'il en soit venu à vendre toute sa collection de Casio au point de ne pouvoir proposer qu'une résolution sur TI-57.

[Marge]

Le match

À ma gauche, l'honorable 15C de 1982, à ma droite sa challenger, la 15C Limited Edition de 2011.

La case de départ sera la case e5 (ou x=5, y=5).

L'arbitrage sera assuré par Miss 41CX munie de son chronomètre.

À vos marques... prêtes ? Partez !



Heu, c'est plié :

• la 15C met environ une minute et vingt secondes pour calculer un déplacement parmi huit possibles ;

• la 15C Limited Edition ne nécessite que vingt-deux secondes pour parcourir tout l'échiquier.

J'ai retiré le temps d'initialisation de la 15C (environ 6 secondes) ; j'ai retiré le pas 54 (R/S) de la 15C LE.

Pour être très précis, il faudrait chronométrer tout le parcours de la 15C : on peut estimer que ce parcours lui demanderait pas loin de soixante-quinze minutes, soit près de 230 fois plus de temps qu'à la Limited Edition.

J'édite à présent ce message car je suis en mesure de revoir le chrono de la tenante du titre (2239A02218) dans la catégorie dite des Drapeaux de Warnsdorf à la baisse. Il a fallu que je m'y reprenne à deux fois tant j'ai été surpris par son sprint final (qui s'explique assez bien par l'amenuisement du nombre de possibilités à mesure que le cavalier avance dans son parcours).

Le nouveau temps officiel est de 57 minutes 43 secondes 92 centièmes, avec une marge d'erreur d'une demi-seconde au maximum.

Cela diminue d'autant le temps moyen par coup (55 s. à peu près) et le rapport de vélocité entre les deux machines : la 15C n'est qu'environ 157 fois moins rapide que la Limited Edition.

Je vous redonne le programme ici, c'est plus pratique :

[C.Ret]

Et oui, c'est bien ce qui m'inquiétais le plus dans cette aventure, c'est qu'une HP-15C classique est très lente et l'HP-15C L.E. très très rapide.

Quand j'ai vu la photo, l'arbitre et les deux modèles en compétition, mon cœur c'est serré très fort pour la classique de 1982 car mon esprit me disait que vu qu'il n'y a pas d'instruction PSE, elle n'a aucune chance face à la technologie de son futur.

Maître Marge, il suffirai d'ajouter un ou deux PSE dans votre code, et l'HP-15C classique de 1982 gagne par forfait suite à l'abandon de sa rivale !

En tout cas, ça donne envie, j'ai moi aussi l'envie d'essayer de faire entrer de Wansdorf dans mon HP-15C.

Ce qui me surprend, c'est que malgré sa vélocité, la cadeau d'anniversaire limité HP-15C L.E. (j'ai du mal avec les traduction en ce moment), est battue par mon algorithme par dé-mnémodirection-polaire-rectangle qui reste plus rapide sur mon HP-15C (U.S.A. 2533A34568 donc 1985) qu'un algorithme Wansdorf sur HP-15c L.E. car chaque coups est calculé en environ 9 s.

Je redonne ci-dessous le code pour HP-15C et le contenu des registres à saisir.

MPO91_HP-15C_Code.gif (66.49 Kio) Vu 6702 fois

HP-15C Registers Initialisation.gif (33.91 Kio) Vu 6702 fois

Par exemple, les premiers coups en partant de la case D5 :

MPO91_HP-15C_Chessboard_(initial D5).gif (7.88 Kio) Vu 6702 fois

[Marge]

Ah, il va falloir que je teste cela. Mais pourquoi n'avoir pas entré les données initiales dans le code ? Ça doit tenir dans les nombreux pas avec seulement 12 registres utilisés, non ?
Il est vrai que, comme tu l'as indiqué précédemment, cela n'est finalement pas très utile puisque les registres sont retenus avant chaque nouveau parcours du cavalier... ce le serait pourtant si on pouvait trouver une astuce mathématique pour raccourcir ces entrées, un peu comme je l'ai fait dans l'initialisation de mon programme.

Je suis vraiment surpris que ton code soit aussi rapide, il va me falloir lire attentivement tes explications...

Ce qui me surprend, c'est que malgré sa vélocité, [la Limited Edition] est battue par mon algorithme par dé-mnémodirection-polaire-rectangle qui reste plus rapide sur mon HP-15C (U.S.A. 2533A34568 donc 1985) qu'un algorithme Warnsdorf sur HP-15c L.E. car chaque coup est calculé en environ 9 s.

En réalité, non : les 22 secondes de la LE correspondent au parcours total du cavalier sur l'échiquier, non pas d'un seul coup.
Cela dit, 9 secondes contre 55 sur les 15C, cela reste un écart gigantesque.

P.-S. : message précédent édité avec le nouveau temps pour la 15C.

[C.Ret]

[...]En réalité, non : les 22 secondes de la LE correspondent au parcours total du cavalier sur l'échiquier, non pas d'un seul coup.[...]

A zut, tous mes espoirs viennent de s'écrouler d'un seul coup...

Et je comprends mieux pourquoi l'instruction PSE ne peut fonctionner convenablement, a cette vitesse on ne voit plus rien...

Sinon, oui, trouver une formule pour "compresser" le parcours mémorisé permettrait d'éviter d'avoir à sacrifier 72 pas pour initialiser l'échiquier et les quelques registres supplémentaires.
Mais je n'ai rien trouvé d'approprié.

Une voie que j'avais entrevue, mais que je n'est pas explorée comme elle le mériterai, est d'utiliser, pour décrire le parcours du cavalier le tracé généré par un système épicycle issue d'une transformée de Fourrier complexe.

[Marge]

Et je comprends mieux pourquoi l'instruction PSE ne peut fonctionner convenablement, a cette vitesse on ne voit plus rien...

Bonsoir, mon unique camarade à ce jeu récréatif,

Rien n'est moins sûr : l'affichage "running" fonctionne tout à fait normalement et même plus lentement sur la nouvelle que sur l'originale.
Que faut-il en conclure ?
Que les circuits commandant l'affichage sont indépendants de ceux impliqués dans le fonctionnement du calcul intérieur à la machine.

Cela reste à démontrer mais j'en suis pour l'instant persuadé.

Je tenterai une boucle...

[Danny]

Je débarque sur ce sujet intéressant
J'ai adapté le code de Marge sur HP-42S, pour essayer de visualiser le déplacement du cavalier en profitant de ses capacités graphiques (quoique plus limitées que celles du Sharp de C.Ret )

Du coup j'ai découvert ce qui suit, je sais pas si c'est normal (parce que j'ai pas l'impression de l'avoir lu dans les messages précédents) ou si j'ai fait une connerie dans le code, mais :
- dans la majorité des cas, le cavalier arrive à parcourir tout l'échiquier, sauf 2 cases : la h8 [8,8] et la h1 [8,1].
- sauf si on part d'une de ces 2 cases, auquel cas seule l'autre reste non parcourue au final.
- il y a des cas où il reste 3 cases non parcourues à la fin, en partant de a4 [1,4] par exemple.

Au final, j'ai pas testé tous les cas possibles mais on dirait bien que l'échiquier n'est jamais parcouru entièrement et qu'il reste toujours au moins 1 case (dans un coin de la colonne h) qui reste vide... vous avez constaté la même chose ?

IMG_7793.jpg (21.89 Kio) Vu 6606 fois

IMG_7794.jpg (21.66 Kio) Vu 6606 fois

IMG_7792.jpg (21.75 Kio) Vu 6606 fois

IMG_7791.jpg (24.38 Kio) Vu 6606 fois

Code : Tout sélectionner

00 { 490-Byte Prgm }
01▸LBL "Cavalie"
02 SCI 01
03 CLRG
04 STO 10
05 X<>Y
06 STO 09
07 0,34666643
08 STO 02
09 STO 07
10 8,9109
11 1/X
12 -
13 STO 08
14 STO 01
15 2
16 ×
17 STO 03
18 STO 04
19 STO 05
20 STO 06
21 0,063
22 STO 00
23 CLLCD
24 CLA
25 CF 34
26 SF 35
27 255
28 XTOA
29 1
30 1
31 AGRAPH
32 R↓
33 8
34 X<>Y
35 AGRAPH
36 R↓
37 19
38 AGRAPH
39 R↓
40 R↓
41 1
42 19
43 AGRAPH
44 "Σ"
45 3
46 35
47 AGRAPH
48 6
49 42
50 PIXEL
51▸LBL 22
52 RCL 00
53 STO 20
54 RCL 10
55 10
56 ÷
57 RCL 09
58 +
59 RCL 00
60 IP
61 1
62 +
63 10↑X
64 ×
65 XEQ 66
66 ISG 20
67 GTO 22
68 RTN
69▸LBL 22
70 RCL 20
71 STO 00
72 RCL 10
73 STO 20
74 RCL 09
75 XEQ 09
76 CLX
77 XEQ 08
78 STO IND 20
79 CF 00
80 CF 01
81 CF 02
82 SF 03
83 8
84 STO 20
85▸LBL 00
86 RCL 09
87 FS? 00
88 RCL 10
89 1
90 FS? 01
91 +/-
92 +
93 X≤0?
94 GTO 00
95 8
96 X<>Y
97 X>Y?
98 GTO 00
99 FS? 03
100 STO 11
101 FS? 00
102 STO 12
103 RCL 10
104 FS? 00
105 RCL 09
106 2
107 FS? 02
108 +/-
109 +
110 X≤0?
111 GTO 00
112 8
113 X<>Y
114 X>Y?
115 GTO 00
116 FS? 03
117 STO 12
118 FS? 00
119 STO 11
120 XEQ 23
121▸LBL 00
122 DSE 20
123 GTO IND 20
124 RCL 13
125 STO 09
126 RCL 14
127 STO 10
128 0
129 STO 15
130 GTO 22
131▸LBL 07
132 SF 00
133 CF 03
134 GTO 00
135▸LBL 06
136 SF 01
137 GTO 00
138▸LBL 05
139 SF 02
140 GTO 00
141▸LBL 04
142 CF 00
143 SF 03
144 GTO 00
145▸LBL 03
146 CF 01
147 GTO 00
148▸LBL 02
149 SF 00
150 CF 03
151 GTO 00
152▸LBL 01
153 CF 00
154 SF 01
155 CF 02
156 SF 03
157 GTO 00
158▸LBL 23
159 RCL 12
160 X<> 20
161 STO 12
162 RCL 11
163 XEQ 09
164 X=0?
165 GTO 23
166 1
167 -
168 STO 16
169 XEQ 08
170 STO IND 20
171 RCL 16
172 RCL 15
173 X=0?
174 GTO 25
175 X>Y?
176 GTO 25
177 GTO 23
178▸LBL 25
179 X<>Y
180 STO 15
181 RCL 11
182 STO 13
183 RCL 20
184 STO 14
185▸LBL 23
186 RCL 12
187 X<> 20
188 STO 12
189 RTN
190▸LBL 09
191 1
192 -
193 10↑X
194 STO 17
195 RCL IND 20
196 FP
197 STO IND 20
198 ×
199 IP
200 RCL 17
201 LASTX
202 FP
203 10
204 ×
205 IP
206 STO+ IND 20
207 R↓
208 LASTX
209 FP
210 R↓
211 ÷
212 X<>Y
213 R↓
214 RCL IND 20
215 IP
216 RTN
217▸LBL 08
218 XEQ 11
219 X<>Y
220▸LBL 11
221 RCL 17
222 ÷
223 10
224 ÷
225 +
226 RTN
227▸LBL 66
228 17
229 RCL 10
230 2
231 ×
232 -
233 RCL 09
234 2
235 ×
236 1
237 +
238 PIXEL
239 1
240 25
241 RCL 00
242 1
243 +
244 IP
245 10
246 X>Y?
247 GTO 67
248 ÷
249 FP
250 10
251 ×
252 5
253 STO+ ST Z
254 R↓
255 XEQ "UFL"
256 1
257 25
258 RCL 00
259 1
260 +
261 IP
262 10
263 ÷
264 IP
265 ENTER
266▸LBL 67
267 R↓
268 XEQ "UFL"
269 1
270 38
271 RCL 09
272 XEQ "UFL"
273 1
274 44
275 RCL 10
276 XEQ "UFL"
277 PSE
278 RTN

[Danny]

Je viens de voir aussi qu'à la fin du parcours complet, il reste quelques cases de la colonne h qui ont toujours le poids 1, comme si elles n'étaient pas occupées (alors qu'elles le sont)... on dirait que la mise à zéro des poids se comporte différemment pour la colonne 8 ?

Et sinon, a priori en modifiant R1 et R8 avec les poids 2 3 4 4 4 4 3 3, l'échiquier est bien parcouru en entier à chaque fois.

(oups, je voulais plutôt éditer mon post précédent)

[Marge]

Bonsoir, Danny,

A priori ça me surprend. Je n'ai pas constaté ce que tu dis mais je n'ai pas tout vérifié, j'ai juste regardé si la machine pouvait aller jusqu'à la case 64, ce qu'elle parvient à faire à chaque fois - mais ce n'est pas très sérieux, je vérifierai ça un peu mieux.
D'autre part je ne comprends pas pourquoi les choses s'arrangent avec le poids 3 dans deux angles de l'échiquier (les registres R1 et R8), ce n'est pas logique...
En dehors de cela, en théorie, j'avais bien prévenu que cette heuristique de Warnsdorf devait permettre de parcourir tout l'échiquier mais que je n'en savais pas plus. Il est possible que certains parcours n'aboutissent pas.
Je ne suis absolument pas sur le sujet en ce moment, mais je regarderai cela au plus vite.

[Danny]

D'autre part je ne comprends pas pourquoi les choses s'arrangent avec le poids 3 dans deux angles de l'échiquier (les registres R1 et R8), ce n'est pas logique...

Eh oui c'est étonnant
J'ai pas non plus essayé de débugger pas à pas pour le moment pour voir pourquoi il évite la case 8,8 (en partant de 5,5 par exemple : 5,5 - 6,7 - 8,6 - ...) quand elle indique 2 possibilités de sauts, alors qu'il y va quand elle en contient 3 (toujours en partant de 5,5 : 5,5 - 6,7 - 8,8 - ...).

[Marge]

Bonjour,

Voici différents tests réalisés sur la fusée HP-15C Limited Edition (il faut plus de temps pour transcrire les résultats ici que pour le calcul), le chiffre des dizaines indique l'abscisse, le chiffre des unités indique l'ordonnée.

Un parcours ouvert :

Code : Tout sélectionner

88, 67, 86, 78, 57, 38, 17, 25,
13, 21, 42, 61, 82, 74, 62, 81,
73, 85, 77, 58, 37, 18, 26, 14,
22, 41, 33, 12, 31, 52, 71, 83,
75, 87, 66, 54, 46, 65, 84, 63, 
51, 72, 53, 34, 15, 27, 48, 36,
28, 16, 24, 45, 64, 76, 55, 43,
35, 47, 68, 56, 44, 23, 11, 32.

Toutes les cases sont parcourues, aucune ne l'est deux fois.

Un parcours fermé :

Code : Tout sélectionner

12, 31, 52, 71, 83, 62, 81, 73,
85, 77, 58, 37, 18, 26, 38, 17,
25, 13, 21, 33, 41, 22, 14, 35,
16, 28, 47, 68, 87, 66, 78, 86,
74, 82, 61, 42, 54, 75, 56, 48,
27, 46, 67, 88, 76, 64, 43, 55,
34, 15, 23, 11, 32, 51, 63, 84,
72, 53, 65, 44, 36, 57, 45, 24.

Idem.

Il doit y avoir une erreur dans ton code, Danny - mais ça prend du temps à réaliser, ce n'est que justice.

[Danny]

Possible, car là :

88, 67, 86, 78, 57, 38, 17, 25,
13, 21, 42, 61, 82, 74, 62, 81

BIM chez moi ça ne va pas sur la 8,1 mais sur la 4,1 !
Je revérifie le code que j'ai saisi... [edit: et non je ne vois pas de différence Je vais saisir à nouveau ton code tel quel sur un émulateur de HP-15C pour voir ]

edit 2 : bon ben j'ai tout saisi à nouveau sur un émulateur de HP-15C, mais idem : ça passe de 6,2 à 4,1
Je pensais que j'avais peut-être mal saisi quelques commandes mergées, car j'avais jamais essayé une 15C avant, mais je ne vois pas lesquelles.
J'ai eu des doutes par exemple sur la façon de saisir STO(i), ST+(i) ou GSB .1 mais on se rend vite compte de la bonne façon en essayant plusieurs possibilités, donc au final je suis sûr d'avoir bien tout entré comme dans le listing.
Et sur HP-15C aussi, je dois modifier R1 et R8 avec les poids 2 3 4 4 4 4 3 3 pour que ça passe de 6,2 à 8,1.