8768 sujets

Développement web côté serveur, CMS

Matrice de jeu d'échecs : tableau simple, double ou objet ?

Bonsoir,

En suivant le fil de l'un des topics du forum, je me suis amusé à coder une première version d'un jeu : Chess Game.

Ce code n'a pas de prétention, dans ce domaine il existe déjà des codes JS très aboutis (Chess.js avec Chessboard JS par exemple), c'est juste un exercice pour progresser dans le code. Pour l'instant il ne s'agit que de l'exposition de parties préjouées.

Donc, bien que cette première version fonctionne je pense qu'elle souffre d'un mauvais design : je me suis appuyé sur le HTML pour garder une trace de la position des pièces (avec des .getElementById). Dans le cas de parties préjouées ça fonctionnera pas trop mal, mais si je commence à calculer la validité d'un coup, ou d'autres choses du même type, ça va devenir compliqué (le calcul des positions où le roi se trouve en échec direct + en échec à la découverte c'est juste du délire). D'où l'idée de passer par un tableau, le HTML se contenterait alors de ne servir que d'interface. Ma première idée a été un tableau en deux dimensions :
const matrix = [
  ['br', 'bn', 'bb', 'bq', 'bk', 'bb', 'bn', 'br'],
  ['bp', 'bp', 'bp', 'bp', 'bp', 'bp', 'bp', 'bp'],
  ['', '', '', '', '', '', '', ''],
  ['', '', '', '', '', '', '', ''],
  ['', '', '', '', '', '', '', ''],
  ['', '', '', '', '', '', '', ''],
  ['wp', 'wp', 'wp', 'wp', 'wp', 'wp', 'wp', 'wp'],
  ['wr', 'wn', 'wb', 'wq', 'wk', 'wb', 'wn', 'wr']
]

Je me suis dit que les objets pouvaient être pertinent aussi :
const matrix = {
  a8: 'br', b8: 'bn', c8: 'bb', d8: 'bq', e8: 'bk', f8: 'bb', g8: 'bn', h8: 'br',
  a7: 'bp', b7: 'bp', c7: 'bp', d7: 'bp', e7: 'bp', f7: 'bp', g7: 'bp', h7: 'bp',
  a6: '', b6: '', c6: '', d6: '', e6: '', f6: '', g6: '', h6: '',
  a5: '', b5: '', c5: '', d5: '', e5: '', f5: '', g5: '', h5: '',
  a4: '', b4: '', c4: '', d4: '', e4: '', f4: '', g4: '', h4: '',
  a3: '', b3: '', c3: '', d3: '', e3: '', f3: '', g3: '', h3: '',
  a2: 'wp', b2: 'wp', c2: 'wp', d2: 'wp', e2: 'wp', f2: 'wp', g2: 'wp', h2: 'wp',
  a1: 'wr', b1: 'wn', c1: 'wb', d1: 'wq', e1: 'wk', f1: 'wb', g1: 'wn', h1: 'wr'
}

Mais il me faut surtout quelque chose de pratique pour repérer non seulement les emplacements sur les cases mais gérer les déplacements... et si un tableau unidimensionnel suffisait ? Avec un simple indexOf() pour retrouver l'emplacement d'une pièce ? (alors oui, ici les identifiants des pièces ne sont pas uniques, mais dans la vraie vie ils le seraient) :
const matrix = [
  'br', 'bn', 'bb', 'bq', 'bk', 'bb', 'bn', 'br',
  'bp', 'bp', 'bp', 'bp', 'bp', 'bp', 'bp', 'bp',
  '', '', '', '', '', '', '', '',
  '', '', '', '', '', '', '', '',
  '', '', '', '', '', '', '', '',
  '', '', '', '', '', '', '', '',
  'wp', 'wp', 'wp', 'wp', 'wp', 'wp', 'wp', 'wp',
  'wr', 'wn', 'wb', 'wq', 'wk', 'wb', 'wn', 'wr',
]

matrix.indexOf('wk') // => '74'

Les cases du tableau pourraient même dépasser de une unité sur les bords, ceci afin que les index correspondent à ceux du jeu ("11" serait "a1" et "88" serait "h8"), un changement de ligne serait un multiple de 10... Qu'en pensez-vous ? Je n'ai aucune expérience dans ce domaine.

PS : ici le code est en JavaScript, mais au final on se moque du langage, il s'agit d'une considération d'ordre générale, une question agnostique par rapport à un langage.
Modifié par Olivier C (18 Jun 2023 - 23:14)
Bonjour,

Le plus performant est évidemment le tableau unidimensionnel de 64 cases, et ce, quelque soit le langage utilisé.

Il existe des structures encore plus spécialisées pour faire des calculs de positions. Si ça t'intéresse, tu peux chercher bitboard par exemple.
Par contre je ne crois pas que ce soit utilisable en JavaScript, car cela présuppose le support des nombres entiers sur 64 bits, ce qui n'est pas le cas de JavaScript (le type flottant double est utilisé, ce qui ne garantit l'exactitude à une unité près que sur 53 bits).

De manière générale, tu fais bien de séparer au maximum les considérations logiques des considérations d'affichage.
Quand tu commenceras à faire des calculs, tu t'apercevras ainsi bien vite que décaler les pièces dans le tableau juste pour commencer à la rangée 1 au lieu de 0 te gêneras plus qu'autre chose, alors que du côté de l'affichage, c'est un bête petit +1 et c'est réglé.
De la même manière que tu as déjà remarqué que de te baser uniquement sur le DOM sans utiliser une structure pour stocker les données du modèle ailleurs n'est pas viable.

De même, utiliser un tableau unidimensionnel peut te paraître malpratique au début, mais tu verras que les avantages dépassent largement la petite multiplication à payer pour convertir des coordonnées en index.

Pour avoir moi-même codé un jeu d'échecs, effectivement, le plus compliqué dans les tests de coups valides, c'est de savoir s'il y a échec et mat ou pas...
J'ai d'ailleurs encore moi-même quelques bugs à ce niveau, on m'a dernièrement encore soumis des positions mal détectées. Le cas typique où on devrait prendre la pièce attaquante avec une pièce clouée, ou ce genre de chose.

Bonne chance.
@QuentinC : j'ai une question si tu es encore là :

Je suis tenté par l'utilisation du tableau unidimensionnel de 64 cases. Mais si pour un tableau bidimensionnel je peux m'appuyer sur undefined ou .length pour gérer les dépassements, comment devrais-je m'y prendre si dépassement d'une ligne lors d'un déplacement ?

Par exemple si je part de l'index 7 et que je me déplace d'une case sur la droite, je vais me retrouver sur la ligne au dessus à gauche de mon tableau. Il va donc falloir que je gère "si déplacement sur la droite et si dépassement au-delà d'un multiple de 8, alors impossible".

Donc, à partir d'un point A, il me faudra gérer la validité du déplacement casse après case. Si j'opte au contraire pour l'utilisation d'un tableau à deux dimensions, il me suffit de voir que le point d'arrivée est dans les choux (undefined) et c'est ok.

Du moins tout cela n'est que supposition de ma part, il va falloir que je teste tout cela. Mais si vous avez déjà des suggestions à ce sujet, des principes fondamentaux de développement que certaines de vous ont certainement dû voir lors de leurs études, ça m'éviterait de réinventer la roue par tâtonnement.
Modifié par Olivier C (18 Jun 2023 - 21:36)
Modérateur
Bonjour,

Je ne vois pas trop à quel moment tu peux avoir besoin de tester si un coup est en dehors de l'échiquier.

Soit le coup provient d'une partie enregistrée dans une base de données et sa case d'arrivée est forcément dans l'échiquier, soit le coup est placé par un utilisateur, et il ne peut le faire arriver que sur une case de l'échiquier.

Ceci étant, pour passer des coordonnées en 2 dimensions à des coordonnées en 1 dimension, et réciproquement, il suffit de se fabriquer des fonctions s'appelant par exemple ij2k() et k2ij(). Si on suppose que les coordonnées à 1 ou 2 dimensions commencent toutes à l'indice 0, on peut utiliser les fonctions suivantes pour passer de l'une à l'autre :
function ij2k(i,j)
{
	return i+j<<3;
}
// EDIT: remplacement de i+j*8 par i+j<<3 qui est légèrement plus efficace

function k2ij(k)
{
	let i=k%8,j=(k-i)>>3;
	return {i:i,j:j}
}
Ceci permet de faire par exemple tes tests "spatiaux" comme si tu étais en 2 dimensions, mais de stocker les données dans un tableau à 1 dimension.

Amicalement,
Modifié par parsimonhi (18 Jun 2023 - 23:21)
parsimonhi a écrit :
Je ne vois pas trop à quel moment tu peux avoir besoin de tester si un coup est en dehors de l'échiquier.

Je crois que le cas ce présente si l'on intègre une intelligence artificielle pour jouer. Mais je n'en suis pas là...

Pour la suite de ton message, merci, je vais potasser cela.
Modérateur
Bonjour,

Olivier C a écrit :
Je crois que le cas se présente si l'on intègre une intelligence artificielle pour jouer. Mais je n'en suis pas là...

Si tu imagines faire jouer ton programme, c'est d'une toute autre difficulté. Et ça ne sera pas un seul tableau qu'il te faudra. Smiley cligne

Amicalement,
parsimonhi a écrit :
Si tu imagines faire jouer ton programme, c'est d'une toute autre difficulté. Et ça ne sera pas un seul tableau qu'il te faudra.

Non, non, il s'agit en fait d'un exercice que je m'impose pour mieux comprendre les tableaux, et aussi les objets, la recherche et le déplacement d'un item par exemple. Si par la suite j'arrive à traiter la validité de certains coups ce sera déjà pas mal pour moi pour l'instant.
a écrit :
Je suis tenté par l'utilisation du tableau unidimensionnel de 64 cases. Mais si pour un tableau bidimensionnel je peux m'appuyer sur undefined ou .length pour gérer les dépassements, comment devrais-je m'y prendre si dépassement d'une ligne lors d'un déplacement ?

Par exemple si je part de l'index 7 et que je me déplace d'une case sur la droite, je vais me retrouver sur la ligne au dessus à gauche de mon tableau. Il va donc falloir que je gère "si déplacement sur la droite et si dépassement au-delà d'un multiple de 8, alors impossible".


Tu as toujours la relation que pour une case aux coordonnées x;y, l'index i = x + 8*y.
Dans le sens inverse, x = i%8 et y = i/8.

En utilisant des petites fonctions comme te le propose Parsimony, c'est assez facile.
Tu convertis les index des cases de départ et d'arrivée en coordonnées et tu verras tout de suite si tu débordes.

Faire ces petites fonctions sont indispensables, parce qu'évidemment, réfléchir en coordonnées est beaucoup plus simple que raisonner en indices.


Après si tu envisages de faire une IA, les échecs est parmi les jeux les plus compliqués, donc pas du tout recommandé pour commencer. Certains y ont consacré des thèses entières !
De mon côté je ne fais qu'utiliser des moteurs open source. IL y a par exemple stockfish, même en niveau facile, avec mon niveau de jeu pas exceptionnel mais tout à fait honorable, il est assez compliqué à battre...

Le jeu classique pour s'entraîner à faire une IA minimax typique pas trop difficile mais quand même assez pour apprendre quelque chose, c'est puissance 4, ou éventuellement othello.
Othello c'est déjà pas mal costaud pour ne pas faire une IA trop stupide.
Merci à vous deux pour ces infos, car j'ai vraiment du mal à me dépatouiller.

Une note sur l'IA : je n'en suis absolument pas là, mais dans l'idée, c'était d'utiliser un algorithme déjà existant, de type "alpha-beta", un arbre de recherche avec calcul du meilleur coup. De toute façon je ne pense pas arriver jusque là, si j'arrive déjà à calculer la validité des coups de certaines pièces, je serais déjà bien content.
Modifié par Olivier C (19 Jun 2023 - 16:40)
Prévenir un modérateur
Répondre au sujet
Aller à