Ubuntu-fr

philoup44

Script jeu d'echec ---> les Tableaux

Salut

j'apprends depuis peu les commandes shell
et pour me motiver sérieusement à potasser la partie théorique
je me suis lancer dans un script shell
qui devrait m'obligeait à revoir régulierement ma copie...

Mon script n'est qu'un simple jeu d'échec
Je sais , c'est pas bien...
Mais pour essayer d'exploiter un max de lectures indigestes, c'est pas mal
Au debut mes connaissances s'arretaient aux commandes ls -l et cd

jusqu'à maintenant je me suis débrouillé seul
Mais maintenant, j'arrive à une phase ou je bloque un peu

Toutes mes pieces se déplace bien sur 1 coup sans commettre d'erreur
Mon Cavalier à un sous programme
pour déterminer le chemin le plus rapide pour atteindre une cible

exemple ci-dessous

Entre les coordonnées du cheval (ex: c3) ----->  c3
Cavalier en c3 

Tableau des cibles   ---> tablciblmax
3 4 3 4 3 4 3 4
2 3 2 3 2 3 4 3
3 2 3 2 3 2 3 4
4 1 2 1 4 3 2 3
1 2 3 2 1 2 3 4
2 3 0 3 2 3 2 3
1 2 3 2 1 2 3 4
4 1 2 1 4 3 2 3

la valeur 0 represente la position du cavalier (ici c3 = colonne 3 ligne 3)
les autres valeurs représentes le nombre de coups pour atteindre chaque case

Entre les coordonnées de la cible (ex: b8) ----->  b8
nombre de coups pour atteindre b8 = 4
voici le nouveau tableau
x 4 x x x x x x
2 x 2 3 2 x x x
3 2 3 x x 2 x x
x 1 2 1 x x x x
1 2 x 2 1 x x x
x x 0 x x x x x
1 x x x 1 x x x
x x x x x x x x

les x représentent les cases « interdites »
pour aller en b8 (28)
le cavalier choisi d'abord une case de valeur 1, puis 2 puis 3 et finalement 4

Depuis peu ,j'ai réussi à utiliser un tableau pour le déplacement de mon roi

Question
En quoi les tableaux sont ils plus pertinents ?
Jusqu'à maintenant, j'utilisais des fichiers temporaires pour stocker des données
Mais depuis que j'ai réussi à utiliser un tableau pour le déplacement d'une pièce
je me demande si cela n'est pas plus approprié pour stocker des données ?

de meme, pour aborder la partie évaluation d'une position
je dois stocker temporairement la position
pour chaques coups possibles (et ce pour chaque piece)
je suis parti du principe que si 2 sacrifices successifs de pièces lourdes (Dame+Tour)
mene à un mat au 3 eme coup
alors l'évaluation de la position ne peut commencer qu'au 3eme coup
Car au 1er coup ---> sacrifice de la dame = -10
       au 2eme coup ---> sacrifice de la tour = -5
evaluation du matériel = -15
la, il faut vraiment que la partie evaluation positionnelle soit beton
si le programme ne voit pas le coup suivant

Mais ,si je pars d'une moyenne de 30 coups possibles pour chaque joueur
Cela donne
1 er    coup    ---> 30 x 30 = 900 (environ 1000 combinaisons)
2 eme coup   ---> 1000 x 1000
3 eme coup   ---> 1000 x 1000 x 1000

en partant du principe que 1 position = 1caractere = 1 octet
alors au 3eme coup le stockage des données temporaires = 1 Go de ram

a moins que le stockage dans un tableau pese moins lourd

est ce plus rapide de lire dans un tableau ?
Est ce que le stockage dans un tableau pese moins lourd ?

Sinon, pour dire
calcul pour les blanc puis pour les noirs puis pour les blancs etc...

est ce un truc du style

while true
do
commande

exit 0
done

exit 0 ;

Merci d'avance pour toutes réponses

darunia_goron

Re : Script jeu d'echec ---> les Tableaux

Tu t'attaques à du lourd pour débuter. Je vais te donner quelques pistes.

Tout d'abord, le script est un langage interprété. Il n'y a pas de compilation, lors de l'exécution, le shell traite ton script ligne par ligne. Pour ce genre de problème, il vaut mieux choisir un langage compilé qui sera bien plus rapide à l'exécution.
Pour les tableaux et les fichiers, la grosse différence et que ton tableau sera en mémoire vive et ton fichier sur le disque dur. Utiliser des fichiers et donc beaucoup plus lent.
Pour les problèmes de stockage, tu utilises un algorithme de type backtracking. La complexité est exponentielle, quelle que soit la manière dont tu t'y prends, tu ne pourras pas tout stocker ni tout évaluer. Un des principes et d'utiliser une heuristique. Déjà, conserve ton idée de points, c'est une bonne base. Étoffe la un peu en rajoutant une « valeur » du coup. Par exemple, un déplacement qui créé une fourchette ou un clouage aura une valeur importante.
À cela tu rajoutes des algorithmes de calcul de prise de pièces. Par exemple, si une pièce est attaquée par trois pièces et est défendue par deux, alors elle peut être prise.

Une fois ton heuristique créé, tu évalues tout les premiers coup et tu ne gardes en mémoire que ceux qui ont une bonne évaluation (par exemple cinq coups). À partir de là, tu passes au second coup et ainsi de suite, en jetant au fur et à mesure les coups qui ont une mauvaise évaluation. De cette manière tu évites que la mémoire ne gonfle trop.

Bon courage, tu en auras besoin.

philoup44

Re : Script jeu d'echec ---> les Tableaux

Salut darunia_goron
Je te remercie pour ta réponse
Sans savoir ce qu'est vraiment la compilation (compression en langage machine ?? à savoir 0 et 1 ?? )
J'ai deja pu lire que le shell n'était pas armé pour un programme d'échec
c'est la raison pour laquelle je dis plus haut " je sais c'est pas bien "

Mais quand on part de zéro, et qu'il faut se manger entre autre, la syntaxes du shell " '  ' [ ] ` $1 () etc ...
Un peu de motivation ne fait pas de mal ...
Et autant commencer par le shell, puisque c'est par lui que je dois passer sur la console
Qui maintenant, ne m'effraie plus ...

Ce qui m'importe avant tout c'est
1) savoir utiliser le langage "shell"
2) Finir  ce script et le mener le plus loin que je peux ( en shell )
Et pour l'instant, le SHELL se "débrouille" bien mieux que je l'aurais cru ...
Au vu de tout ce que j'ai pu lire sur le sujet

Quand aux tableaux

Si cela est vrai
Je vais devoir réecrire une partie de mes scripts (pour optimiser le bébé )
Heureusement, pour l'instant toute les parties sont écrites dans des scripts differents (Que je rassemblerait plus tard)

backtracking
Je connaissais pas
J'ai lu des sujets sur les Algorithme, Algorithme récursif, L’algorithme MinMax, Arbre enraciné, La récursivité...

heuristique
J'aime bien la definition

un déplacement qui créé une fourchette ou un clouage aura une valeur importante

J'avais deja pensé entre autre au clouage, au structure de pions, colonnes ouvertes, etc ...
mais curieusement pas à ... la fourchette
A rajouter à mon fichier EVALUATION

Nombres de pièces qui attaquent ou défendent une case

J'ai déja fait ce "sous programme"

      3 66
      3 65
      3 57
      3 46
      3 33
      2 15
      2 13
      2 83
      1 77
etc ...

ici la case 66 (f6) est "controlée" 3 fois par les noirs
    la case 83 (h3) est "controlée" 2 fois par les noirs

Une fois ton heuristique créé, tu évalues tout les premiers coup et tu ne gardes en mémoire que ceux qui ont une bonne évaluation (par exemple cinq coups)

Je n'ai pas bien saisi la fin
il faut lire 5 points d'avance ??

Encore merci pour ton temps passé à me répondre

Dernière modification par philoup44 (Le 07/08/2012, à 00:24)

darunia_goron

Re : Script jeu d'echec ---> les Tableaux

Sans savoir ce qu'est vraiment la compilation (compression en langage machine ?? à savoir 0 et 1 ?? )

Dans l'idée, c'est ça. Le terme est plutôt traduction en langage machine. Je t'invite à déambuler sur les articles de Wikipédia traitant le sujet (script shell, compilation…)
Libre à toi de programmer ça en script. Je maintiens que c'est inadapté. Le but étant juste de parfaire ton niveau, pourquoi pas.

Une fois ton heuristique créé, tu évalues tout les premiers coup et tu ne gardes en mémoire que ceux qui ont une bonne évaluation (par exemple cinq coups)

Je n'ai pas bien saisi la fin
il faut lire 5 points d'avance ??

Je n'ai pas été très clair, je reprends. Dans ton premier message tu donnes l'exemple de 30 coups possible par tour. Grâce à ton heuristique, tu peux classer ces coups et éliminer les moins bon. Par exemple, tu gardes 5 de ces 30 coups comme ça (je reprends ton exemple) :
1 er    coup    ---> 5 x 5 = 25
2 eme coup   --->  25 x 25 = 625
3 eme coup   ---> 25 x 25 x 25 = 15625
En plus de ça, tu peux à tout moment supprimer des coups. Par exemple au troisième coup, tu en gardes 1000 sur les 15625. De cette manière tu peux anticiper plus loin. Là, je te donne des valeurs au pif, à toi d'adapter et de trouver le bon compromis. De plus, l'algorithme ne devra pas se comporter pareil en début et en fin de partie. Lorsqu'il reste peu de pièces, on peut se permettre d'évaluer tout les coups.
Bien sûr, cette méthode ne sera pas capable de calculer un bon sacrifice (du type sacrifice du cavalier dans une fégatello) car le coup sera jugé comme mauvais et donc supprimé immédiatement.

philoup44

Re : Script jeu d'echec ---> les Tableaux

Je n'ai pas été très clair

En fait si
Mais hier soir, apres 2 heures de lecture sur les Tableaux, tableaux associatifs etc ...
Je n'avais plus beaucoup de neurones valides

Tes exemples sont à mon sens tres pertinents

sacrifice du cavalier dans une fégatello

Celui ci ... est tres bien pour servir de test au script EVALUATION
que je vais commencer à mettre en forme
Toute la difficulté est de savoir comment stocker des données pour les exploiter plus tard
Car il y a plusieurs méthodes possibles

a)Variables
cases='a8 b8 c8 d8 e8 f8 g8 h8'
b)Tableau
Cases=( a8 b8 c8 d8 e8 f8 g8 h8 )
c)Fichier
cat < fichier

les tableaux me plaisent bien
pour appeler un élément du tableau
${nomTableau[indice]}
ex:

echo $ {Cases[0]}   ----> affiche la valeur à la position 0    ici a8
echo ${Cases[*]}     ----> affiche tous les éléments             ici a8 b8 c8 d8 e8 f8 g8 h8
echo ${#Cases[*]}    ---> affiche le nombre d'éléments       ici 8

Mais si une position = 64 cases
et que je prends par exemple 1 caractere par case
alors 1 position = 64 caracteres
donc 1 tableau contiendra minimum 64 elements

1 er    coup    --->      25
2 eme coup   --->     625
3 eme coup   ---> 15625  ---> 15625 positions  x 64 éléments

Question
Quel est la capacité des tableaux ?
Combiens d'éléments maxi peuvent-ils contenir ?
Combiens pésent les données sous forme de tableau ? (1 caractere = 1 octet ??)

Dans un fichier , je me représente bien
15625 positions  de 64 éléments = 15625 lignes de 64 caractéres (mini)
On peut savoir la taille du fichier
les données étant dans un fichier => soulage la ram ?
apres pour le traitement des données ... qui sera le plus efficace ??

encore merci à toi darunia_goron

Dernière modification par philoup44 (Le 12/08/2012, à 20:55)

philoup44

Re : Script jeu d'echec ---> les Tableaux

J'ai fait un petit test
Je me suis fait 2 scripts differents
pour simuler 3 demi-coups (un coup, les blancs un coup les noirs et enfin un coup les blancs)
l'un en stockant le résultat dans un fichier texte
l'autre en stockant le résultat dans un tableau
( ici , 1 position = 1 ligne = 88 à 150 caracteres max)

Fichiers
Temps (sec)  Lignes
2             3650
3             5550
5             9861
8            13308
20           26175
40           45552
67           72552

Tableaux
Temps (sec)  Positions
2             4623
4             8721
8            18831
11           23547
15           34704
21           41652
29           57633
34           67242

En passant par les tableaux, je gagne en rapidité
Ils peuvent, à priori stocker pas mal de données
Au mieux, pour l'instant j'atteint 2000 positions / sec ---> soit 2 Kn/s ??
Ce qui à l'air rapide mais , un moteur d'echec à ... 2 Kn/s
...... c'est un cycliste amateur qui participe au 24h du mans

ça m'a un peu bloqué pour déterminer la suite ...
Je cherche comment améliorer ses calculs (tableaux à trous etc ... )
Calculs en paralleles (je ne sais pas si c'est faisable en shell)
Je sais que l'on peut faire tourner un processus en tache de fond, mais je ne sais pas si c'est la meme chose ??
Mais bon, pour l'instant ça progresse
En tout cas j'aurais beaucoup appris sur le shell

darunia_goron

Re : Script jeu d'echec ---> les Tableaux

J'ai fait un petit test
...... c'est un cycliste amateur qui participe au 24h du mans

Utilise une voiture. Voici une liste des différentes écuries : C, Java, Python, OCaml, Prolog…
Je le redis, tu ne pourra pas faire quelque chose de performant en script shell. Ce n'est pas fait pour.

Je vais tout de même donner un peu de dopage à ton cycliste amateur.
As-tu des notions solides en complexité ? Tant que tu ne maîtrise pas ce point, tu n'arriveras à rien de performant. Par exemple, si tu as un tableau n x n, rechercher un élément dedans a une complexité en O(n²). C'est le genre de manipulation qu'il faut éviter car souvent inutilement gourmande.
Tu fais tout à l'aide de tableau, ce n'est pas la seule structure de donnée. Il y a aussi les structures de donnée de type récursif (les listes, les arbres, les graphes). Je n'ai aucune idée de comment ça se manipule en script bash mais c'est définitivement le genre de structure de donnée dont tu aurais besoin. Un tableau est statique ; tu ne peux pas l'agrandir à ta guise.

Le calcul en parallèle, dans le meilleur des cas, tu divises le temps d'exécution par le nombre de processeur.

philoup44

Re : Script jeu d'echec ---> les Tableaux

Merci darunia_goron

Je me rends bien compte de toutes les difficultés qui m'attendent
Meme si le shell n'est pas "armé" pour
ca me ferait plaisir d'arriver au bout
J'ai commencé à apprendre le shell il y a un peu pres un mois
Et sans ce "projet", je n'aurais jamais lu tout ce que j'ai lu ( lu ....lu )
Mais sinon, pour plus tard

quel est le langage le plus adapté pour les échecs
et qui éventuellement, se rapproche le plus du shell ( transition douce oblige ) ??

NB
j'ai lu toute la page de ton lien
plusieurs lectures me seront nécessaires pour comprendre ....

darunia_goron

Re : Script jeu d'echec ---> les Tableaux

Le meilleur langage ? Quelle question épineuse.

Ma certitude est que le script shell est le pire (je crois que tu l'as compris).

Tout les langages que j'ai cité précédemment peuvent faire l'affaire.
À mon humble avis, j'utiliserai le Prolog. Seulement, Prolog est un langage de programmation logique qui n'a rien à voir avec la programmation impérative que tu as l'habitude de manipuler.

J'ai débuté avec OCaml (caml Light pour être plus précis). C'est un langage fonctionnel, il est au choix compilé ou interprété. Il est aussi orienté objet. Tu as donc un interpréteur de commande dans lequel tu peux taper tes fonctions, en ce sens, ça se rapproche un peu du shell.

Le C c'est le roi des langages, tout est faisable, c'est également le plus bas des langages de haut niveau (i.e. le plus proche de la machine). Certains le considèrent même de bas niveau au même titre que l'assembleur. Parmi les langages que j'ai cité, c'est le seul où tu es responsable de la gestion de la mémoire. Si tu codes bien, c'est ce langage qui te donnera les meilleurs performances. Du fait que tu doives géré la mémoire, ça en fait un langage assez difficile pour un débutant. Je le conseillerai comme second langage une fois que l'algorithmique et la complexité sont bien maîtrisées.

Python, je n'ai pas encore essayé mais je compte m'y mettre. Et pour ce que j'en ai entendu, il est très bon. Il est aussi utilisable comme langage de script. C'est sans doute lui qui est le plus proche de ce que tu désires.

Java est bon aussi, à mon goût le langage orienté objet le plus complet.

Pour conclure, le langage le plus performant sera C, le langage le plus adapté sera Prolog et le langage le plus proche de ce que tu connais déjà semble être Python (je dis semble car je n'ai jamais manipulé).

Enfin, je n'aime pas C++. Je risque de me faire incendier en disant cela ici-bas. Néanmoins,  Richard Stallman et Linus Torvarlds, les deux plus grand gourous du logiciel libre, partagent cet avis.

P.S. : j'ai balancé beaucoup de termes techniques. N'hésite pas à faire moult recherches.
P.S.S : ceci n'est que mon avis, il n'appartient qu'à toi de faire ton choix.

Dernière modification par darunia_goron (Le 24/08/2012, à 15:36)

philoup44

Re : Script jeu d'echec ---> les Tableaux

Merci pour le temps que tu as consacré à me répondre

Aujourd'hui, je serais bien incapable de choisir
Car pendant longtemps, j'étais à pied , depuis peu j'apprends à monter une mule
qui régulièrement refuse d'avancer et pas toujours à tord ( faut dire que je suis un pietre cavalier )
Et pour plus tard, on me propose de choisir entre des Rolls, jaguar, porches ... ( que je n'ai vu qu'en photo )
sans savoir si je pourrais y adapter les rennes de ma mule ...

encore merci
je suis toujours preneur d'infos