8 | |||||||||
7 | |||||||||
6 | |||||||||
5 | |||||||||
4 | |||||||||
3 | |||||||||
2 | |||||||||
1 | |||||||||
a | b | c | d | e | f | g | h |
8/7P/8/3P4/1p6/1k1K4/p7/8 w - - 0 1
Moderator: Ras
8 | |||||||||
7 | |||||||||
6 | |||||||||
5 | |||||||||
4 | |||||||||
3 | |||||||||
2 | |||||||||
1 | |||||||||
a | b | c | d | e | f | g | h |
hgm wrote: ↑Sun Apr 12, 2020 9:46 pm It occurred to me that pairs can be encoded such that the individual locations are easy to derive by calculation rather than tabe lookup. You can encode them such that the 6 lowest bits are the square number of the first piece, while the second can be calculated from the other 5 bits as
sqr1 = pairCode & 63;
sqr2 = pairCode >> 5 & 62; // an even number
sqr2 += sqr1 & 1;
sqr2 += (sqr2 >= sqr1);
Code: Select all
sqr1 = pairCode & 63;
sqr2 = pairCode >> 6;
sqr2 -= sqr1 + 1;
sqr2 &= 63;
Right. I was trying to optimise the conditional away. The root of all evil, as they say...hgm wrote: ↑Mon Apr 13, 2020 10:21 am What you propose doesn't seem to work at all. E.g. when sqr1 = 0, there is no way to get sqr2 = 40, as pairCode>>6 can only range from 0-31, so that after the modulo 64 sqr2 must be 0-30 or 63. And when sqr1 = 40, sqr2 can only be 23-54. So there is no way to encode (0, 40).
I'm unfamiliar with x86-64. If there is a single instruction that increments conditionally, that's already optimal, of course.
It is redundant. The problem with the 'at king' approach, however, is that it involves traversal of the entire piece list for every king move. If the captures are recorded separately and only the castling rights are encoded as 'at king', only the rooks are updated, and only during the first king move.I don't grasp the significance of your calculation of the number of material combinations. We don't need any extra bits to describe how many 'ordinary' Knights (say) there are; the fields containing the locations already tell us that, by whether they coincide with the King location.
It is almost as good as that. Comparison sets 'condition codes' in the CPU status register depending on the outcome (as in most architectures). In a following instruction these condition codes can be used to branch on, but there also is an instructtion that copies a specified condition into the lowest bit of one of a register, zeroing allother bits, such that a 0 or 1 results. Even on architectures that do not have that there usually are branch-free tricks. E.g. they might have an 'add with carry' instruction for the purpose of implementing integer arithmetic for longer data types, and a comparison (basically a subtraction) can set the carry or not depending on the relative magnitude of the compared quantities. And then adding 0+0 with carry would create 0 or 1 depending on the magnitude. And to test for equallity you can subtract two quantities, and then add an all-1 constant. This produces a carry whenever the difference was not exactly zero, and a subsequent 0+0 with carry then produces 1 in that case, to implement the != operator. Optimizing compilers should know these tricks.
We have that problem anyway. When two pieces of the same type are encoded as singles, exchanging their location alters the encoding, but not the position.Edit: I just realised that simply marking a piece as captured would create multiple encodings for equal positions. I propose encoding captured pieces as a1 (or h1 for the second in each pair) in addition to marking them as captured.
I forgot about ADC. Still, had my suggestion worked, the last three operations could have been performed on two pairs in parallel.hgm wrote: ↑Mon Apr 13, 2020 1:32 pm It is almost as good as that. Comparison sets 'condition codes' in the CPU status register depending on the outcome (as in most architectures). In a following instruction these condition codes can be used to branch on, but there also is an instructtion that copies a specified condition into the lowest bit of one of a register, zeroing allother bits, such that a 0 or 1 results. Even on architectures that do not have that there usually are branch-free tricks. E.g. they might have an 'add with carry' instruction for the purpose of implementing integer arithmetic for longer data types, and a comparison (basically a subtraction) can set the carry or not depending on the relative magnitude of the compared quantities. And then adding 0+0 with carry would create 0 or 1 depending on the magnitude. And to test for equallity you can subtract two quantities, and then add an all-1 constant. This produces a carry whenever the difference was not exactly zero, and a subsequent 0+0 with carry then produces 1 in that case, to implement the != operator. Optimizing compilers should know these tricks.
Code: Select all
sqr1 = pairCode & 63;
sqr2 = pairCode >> 5 & 62;
sqr2 -= (sqr1 & 30) - 1;
sqr2 &= 63;
Code: Select all
sqr1 = pairCode & 63;
sqr2 = pairCode >> 6;
sqr2 += sqr1 + 1;
sqr2 &= 63;