Dév du jeu "ISOLA" sur Casio FX-602P et autres

[Gilles59]

INTRODUCTION :

L'idée de ce TOPIC est d'aboutir à un programme « ambitieux » (par rapport aux capacités des machines concernées ! ) fonctionnant sur une calculatrice programmable de type Langage Spécialisé. Cela concerne par exemple les calculatrices de type Casio FX-502P ou 602P ou TI58/59 ou similaires. Bien que disposant d'un langage plus évolué, la HP41 peut aussi en être. On peut caractériser ces machines par le fait qu'elles ne disposent pas (ou très marginalement pour la 602P / un peu plus pour la HP41) de possibilités de traitement de chaines de caractères ou autre traitement symbolique, et pas non plus de structures de données élaborées (tableaux a n dimension etc. -possible avec certaines extension de la HP41 je pense). Par contre la notion « d' adressage indirect » est indispensable (on y revendra). De toute façon, on va se limiter dans ce qui suit à travailler avec des nombres réels exclusivement; Bien sûr les programmes et idées seront utilisables sur des matériels permettant une programmation plus sophistiquées sur le principe de « qui peut le plus peut le moins »

Le programme qui va être écrit ici n'existe pas à ce stade et je posterai différents articles qui devraient aboutir (ou pas !) à un programme fonctionnant correctement. Il est donc possible qu'il y ait des retours arrières sur certains choix, des impasses etc. Mais ce qui me plait aujourd'hui en utilisant cette vieille machine, c'est le coté challenge, résolution de problème, rubik's cube en quelque sorte. C'est de pousser au max de ce qu'on peut faire avec des contraintes fortes.

Concrètement, je testerai ici les idées sur une CASIO-FX602P. Les possibilités alpha numériques serviront juste à afficher divers messages et rendre le programme plus simple à utiliser mais on pourra tout à fait s'en passer.

(A suivre… : Le choix du jeu à programmer)

[Gilles59]

SUITE #1 : LE CHOIX DU JEU

L'idée est de choisir un jeu qui soit 'limite' à programmer sur ce type de machine. Ne pas être certain à priori que cela est réalisable serait l'idéal. J'ai pensé intéressant de choisir un jeu où il s'agit de jouer contre la machine.

Mon choix s'est arrêté sur ce jeu, dont je reprends la description depuis l'excellent site http://jeuxsoc.fr

ISOLA



La règle d'Isola est très simple. Après avoir déplacé votre pion (comme un roi aux échecs) , vous enfoncez une case de votre choix du tablier de jeu (les cases sont en plastique mou). Le premier qui ne peut plus déplacer son pion (il est isolé autour de cases vides) a perdu la partie.

Lien et version Windows: http://jeuxsoc.fr/?principal=/i/isola.php?

La 602P ne disposant pas d'écran graphique, l'idéal est d'avoir le jeu physique pour jouer. Mais si vous êtes joueur, vous pouvez utiliser un échiquier, deux rois, et des jetons quelconques (pièces de jeu de dames ou Go ou ...) pour y jouer. Si vous n'avez rien de tout cela, une feuille de papier et un crayon suffiront. Tracez juste la surface de jeux ( damier 8x6), des jetons ou piéces de 2 couleurs pour les rois, et marquez d'une croix les cases que vous (ou la 602P) enfoncez.

Par rapport au cahier des charges initial, je dois dire que je triche un peu, car je sais déjà qu'un tel programme est réalisable sur ce type de machine (l'ayant fait dans le passé sur la 502P me semble-t-il), mais j'en garde un juste un souvenir lointain. Bref ce topic devrait aboutir finalement à une version d'ISOLA pour 602P !


(A suivre …. : Faisabilité sur une 602P, surface de jeu et position des pions)

[Gilles59]

SUITE #2 : Faisabilité, surface de jeu et position des pions

Déjà, examiner et connaître le jeu. Le mieux est d'y jouer ! Vous pouvez vous exercer sur la version Windows de Said Koudache dont le lien est donné ci dessus.

On constate que le jeux se déroule sur un damier de 6x8 cases, soit 48 cases. Sur une machine de la classe 602P un problème immédiat se pose. Ce genre ne machine ne dispose pas de structures de données 2D genre tableau DAMIER [1..6 ; 1..8]. Pire encore, si on part sur le principe d'utiliser une mémoire par case de jeu on n'ira vraiment pas loin, la mémoire globale de la calculatrice étant limitée. (cela reste cependant possible mais le nombre de pas de programmes sera très diminué et peut être insuffisant... A voir...)

Il faut donc ruser...

L'idée que je retiens est simple. Nous allons modéliser la surface de jeu en utilisant seulement 6 mémoires de la calculatrice et en prenant en compte la position des chiffres dans les nombres. Pour éviter ultérieurement des tests « complexes »et faire en sorte que la 602P ne propose pas de coups en dehors de la surface de jeu, on considère qu'on a par défaut une rangée des cases enfoncées en bordure du damier (ce qui nécessite donc 8 mémoires au lieu de 6) :

Code : Tout sélectionner

1 → case 'libre'
0 → case 'enfoncée'

MR08 = 0.0000000000
MR07 = 0.0111111110
MR06 = 0.0111111110
MR05 = 0.0111111110
MR04 = 0.0111111110
MR03 = 0.0111111110
MR02 = 0.0111111110
MR01 = 0.0000000000

l'utilisation de nombres en 0.xxxxxxxxx facilitera l'accès au chiffre en n-iéme position

Cette « ruse » a tout de même un clair désavantage : l'accès et la mise à jour des informations sera plus lent car nécessitant des calculs arithmétiques.

Il nous faut aussi mémoriser la position des pions rouge et bleu. On peut penser les stocker comme ceci en utilisant la partie entière et décimale. La position initiale est donc :

Code : Tout sélectionner

Rouge (602P)   : MR18 = 2.5
Bleu (joueur)  : MR19 = 9.4

Les positions sont décalées de +1.1 pour tenir compte de nos cases enfoncées fictives

Cette fois encore, l'inconvénient de cette solution est qu'elle nécessite un petit calcul pour retrouver la position en x et y de chaque pion, mais on gagne 2 mémoire. On verra à la fin si il est nécessaire d'optimiser cela.

(à suivre … : Structure générale du programme)

[Gilles59]

SUITE # 3 : ORGANISATION GENERALE DU PROGRAMME

On peut partir sur çà :

Code : Tout sélectionner

Programme Isola

Initialisation

Suivant qui démarre : '602P' → Joueur_qui_joue ou 'Humain' → Joueur_qui_joue

Tant que (Joueur_qui_joue peut jouer)

	Si  Joueur_qui_joue est '602P'  Alors
		Calcul le meilleur coup estimé pour la 602P
                Libère case de départ du roi
		La 602 déplace son roi
                Enfonce case d'arrivée du roi
		La 602P enfonce une case	
		Affiche choix 602P
		'Humain' → Joueur_qui_joue
			
	Sinon
		Demande ses choix au joueur
                Libère case de départ du roi
		Le joueur déplace son roi
                Enfonce case d'arrivée du roi
		Le joueur enfonce sa case
		'602P' → Joueur_qui_joue
	FinSi

Fin Tant Que 

Affiche qui_gagne

FinProgramme

Bon, la ligne la plus compliquée dans tout cela est sans doute « Calcul le meilleur coup estimé pour la 602P ». Nous y viendront le moment venu...

Gardons le meilleur pour la fin Dans les chapitres qui viennent on va commencer par tout le reste .

(à suivre … : Structure générale en langage 602P)

[ledudu]

J'ose tout juste intervenir au milieu de ton exposé pour te confirmer que je suis, que j'espère qu tu auras un moyen de transférer le programme en fichier au fur et a mesure et que je suis partant pour être beta-testeur...
a+

[Gilles59]

J'ose tout juste intervenir au milieu de ton exposé pour te confirmer que je suis, que j'espère qu tu auras un moyen de transférer le programme en fichier au fur et a mesure et que je suis partant pour être beta-testeur...
a+

Merci Ose ! C'estle but aussi. Je numérote de toute façon les "suites" pour s'y retrouver. je vais tester l'émulateur (simulateur 602P) qui a l'air fort bien, j'ai vu des posts de krischik la dessus sur Silicium. Je re-essaierai comme çà de connecter l'interface K7 FA-1 avec mon PC ce que je n'ai réussi à faire encore.
Je précise aussi (je ne veux pas que vous ayez des illusions lol) que le niveau de jeu et les temps de réponses seront... ce qu'il seront ! Et çà peut s'améliorer après çà.

[Gilles59]

SUITE #4 : Quelques petites remarques et structure générale en langage 602P

Langage de la 602P n'est pas vraiment structuré, c'est le moins qu'on puisse dire. Mais enfin, on peut tout faire (si ce n'est que la mémoire est limitée et les temps de réponses sont ce qu'ils sont). Il faut juste s'organiser un peu et optimiser au mieux.

Par exemple, on va utiliser la Mr1F (qui n'a rien de spécial à part son nom...) pour savoir à qui est le tour de jouer. Par exemple :

Code : Tout sélectionner

Mr1F = 1 quand la 602P doit jouer
Mr1F = 0 quand le joueur doit jouer

A chaque tour de jeu, on doit passer de 0 ->1 ->0 ->1 ->0 etc.

Plutôt que de s'embêter avec des tests on peut plus facilement faire :

Code : Tout sélectionner

1 M-1F Mr1F ABS Min1F

En  langage Pascal, en supposant Mr1F initialisé à 0 ou 1,  ca donnerait  Mr1F := Abs(Mr1F – 1)

Quand le programme sortira de la boucle de jeu principale, la variable Mr1F contient le perdant.
Sur la 602P on peut clarifier le message comme suit:

Code : Tout sélectionner

Mr1F "Je" x=0 "Tu" "; gagne" x=0 ";s" "; !!!"

Pour comprendre, il suffit de savoir que quand un test est faux la 602P 'saute' le pas de programme après le test, que toute chaine alpha est considérée comme un pas unique, et que le caractère « ; » en début de chaine permet de concaténer le nouveau texte avec le texte déjà affiché. Tout nouvel affichage d'un texte alpha sans « ; » au début supprime le texte précédemment affiché. Je précise aussi que les tests ne concernent que les nombres ! Les possibiltés alpha dela 602P se résume en gros à ce que je viens de dire

La structure générale va donc ressembler à çà

Code : Tout sélectionner

« Initialisations »
1 Min1F

LBL0 
« Si impossible de jouer »  GOTO9
« Si Mr1F =0 alors Joueur_joue sinon 602P joue »
1 M-1F Mr1F ABS Min1F
GOTO0

LBL9
Mr1F "Je" x=0 "Tu" "; gagne" x=0 ";s" "; !!!"

A suivre … Comment déterminer que la 602 ou le le joueur a perdu « Si impossible de jouer » ?

[Gilles59]

SUITE #5 : Comment déterminer qu'un joueur a perdu

La structure du plateau de jeu est définie en Suite#2. (J'ai modifié d'ailleurs la logique, 1 est désormais une case 'libre' et 0 une case 'enfoncée', c'est plus clair)

Il est clair qu'un joueur ne plus jouer (donc a perdu) quand la position qu'il occupe est entouré de '0'. Il n'a dans ce cas plus aucune case ou aller. Prenons un exemple où la 602P doit jouer :

Code : Tout sélectionner

0 → case 'enfoncée'
1 → case 'libre'

MR08 = 0.0000000000
MR07 = 0.0110001110
MR06 = 0.0111010010
MR05 = 0.0001100110
MR04 = 0.0*01001110        y
MR03 = 0.0001101110       ^
MR02 = 0.0110010110        !
MR01 = 0.0000000000         -→ x
__________23456789_

et Rouge (602P) en MR18 = 2.4 (en fait çà correspond à la place 1.3 sur le plateau mais nous avons ajouté une série de case 'enfoncées' fictive et donc cela décale l'origine, j'ai remplacé le 1 par un étoile pour se repérer)

La 602P a perdu et ne peut aller nulle par. Plutôt que de tester toutes les cases adjacentes, on va ruser (encore...) comme suit :

<1> Calcul la somme des mémoires 'autour' y=4, soit les mémoires MR03 MR4 MR05
<2> Calcul la somme des chiffres 'autour' de x=2, soit les chiffres en position 1, 2 et 3

On va appeler ce total « Libertés primaires » (on verra pourquoi après).
Si Libertés_primaires = 1 alors la 602P a perdu...

Là, la programmation se corse un peu. On va passer par un sous-programme [P9] qui reçoit en entrée x.y et donne en sortie le nombre de liberté de la case. Cela permettra de vérifier que çà fonctionne et voir les temps de calculs.

Code : Tout sélectionner

[P9]

- INT Min16 = x 10 = Min17 {position x et y du pion}
IND Mr17 Min15 1 M-17 IND Mr17 M+15 2 M+17 IND Mr17 M+15 {somme des 3 mémoires adjacentes}
Mr16 – 2 = 10^x  x Mr15 = FRAC x 10 – INT Min14 =  x 10 – INT M+14 = x 10 = INT M+14  {somme des 3 chiffres adjacents)
Mr14 { nbre de libertés primaires }

2.4 [P9] -> 1
3.5 [P9] -> 6
etc.

(… a suivre demain peut-être...)

[charognard]

Interressant, je suis aussi
Je viens de vérifier pas d'opérateurs binaire sur 602P ... dommage

[Gilles59]

Interressant, je suis aussi
Je viens de vérifier pas d'opérateurs binaire sur 602P ... dommage

non y'a pas ! j'ai cru voir qu'il y en a sur la 603P.. Cà faciliterait bien :O

Je m'interroge pour la suite... Une façon basique de faire jouer la 602 serait de calculer les libertés primaires des cases où le pion peut aller. Je me souviens que dans le passé j'avais utilisé la notion de "libertés secondaires" (en gros les libertés des cases plus éloignés mais pas trop). Le tout calculé à chaque tour pour chacun des déplacements possibles et choix du meilleur. de toute façon les limitations de la machine ne permettent pas des algo de type "voir 4 coups à l'avance", donc ruser encore !

Je me demande si il ne serait pas mieux d'utiliser un autre tableau du même genre que MR01..MRO08 et de stocker dedans les libertés de chaque case en les recalculant seulement à chaque fois qu'une case est enfoncée ....

Une autre difficulté sera de coordonner les déplacements du pion et l'"enfoncage" de la case qu'on ne peut pas théoriquement considérer séparément. Là j'ai pas de solution parfaite.

Pour les déplacement du pion je ferai comme suit :

!7!8!9!
!4!X!6!
!1!2!3!

7 pour Nord-ouest, 8 au nord, 2 au sud etc ....

[gege]

Cool, mais ça va un peu trop vite, un gros post toutes les demi-heures, mon cerveau (enfin... ) surchauffe.
Ok je relis tout !
G.E.

[Gilles59]

SUITE#6 quelques petites routines nécessaires. Lire l'état d'une case / Enfoncer une case / Liste des cases où peut aller un pion

On va y aller cool ce dimanche midi pendant que le repas est en train de cuire Pour le moment certains bouts de codes sont redondants, on verra plus tard si on met çà en sous programme ou pas suivant qu'on souhaite optimiser la mémoire utilisée ou plutôt la rapidité.

Pour avancer dans notre programme, on a besoin de :


1/ connaitre l'état d' une case

On suppose avoir x.y en entrée. On veut en sortie l'état de la case (1 libre, 0 enfoncée)

Code : Tout sélectionner

- INT Min16 = x 10 = Min17 {position x et y du pion}
1 M-16 IND MR17 x Mr16 10^x = FRAC x 10 = INT

2/ Enfoncer une case

On part du principe qu'on ne vérifie pas que la case est "libre" avant de l'enfoncer.
On a x.y en entrée. On veut enfoncer la case (passer le contenu à 0)

Code : Tout sélectionner

- INT Min16 = x 10 = Min17 {position x et y de la case à enfoncer}
Mr16 +/- 10^x IND M-17

3/ Remettre une case enfoncée

Cette fonction est utile pour permettre d'enfoncer/remettre la case lors d'un déplacement de roi (pion)

On part du principe qu'on ne vérifie pas que la case est "enfoncée" avant de la libérer
On a x.y en entrée. On veut "libérerer" (remettre) la case (passer le contenu à 1)

Code : Tout sélectionner

- INT Min16 = x 10 = Min17 {position x et y de la case à enfoncer}
Mr16 +/- 10^x IND M+17

4/ Liste des cases où peut aller un pion

Les pions se déplacent comme les rois aux échecs. Comme on mémorise la position d'un pion sous la forme x.y et qu'on a 'agrandi' notre surface de jeu par une bordure de cases enfoncées (c'est à dire qu'un pion ne peut pas être en 1.y ou x.1 ou 10.y ou x., la liste des 8 cases où peut potentiellement aller un pion est de la forme

x,y -1
x,y -1,1
x,y -0,1
x,y + 0,1
x,y + 1,1
x,y + 1

On suppose la position du pion sous la forme x.y en entrée

Code : Tout sélectionner

Min13
1 M-13 GSBPx
.1 M-13 GSBPx
1 M+13 GSBPx
.2 M+13 GSBPx
1 M+13 GBPPx
.1 M-13 GSPPx

le sous-programme Px vérifiera que le coup est jouable (point 1 ci dessus) et éventuellement calculera la valeur du coup (on y viendra).

Bon, j'arrête là pour aujourd'hui avant que le repas ne brule


(... a suivre... Peut etre une premiere version du programme joueur/ joueur et premiers éléments d'évaluation des positions/coups )
Mine de rien on a déjà beaucoup avancé. On a presque tous les éléments pour écrire un programme qui fonctionne.

[Marge]

Ton développement m'intéresse ; j'ai surtout apprécié la mise en place du plateau de jeu sur les huit mémoires, c'est ingénieux, et ça nous change des cases numérotées habituellement utilisées dans ce genre de jeu. Toutefois l'évaluation des cases adjacentes risque peut-être de prendre beaucoup de mémoire programme, en dehors du casse-tête que cela représente en algorithmie pure. Bon courage en tout cas !

[Gilles59]

Toutefois l'évaluation des cases adjacentes risque peut-être de prendre beaucoup de mémoire programme, en dehors du casse-tête que cela représente en algorithmie pure. Bon courage en tout cas !

Merci, Et bien pas vraiment en fait... On fait la somme de 3 mémoires + la somme de 3 chiffres dans le nombre résultant. Ca fait 51 pas voir suite#5 et çà s'exécute "assez vite", ce qui fait que je suis confiant sur la 'jouabilité' réelle. j'ai aussi un idée à suivre sur la qualité de jeu de la calcu

Ce ne ferait pas beaucoup moins (plus ?) sur un pocket type basic qui gère les tableau 2D
T(x+1,y-1)+T(x+1,y)+T(x+1,y+1)+T(x-1,y-1)+T(x-1,y)+T(x-1,y+1)+T(x,y-1)+T(x,y+1)+T(x,y)
On peut faire aussi 2 boucles imbriquées bien sur

Sur un 602P en conservant la logique des bords décrites, ca nous prendrait 80 mémoires (MR01 ... MR80) et un calcul du genre :
M1F correspond à la position 'linéaire' du pion genre Mr1F:= x + 10*y (pour un plateau de 8+2 de large)
1 M+1F IND MR1F M+81 2 M-1F IND MR1F M+81 10 M+1F IND MR1F M+81 1 M-1F IND MR1F M+81 etc.
. soit 47 pas (42 pas si on ne compte la case sur laquelle est le pion). Bref même ordre de grandeur.

PS : Marge, j'ai peut etre mal compris ta remarque sur "l'évaluation des cases adjacentes". Je suppose que tu veux dire par là sur quelle case la calculatrice doit déplacer son pion. Un algo tres simple serait de la faire jouer là où il y a le plus de libertés possibles (algo Suite#5 qui ne se contente pas de dire si le joueur a perdu mais renvoi le nombre de 'libertés' de toute case qu'on veut tester). c'est tres simpliste mais déjà une base et çà marcherait. J'ai d'autres idées la dessus à tester

PS2 :dans le même ordre d'idée et beaucoup plus simple on peut souvent "doubler" le nombre de mémoires sur les calculatrices programmable en utilisant les parties entières et fractionnelles des nombres stockés. Il faut juste être vigilant pour que la partie fractionnaire de déborde pas sur la partie fixe et la plage d'utilisation des nombres est réduite.

[Marge]

PS : Marge, j'ai peut etre mal compris ta remarque sur "l'évaluation des cases adjacentes". Je suppose que tu veux dire par là sur quelle case la calculatrice doit déplacer son pion. Un algo tres simple serait de la faire jouer là où il y a le plus de libertés possibles (algo Suite#5 qui ne se contente pas de dire si le joueur a perdu mais renvoi le nombre de 'libertés' de toute case qu'on veut tester). c'est tres simpliste mais déjà une base et çà marcherait. J'ai d'autres idées la dessus à tester

Non, non, tu as très bien compris, et donc je te souhaite tout le succès que tu mérites à voir tes efforts.

Cela dit, la stratégie du "plus de liberté possible" était déjà le sujet d'un Science & Vie relatif au jeu d'échecs et sa stratégie gagnante. Le retrouver serait d'ailleurs assez sympa également.