programmation d'un jeu de dames

**Sylvain255** · 28/07/2021, 17h43

bonjour,
je cherche à programmer un jeu de dames mais suis bloqué sur un problème
algorithmique qui me bloque :
si le tableau de jeu est codé comme ceci :
type

Code :

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

1
2
// 1 noirs 2 blancs 3 dames noires 4 dames blanches
  ttab = array [0..9] of array[0..9] of Integer;

si les cases sont codées comme ceci :

Code :

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

1
2
3
4
tcase=record
    ligne:byte;
    colonne:byte;
  end;

si les coups sont codés comme ceci :

Code :

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

1
2
3
4
5
tcoup = record
    cases : array[0..19] of tcase;
    nb_cases:integer;
    prises:integer;
  end;

comment en connaissant la ligne et la colonne ainsi que le tableau de jeu
savoir l'ensemble des coups possibles (un coup peut être une prise multiple), j'y suis arrivé pour les avancées simples
mais pas pour les prises car ça part dans tous les sens et c'est encore pire avec les dames !!
Merci de m'aider
Bien cordialement

**anapurna** · 28/07/2021, 20h01

salut

algorithme minimax avec coupe alphabeta cela évite les solutions non pertinente

**Sylvain255** · 28/07/2021, 20h02

non mais ce n'est pas ma question ma question est de trouver l'ensemble des coups possibles pas de faire travailler l'ordi ça je sais faire

**anapurna** · 28/07/2021, 20h06

salut

bin pour trouver tes coups il faut bien que tu essaie une fois les essaient fait tu reviens en arrière
tu as enregistré la position de depart
et les differente combinaison en ne gardant que la meilleur

**Sylvain255** · 28/07/2021, 20h07

je n'y arrive pas justement

**Sylvain255** · 28/07/2021, 20h14

ce que je souhaiterais c'est d'avoir tous les coups possibles mêmes invalides car et seulement car pas assez de prises dans une fonction coupsPossiblesAux puis ensuite de lancer coupsPossibles en ne gardant que les coups dont le nombre de prises est le nombre de prises maximum

**Galet** · 28/07/2021, 21h59

Bonjour,
Il me semble que la solution est d'utiliser un programme recurssif pour tester toutes les solutions possibles à partir de ton point de départ.
Il faut "empiler" les appels pour scruter les cases autour d'une case en cours et mémoriser la meilleure option puis, au dépilage, mémoriser le chemin retour qui constituera la meilleure option.

Case à traiter = case initiale

Reset valeur meilleur coup et coup attribué
Reset meilleur chemin général
Reset Compteur de coup

-Fonction recherche (case à traiter) :
- Reset meilleur chemin de la case
- Reset meilleure option
- Compteur de coups = +1
-Pour chaque case en cours en contact avec la case à traiter
-- Si case de même couleur => coup impossible
-- Si case vide et case en avant et Valeur meilleur coup=0 => Avancement possible (mémoriser valeur 1 dans meilleur coup, et case visée)
-- Si case adverse => prise possible (Additionner 2 à valeur meilleur coup et meilleur chemin de la case) et rappeler (recurssif) la fonction recherche (case en cours)
-FinPour
- Si meilleur Option> meilleur chemin général => Memorisation valeur et chemin associé

Traitement résultat
La meilleure option et le meilleur chemin sont mémorisés et constitue le coup à jouer.

Si la piste te convient, j'essayerai d’écrire un code plus réfléchi...

Belle soirée..

**Sylvain255** · 28/07/2021, 22h07

oui je veux bien que tu me l'écrive en Pascal je le lirais mieux, par ailleurs il peut y avoir plusieurs chemins possibles donnant lieu au même maximum de prises et je veux évidemment tous ces chemins
merci de ton aide

**Sylvain255** · 28/07/2021, 22h09

j'ai eu l'intuition que la solution était en récursif et/ou avec des arbres mais ça me dépasse

**Sylvain255** · 30/07/2021, 16h01

des nouvelles SVP ?

**ShaiLeTroll** · 30/07/2021, 16h19

Si vous n'apportez pas d'élément supplémentaire pour débattre avec les membres, vous n'aurez pas de réponse.

En dehors des défis organisés par le forum comme par exemple un solveur de Sudoku, disons que la programmation de jeu n'est pas parmi les questions fréquentes et un sujet très rarement abordé par les professionnels.
C'est donc à vous de fournir vos efforts et éventuellement un membre pourra aider sur un cas précis.

Proposer nous un code que l'on puisse vous orientez.

**Sylvain255** · 30/07/2021, 16h41

j'ai déjà dit que la récursivité et les arbres me dépassaient donc je ne peut pas apporter de code, j'ai suffisamment expliqué mon problème je pense pour qu'il soit clair pour la communauté.

**Sylvain255** · 30/07/2021, 18h16

voici ma proposition, à vous de l'étudier :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
type
 
tdirection=record
	offsetX:integer;
	offsetY:integer;
end;
 
ttab=array[0..9] of array[0..9] of byte;
 
tcase=record
	ligne:byte;
	colonne:byte;
end;
 
tcoup=record
	nb_cases:integer;
	cases:array[0..100] of tcase;
	prises:integer;
	tableauApres:ttab;
end;
 
tcoups=record
	nb_coups:integer;
	coups:array[0..100] of tcoup;
end;
 
const
 
directions:array [0..7] of tdirection=(
	(offsetX:-1;offsetY:-1),
	(offsetX:-1;offsetY:1),
	(offsetX:1;offsetY:-1),
 	(offsetX:1;offsetY:1));
var
tableau:ttab;
//joueur vaut 1 ou 2, case vide vaut 0	$
 
function concateneCoups(a,b:tcoup;tableau:ttab):tcoup;
var i:integer;
begin
	result.nb_cases:=a.nb_cases+b.nb_cases;
	for i:=0 to a.nb_cases-1 do
		result.cases[i]:=a.cases[i];
	for i:=0 to b.nb_cases-1 do
		result.cases[i+a.nb_cases]:=b.cases[i];
	result.tableau:=tableau;
	result.prises:=a.prises+b.prises;
end;
 
function buildCoupAtomique(ligne:byte;colonne:byte;tableau:ttab;prises:integer=0):tcoup;
var tempcase:tcase;
begin
	tempcase.ligne:=ligne;
	tempcase.colonne:=colonne;
	result.nb_cases:=1;
	result.cases[0]:=tempcase;
	result.tableauApres:=tableau;
	result.prises:=prises;
end;
 
function prises(tableau:ttab;case_:tcase;joueur:integer):tcoups;//donne toutes les prises possibles
var coup:tcoup;
begin
	result.coups.nb_coups:=1;
	coup:=buildCoupAtomique(case_.ligne,case_.colonne,tableau);
	result.coups[0]:=coup;
	prisesAux(tableau,coup,result,joueur);
end;
 
function prisesAux(tableau:ttab;coup : tcoup; var coupsTotaux : tcoups;joueur:integer):ttab;//fonctiona auxiliaire
var i,offsetX,offsetY,ligne,colonne:integer;
case,tempcase:tcase;
tempcoup:tcoup;
temptab:ttab;
begin
 
	case:=coup.cases[coup.nb_coups-1];
	ligne:=case.ligne;
	colonne:=case.colonne;
	if tableau[case.ligne,case.colonne]<>joueur then
		exit;
	//recherche des prises possibles
	for i:=0 to 3 do
	begin
		temptab:=tableau;
		offsetX:=directions[i].offsetX;
		offsetY:=directions[i].offsetY;
		//vérifie si sort du tableau
		if (ligne+2*offsetY<0) or (ligne+2*offsetY>9) or (colonne+2*offsetX<0) or (colonne+2*offsetX>9) then
			continue;
		if tableau[ligne+offsetY,colonne+offsetX]=3-joueur and tableau[ligne+2*offsetY,colonne+2*offsetX]=0 then
		//ya prise
		begin
			temptab[ligne+offsetY,colonne+offsetX]:=0;
			temptab[ligne+2*offsetY,colonne+2*offsetX]:=joueur;
			tempcoup:=concateneCoups(coup,buildCoupAtomique(ligne+2*offsetY,colonne+2*offsetX,temptab,1),temptab);
			//aboutement à coupsTotaux
			coupsTotaux.nb_coups:=coupsTotaux.nb_coups+1;
			coupsTotaux.coups[coupsTotaux.nb_coups-1]:=tempcoup;
			//appel récursif
			prisesAux(temptab,tempcoup,coupsTotaux,joueur);
		end;
	end;
end;

**Sylvain255** · 30/07/2021, 18h31

ça c'est pour un pion je vais faire pour une dame maintenant

**Sylvain255** · 30/07/2021, 18h40

voici ma proposition pour à la fois le pion et la dame :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
type
 
type
 
tdirection=record
	offsetX:integer;
	offsetY:integer;
end;
 
ttab=array[0..9] of array[0..9] of byte;
 
tcase=record
	ligne:byte;
	colonne:byte;
end;
 
tcoup=record
	nb_cases:integer;
	cases:array[0..100] of tcase;
	prises:integer;
	tableauApres:ttab;
end;
 
tcoups=record
	nb_coups:integer;
	coups:array[0..100] of tcoup;
end;
 
const
 
directions:array [0..7] of tdirection=(
	(offsetX:-1;offsetY:-1),
	(offsetX:-1;offsetY:1),
	(offsetX:1;offsetY:-1),
	(offsetX:1;offsetY:1));
var
tableau:ttab;
//joueur vaut 1 (noir) ou 2 (blanc), case vide vaut 0, dame noire : 3, dame blanche : 4
 
function concateneCoups(a,b:tcoup;tableau:ttab):tcoup;
var i:integer;
begin
	result.nb_cases:=a.nb_cases+b.nb_cases;
	for i:=0 to a.nb_cases-1 do
		result.cases[i]:=a.cases[i];
	for i:=0 to b.nb_cases-1 do
		result.cases[i+a.nb_cases]:=b.cases[i];
	result.tableau:=tableau;
	result.prises:=a.prises+b.prises;
end;
 
function buildCoupAtomique(ligne:byte;colonne:byte;tableau:ttab;prises:integer=0):tcoup;
var tempcase:tcase;
begin
	tempcase.ligne:=ligne;
	tempcase.colonne:=colonne;
	result.nb_cases:=1;
	result.cases[0]:=tempcase;
	result.tableauApres:=tableau;
	result.prises:=prises;
end;
 
function prises(tableau:ttab;case_:tcase;joueur:integer):tcoups;//donne toutes les prises possibles
var coup:tcoup;
begin
	result.coups.nb_coups:=1;
	coup:=buildCoupAtomique(case_.ligne,case_.colonne,tableau);
	result.coups[0]:=coup;
	prisesAux(tableau,coup,result,joueur);
end;
 
function prisesAux(tableau:ttab;coup : tcoup; var coupsTotaux : tcoups;joueur:integer):ttab;//fonctiona auxiliaire
var i,j,offsetX,offsetY,ligne,colonne:integer;
case,tempcase:tcase;
tempcoup:tcoup;
temptab:ttab;
begin
 
	case:=coup.cases[coup.nb_coups-1];
	ligne:=case.ligne;
	colonne:=case.colonne;
	if tableau[case.ligne,case.colonne]<>joueur then
		exit;
	//recherche des prises possibles
 
	if joueur < 3 then//pion 
	begin
		for i:=0 to 3 do
		begin
			temptab:=tableau;
			offsetX:=directions[i].offsetX;
			offsetY:=directions[i].offsetY;
			//vérifie si sort du tableau
			if (ligne+2*offsetY<0) or (ligne+2*offsetY>9) or (colonne+2*offsetX<0) or (colonne+2*offsetX>9) then
				continue;
			if tableau[ligne+offsetY,colonne+offsetX]=3-joueur and tableau[ligne+2*offsetY,colonne+2*offsetX]=0 then
			//ya prise
			begin
				temptab[ligne+offsetY,colonne+offsetX]:=0;
				temptab[ligne+2*offsetY,colonne+2*offsetX]:=joueur;
				tempcoup:=concateneCoups(coup,buildCoupAtomique(ligne+2*offsetY,colonne+2*offsetX,temptab,1),temptab);
				//aboutement à coupsTotaux
				coupsTotaux.nb_coups:=coupsTotaux.nb_coups+1;
				coupsTotaux.coups[coupsTotaux.nb_coups-1]:=tempcoup;
				//appel récursif
				prisesAux(temptab,tempcoup,coupsTotaux,joueur);
			end;
		end;
	end
	else//dame
	begin
		for i:=0 to 3 do
		begin
			temptab:=tableau;
			offsetX:=directions[i].offsetX;
			offsetY:=directions[i].offsetY;
 
			for j:=2 to 9 do//déplacement de la dame
			begin
				//vérifie si sort du tableau
				if (ligne+j*offsetY<0) or (ligne+j*offsetY>9) then
					continue;
				for k:=1 to j-1 do//emplacement du pion adverse
				begin
					if tableau[ligne+k*offsetY,colonne+k*offsetX]=3-joueur and tableau[ligne+j*offsetY,colonne+j*offsetX]=0 then
					//ya prise
					begin
						temptab[ligne+k*offsetY,colonne+k*offsetX]:=0;
						temptab[ligne+j*offsetY,colonne+j*offsetX]:=joueur;
						tempcoup:=concateneCoups(coup,buildCoupAtomique(ligne+j*offsetY,colonne+j*offsetX,temptab,1),temptab);
						//aboutement à coupsTotaux
						coupsTotaux.nb_coups:=coupsTotaux.nb_coups+1;
						coupsTotaux.coups[coupsTotaux.nb_coups-1]:=tempcoup;
						//appel récursif
						prisesAux(temptab,tempcoup,coupsTotaux,joueur);
					end;
				end;
			end;
		end;
	end;
end;

**Paul TOTH** · 31/07/2021, 10h53

Envoyé par Sylvain255

j'ai déjà dit que la récursivité et les arbres me dépassaient donc je ne peut pas apporter de code, j'ai suffisamment expliqué mon problème je pense pour qu'il soit clair pour la communauté.

alors, soyons clair, la "communauté" n'est pas un groupe de gens qui se penchent sur des problèmes de programmation pour le compte d'un seul, c'est un endroit d'échanges sur des points précis, voir sur un projet complet quand plusieurs personnes sont intéressées par un même sujet. Et souvent simplement un endroit pour exposer ses propres découvertes pour le compte de tous.

là ton projet n'intéresse pas grand monde manifestement, donc si tu as des questions du type, "pensez vous que cette structure est adaptée pour stocker un historique de coups", ou encore "cette boucle est très lente, voyez vous un moyen de l'optimiser", tu auras sans doute des réponses...quand à écrire le code que tu souhaites quand tu balances une structure ça il y a peu de chance que quelqu'un réponde (sauf encore une fois s'il est lui-même très intéressé par le sujet).

tu pourras aussi constaté que le thème a déjà été abordé
https://www.developpez.net/forums/d7...aux-jeu-dames/

et tu trouves aussi facilement des explications sur mini max
en anglais
http://delphiforfun.org/programs/nim_minimax.htm

en français
https://fabien-torre.fr/Enseignement...ielle/jeux.php

et même en Delphi, pour le puissance 4
https://lazarus.developpez.com/telec...orithme-MinMax

**Sylvain255** · 31/07/2021, 11h22

c'est pas grave car finalement j'y suis arrivé seul

**Paul TOTH** · 31/07/2021, 18h01

Envoyé par Sylvain255

c'est pas grave car finalement j'y suis arrivé seul

et dans l'esprit du forum, on donne la solution qu'on a trouvé afin que quelqu'un qui dans un certain temps s'intéresserait à la question puisse bénéficier de ton expérience.

**Galet** · 31/07/2021, 18h17

Désolé Sylvain, je reviens un peu après la bataille. Vraiment pas de temps à y consacrer.

Je ne peux que rejoindre Paul sur l'intérêt de ce forum. On y trouve pas toujours LA solution, mais toujours beaucoup, beaucoup de conseils...
Si tu as vraiment trouvé la solution, alors, bravo à toi. Tu peux partager ton expérience, pour donner de l'aide, ou envie à d'autres de rebondir sur ton idée ou ton travail.
Si ce n'est pas le cas, n'hésites pas à revenir. Tu as avancé, donc tes questions sont surement plus précises...

Bell journée,

**Andnotor** · 01/08/2021, 11h16

Commentaires moralisateurs pas forcément utiles. Si le sujet n'intéresse pas, ben on ne répond pas, simplement !

Ce qu'on peut dire sur le dernier code posté est qu'il ne doit pas compiler.

La constante directions n'est pas entièrement définie.
L'utilisation du mot réservé case comme nom de variable. Devrait être précédé d'un & :&case.
Manque de parenthèses en ligne 96, and est prioritaire sur =.

Sinon

3-joueur, impossible de prendre une dame.
temptab[]:=0 est faux puisque les pions ne doivent être retirés qu'à la fin du coup.
Il manque quelque chose en fonction du nombre de prises puisque seuls les maximum sont possibles. Devrait certainement remplacer TCoup et TCoups.

Et sur le code lui-même

Parfois X/Y, parfois ligne/colonne. Ce serait bien de normaliser le tout.
Inutile de réinventer la roue, TDirection et TCase pourraient être des TPoint.
TCoups (si nécessaire) devrait être un tableau dynamique.
Calculer les indices en début de procédure rendrait le code plus concis et facile à lire.
Les déplacements d'une dame ou d'un pion sont les mêmes. Seul le nombre de vides autorisé est différent (0 ou N). Ca pourrait être une seule procédure.

En résumé, les règles du jeux ne sont pas respectées et le code pourrait être plus simple et plus clair.

programmation d'un jeu de dames

Delphi

Discussions similaires

Partager

Partager