My board representation is color independent and do not need flipping position between moves.
All square coordinates are relative to its own side. So White's E1 is equal to Black's E8, but there is no need to know color except for UCI input and output.
Black/White symmetry in move generation
Moderators: hgm, Rebel, chrisw
-
Aleks Peshkov
- Posts: 892
- Joined: Sun Nov 19, 2006 9:16 pm
- Location: Russia
-
SMIRF
- Posts: 91
- Joined: Wed Mar 26, 2014 4:29 pm
- Location: Buettelborn/Hessen/Germany
Re: Black/White symmetry in move generation
That is not quite exact, what I am about to get working. There are two colorless boards, and links to them are switched when making a move. The board view (of the black opponent) is mirrored to get his own starting array in front. At both simultaneaous to be updated boards all enemy pieces are all uniquly encoded as opponent (*).Gerd Isenberg wrote:... Reinhard keeps both a normal and color flipped board and has more effort to incrementally update them, and gains from some special piece encoding. ...
Moreover all pieces are sorted double linked within their inner encoding having an extern root pointer linking to the local king. Additionally there are pawn influeces encoded, +2 for any threat and +1 for passed pawn blocking.
This leads to a uniform move generator no more at all being color depending in any way. It is already usable for 8x8 and 10x8 chess variations.
Here is a modified dump example of two encoded 10x8 twin boads (black side is active here):
Code: Select all
(b) view at 01CF2490: (active)
70 07 c0 ## ## ## ## ## ## ## ## ## ## ## ## ## Pj7 Pi7 Ph7
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## Pg7 Pf7 Pe7
## ## ## ## ## ## ## ## ## ## *0 ## ## K0 ## ## Pd7 Pc7 Pb7
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## Pa7 Nf8 Nd8
A0 P0 3 1 1 1 *1 *1 ## ## ## ## ## ## ## ## Bg8 Bb8 Aa8
B0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ## Rj8 Re8 Cc8
C0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ## Qh8 Ki8
N0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
R0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
N0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
B0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
Q0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
K0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
R0 P0 3 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
(w) view at 01CF2070: (passive)
90 00 c0 ## ## ## ## ## ## ## ## ## ## ## ## ## Pj2 Pi2 Ph2
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## Pg2 Pf2 Pe2
## ## ## ## ## ## ## ## ## ## *0 ## ## K0 ## ## Pd2 Pc2 Pb2
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## Pa2 Nf1 Nd1
A0 P0 3 1 1 1 *1 *1 ## ## ## ## ## ## ## ## Bg1 Bb1 Aa1
B0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ## Rj1 Re1 Cc1
C0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ## Qh1 Ki1
N0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
R0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
N0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
B0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
Q0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
K0 P0 5 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
R0 P0 3 1 1 1 *1 *1 ## ## ## ## ## ## ## ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
-
syzygy
- Posts: 5563
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Black/White symmetry in move generation
I don't remember exactly, but nothing fancy. The first version ran on an (already then old) Amiga 500.Gerd Isenberg wrote:Why? For which board representation?syzygy wrote:If I remember well, the first version of my engine only generated moves for white and flipped the board after every move.
But this was/is not a good idea
Btw, I did not want to imply (at all) that Reinhard's approach is not a good idea. My approach was not a good idea, at least not then and with my board representation.
-
SMIRF
- Posts: 91
- Joined: Wed Mar 26, 2014 4:29 pm
- Location: Buettelborn/Hessen/Germany
Re: Black/White symmetry in move generation
Continuing working on an 8x8 and 10x8 chess engine having a colorless board representation at a first progress there are well running tests for random king placements: the routine answers with an opponent piece type, when a king placement will fail by its check threat. That written routine is working without having any type of color specific parts inside, neither of any such code would be generated.
Code: Select all
Compiler: Embarcadero RAD C/C++ 32-Bit Vers. 6.90
XFEN: 3q2R1/2P5/1k1B4/4np2/1NPK1Pr1/1R6/PP1N1Q2/3q2b1 w - - 0 1
+-a--b--c--d--e--f--g--h-+
8 | ::: [q] :::<R>:::| Q Q Q - Q Q Q -
7 |::: <P> ::: ::: | K K K Q Q N R -
6 | [k] <B> ::: :::| K - K Q - Q R -
5 |::: ::: [n][p]::: | K K K - - - Q -
4 | <N><P><K> <P>[r]:::| - - N - P R P Q
3 |:::<R>::: ::: ::: | - Q - N - Q R -
2 |<P><P> <N> <Q> :::| - - Q Q Q B R B
1 |::: :::[q]::: [b] | Q Q Q - Q Q Q -
=>+-a--b--c--d--e--f--g--h-+
Test #0: 192 M tests in 1.94 sec, rate 98.97 M tests/sec
XFEN: 3R4/b1N1Q3/2B4K/r2P3b/pB1k2p1/1qR1p3/1Nn5/6n1 w - - 0 1
+-a--b--c--d--e--f--g--h-+
8 | ::: <R> ::: :::| - B - - B - - -
7 |[b] <N> <Q> ::: | R - - - - B - -
6 | :::<B>::: ::: <K>| R B - - - - B -
5 |[r] :::<P>::: :::[b]| - R K K K - - -
4 |[p]<B> [k] :::[p]:::| Q Q K B K - B -
3 |:::[q]<R> [p] ::: | Q P K K K P - P
2 | <N>[n]::: ::: :::| Q Q Q P N P - -
1 |::: ::: ::: [n] | N - - - N - - -
=>+-a--b--c--d--e--f--g--h-+
Test #1: 192 M tests in 2.19 sec, rate 87.67 M tests/sec
-
SMIRF
- Posts: 91
- Joined: Wed Mar 26, 2014 4:29 pm
- Location: Buettelborn/Hessen/Germany
Re: Black/White symmetry in move generation
The textual view has been improved. Castling rights are shown by '*' symbols, e.p. fields are also marked. An existing check threat will be shown by a (+) at the left side, were also is a color symbol in front of the moving view. 8x8 and 10x8 Chess XFEN positions are well accepted.
Thus now XFEN (also when partially irregular) will be interpreted correctly. The slowly growing solution is working fine at 32 bit and 64 bit, but improvements by that are yet small. Maybe this is related to the C compiler from Embarcadero. Nevertheless this is not yet the time for extensive optimization apart from the data structure.
Thus now XFEN (also when partially irregular) will be interpreted correctly. The slowly growing solution is working fine at 32 bit and 64 bit, but improvements by that are yet small. Maybe this is related to the C compiler from Embarcadero. Nevertheless this is not yet the time for extensive optimization apart from the data structure.
Code: Select all
XFEN: rcbbkarnqn/pppppppppp/////PPPPPPPPPP/RCBBKARNQN w KQkq - 0 1
+-*--b--c--d--*--f--*--h--i--j-+
8 |[r][c][b][b][k][a][r][n][q][n]| C R C K - K - Q - Q
7 |[p][p][p][p][p][p][p][p][p][p]| R P P P P P P P Q P
6 | ::: ::: ::: ::: :::| P P P P P P P P P P
5 |::: ::: ::: ::: ::: | - - - - - - - - - -
4 | ::: ::: ::: ::: :::| - - - - - - - - - -
3 |::: ::: ::: ::: ::: | - - - - - - - - - -
2 |<P><P><P><P><P><P><P><P><P><P>| - - - - - - - - - -
1 |<R><C><B><B><K><A><R><N><Q><N>| - - - - - - - - - -
(w)+-*--b--c--d--*--f--*--h--i--j-+
Test #19: 240 M tests in 4.00 sec, rate 60.00 M tests/sec
XFEN: 2q7//2kP1a1c2/1pP4N1R/pB2K1p3/P2r1PN3/1b2P5/3B3C2 w - b6 0 1
+-a--b--c--d--e--f--g--h--i--j-+
8 | :::[q]::: ::: ::: :::| Q Q - Q Q Q Q Q Q Q
7 |::: ::: ::: ::: ::: | - P K P A C A C - C
6 | :*:[k]<P> [a] [c] :::| Q K Q K Q C C - C C
5 |:::[p]<P> ::: :::<N>:::<R>| - P K P P Q P C - C
(+)|[p]<B> :::<K>:::[p]::: :::| P - P A A - Q A C -
3 |<P> :::[r]:::<P><N> ::: | R P A - R P - P A -
2 | [b] :::<P>::: ::: :::| - A - R - - - - - A
1 |::: :::<B>::: :::<C>::: | P - P R - - - - - -
(w)+-a--b--c--d--e--f--g--h--i--j-+
Test #20: 240 M tests in 2.22 sec, rate 108.11 M tests/sec
-
SMIRF
- Posts: 91
- Joined: Wed Mar 26, 2014 4:29 pm
- Location: Buettelborn/Hessen/Germany
Re: Black/White symmetry in move generation
Now the inner structure no longer needs any switching of the two twin boards. An ability has been included, to fully support castling rights for 8x8- and 10x8-Chess including random variations. There is a built-in function to produce an XFEN string from a given position in original, color-swapped or mirrored (without making internal replacings).
Color-swapping is important for the later verifying of a color independant and thus fully symmetric move generation.
Color-swapping is important for the later verifying of a color independant and thus fully symmetric move generation.
Code: Select all
rrbRN1k1/p3pppb/3p4/K1pPPP2/5R2/5B2/8/8 w b c6 0 1
+-a--*--c--d--e--f--*--h-+
8 |[r][r][b]<R><N>:::[k]:::|
7 |[p] ::: [p][p][p][b]|
6 | ::: * [p] ::: :::|
5 |<K> [p]<P><P><P>::: |
4 | ::: ::: <R> :::|
3 |::: ::: :::<B>::: |
2 | ::: ::: ::: :::|
1 |::: ::: ::: ::: |
(w)+-a--b--c--d--e--f--g--h-+
8/8/5b2/5r2/k1Pppp2/3P4/P3PPPB/RRBrn1K1 b B c3 0 1
(b)+-a--b--c--d--e--f--g--h-+
8 | ::: ::: ::: :::|
7 |::: ::: ::: ::: |
6 | ::: ::: [b] :::|
5 |::: ::: :::[r]::: |
4 |[k]:::<P>[p][p][p] :::|
3 |::: :*:<P>::: ::: |
2 |<P>::: :::<P><P><P><B>|
1 |<R><R><B>[r][n] <K> |
+-a--*--c--d--e--f--*--h-+
8/8/2b5/2r5/2pppP1k/4P3/BPPP3P/1K1nrBRR b G f3 0 1
(b)+-a--b--c--d--e--f--g--h-+
8 | ::: ::: ::: :::|
7 |::: ::: ::: ::: |
6 | :::[b]::: ::: :::|
5 |::: [r] ::: ::: |
4 | :::[p][p][p]<P> [k]|
3 |::: ::: <P> * ::: |
2 |<B><P><P><P> ::: <P>|
1 |:::<K>:::[n][r]<B><R><R>|
+-a--*--c--d--e--f--*--h-+
-
sje
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Move ordering bias
I suggest that moves which gain center tropism are better than those which lose such, and that this technique is overall better than advance/retreat ordering. It's an old idea which was used by the Spraklens some forty years ago.bob wrote:There is an an advantage to generate moves that advance before moves that retreat.
For generating an additive bias to enforce color symmetry for ordering otherwise equal merit moves, I suggest using a look-up table or maybe a simple calculation using the move's from/to square coordinates. The calculation or table is cleverly constructed to grant a small but effective additive bias per move which cancels differences in color specific move generation ordering. Of course, the details would be heavily dependent upon the exact generation algorithm in use. I doubt if it's worth the effort, but it could be done.
-
SMIRF
- Posts: 91
- Joined: Wed Mar 26, 2014 4:29 pm
- Location: Buettelborn/Hessen/Germany
Re: Move ordering bias
To modify move ordering aiming to preserve color symmetrie is merely a compromise and is risking the goal of efficiency. To get rid of color unbalances simply get rid of any piece color inside of position representation. I am tardily working on an approach related to this.
-
SMIRF
- Posts: 91
- Joined: Wed Mar 26, 2014 4:29 pm
- Location: Buettelborn/Hessen/Germany
Re: color symmetric behaviour
Here is an example of color neutral behaviour in testing intended positions for the king of the active side of being in check. This is done twice: first using the original position, then using the color swapped one. Results are symmetric and time consumation equals, too.
Code: Select all
XFEN: rn1bqkb2r/ppppa1pppp/4p1cn2/10/5pP3/2NA1P4/PPPPPBNPPP/R2BQK1C1R w KQkq - 0 1
+-*--b--c--d--e--*--g--h--i--*-+
8 |[r][n] [b][q][k][b]::: [r]| - R A Q K Q K C R -
7 |[p][p][p][p][a] [p][p][p][p]| R - B Q K K K B C R
6 | ::: :::[p]:::[c][n] :::| P P P P P P P P P P
5 |::: ::: ::: ::: ::: | - - A P C P C - C N
4 | ::: ::: [p]<P>::: :::| - A - - - C C C N -
3 |::: <N><A>:::<P>::: ::: | A - - - P - P - A -
2 |<P><P><P><P><P><B><N><P><P><P>| - - - - - - - - - A
1 |<R> :::<B><Q><K>:::<C>:::<R>| - - - - - - - - - -
(w)+-*--b--c--d--e--*--g--h--i--*-+
Test-a #23: 400 M tests in 5.59 sec, rate 71.56 M tests/sec
XFEN: r2bqk1c1r/pppppbnppp/2na1p4/5Pp3/10/4P1CN2/PPPPA1PPPP/RN1BQKB2R b KQkq - 0 1
(b)+-*--b--c--d--e--*--g--h--i--*-+
8 |[r]::: [b][q][k] [c] [r]| - - - - - - - - - -
7 |[p][p][p][p][p][b][n][p][p][p]| - - - - - - - - - A
6 | :::[n][a] [p] ::: :::| A - - - P - P - A -
5 |::: ::: :::<P>[p] ::: | - A - - - C C C N -
4 | ::: ::: ::: ::: :::| - - A P C P C - C N
3 |::: ::: <P> <C><N>::: | P P P P P P P P P P
2 |<P><P><P><P><A>:::<P><P><P><P>| R - B Q K K K B C R
1 |<R><N>:::<B><Q><K><B> :::<R>| - R A Q K Q K C R -
+-*--b--c--d--e--*--g--h--i--*-+
Test-b #23: 400 M tests in 5.59 sec, rate 71.56 M tests/sec
-
SMIRF
- Posts: 91
- Joined: Wed Mar 26, 2014 4:29 pm
- Location: Buettelborn/Hessen/Germany
Re: color symmetric behaviour
Now there has been some progress in my slowly growing C++ written engine. The colorless representation holds and there now is a rough move generator (able to handle 8x8, 10x8, random ...) creating VALID moves only, each also supplied by CHECK threat information:
This example shows the created moves in long, algebraic and PGN format.
Speed of generation alreay seems to be sufficient before further optimization (generating moves with king in check threat still seems to be slow).
Code: Select all
XFEN 2: 3k4/8/8/2N4b/6n1/8/5P2/R3K2R w KQ - 0 1
(move count: 32)
+-a--b--c--d--e--f--g--h-+
8 | ::: [k] ::: :::|
7 |::: ::: ::: ::: |
6 | ::: ::: ::: :::|
5 |::: <N> ::: :::[b]|
4 | ::: ::: :::[n]:::|
3 |::: ::: ::: ::: |
2 | ::: ::: <P> :::|
1 |<R> ::: <K> :::<R>|
(w)+-*--b--c--d--*--f--g--*-+
Generats 320 M moves in 2.00 sec, rate 160.00 M moves/sec
Ke1-e2 Ke1-d1 Ke1-d2 Ke1-f1 f2-f3 f2-f4 Nc5-d7
Nc5-b7+ Nc5-e6+ Nc5-a6 Nc5-e4 Nc5-a4 Nc5-d3 Nc5-b3
Ra1-a2 Ra1-a3 Ra1-a4 Ra1-a5 Ra1-a6 Ra1-a7 Ra1-a8+
Ra1-b1 Ra1-c1 Ra1-d1+ O-O-O+ Rh1-h2 Rh1-h3 Rh1-h4
Rh1xh5 Rh1-g1 Rh1-f1 O-O
e1e2 e1d1 e1d2 e1f1 f2f3 f2f4 c5d7
c5b7 c5e6 c5a6 c5e4 c5a4 c5d3 c5b3
a1a2 a1a3 a1a4 a1a5 a1a6 a1a7 a1a8
a1b1 a1c1 a1d1 e1c1 h1h2 h1h3 h1h4
h1h5 h1g1 h1f1 e1g1
Ke2 Kd1 Kd2 Kf1 f3 f4 Nd7
Nb7+ Ne6+ Na6 Ne4 Na4 Nd3 Nb3
Ra2 Ra3 Ra4 Ra5 Ra6 Ra7 Ra8+
Rb1 Rc1 Rd1+ O-O-O+ Rh2 Rh3 Rh4
Rxh5 Rg1 Rf1 O-O
XFEN 22: 2q7/10/2kP1a1c2/1pP4N1R/pB2K1p3/P2r1PN3/1b2P5/3B3C2 w - b6 0 1
(move count: 3)
+-a--b--c--d--e--f--g--h--i--j-+
8 | :::[q]::: ::: ::: :::|
7 |::: ::: ::: ::: ::: |
6 | :*:[k]<P> [a] [c] :::|
5 |:::[p]<P> ::: :::<N>:::<R>|
(+)|[p]<B> :::<K>:::[p]::: :::|
3 |<P> :::[r]:::<P><N> ::: |
2 | [b] :::<P>::: ::: :::|
1 |::: :::<B>::: :::<C>::: |
(w)+-a--b--c--d--e--f--g--h--i--j-+
Generats 60 M moves in 4.41 sec, rate 13.61 M moves/sec
Ke4-f4 Ke4xd3 Nh5xf6
e4f4 e4d3 h5f6
Kf4 Kxd3 Nxf6
Speed of generation alreay seems to be sufficient before further optimization (generating moves with king in check threat still seems to be slow).