bob wrote:Carey wrote:bob wrote:Carey wrote:bob wrote:
BTW, one error above. You have 52 bits, not 53. The 53rd bit _must_ be a 1 bit (the IEEE "hidden" bit).
Sorry Bob, but no. Obvious example is the number zero. It has no bits set. (Yes, I know it uses a special exponent code to indicate zero.)
Here we are going to have to disagree, because I teach IEEE floating point in my asm class.
Then you don't teach it very well, Sir.
I mean no disrespect, especially considering how much I respect your chess programming abilities and history. When I tell somebody that "Hyatt said..." I know you are right because I know you've tested it thourghly.
But if you
are going to brag about teaching float in your asm class, then I have to stand up and say that I don't think you do it well. That in this case, you are wrong.
Zero is a special case. when the exponent field is all zero, we now have an unnormalized number (perfectly legal) which eliminates that hidden 1 bit. But you can't use it. For 32 bit IEEE, you have 1 sign bit, 8 exponents, and 32 - 1 - 8 leaves 23 bits, not 24. Ditto for 64 bit IEEE which has 52 bits stored in the value, + the hidden 1 bit that is always present except for non-nomalized numbers.
But you show me any way to represent a 53 bit number with the high-order bit 0 or 1, and I'll kiss you.
The specs say that there *are* 52 bits of genuine data space physically available with the 53rd bit being implicitly and unchangably set as '1'. You are saying that as well.
So, for a 53 bit integer where the 53rd bit *is* set, then there's no problem. Because you have the high bit set and 52 bits of other data. The very thing the float specs explicitly allow with the 53rd bit being set but not physically present.
Not so fast. There _is_ a problem. Notably when I want to turn that 1 bit into a zero. That is no longer a "single bit operation". Which was my point.
No, it's not a single *bit* operation. It's a math operation.
FloatNum - 2^53.
Simple subtraction. The FPU will then perform the subtraction and renormalize.
"renormalize"? Shifts the entire fraction. I don't think you want to do that.
Doesn't matter what I *want*.
The reality is that's what the FPU does. So you live with it.
You work with abstractions instead.
If I have squares A1 A3 and D5 set, then the FPU is going to put them wherever it wants. I have no real control over that (without jumping through lots of hoops and kludges etc. and I don't want to do that.)
Sure, it'll normalize things and move the bits up or down in the FPU word. But, it keeps track of it. *It* knows where the bits are really located even if I don't.
So, if later want to clear A1, then I load from a var that has A1 set. That var will also be normaled. (In fact, since it's a single bit, it'll actually be in that hidden 53rd bit.)
BUT, when I do Board-Sqr the FPU will automatically align things so that when it removes the A1 square from the board, it'll effect the right square.
That's just basic floating point math.
As long as you don't try to peek at the float's bits, it just doesn't matter because the math works.
Since I'd be treating the numbers as floating point numbers, I don't care if the FPU normalizes them. It doesn't matter that bit 1 is really in bit position one. I let the FPU worry about aligning the bits properly to its math.
The numbers are no longer 64 bit sets but instead floating point numbers. It's a mental shift.
OK, that has a possibility. But it makes absolutely no sense to me, as to use bitboards, one has to visualize what the bits represent. For example, "is the E-file open?" The bits can't move around all over, or you can never visualize how to set up the masks to ask that kind of question.
That would require doing a AND operation. Which, as I've said before, is definetly a problem in floating point. AND & OR seem to be the only two operations that will be difficult to simulate or work around.
The only three things I can think of are:
1) to actually go ahead and un-normalize the numbers and use the data as indices into a truth table. Unormalizing it is fairly simple. You add a huge value to it so the FPU's auto-normalization will force the bits down into the proper spot. This is trivial stuff. A few implimentation issues, such as it would be more convenient to not put 53 bits into a double. Probably better to put 32 into both 'double's just to make things the same.
But that's implementation issues & personal choices. The point is, doing that kind of forced un-normalization has been around a long long time and is quite solid.
2) Do the software un-normalization like in #1 but skip the truth tables and cheat and just use integer AND & OR operations. Accept that it's too darn difficult to do AND & OR as floating point ops. I really don't like this option because I want to pretend we're on a cpu that either doesn't have integers or at least they are slow & difficult to use.
3) Still hoping that there might be some sort of MAGIC multiplication that could prepare the numbers for binary operations.
Converting 1 to the bit pair 01 and then add your other number. If the result is 10 then AND was true and your result is 1, else it's 0.
Trying to do that in large scale though.... I really don't know, but then I'm still amazed at all the MAGIC multiplications being done for bitboard attacks.
But anyway, I've said from the beginning that doing the AND & OR operations seem to be the big problems. It can be worked around, but not in a nice floating point way.
The concept of bitboards is that a specific bit represents a specific square. Going one level up as you are describing appears to me to be an impossible task, mentally...
It's not really. In fact, I bet you've been doing it for years.
Think of C's regular Long Long and doing operations on it.
If you do LL |= 1 or LL <<= 8 do you *really* know how the bits are arranged?
C guarantees the operations will work the same regardless of how it chooses to arange things in the CPU.
You could be working on a 64 bit big endian system. Or a 64 bit little endian system. Or a 32 bit little endian system simulating 64 bit integers. Or a 32 bit big endian system simulating 64 bit integers. Or even an old 8 bit micro that is simulating 64 bit integers.
C even allows the bits to be out of order in the CPU registers!! As long as its consistant and does the operations correctly, C doesn't care.
You don't truely know where the bits are. All you really know is how the C language represents it in the source code you write and you just trust that the compiler knows how the cpu will do things and that it'll be consistant.
Same thing when doing it with floating point. (Except for AND & OR, of course.) As long as you don't look at where the FPU wants to put the bits, the math is going to work.
If I say A1= 2^0 and B1=2^1 and so on, then I can keep using those values without caring how the FPU arranges the data.
In the bitboard programs I've done, I rarely need to set specific bits. It's not a case of setting Bit 53, for example. It's usually a matter of clearing a bit and setting a bit like while making a move.
I have to set specific bits every time I make or unmake a move. And then for the special case moves it is even more involved (castling, en passant, pawn promotions.
Setting a bit is addition. Clearing a bit is subtration. That's true whether you are working in LongLong or floating point. In my programs, I never try to set a bit that is already set or clear a bit that is already clear. I already know based on program flow. So addition & subtration work fine. In fact, in one of my early bitboard programs I did it all as add & sub of LongLong.
And then there are the masks set up to ask specific questions like "is the pawn on e4 passed?" or "is the e-file open?" or "is the pawn on f3 backward?"
And yet again, as I have said repeatedly.... Those are AND & OR operations and those are the very ones that I'm having trouble with.
They can be done, but not as pure float math. Which is what I'd like.
As for XOR, that's just a luxury. A convenience. I've never truely needed it.
The only place it's a problem is in the Zobrist hashing. But there are other methods that would work. Addition & subtration of large numbers would also generate a unique signature. You just have to allow enough extra room that they don't overflow and cause data loss.
In that case, I already know whether the bits are set or clear. So I can safely add and subtract. I don't have to do OR to set it or NAND to clear it. I can't be clever and XOR it flip it, but that's just a convenience.
What about captures? Bit is already set, you want to set it again as you move the piece to make the capture...
In my early programs, just to make sure I was doing things right, I always removed the capture first.
if (Capture) Board -= Capture.
Board -= From
Board += To;
It is not as convenient as being able to do Board |= To but it works.
Even later on, with only a few convenience factors like above, I was never in a position where I tried to clear a bit that was already clear or set one that was already set.
I knew from the program flow what things were.
Even when I do need to set a specific bit, I don't actually care that it's stored at certain location. What I do care is that when I do an operation, things will align themselves so the correct bit is effected. The FPU does guarantee that.
Again, that sounds like no chess program/engine I know of. Chess knowledge is pattern-based. The patterns are expressed as specific sets of 1 bits or 0 bits, depending on how it will be used. I very much care what is what.
You can think of them as being in specific locations, if it'll make you happy.
The FPU math will take care of aligning the decimal point to make sure the right bits are done.
And as I pointed out, even in C with LongLong you don't really know where the bits are truely located. You just trust the compiler and cpu to be consistant and do the right things.
It may normalize things for its own convenience but it doesn't matter as long as its consistant and knows how to align things when I do math on them. Which it does.
I don't have to treat them as binary operations but can do it as arithmetic operations and let the FPU normalize the numbers however it wants.
The other operations, such as shifting, can also be done without too much effort. It's just multiplication by 2 and will require a bit of software renormalization. (By 'without too much effort' I mean its possible to do wholely within floating point. I don't have to do it as integers or precomputed tables, etc.)
Now you go to far. Previously you said you don't care where the bits are, but now you are talking about shifting 1 bit. So either you _do_ care where the bits are and what they represent, or else you would _never_ want to shift 1 bit since you don't know what it represents...
No Bob, you are still very confused.
I do know what it represents. Square A1, B1, C1 etc. I know that the numeric value representing A1 is less than B1 (because I choose for it to be.)
I just don't know (or care) where the FPU puts it. That's two different things.
I care that the FPU holds them and is consistant. I don't care *how* the fpu holds them. I don't care whether they are normalized or not. I don't care whether I'm really using an 80 bit Long Double. I don't care whether I am using a software based 'double-double'. I don't even care if the FPU is working in binary or decimal (with the exception of AND & OR which would be rather difficult to do in decimal).
All I care is that the FPU can hold my data without data loss and lets me do the basic mathematical operations. (Plus AND & OR, of course....)
If I need to shift a row of the BITBOARD, then that would involve multiplying by 256 or dividing by 256.
I don't care how the FPU holds the data as long as it understands basic math.
I DO care about the BITBOARD, but unlike you I'm not thinking of the bitboard as a 64 bit SET. I'm thinking of it as 64 binary numbers. 2^0, 2^1, 2^2, 2^3... 2^63.
There are still chess concepts of rows and columns and shifting, but those aren't applied to a bit set. They are applied to a numeric value. And the FPU is free to mangle that value all it wants (ie: normalize it) as long as it doesn't actually change the value of that number it is holding (like it would if we overflowed and we lost some bits.)
This sounds like a bad dream at best, approaching a nightmare.
The only problems I see are AND, OR, PopCount and NextSetBit.
The first two could be done via truth table. The third by a look up table. The fourth could be done several ways including tables or maybe even using frexp().
Some operations will need software 'normalization'. Such as trying to shift bits from one double to another. But that's entirely do-able. The 'double-double' math packages already handle things just like. And do so reliably. (From a math point of view, those 'double-double' packages look just like a real 128 bit floating point number with a 106 bit mantissa.)
For the case where you have 53 bits of data where the 53rd bit is *NOT* set then you don't actually have 53 bits of data. You have 52 bits. Or 51 or 50 or where ever the highest bit is set. In which case the 52 bits that are physically there are enough to hold it without issue. The FPU will normalize things so the highest bit is set and adjust its exponent accordingly.
For the case where there are no bits at all set, the FPU has a special flag to idicate that.
So you've covered all the bases. Bit 53 set and 52 bits of other data. Bit 53 not set and up to 52 bits of other data. No bits set.
A total of 53 bits of user data.
You are completely missing my point. My point was, and is, that you do not have any specific operation that can change that upper bit from 0 to 1 or 1 to zero, when dealing with a single bit. For example, I have all "53 bits" set to zero. By using the IEEE fp 0.0 representation. Now I want to turn that leftmost bit to a 1. I have to mangle the exponent to do this, there is no arithmetic operation that will accomplish that. I can turn any of the other 52 bits on or off whenever I want. Simple subtraction or addition will work. But that 53rd bit won't work the same way, which is a problem IMHO, and this is _the_ problem I have been trying (without success) to explain. Using that single extra bit is going to make this much more complicated to do, when there is no benefit to the idea in the first place.
Bob, you are still thinking of the double's as if they were bit sets. Where a specific bit *HAS* to be in a specific location. Where Bit 53 really is bit 53 and bit 17 really is at bit 17.
And for some reason you are really hung up about the exponent ....
When you treat them as math, you no longer have to worry about that. It doesn't matter if the FPU normalizes things so bit 17 is really that hidden 53rd bit.
There is no 'leftmost' or 'rightmost' bit. You just have a floating point number that just happens to be able to hold 53 bits of data. How it organizes it is irrelevant.
If you have all zeros and you want to set that 53rd bit, then set it. Just add 2^53 to it.
If you have all zeros and you want to set bit 1, then just add 1. And guess what, the FPU will normalize that and put it into that hidden 53rd bit. That's OKAY.
So WHAT if the fpu messes with the exponent to normalize things. That's what it does. Let it. It's not part of your 53 bits of data so let it normalize its little heart out.
With only a few exceptions we don't have to care how the bits are stored in the double. The few times we would care, we can take steps to force alignment so that bit 1 of data really is at bit 1 location. But we don't have to keep them that way when doing math because the FPU will adjust things to keep itself happy.
We are trying to do this as
MATH not bit / set operations. (Which is why AND & OR are so difficult....)
And, as I've said several times, we don't have to use 53 bits. If you are uncomfortable with it, then don't.... In fact, for convenience it would actually be better to just do 32 bits into each double. Some things will have to change but are do-able. And some things would actually be more convenient.
And if we went all the way and actually used some pre-existing "double-double" math package (like David Baiely's) then our mantissa will actually be 106 bits. We wouldn't have to worry about hidden bits or how they behave. The whole 64 bit bitboard would fit into the mantissa with room to spare.
You can get it to be zero with a zero exponent. You can get it to be 1 with a normal exponent. But you can't do boolean operations on that bit. It would require fiddling with the exponent instead since that 53rd bit does not exist in the actual number in IEEE format.
Doing boolean operations would require some fiddling with the numbers.
It's possible some sort of MAGIC multiplication would work, but I'm not sure. I suspect it would, but I don't know the values or how many bits you could do at a time.
The best I've been able to come up that I know would work is that since we would have to use two doubles to hold 64 bits of real data, we'd keep 32 bits in each one. (Just to make things consistant with both doubles.)
We'd then add a huge value to shift our 32 bits down to the lower word.
We then use the lowest 8 bits as an index into an array of truth tables. Repeat with the other bytes of data. We are using an integer to grab the lowest 8 bits and use it as an index, but we aren't really doing math as integers.
I'm not real fond of using truth tables but that's the best I've come up with.
(The addition of huge values to shift our data to a lower part of the word was a classic x87 hack for conversion to integer, truncating, etc. The x87 was so slow doing those operations it was actually faster to do them by hand with some clever math. Not common today, but the ideas are well tested and would still work.)
You can safely have any arbitrary 53 bit integer stored into a double without any risk of corruption. The FPU will represent it however it needs to.
See above. one of those 53 bits does not physically exist. Which means to manipulate the rightmost 52 bits, you twiddle with those. To manipulate that non-existent bit, you have to twiddle with the entire left end (exponent field) of the number rather than a single bit.
1) We don't have to actually store a full 53 bits into each double. We could store just 32, that way we have some extra space to mess with if we want.
2) If we did do some floating point operation that involved the hidden 53rd bit, then the FPU would take care of that automatically. It's designed to do that.
No, it's not designed to do boolean operations, but with the right kind of math we might be able to trick it. If not, then there's always the 'cheating' method of using truth tables like I mentioned above.
Yes, there are only 52 bits available, but the FPU does what it needs to hold the full 53 bits of integer data.
It normalizes things and has a special code for zero, etc. If the 53'rd bit is '1' then things are fine. If it's a zero then the FPU normalizes it and the exponent is adjusted. It all works out that you can safely hold 53 bits of integer data.
*HOWEVER*, just to make you happy, I'll say that you can only old 40 bits of mantissa in a double. Doesn't matter because I'm talking about using software based 'double-double' math that doubles the number of mantissa bits anyway.
So in this case instead of 53*2=106 it'd be 40*2=80 which is still more than enough for what I'm talking about.
Makes no difference because I'm curious about the bit operations as floating points.
Those do not naturally exist in any processor I know of (IEEE math processor). One can do any arbitrary boolean function as a mathematical operation. "not" means subtract from all 1's, AND means to multiply bit by bit. Etc. Not going to be fast at all when compared to using two normal 32 bit integer values which do have AND/OR/XOR operations that operate on all bits at once...
No, they don't exist. I thought I was pretty clear about that in my first post. And was one of the reasons I was asking if anybody had thought about this kind of useless stuff.
And no, it's not going to be fast. But who cares? As I've said several times this wasn't a practical method. It was just something I got curious about.
Just a "Can it be done?" kind of thing.
Anything "can be done". Whether it "should be done" is another matter, of course.
That's probably the same attitude many people had in the 60's about using expensive, serious business computers for something as frivolous as chess....
Not the same thing. I can represent chess positions by sets of 64 bit integer values, and manipulate them directly using hardware, including finding the first or last one bit or popcnt.
Bob, there really isn't that much effort in what I'm talking about.
It wouldn't be high performance. But most of what I'm talking about will work equivelent to how 64 bit integers work.
Just differently.
The big exception, of course, still seems to be AND & OR. They can be done but not convenient.
And so what if you can use a 64 bit integer in a 64 bit cpu? It's not even slightly relevant.
Why on earth would anyone _want_ to do something that is going to be so much more complex was my point.
For a teacher, that's a pretty surprising attitude!
For a chess programmer it's a pretty surprising attitude.
Look at the classic Slate & Aktin bitboards. it was a mess to do, espeically on the hardware they had. And look how little they actually used all that data they generated.
But yet they did it anyway and discovered there were benefits and now most high performance programs depend on the concepts they pioneered.
Look at Magic Multiplication for the attacks. In the beginning I think a lot of people didn't expect it to really work, much less end up being so efficient. It was just a toy.
(I didn't take it seriously. I thought it was a toy. I accept that it works, but I'm still not comfortable with using 'random' numbers to do necessary stuff. But I do admit that it works and is fast.)
But yet just a couple years later it's turned into a very fast way to do attacks and move generation and has become the standard way to do things.
Will my ideas join those two greats. Of course not. But that doesn't mean I can't be curious about something.
As I said.... that was a very odd attitude for a teacher.
We already have a requirement to do 64 bit multiplies for the magic move generation stuff.
Really? Gee... all these years people have been managing to do bitboard move gen stuff without 64 bit magic muls....
Who says you *have* to do 64 bit magic multiplication?
You could do 32 bit magic multiplication methods.
Or no magic multiplication and depend on FirstBit() / LastBit() and some precomputed rays etc.
Or some other method.
There are lots of ways that don't require 64 bit magic muls. (Especially since magic muls tend to require AND operations)
But I had already thought of that. Instead of using two doubles to have enough space to hold 64 bits, it might be better to work with three floats instead, and put 22 bits into each.
That way we can do multiplications in a 'double' and hold the whole result.
So instead of doing two 32 bit Magic Muls for attacks (like on 32 bit cpus), we've changed things and are now doing three 22 bit Magic Muls for attacks.
But the point is, you don't *HAVE* to use 64 bit magic multiplication. There are alternatives.
That doesn't have a prayer on this kind of approach. So we start to give up things that are quite common.
They weren't "quite common" two years ago....
Amazing how quickly you can latch onto one idea while discarding the old and rejecting yet others just because they are different.
I never said this would be *practical*. In fact, I've actually explicitly said several times that is would NOT be practical.
Remember, this all started out as simply the question "Is this possible?"
It seems to be a firm yes, with the caveat that AND & OR are likely to be slow & inconvenient or cheating and using integers in those two spots. (At least unless somebody comes up with a better idea.)
If we were working with a FPU that actually had AND & OR, and were willing to loose some portability, I guess that would be toleable.
Like the SEE stuff Gerd pointed.
I'd rather not do SEE stuff though. I would rather depend on normal stuff in C.
Frankly, I doubt many people in this forum would find it too odd that somebody got curious about something and wondered if it could be done. They may not care about this particular thing, but I doubt they'd find it odd.
