A jouer aux reines avec une calculette de presque 40 ans !

Les derniers trucs auxquels vous avez joué, les derniers ordinateurs que vous avez bidouillés.

Modérateur : Politburo

Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A jouer aux reines avec une calculette de presque 40 ans !

Message par C.Ret »

Sympa ce code.

Et oui, je réalise que dans l'article il s'agit bien d'une Ti-58 et non d'une Ti-58C ce qui serait une bonne explication pour la différence de vitesse. Il peut y avoir de variation entre les machines d'une même époque ou entre des machines issues de séries différente (éloignées dans le temps ou ayant profiter d'avancée technique ou modification des circuits), mais pas d'un ratio aussi élevé.

Concernant la vitesse sur fx-602p, il y a peut-être quelque choix d'organisation du code ou sens d'un test qui expliquerait une différence du rendement. Ce n'est pas toujours évident de concevoir au plus rapide. Parfois une solution que l'on trouve efficace ne l'est pas tant que ça, voir parfois une astuce est un faux ami.

J'attends avec impatience la version pour l'Amstrad CPC. Elle me donnera peut-être l'envie de faire pour Commodore C128D avec graphique et language machine.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: A jouer aux reines avec une calculette de presque 40 ans !

Message par Gilles59 »

C.Ret a écrit : 14 août 2022 11:28
Concernant la vitesse sur fx-602p, il y a peut-être quelque choix d'organisation du code ou sens d'un test qui expliquerait une différence du rendement. Ce n'est pas toujours évident de concevoir au plus rapide. Parfois une solution que l'on trouve efficace ne l'est pas tant que ça, voir parfois une astuce est un faux ami.
J’ai édité le code du msg précédent pour résoudre toute taille d’echiquier.
Pour optimiser la vitesse sur 602 il y a un truc utile à savoir. Un GOTO cherche toujours son label en « montant » vers le haut du code, si il ne trouve pas il repart du GOTO et cherche vers le bas. J’ai gagné 45 secondes pour la première solution 8x8 en prenant ça en compte et en adaptant le code.

A noter aussi les séquences x=0 x=F équivalent à x<>0 quand MRF n’est pas nul.c’est bien la seule chose que je reproche la gamme 501->603 : l’absence de certains tests même si on s’en sort toujours.
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: A jouer aux reines avec une calculette de presque 40 ans !

Message par Gilles59 »

Schraf a écrit : 29 juil. 2022 16:57 Vu aujourd'hui dans cette vidéo consacrée à la calculatrice scientifique Casio fx-5800P

Image
Bonjour Shraf. Je me demande bien à quoi sert le passage en mode degré (DEG) au beau milieu du code.
Ou alors c’est un NOP (no opération)? Mais dans ce cas pourquoi pas DSZ Y GOTO 0 ?

ÉDIT : je ne suis pas encore bien réveillé mais je vous laisse chercher.

ça semble le même code que celui que j’utilise basé sur les benchmark de Xerxes. Perso je changerai l’affichage final pour afficher la solution d’un bloc sur une ligne
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: A jouer aux reines avec une calculette de presque 40 ans !

Message par Gilles59 »

Bonjour. J'ai écrit une version graphique (et récursive) du problèmes des n-reines sur Amstrad CPC+.
Copie d'écran du programme
Copie d'écran du programme
8-dames2.png (6.78 Kio) Vu 2508 fois
et une vidéo:
https://youtu.be/VAKbfoKBBW8

Le fichier .dsk (fonctionne avec gotek) avec les sources et exécutables (reines.com) est ici :https://drive.google.com/file/d/1j1C3l6 ... sp=sharing
Ça tourne en Cpm3, pour lancer le programme :
|Cpm reines
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Trypilec
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 91
Enregistré le : 23 déc. 2023 09:09

Re: A jouer aux reines avec une calculette de presque 40 ans !

Message par Trypilec »

Passer en revue toutes les options prend beaucoup de temps. Il existe une autre stratégie.
Nous mettons la reine sur a1, la suivante sur le champ disponible le plus proche de la colonne voisine est b3 (c'est aux coordonnées +1+2), la suivante est c5. Nous nous trouvons maintenant dans une situation qui n’a pas de solution valable pour 8 dames.
Image
Retirez la reine c5 et placez-la sur la case ci-dessus. Nous vérifions si le poste a une solution. Sinon, on réorganise à nouveau la reine sur la c. Si la reine c ne peut se tenir sur aucune case, alors réorganisons la reine b.
"N'importe quel programme peut être raccourci d'une pas": — un vieux dicton des programmeurs.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: A jouer aux reines avec une calculette de presque 40 ans !

Message par C.Ret »

Trypilec a écrit : 04 janv. 2024 17:49Passer en revue toutes les options prend beaucoup de temps.
cela est très vrai ! Surtout sur une Ti-58C qui n'est pas une machine supersonique.

Par contre, passer ne revue toutes les options de cette façon a le mérite de n'utiliser que très peu (un minimum ?) de registres mémoires.

Et je suis d'accord, il a certainement suffisamment de registres dans une Ti-58 (et certainement dans une Ti-59) pour envisager une stratégie plus efficace et utilisant un peu plus de registres.

Mais, même un échiquier de petite taille utilise n² cases. Pour aller vite, il faut que le codage des positions possibles se fasse facilement (en un minimum d'instructions). Avec cette contrainte, même un l'échiquier faisant 8x8 cases nécessite 64 registres (ou cases) et cela ne tient plus dans une ti-58. Et je ne parle que des registres nécessaires pour coder l'état des case, il faut certainement ajouter autant de registre pour code les HEAP qui per met de trouver sans avoir à parcourir inlassablement en long et en large tout l'échiquier pour trouver la solution la plus proche suivante !

N'oublions pas que le code utilisé permet d'étudier des solutions sur des échiquiers plus ou moins grands. Etre limité à un échiquier 4x4 pour avoir une recherche rapide n'est pas très intéressant.

Mais, je suis preneur d'un meilleurs algorithme, comme celui indiqué par Trypilec, mais je ne sais pas comment l'implanter efficacement dans le ventre tout petit d'une Ti-58c. Surtout sans perdre un temps presque infini à coder ou compresser l'information par des calculs longs ou complexes à chaque changement de l'état binaire d'une case.

Par contre, sur d'autres machines, comme par exemple un SHARP PC-1360 ou un HP-28S, qui ont une arithmétique binaire et des instructions logiques pouvant traiter l'état de plusieurs cases simultanément; alors là oui, je sais comment implémenter quelque algorithme plus astucieux. Malheureusement, ces algorithmes deviennent lents et poussifs sur une machine AOS de 1977.

Peut-être Trypilec sait comment faire ?
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Trypilec
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 91
Enregistré le : 23 déc. 2023 09:09

Re: A jouer aux reines avec une calculette de presque 40 ans !

Message par Trypilec »

théoriquement 8 registres pour les reines, 64 pour les casés, 16 pour les lignes et colonnes et 16 pour les diagonales. Mais vous pouvez faire moins. Pour le champ, 8 registres suffisent, où le nombre 11111111 signifie que tous les champs ne sont pas disponibles, et 11001111, que les champs d'ordonnées 5 et 6 sont disponibles. Mais alors il est difficile de vérifier si tous les champs de la ligne sont occupé. Et il est quelque peu difficile de remarquer que les champs diagonaux sont brisés. Deux cycles sont nécessaires. Est-ce que tout le monde est occupé dans la colonne:
frac{log(11111111-n)}=0 — si c'est le cas, alors tout le monde est occupé.
"N'importe quel programme peut être raccourci d'une pas": — un vieux dicton des programmeurs.
Trypilec
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 91
Enregistré le : 23 déc. 2023 09:09

Re: A jouer aux reines avec une calculette de presque 40 ans !

Message par Trypilec »

"N'importe quel programme peut être raccourci d'une pas": — un vieux dicton des programmeurs.
Trypilec
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 91
Enregistré le : 23 déc. 2023 09:09

Re: A jouer aux reines avec une calculette de presque 40 ans !

Message par Trypilec »

Pour marquer en diagonale les champs inaccessibles, il faut deux cycles pour les nombres en colonnes et deux pour les nombres en lignes. Seules les colonnes et les lignes peuvent être vérifiées pour un seul champ ou l'indisponibilité des champs. Mais 4 cycles, c'est aussi du temps supplémentaire. Y aura-t-il une victoire ? Cela sera possible pour les calculatrices à arithmétique binaire, mais le sera-t-il pour les calculatrices ordinaires ? Bien que, selon un tel algorithme, il soit plus rapide de trouver toutes les solutions sans calculatrice :)
"N'importe quel programme peut être raccourci d'une pas": — un vieux dicton des programmeurs.
Répondre

Retourner vers « A quoi t'as joué hier ? »