Discussion :

[oliverell62]

bonjour,

je suis en train d essayer de faire un moteur d echecs, pour ce faire je dois concevoir l "échiquier" pour ma bébête ...

j ai plusieurs solutions :

=> tableau a deux dim ( surement le plus simple mais a mon avis le moins rapide )

=> un systeme "mail box" : tableau a une dimension de 160 cases ( de memoire ....) qui permet mathématiquement de sortir un échiquier

par contre, je me questionne sur une troisième possibilité


=> un collection d objets genre ( list of() ) a qui je donnerai l indice
genre
( 11 . 12 . 13 etc ... 18)
( 21 . 22 . 23 etc ... 28)
etc
( 81 . 82 . 83 etc ... 88)
===>qui me permettrai de le faire contenir des objets " pieces " la ou elles doivent être présente
===> de mathématiquement permettre le déplacement des pièces
===> vérifier les déplacements illegaux ( exemple fou en indice 88 ne peut pas avoir +11 en déplacement : indice 99 n existant pas )


j ai une préférence perso pour la 3eme ...

voila mon questionnement :


1) quelle methode est le plus rapide ( tableau a 2 dim de (64 cases ), tableau a une dim de 160 cases , ou la collection ) ( autant ne pas s enfacer dans une methode non adequat )

2) est t il possible dans une collection d objet de type : List(Of Object) de determiner l indice des membres de la collection ( et de n utiliser donc que 11 12 13 14 15 16 17 18 21 22 etc etc

3) alternative si pas possible ( une collection de type dictionnary est elle aussi rapide que list(of object )

4) concernant la collection list(of object )
si je la defini comme conteneur a objet piece , puis je y mettre l objet roi héritant de pièce ?



merci d avance

[Graffito]

Pour un echiquier de 8x8 cases, le plus rapide serait un tableau à 1 dimension.

Par Exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
int [] Info1 = new int[64]; 
Info[x+y<<6] = ...     ;

sera équivalent à :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
int [,] Info1 = new int[8,8]; 
Info[x,y] = ... ;

[oliverell62]

merci, pour cette reponse,

apres quelques tests je ne pense pas que je utiliserai la collection d objet ...
pb d indice entre autre


donc me voila parti pour le tableau a une dimension plus conventionnel ...

enjoy

[Graffito]

Erratum:
Pour multiplier par 8, c'est c'est Info1[x+y<<3]
(et non <<6 qui multiplie par 64)

De plus, il vaudrait mieux permuter les indices de cette façon "Info1[x<<3+y]" afin de pouvoir - par simple remplacement systématique de "<<3+" par "," - passer à Info1[x,y].

[davcha]

En fait, tableau à 1 ou 2 dimensions, c'est exactement la même chose :
- Le tableau à 1 dimension t'oblige à convertir les coordonnées de tes pièces en indice du tableau, typiquement x*H+y (où H est la hauteur de ton échiquier).
- Le tableau à deux dimensions fera exactement le même calcul, mais c'est le compilateur qui s'en occupera.

Conclusion, à ce niveau là, il vaut mieux taper dans le tableau à deux dimensions qui est un peu plus clair.

Ce qui serait différent c'est un tableau de tableaux, qui t'obligerait à faire un double déréférencement. Mais là encore, le gain de perf est vraiment minime.

Il y a d'autres façons de voir les choses que des tableaux de ce type : les bitboards, notamment, qui te permettront de visualiser l'ensemble des coups légaux d'une pièce en une opération logique (à peu de choses près, en fait, tu auras quelques soucis avec les pièces glissantes).

Tableau à 1 dimension ou 2 dimensions, tu peux t'inspirer des bitboards pour conserver des metadonnées sur ton échiquier. Autrement dit, les éléments de ton tableau ne sont plus des pièces mais des cases, dans lesquelles tu conserves des informations supplémentaires, ce qui peut aider à accélérer la génération de la liste des coups.
Dans l'exemple d'un tableau à 2 dimensions, par exemple, tu n'auras pas 64 cases, mais 144 : tu entoures tes 64 cases d'un jeu de deux cases supplémentaires qui te permettent de gérer tous les déplacements, y compris ceux du cavalier, d'une manière uniforme.

[oliverell62]

Ce qui serait différent c'est un tableau de tableaux, qui t'obligerait à faire un double déréférencement. Mais là encore, le gain de perf est vraiment minime.

Je cherche effectivement l approche qui me permettra de gagner le plus de temps
c'est de cette approche que je pensais utiliser du coup ...

Tableau à 1 dimension ou 2 dimensions, tu peux t'inspirer des bitboards pour conserver des metadonnées sur ton échiquier. Autrement dit, les éléments de ton tableau ne sont plus des pièces mais des cases, dans lesquelles tu conserves des informations supplémentaires, ce qui peut aider à accélérer la génération de la liste des coups.
Dans l'exemple d'un tableau à 2 dimensions, par exemple, tu n'auras pas 64 cases, mais 144 : tu entoures tes 64 cases d'un jeu de deux cases supplémentaires qui te permettent de gérer tous les déplacements, y compris ceux du cavalier, d'une manière uniforme.

ton post m a permis de lancer de nouvelle recherche, tu fais référence a ca j imagine :

http://analyseprogrammation.com/eche...e-coup?start=1

si tu as d autre lecture en référence ( en francais uniquement stp), a la premiere lecture ca me semble pas super évident

[oliverell62]

ola j ai mis résolu car mes questions premières le sont,

des portes ont été ouvertes, a moi de les explorer

donc :

tableau a une dimension ( 64 case )

ensuite utilisation de bitboard pour faire ressortir les coups possible

@davcha a priori tu as deja travailler sur la question ...


donc imaginons une seule ligne avec tour en a1 et une piece en a4 a5 et a6

ca donne

bitboard déplacement tour horizontale :

- x x x x x x x


bitboard échiquier ( on se réduit a la première ligne )

- - - x x x - -


ce qui d un coup d un seul doit donner ca :

- x x - - - (x x )

a moi de faire une fonction empêchant les deux derniers X X ( qui sont "- -" puisqu on ne peut sauter des pieces ) ( les croix étant les déplacement possible )

merci a tous les intervenants

si j ai bien compris le système, je n ai plus qu a voir pour apprendre a manipuler tout ca en vb.net


edit

eventuellement utilisation de BitArray ... ?

[Graffito]

eventuellement utilisation de BitArray ... ?

BitArray : pour économoiser de la mémoire (1 seul bit par élément),
bool[] ou byte[] : pour la performance (mais 8 bits par élément).

[Sehnsucht]

Bonsoir,

Il existe aussi la structure BitVector32 qui me semble pourrait peut-être être adaptée au propos (mais à vérifier j'ai un peu survolé )

Cordialement !

[oliverell62]

Bonsoir,

Il existe aussi la structure BitVector32 qui me semble pourrait peut-être être adaptée au propos (mais à vérifier j'ai un peu survolé )

Cordialement !

voui, j ai vu sur msdn mais a priori bitvector32 ne donne pas le choix c'est du 32 bit ( meme si c plus rapide d apres msdn )
il faut impérativement du 64 afin de représenter l echiquier ...

BitArray : pour économoiser de la mémoire (1 seul bit par élément),
bool[] ou byte[] : pour la performance (mais 8 bits par élément).

je vais devoir tester les trois, je ne sais pas ce qui est le plus interessant
surement la vitesse ...

merci

[meziantou]

voui, j ai vu sur msdn mais a priori bitvector32 ne donne pas le choix c'est du 32 bit ( meme si c plus rapide d apres msdn )
il faut impérativement du 64 afin de représenter l echiquier ...

Tu peux créer le type toi-même. Il suffit de prendre un type de 64bits: long et de manipuler les bits avec les opérateurs &, >>, <<.
Si tu ne veux pas t'embéter tu regardes le code de BitVector32 avec Reflector.

[davcha]

@davcha a priori tu as deja travailler sur la question ...


donc imaginons une seule ligne avec tour en a1 et une piece en a4 a5 et a6

ca donne

bitboard déplacement tour horizontale :

- x x x x x x x


bitboard échiquier ( on se réduit a la première ligne )

- - - x x x - -


ce qui d un coup d un seul doit donner ca :

- x x - - - (x x )

a moi de faire une fonction empêchant les deux derniers X X ( qui sont "- -" puisqu on ne peut sauter des pieces ) ( les croix étant les déplacement possible )

J'ai réalisé il y a une dizaine d'années un jeu d'échecs en C++ plutôt bien classé, comme il battait des jeux/joueurs classés 2700 ELO. Ca, c'est pour la petite histoire.


Concernant la suppression de ces deux bits de trop, en fait, tu as juste besoin d'un moyen de récupérer les bits limites d'une ligne ou colonne.
Suivant le sens de lecture, soit la ligne, soit la colonne est très facile à faire. Surtout si tu bosses sur un processeur x86 ou x64 récent : les instructions BSF et BSR sont là pour ça.

Quand tu as sais quelle ligne/colonne est limite, dans ton exemple, c'est la colonne 5 la limite : tout ce qu'il y a au delà de 5, 5 compris ne doit pas être prit en compte.
Tu as un ensemble de bitboards par défaut, représentant les différents mouvements possibles dans une direction pour chaque pièce glissante.

il suffit de faire un (& ~) sur le bitboard qui t'intéresse.
Dans ton exemple : bitboard & (a5e), a5e étant le bitboard des mouvements possibles vers l'est depuis la case a5.

Pour compter le nombre de coups, chose qui sera utile lors de l'évaluation d'une position, il existe différents algorithmes plus ou moins efficaces, je te trouverais un lien plus tard à ce sujet.



Après, ça peut sembler bizarre à priori, mais l'idée est d'avoir autant de bitboards que nécessaires.
Donc déjà, un bitboard par pièce ou type de pièce. Un bitboard par couleur. un bitboard pour chaque déplacement possible, etc...
Ca consomme "beaucoup" de mémoire, à priori. En fait, il faut se souvenir que tu ne consommes que 8 octets par bitboard, c'est pas énorme.

Suite plus tard.

[oliverell62]

Après, ça peut sembler bizarre à priori, mais l'idée est d'avoir autant de bitboards que nécessaires.

c 'est a peu de chose ce a quoi je me preparais ...
( meme si je ne pensais pas devoir en faire autant )

Suite plus tard.

je suis impatient, c'est super instructif ..
( pour l instant je suis totalement ton raisonnement )

( pour la petite histoire, tu as un lien vers ton moteur ? , je suis assez fan je dois dire des "echecs electroniques")

[davcha]

( pour la petite histoire, tu as un lien vers ton moteur ? , je suis assez fan je dois dire des "echecs electroniques")

J'ai pas de lien, non.

Il s'agissait d'échecs orthodoxes. J'aimerais bien en refaire un qui permette d'utiliser des jeux de règles différents, pour gérer les échecs féériques.

[oliverell62]

J'ai pas de lien, non.

Il s'agissait d'échecs orthodoxes. J'aimerais bien en refaire un qui permette d'utiliser des jeux de règles différents, pour gérer les échecs féériques.

oki, tant pis, rien a voir avec ca alors ?

http://cheesechess.free.fr/

je pensais avoir trouver ...

Suite plus tard.

prends le temps qu'il faudra, je suis abonné :p
je vais surement commencer quelques trucs les tout prochains jours, j'ai deja la base ( j'utiliserai en dernier recours un generateur de coup autre que les bitboards en attendant tes lumieres )


ps : j ai beaucoup reflechis au bitboard, il ne me semble pas irrealiste de pouvoir en parti les utiliser pour evaluer une position ( position des pieces / structure de pions / colonne ouvertes .... )

[DonQuiche]

Bonjour, je me permets d'ajouter mon petit grain de sel.

Concernant le coup du tableau à une dimension ou deux dimensions, ça devrait être un détail d'implémentation. En effet, si on utilise C#, c'est pour faire de l'objet, sinon autant utiliser du C. La bonne question à se poser est donc : à quoi est-ce que je veux que ma classe "échiquier" ressemble ? Et là...
* Il faut des accesseurs bi-dimensionnels (x, y)
* Il faut des accesseurs uni-dimensionnels (i)
* Il faut peut-être un énumérateur des pièces actuellement présentes avec leurs positions (pièce, indice)

Après, "chess" elle-même peut reposer en interne sur un tableau unidimensionnel ou bidimensionnel, ce n'est qu'un détail sans grandes conséquences. L'unidimensionnel me semble meilleur (plus simple et plus rapide à manipuler).

Enfin, concernant la question du bitboard... Stop ! C'est de l'optimisation prématurée et pas forcément judicieuse (*) qui va alourdir et obscurcir le code. Mieux vaut faire les choses dans le bon sens : d'abord on écrit rapidement un noyau qui fonctionne et réussit les tests, en utilisant assez d'abstractions pour garder une souplesse en cas de problèmes. Puis on fait un bilan des performances en relevant les éventuels bottlenecks et on optimise alors ceux-ci et rien que ceux-ci. Et on reprend le développement du programme en ajoutant de nouvelles fonctionnalités.

(*) : l'échiquier prend une place ridicule (64-512 octets sans bitboard) et tient à l'aise dans le cache L1, les combinaisons logiques d'échiquiers ne sont pas nécessaires, etc... Je cherche désespérément le moindre avantage. En revanche chaque opération est ralentie et la taille du code est augmentée. Enfin, pour une vraie conception objet on pourrait préférer avoir un tableau de références vers des objets "pawn", "king", etc, plutôt qu'un tableau de bits.