Discussion :

[davcha]

Dans un jeu d'echecs on peut utiliser une méthode appelée les rotating bitboards. Le principe est de considérer l'échiquier comme un nombre sur 64 bits. 1 bit par case.

Code :

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

1
2
3
4
5
6
7
8
A8 B8 C8 D8 E8 F8 G8 H8
A7 B7 C7 D7 E7 F7 G7 H7
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 B2 C2 D2 E2 F2 G2 H2
A1 B1 C1 D1 E1 F1 G1 H1

A1 étant le bit 0, B1 le bit 1, C1 le bit 2 etc...

Jusqu'ici pas de problème, mais j'ai besoin de connaitre les algos permettant de réaliser des rotations de +45, -45 et +90 degrés sur ce nombre.

Exemple sur un nombre de 4 bits :

Code :

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

1
2
3
4
5
 
3210
 
2 3
0 1

devient après une rotation de +45° :

Code :

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

1
2
3
4
5
 
3120
 
1 3
0 2

-45° :

Code :

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

1
2
3
4
5
 
2301
 
3 2
1 0

+90° :

Code :

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

1
2
3
4
5
 
1302
 
3 1
2 0

Des idées ?

[bragon]

Je ne comprend pas ton systéme de rotating bitboard , pourrais tu expliquer ?

Quel est l'intérêt des rotating bitboard ? Je connais la méthode des bitboard pour représenter un échiquier mais pas celle des rotating bitboard .

A+

[GoldenEye]

Conversion en une matrice 2D et transposées ou matrices de rotation ?
Non il doit y avoir bcp mieux
Mais pkoi as tu besoin d'une rotation de ton échiquier ???
La méthode bitboard permet de gagner de la place et du temps. Un seul test suffit pour savoir si on est dans l'échiquier
soit i ta case
if (i&0x88)
faire_mouvement()

alors qu'en 2D, tu te tapes
if(i>0 && i < 8 && j >0 && j < 8)
faire_mouvement()

[davcha]

la méthode du 0x88 requiert un échiquier double, c'est à dire un échiquier réel et un échiquier virtuel qui ne sert qu'à délester les cases où le bit 0x8 de l'index est présent.

avec les rotating bitboard, on fait un seul test 0x40 sur un échiquier de 64 cases, et non 128 cases.

Pour la rotation c'est bon j'ai trouvé, par contre c'est bizarrement plus lent que ce que je fais actuellement (série de tests ordonnés pour en faire le moins possible).

C'est sûrement dû à la génération du bitboard, ainsi que la mise à jour des bitboards des pièces blanches et noires.

voilà comment je faisais en gros pour tourner les bitboards :

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
typedef __int64 BITBOARD;
 
const BITBOARD BIT=1;
 
const int
	a8= 0, b8= 1, c8= 2, d8= 3, e8= 4, f8= 5, g8= 6, h8= 7,
	a7= 8, b7= 9, c7=10, d7=11, e7=12, f7=13, g7=14, h7=15,
	a6=16, b6=17, c6=18, d6=19, e6=20, f6=21, g6=22, h6=23,
	a5=24, b5=25, c5=26, d5=27, e5=28, f5=29, g5=30, h5=31,
	a4=32, b4=33, c4=34, d4=35, e4=36, f4=37, g4=38, h4=39,
	a3=40, b3=41, c3=42, d3=43, e3=44, f3=45, g3=46, h3=47,
	a2=48, b2=49, c2=50, d2=51, e2=52, f2=53, g2=54, h2=55,
	a1=56, b1=57, c1=58, d1=59, e1=60, f1=61, g1=62, h1=63;
 
const int Rotate90[]={
	h8,h7,h6,h5,h4,h3,h2,h1,
	g8,g7,g6,g5,g4,g3,g2,g1,
	f8,f7,f6,f5,f4,f3,f2,f1,
	e8,e7,e6,e5,e4,e3,e2,e1,
	d8,d7,d6,d5,d4,d3,d2,d1,
	c8,c7,c6,c5,c4,c3,c2,c1,
	b8,b7,b6,b5,b4,b3,b2,b1,
	a8,a7,a6,a5,a4,a3,a2,a1
};
 
const int RotateL45[64] = {
	h8,
	g8,h7,
	f8,g7,h6,
	e8,f7,g6,h5,
	d8,e7,f6,g5,h4,
	c8,d7,e6,f5,g4,h3,
	b8,c7,d6,e5,f4,g3,h2,
	a8,b7,c6,d5,e4,f3,g2,h1,
	a7,b6,c5,d4,e3,f2,g1,
	a6,b5,c4,d3,e2,f1,
	a5,b4,c3,d2,e1,
	a4,b3,c2,d1,
	a3,b2,c1,
	a2,b1,
	a1   
};
 
 
const int RotateR45[]={
	a8,
	a7,b8,
	a6,b7,c8,
	a5,b6,c7,d8,
	a4,b5,c6,d7,e8,
	a3,b4,c5,d6,e7,f8,
	a2,b3,c4,d5,e6,f7,g8,
	a1,b2,c3,d4,e5,f6,g7,h8,
	b1,c2,d3,e4,f5,g6,h7,
	c1,d2,e3,f4,g5,h6,
	d1,e2,f3,g4,h5,
	e1,f2,g3,h4,
	f1,g2,h3,
	g1,h2,
	h1
};
 
__int64 Mask[64];
 
void bbInit(){
	for(int i=0;i<64;i++)
		Mask[i]=BIT<<i;
}
 
BITBOARD bbRotate(const BITBOARD B,const int Rot[]){
	BITBOARD R=0;
	for(int i=0;i<64;i++)
		if(B & Mask[Rot[i]])R|=BIT<<i;
	return R;
}

En gros on commence par bbInit(); ensuite, il suffit d'appeler R=bbRotate(B,Rot); avec B le bitboard à tourner, R le résultat, et Rot la rotation (soit Rotate[90/L45/R45])
C'est la méthode utilisée par Beowulf

[GoldenEye]

Très intéréssant j'avoue avoir lu un peu trop vite ton topic de départ
Content que tu aies pu trouver tout seul !