Evaluation using unsigned integers question

[maksimKorzh]

Hi guys, recently I've developed an imaginary CPU emulator running on arduino
and now I'm writing a chess program in assembly of my own design to run on it.

My question is how to handle evaluation scores when I only have 8-bit unsigned memory/registers?
I mean the value can be in range from 0x00 to 0xFF and there doesn't seem to be an option to
mimic recursive negamax call, so should I just stick to minimax instead or maybe I can rely on most significant bit
to distinguish between positive and negative scores?

In short: how would you implement brute force search using only 8-bit unsigned integers?

THANKS IN ADVANCE!

[Deberger]

Hi guys, recently I've developed an imaginary CPU emulator running on arduino
and now I'm writing a chess program in assembly of my own design to run on it.

My question is how to handle evaluation scores when I only have 8-bit unsigned memory/registers?
I mean the value can be in range from 0x00 to 0xFF and there doesn't seem to be an option to
mimic recursive negamax call, so should I just stick to minimax instead or maybe I can rely on most significant bit
to distinguish between positive and negative scores?

In short: how would you implement brute force search using only 8-bit unsigned integers?

THANKS IN ADVANCE!

One can definitely implement signed 16-bit math, in software, using only signed 8-bit operations.

[Bo Persson]

Negative values are not limited to negamax. For example, if you have lost your queen, surely the score will be negative even for a minimax search.

[dangi12012]

Hi guys, recently I've developed an imaginary CPU emulator running on arduino
and now I'm writing a chess program in assembly of my own design to run on it.

My question is how to handle evaluation scores when I only have 8-bit unsigned memory/registers?
I mean the value can be in range from 0x00 to 0xFF and there doesn't seem to be an option to
mimic recursive negamax call, so should I just stick to minimax instead or maybe I can rely on most significant bit
to distinguish between positive and negative scores?

In short: how would you implement brute force search using only 8-bit unsigned integers?

THANKS IN ADVANCE!

Of course you can. There are even some very good C++ header files that can do that for you with operator overloading and implicit casting. You wont even know that its not float in normal ranges.
Also you can implement the > operator yourself. Just check if the first bit is set - then its a negative number and thus smaller than all positives. Then you mask / compare the other 7 bits.
Only having unsigned really doesnt stop you from writing as if its signed.

[Brunetti]

I mean the value can be in range from 0x00 to 0xFF and there doesn't seem to be an option to
mimic recursive negamax call

You could just consider your score shifted by 128, so 0x80 means "score 0". In negamax, and wherever, use X-0x80 to refer to the score, and 0x80-X to negate it.

Alex

[hgm]

Indeed, just offset the scores 128. I did something like that in my engine HaQiKi D, because I had packed the PST scores with an unsigned attackers count for the Palaces, to save work on the incremental update. But the problem was that the score has to be negated, and the counts not. I replaced that negation by an XOR with 0xffff (I used 16 bits for score in the low bits). This is nearly the same, if you imagine the score to be offsetted by an extra .5 unit. (So with 8 bits, use offset 127.5.) This makes an exact 0 unrepresentable, but who cares? Or you could imagine that the offset in wtm positions iss 127, but in btm positions 128. Of course alpha and beta will have to be 'negated' in the same way as the score.

[Karlo Bala]

Hi guys, recently I've developed an imaginary CPU emulator running on arduino
and now I'm writing a chess program in assembly of my own design to run on it.

My question is how to handle evaluation scores when I only have 8-bit unsigned memory/registers?
I mean the value can be in range from 0x00 to 0xFF and there doesn't seem to be an option to
mimic recursive negamax call, so should I just stick to minimax instead or maybe I can rely on most significant bit
to distinguish between positive and negative scores?

In short: how would you implement brute force search using only 8-bit unsigned integers?

THANKS IN ADVANCE!

Of course you can. There are even some very good C++ header files that can do that for you with operator overloading and implicit casting. You wont even know that its not float in normal ranges.
Also you can implement the > operator yourself. Just check if the first bit is set - then its a negative number and thus smaller than all positives. Then you mask / compare the other 7 bits.
Only having unsigned really doesnt stop you from writing as if its signed.

C++ headers and operator overloading can be very helpful in assembly language...

[maksimKorzh]

Thanks for your replies guys!
I'm currently thinking about just using sign bit with magnitude. Since I don't care about +0 and -0 just XORing sign bit on recursive call should be fine. And also I will use it to encode the move offsets. I'm also limited to 512 bytes for instructions hence 2's complement feels a bit of an overkill.

Thanks again for all the replies!

[maksimKorzh]

Indeed, just offset the scores 128. I did something like that in my engine HaQiKi D, because I had packed the PST scores with an unsigned attackers count for the Palaces, to save work on the incremental update. But the problem was that the score has to be negated, and the counts not. I replaced that negation by an XOR with 0xffff (I used 16 bits for score in the low bits). This is nearly the same, if you imagine the score to be offsetted by an extra .5 unit. (So with 8 bits, use offset 127.5.) This makes an exact 0 unrepresentable, but who cares? Or you could imagine that the offset in wtm positions iss 127, but in btm positions 128. Of course alpha and beta will have to be 'negated' in the same way as the score.

Thank you mr. Muller, I was thinking exactly this way, just wanted to confirm that this approach is ok. I will start by simply inspecting MSB to figure out whether I need to add or subtract move offset during move generation and for negamax call I'll stick to XORing the MSB. 127 should be fairly enough for score and since I won't use alpha beta +-infinity is out of question. Thanks for taking your time to explain the details.

[hgm]

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.