Score multiply

[mcostalba]

In a recent thread has been discussed the possibility to use an integer to keep both midgame and endgame scores, using the higher 16 bits for the midgame and the lower 16 bits for the endgame.

Now I stumbled acorss the problem of multiply 2 scores and create the score of the result.

IOW I want a multiply function that does the following:

Code: Select all

enum Score;

inline Score make_score&#40;int mg, int eg&#41; &#123; return Score&#40;&#40;mg << 16&#41; + eg&#41;; &#125;

Score s1 = make_score&#40;5, 6&#41;;
Score s2 = make_score&#40;3, 4&#41;;

Score s3 = multiply&#40;s1, s2&#41;;

assert&#40;s3 == make_score&#40;15, 24&#41;);

Of course I can do something like

Code: Select all

Score multiply(Score s1, Score s2)
{
  return make_score(mg_value(s1) * mg_value(s2), eg_value(s1) * eg_value(s2));
}

But I would like to avoid to decompose, multiply and then compose again.

So I was thinking of the mutiplication of two polinomials:

Code: Select all

(aK + b) * (cK + d) == acK^2 + bd + K(ad + bc)

Now if K is big enough (in our case is 2^16) so that the terms do not overlap I could achieve the result with something like:

Code: Select all

Score multiply(Score s1, Score s2)
{
  int64_t v64 = int64_t(s1) * int64_t(s2);

  short bd = short(v64);
  short ac = short(v64 >> 32);

  if &#40;ac < 0&#41; ac++;

  return make_score&#40;ac, bd&#41;;
&#125;

This seems to always work for positive terms and almost always for negative terms, but sometime it doesn't for instance with

Code: Select all

Score s1 = make_score(-3, 14);
Score s2 = make_score(248, 271);

I got 

s3 == (-743, 3794)

instead of the correct result

s3 == (-744, 3794)

Could someone tell me what I am doing wrong ?

Thanks in advance.

[Gerd Isenberg]

So I was thinking of the mutiplication of two polinomials:

Code: Select all

(aK + b) * (cK + d) == acK^2 + bd + K(ad + bc)

Now if K is big enough (in our case is 2^16) so that the terms do not overlap I could achieve the result with something like:

Code: Select all

Score multiply(Score s1, Score s2)
{
  int64_t v64 = int64_t(s1) * int64_t(s2);

  short bd = short(v64);
  short ac = short(v64 >> 32);

  if &#40;ac < 0&#41; ac++;

  return make_score&#40;ac, bd&#41;;
&#125;

This seems to always work for positive terms and almost always for negative terms, but sometime it doesn't for instance with

Code: Select all

Score s1 = make_score(-3, 14);
Score s2 = make_score(248, 271);

I got 

s3 == (-743, 3794)

instead of the correct result

s3 == (-744, 3794)

Could someone tell me what I am doing wrong ?

Thanks in advance.

This is tricky, guess you have to test the sign of the intermediate (ad + bc) bits 16..31, that is bit 31 of v64 to modify ac accordantly.

[mcostalba]

This is tricky, guess you have to test the sign of the intermediate (ad + bc) bits 16..31, that is bit 31 of v64 to modify ac accordantly.

It doesn't seems to work, btw the 64bit value with the above example is:

Code: Select all

v64 = 0xFFFFFD180A630ED2

[Gerd Isenberg]

for what is
if (ac < 0) ac++;
?
If you skip that the result looks correct.

[mcostalba]

for what is
if (ac < 0) ac++;
?
If you skip that the result looks correct.

Yes, in that case, but in others is not, for instance without that condition I got:

Code: Select all

Score s1 = make_score(-7, 7);
Score s2 = make_score(248, 271);

result s3 == make_score(-1737, 1897)

instead of make_score(-1736, 1897), in this case

v64 = 0xFFFFF937FF5F0769

That ugly condition is simply an ad-hoc rule that I have found by trials to be almost correct in most cases, more then if I don't use that.

I think there should exsist some correct test to now when to add 1 or not. All the wrong results are always wrong by 1, so the secret is to find _when_ to add that 1 to the first term. Also it is something related to sign because when the numbers are positive everything works.

[bob]

for what is
if (ac < 0) ac++;
?
If you skip that the result looks correct.

Yes, in that case, but in others is not, for instance without that condition I got:

Code: Select all

Score s1 = make_score(-7, 7);
Score s2 = make_score(248, 271);

result s3 == make_score(-1737, 1897)

instead of make_score(-1736, 1897), in this case

v64 = 0xFFFFF937FF5F0769

That ugly condition is simply an ad-hoc rule that I have found by trials to be almost correct in most cases, more then if I don't use that.

I think there should exsist some correct test to now when to add 1 or not. All the wrong results are always wrong by 1, so the secret is to find _when_ to add that 1 to the first term. Also it is something related to sign because when the numbers are positive everything works.

First idea, why not get rid of the negative scores completely? Negative numbers embedded like that are going to be an issue. If you make everything positive, then you don't worry about 2's complement stuff letting the lower order half wreck the high-order half.

Whether this is a good idea at all is a good question. Extra adds are not bad. You rarely keep multiple pipelines busy anyway...

[Gerd Isenberg]

That ugly condition is simply an ad-hoc rule that I have found by trials to be almost correct in most cases, more then if I don't use that.

I think there should exsist some correct test to now when to add 1 or not. All the wrong results are always wrong by 1, so the secret is to find _when_ to add that 1 to the first term. Also it is something related to sign because when the numbers are positive everything works.

if ( v64 & 0x80000000 ) ac++;
That indicates that something was borrowed (subtracted one) from the upper 32 bits and thus needs correction.

Or branchless

Code: Select all

Score multiply(Score s1, Score s2)
{
  int64_t v64 = int64_t(s1) * int64_t(s2);
  short bd = short(v64);
  short ac = short((v64 + 2*(v64 & 0x80000000)) >> 32);
  return make_score(ac, bd);
}

[mcostalba]

First idea, why not get rid of the negative scores completely?

The score actually is an accumulated score after a part of an evaluation so can assume any value: positive if that part of evaluation is good for us, negative if is bad or even zero.

Extra adds are not bad. You rarely keep multiple pipelines busy anyway...

Yes, this statement is _very_ right.

I have spent a good part of this week end to implement the unified score approach instead of two variables, one per midgame and one per endgame.

And after a very looooong day (it was very tricky indeed and with a lot of code changed) we have found with great disappointment that the speed is almost the same

So practically no advantage. We have chosen to keep the modifications because are also a good cleanup (70 lines of code less), but this is the _only_ reason of the unified score approach. We didn't find any other reason.

And btw this trick is very prone to overflow if you are not careful.

So my last word on this subject is: it really didn't derserve all the work that we put in during these two days

[mcostalba]

if ( v64 & 0x80000000 ) ac++;
That indicates that something was borrowed (subtracted one) from the upper 32 bits and thus needs correction.

Don't work with (70, 71) * (248, 271) = (17361, 19241)

instead of (17360, 19241)

in this case

v64 = 0x43D08EE24B29

[Gerd Isenberg]

if ( v64 & 0x80000000 ) ac++;
That indicates that something was borrowed (subtracted one) from the upper 32 bits and thus needs correction.

Don't work with (70, 71) * (248, 271) = (17361, 19241)

instead of (17360, 19241)

in this case

v64 = 0x43D08EE24B29

Sure, 70*248 + 71*271 == 36601 which is an short overflow. The value range is a bit restricted.