Gerd Isenberg wrote:... Was the doubled linked piece list your invention?
SMIRF uses it from its beginning. I have mentioned that detail here sometimes. Though I have not seen that approach before, I am unsure whether possible parallel activities have existed.
The doubly linked piece list is too obvious to be the invention of any one person. My little first working chess program, Carnivor, uses them. Nothing fancy, just a next piece array (nxt) and a previous piece array (prv) and the pieces on the board are indexs, not types/colors (linking squares). Then a year after Carnivor was written I noticed that Tord does the same thing in Glaurung 1.21, except that he uses a structure (struct.next struct.prev, IIRC).
The big advantage to doubly linked list (for me anyway) is updating the list on the fly is very fast and once a piece is disconnected (removed/captured) it requires no more clock cycles. The removed piece remains in the list with its pointers intact and is just reconnected on takeback().
As s funny side note in one of the functions Remove()/PutBack() (I forget which one) the optimizing C compiler used about twenty machine instructions while my hand written assembler code did it in four.
Last edited by Michael Sherwin on Sat Aug 22, 2009 7:12 pm, edited 1 time in total.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Gerd Isenberg wrote:Congrats to Fritz Reul for his Ph.D. Thesis New Architectures in Computer Chess, which mainly refers to his innovative mailbox 8*8 board structure with a 15*12 board array, and doubly linked piece list for disjoint pieces, even light and dark bishops. Fritz also covers magic bitboards and SEE. He mentiones f.i. that using the homogeneous ~2MB array (Lasse Hansen's initial approach) with constant shifts (64-12) versus the denser Pradu's 800K, with individual sizes for each square but slightly longer code was about the same speed inside his chess program Loop Amsterdam. Reul's thesis deserves a recommendation for each computer chess programmer and people interested in computer chess programming.
Gerd
Weird, you can prove mailbox 16x16 is faster than 15x12.
He did not compare it with that is it?
Gerd Isenberg wrote:... Was the doubled linked piece list your invention?
SMIRF uses it from its beginning. I have mentioned that detail here sometimes. Though I have not seen that approach before, I am unsure whether possible parallel activities have existed.
The doubly linked piece list is too obvious to be the invention of any one person. My little first working chess program, Carnivor, uses them. Nothing fancy, just a next piece array (nxt) and a previous piece array (prv) and the pieces on the board are indexs, not types/colors (linking squares). Then a year after Carnivor was written I noticed that Tord does the same thing in Glaurung 1.21, except that he uses a structure (struct.next struct.prev, IIRC).
The big advantage to doubly linked list (for me anyway) is updating the list on the fly is very fast and once a piece is disconnected (removed/captured) it requires no more clock cycles. The removed piece remains in the list with its pointers intact and is just reconnected on takeback().
As s funny side note in one of the functions Remove()/PutBack() (I forget which one) the optimizing C compiler used about twenty machine instructions while my hand written assembler code did it in four.
He raises a point though, which rises the obvious question which open source exists for 15x12.
Gerd Isenberg wrote:Congrats to Fritz Reul for his Ph.D. Thesis New Architectures in Computer Chess, which mainly refers to his innovative mailbox 8*8 board structure with a 15*12 board array, and doubly linked piece list for disjoint pieces, even light and dark bishops. Fritz also covers magic bitboards and SEE. He mentiones f.i. that using the homogeneous ~2MB array (Lasse Hansen's initial approach) with constant shifts (64-12) versus the denser Pradu's 800K, with individual sizes for each square but slightly longer code was about the same speed inside his chess program Loop Amsterdam. Reul's thesis deserves a recommendation for each computer chess programmer and people interested in computer chess programming.
Gerd
Weird, you can prove mailbox 16x16 is faster than 15x12.
He did not compare it with that is it?
Vincent
He compared it with the GNU Chess approach and rotated bitboards (in 64-bit mode). His blocking loops don't need the & 0x88 condition, but I guess this is true for other mailbox approaches as well. Having 3+4 or 4+3 boarder files make square differences (+offset) unique relative to square distance and directions alá 0x88 with a denser board array. According to Fritz, Chrilly used the New Technology approach in Hydra as well.
His elaborate on magic hashing does not bear any new insights for me and has some weak spots, f.i. he mentions 12-bit indices, without explaining where the 12 bits come from (2 * inner six bits).
Gerd Isenberg wrote:Congrats to Fritz Reul for his Ph.D. Thesis New Architectures in Computer Chess, which mainly refers to his innovative mailbox 8*8 board structure with a 15*12 board array, and doubly linked piece list for disjoint pieces, even light and dark bishops. Fritz also covers magic bitboards and SEE. He mentiones f.i. that using the homogeneous ~2MB array (Lasse Hansen's initial approach) with constant shifts (64-12) versus the denser Pradu's 800K, with individual sizes for each square but slightly longer code was about the same speed inside his chess program Loop Amsterdam. Reul's thesis deserves a recommendation for each computer chess programmer and people interested in computer chess programming.
Gerd
Weird, you can prove mailbox 16x16 is faster than 15x12.
He did not compare it with that is it?
Vincent
He compared it with the GNU Chess approach and rotated bitboards (in 64-bit mode). His blocking loops don't need the & 0x88 condition, but I guess this is true for other mailbox approaches as well. Having 3+4 or 4+3 boarder files make square differences (+offset) unique relative to square distance and directions alá 0x88 with a denser board array. According to Fritz, Chrilly used the New Technology approach in Hydra as well.
His elaborate on magic hashing does not bear any new insights for me and has some weak spots, f.i. he mentions 12-bit indices, without explaining where the 12 bits come from (2 * inner six bits).
When do you make your PhD?
Actually his "comparison" was only for move generation with rotated bitboards. That means the make/unmake overhead is a biggie. He failed to include the other advantages of bitboards and only emphasized the weakest point. And then there are magic bitboards without the extra overhead of maintaining the rotated occipied-squares data.
The only interesting point I saw was the recursive see data that, done correctly, might eliminate a bit of overhead. Maybe.
Gerd Isenberg wrote:According to Fritz, Chrilly used the New Technology approach in Hydra as well.
The approach used in Hydra is documented in several papers and doesn't have anything to do with what you describe. (It's hardly original, and traces back to the Ken Thompson system in Belle).
I guess Fritz completely misunderstood those papers if he made such a claim.
Gerd Isenberg wrote:According to Fritz, Chrilly used the New Technology approach in Hydra as well.
The approach used in Hydra is documented in several papers and doesn't have anything to do with what you describe. (It's hardly original, and traces back to the Ken Thompson system in Belle).
I guess Fritz completely misunderstood those papers if he made such a claim.
Read the thesis! 2.1.1 The Chess Machine Hydra, Page 11.
Due to the simplicity and the ease of implementation, this computer-chess architecture could be implemented into the existing Hydra project [three papers referred] in a short time.... (since 2006)
According to a statement by Donninger, the efficiency increment ...
