Evaluation using unsigned integers question

[maksimKorzh]

I think you are making that more complex than needed. Signed addition is not really different from unsigned. The bit patterns are always the same. It is just that overflow happens in other cases. So you can simply tabulate the move offsets as 2's-complement signed numbers, and interpret square numbers as unsigned. Then when you add the offset to the from-square number, you get the correct to-square number.

Wow! I didn't think about that! I thought 2's complement is too expensive to implement from the number of involved instructions perpective but if we can combine single 2's complement for a given offset with unsigned squares this should be more effective size wise as opposed to my initial idea. I will try this! Thank you for sharing the idea!

[BeyondCritics]

If you really want to get fluent with this stuff there is no way around some elementary number theory . It is also part of the standard education for sports programming, look e.g. https://cp-algorithms.com/index.html and countless other sites.

As already mentioned, the point is, that signed and unsigned arithmetic (add, sub, mul) is machine wise exactly the same for signed and unsigned numbers, making it as fast as it can get.
Lets make it more concrete. Define m := 256, m is even. N:= {0,...,m-1}, S:= {-m/2,...,m/2-1}.
The machine implements arithmetic modulo m with numbers from N in hardware and C/C++ forwards it:
a + b := (a + b) mod m, a - b := (a-b) mod m, a* b := (a*b) mod m.
Now define psi(s) = s + [n<0] * m for s in S. psi is one-to-one with psi^(-1)(n)= n - [n>= m/2] * m. Also psi(s) is kongruent to s mod n for all s.
Therefore psi is an isomorphism from the ring (S,+,*) to the ring (N,+,*), that means you can transfer calculations in S to N:
a + b = psi^(-1)(psi(a+b))) = psi^(-1)(psi(a)+psi(b)) for all a,b in S.
If you choose the machine representation rep(s) = psi(s) for s in S, you have therefore for a,b in S:
rep(a+b) = rep(a)+rep(b), that means you simply calculate with the representation.
On the downside you cannot compare negative numbers with positive ones and you can not divide with negative numbers. Convert the operands somehow to positive ones.

[hgm]

To specify it more explicitly for the case of 8-bit registers: the difference between unsigned and signed is that in the latter case the msb is interpreted as -128, instead of +128. So negative numbers get 256 added when interpreted as unsigned. But overflow clips off the 256 bit anyway. So it never matters whether the operands are interpreted as signed or unsigned, in arithmetic operations. This is why they invented 2's complement in the first place: you get it completely for free.

CPU architectures make use of that. The only tricky thing is when you compare numbers. Then it does matter which of the msb should be interpreted as -128, and which as +128. This is usually solved by having the compare instruction do two comparisons at once, one for when both operands would be signed, and one for both operands unsigned. (The only difference is in the treatment of the msb, so this takes only very little extra hardware.) The results of these comparisons are recorded in different 'condition code' bits (usually called C and V), tested by different branch instructions. So after a compare you do either BHS (branch if high or same) if the compared values were unsigned, and BGE (branch if greater or equal) when the values were signed.

[maksimKorzh]

If you really want to get fluent with this stuff there is no way around some elementary number theory . It is also part of the standard education for sports programming, look e.g. https://cp-algorithms.com/index.html and countless other sites.

As already mentioned, the point is, that signed and unsigned arithmetic (add, sub, mul) is machine wise exactly the same for signed and unsigned numbers, making it as fast as it can get.
Lets make it more concrete. Define m := 256, m is even. N:= {0,...,m-1}, S:= {-m/2,...,m/2-1}.
The machine implements arithmetic modulo m with numbers from N in hardware and C/C++ forwards it:
a + b := (a + b) mod m, a - b := (a-b) mod m, a* b := (a*b) mod m.
Now define psi(s) = s + [n<0] * m for s in S. psi is one-to-one with psi^(-1)(n)= n - [n>= m/2] * m. Also psi(s) is kongruent to s mod n for all s.
Therefore psi is an isomorphism from the ring (S,+,*) to the ring (N,+,*), that means you can transfer calculations in S to N:
a + b = psi^(-1)(psi(a+b))) = psi^(-1)(psi(a)+psi(b)) for all a,b in S.
If you choose the machine representation rep(s) = psi(s) for s in S, you have therefore for a,b in S:
rep(a+b) = rep(a)+rep(b), that means you simply calculate with the representation.
On the downside you cannot compare negative numbers with positive ones and you can not divide with negative numbers. Convert the operands somehow to positive ones.

Um...thank you, i just feel a bit overwhelmed)
I'm not trying to implement signed arithmetics using unsigned hardware - I just need to distinguish move offset directions and relate scores to the side to move. Hopefully there're already enough information on how to do that.
But anyway thanks for taking your time to explain
- your explanation is clear and concise.

[maksimKorzh]

To specify it more explicitly for the case of 8-bit registers: the difference between unsigned and signed is that in the latter case the msb is interpreted as -128, instead of +128. So negative numbers get 256 added when interpreted as unsigned. But overflow clips off the 256 bit anyway. So it never matters whether the operands are interpreted as signed or unsigned, in arithmetic operations. This is why they invented 2's complement in the first place: you get it completely for free.

CPU architectures make use of that. The only tricky thing is when you compare numbers. Then it does matter which of the msb should be interpreted as -128, and which as +128. This is usually solved by having the compare instruction do two comparisons at once, one for when both operands would be signed, and one for both operands unsigned. (The only difference is in the treatment of the msb, so this takes only very little extra hardware.) The results of these comparisons are recorded in different 'condition code' bits (usually called C and V), tested by different branch instructions. So after a compare you do either BHS (branch if high or same) if the compared values were unsigned, and BGE (branch if greater or equal) when the values were signed.

Mr.Muller thank you so much for clarifications! You've just explained to me how carry and overflow flags are working in 6502! I did understand zero and carry but not overflow flag but now I do. 41 instructions of my imaginary CPU are heavily inspired by 6502 processor but I used only zero flag for conditional jumps since it was the only thing I had the complete understanding of) Now the issue with chess program I ran into is simply how to distinguish between offset directions and assign the score ralative to the side. I think now I have enough understanding to implement that.

[hgm]

Please note that there is no such thing as 'unsigned hardware'. The same hardware does signed andunsigned arithmetic alike.

But you cannot implement minimax by only comparing for equality. You have to implement some method for deciding which of two scores is larger. For small score differences this is easy: you can subtract those, and test the sign bit with an AND instruction. (Which then becomes a test for equality.) The problem is that the subtraction of the scores can overflow. In which case the sign bit has the opposit value of what it should be. And the score range you have with 8 bits is so small that you probably will need the whole range. If scores would run up to half of what you can represent only, subtraction would never overflow.

[maksimKorzh]

Please note that there is no such thing as 'unsigned hardware'. The same hardware does signed andunsigned arithmetic alike.

But you cannot implement minimax by only comparing for equality. You have to implement some method for deciding which of two scores is larger. For small score differences this is easy: you can subtract those, and test the sign bit with an AND instruction. (Which then becomes a test for equality.) The problem is that the subtraction of the scores can overflow. In which case the sign bit has the opposit value of what it should be. And the score range you have with 8 bits is so small that you probably will need the whole range. If scores would run up to half of what you can represent only, subtraction would never overflow.

Oh, please excuse my dumbness))) Obviously there's no such thing as unsigned hardware - I just meant that 8-bit registers and 8-bit memory cells in
my emulated CPU/RAM are defined as uint8_t types.

And as for score comparison - I've been already thinking about that, but for now I hope to stay within +-127 bounds for both material and positional score.
Since I don't care about the strength and accuracy and only want my program to exchange pieces reasonably and from the PST perspective - just to give'em an idea of where to go hopefully that would be enough. Well at least when I've been designing the CPU arch that's what was in my mind) Let's see how it goes) Anyway I'm gonna be making progress videos on that project.

[Henk]

Even if you only have three bits you can inplement equal, better, much better. So three bits are enough. Why waste bits.

[Brunetti]

Even if you only have three bits you can inplement equal, better, much better. So three bits are enough. Why waste bits.

Actually only two are enough for three states. Why waste bits?

Alex

[Desperado]

Even if you only have three bits you can inplement equal, better, much better. So three bits are enough. Why waste bits.

Actually only two are enough for three states. Why waste bits?

Alex