A simple computer chess programming puzzle

[rjgibert]

Using the relative piece values N = B = 3 pawns and R = 5 pawns and Q= 9 pawns, how many material balances (without promotions) are even? Within a pawn? How many allowing each side to promote 1 pawn to a Queen?

I've computed these, but I may have easily made a mistake. I've also upped the value of the bishop and gotten a reduction in the counts.

Big hint: Some of you may find the version allowing each side to queen to be trickier than expected.

BTW, what do you get using your favorite set of relative piece values?

[Dann Corbit]

If we really want to count the value, we need to count the real value.
For instance, an A or H pawn is definiteily not worth as much as a B-G pawn. Edge pawns might really need another name.

In your counts did you allow up to 10 bishops, rooks, and knights and 9 queens?

The total number of material signatures is pretty large if you allow all possible promotions and if you count even the boring ones like:

KQQQQQQQQQRRBBNNk

[rjgibert]

If we really want to count the value, we need to count the real value.
For instance, an A or H pawn is definiteily not worth as much as a B-G pawn. Edge pawns might really need another name.

In your counts did you allow up to 10 bishops, rooks, and knights and 9 queens?

The total number of material signatures is pretty large if you allow all possible promotions and if you count even the boring ones like:

KQQQQQQQQQRRBBNNk

I only tried to incorporate the most common material balances. As for edge pawns, it is not unreasonable to include this distinction, but note that you have to draw the line somewhere e.g. passed pawns, isolated pawns and double pawns and anything else location dependent would quickly make the puzzle too difficult.

Perhaps it would help to understand my motive for the puzzle. It comes from an idea I have of incorporating all the most common material balances of practical value into a lookup table. Material balances where one side is significantly ahead in material or with unusual promotions aren't nearly as useful. That doesn't mean that they don't occur, but rather knowing how to value them precisely is not as important and do not need to be in the lookup table. An approximate valuation is fine in such instances. Including all the promotion possibilites is being way too anal. Besides, you would need to consider how many captures need to take place for x number of promotions to be possible. I did not want to get into that.

After calculating what I did calculate, I was a bit disappointed that the numbers I was coming up with were larger than I hoped for even when you you divide the result by 2 to remove the white/black symmetry. I think I will aim for a lookup table that only includes material balances that cannot be determined by a simple heuristic.

[Dann Corbit]

If we really want to count the value, we need to count the real value.
For instance, an A or H pawn is definiteily not worth as much as a B-G pawn. Edge pawns might really need another name.

In your counts did you allow up to 10 bishops, rooks, and knights and 9 queens?

The total number of material signatures is pretty large if you allow all possible promotions and if you count even the boring ones like:

KQQQQQQQQQRRBBNNk

I only tried to incorporate the most common material balances. As for edge pawns, it is not unreasonable to include this distinction, but note that you have to draw the line somewhere e.g. passed pawns, isolated pawns and double pawns and anything else location dependent would quickly make the puzzle too difficult.

Perhaps it would help to understand my motive for the puzzle. It comes from an idea I have of incorporating all the most common material balances of practical value into a lookup table.

This is (of course) the Strelka approach. It seems to perform very well.

Material balances where one side is significantly ahead in material or with unusual promotions aren't nearly as useful. That doesn't mean that they don't occur, but rather knowing how to value them precisely is not as important and do not need to be in the lookup table. An approximate valuation is fine in such instances. Including all the promotion possibilites is being way too anal. Besides, you would need to consider how many captures need to take place for x number of promotions to be possible. I did not want to get into that.

After calculating what I did calculate, I was a bit disappointed that the numbers I was coming up with were larger than I hoped for even when you you divide the result by 2 to remove the white/black symmetry. I think I will aim for a lookup table that only includes material balances that cannot be determined by a simple heuristic.

When you say that the numbers were too large, do you mean "the table was too big"?

[rjgibert]

If we really want to count the value, we need to count the real value.
For instance, an A or H pawn is definiteily not worth as much as a B-G pawn. Edge pawns might really need another name.

In your counts did you allow up to 10 bishops, rooks, and knights and 9 queens?

The total number of material signatures is pretty large if you allow all possible promotions and if you count even the boring ones like:

KQQQQQQQQQRRBBNNk

I only tried to incorporate the most common material balances. As for edge pawns, it is not unreasonable to include this distinction, but note that you have to draw the line somewhere e.g. passed pawns, isolated pawns and double pawns and anything else location dependent would quickly make the puzzle too difficult.

Perhaps it would help to understand my motive for the puzzle. It comes from an idea I have of incorporating all the most common material balances of practical value into a lookup table.

This is (of course) the Strelka approach. It seems to perform very well.

Material balances where one side is significantly ahead in material or with unusual promotions aren't nearly as useful. That doesn't mean that they don't occur, but rather knowing how to value them precisely is not as important and do not need to be in the lookup table. An approximate valuation is fine in such instances. Including all the promotion possibilites is being way too anal. Besides, you would need to consider how many captures need to take place for x number of promotions to be possible. I did not want to get into that.

After calculating what I did calculate, I was a bit disappointed that the numbers I was coming up with were larger than I hoped for even when you you divide the result by 2 to remove the white/black symmetry. I think I will aim for a lookup table that only includes material balances that cannot be determined by a simple heuristic.

When you say that the numbers were too large, do you mean "the table was too big"?

I could answer yes, but the ambiguity would remain. What's too big? I don't like large lookup tables and my standards in this regard are more stringent than most. More than 10,000 entries is way too much, though naturally, it all depends on how much computation you are saving yourselfand how many elo it adds to your program. I don't want to be more specific, since this might spoil the puzzle for someone.

BTW, I've also solved a version where I make a distinction between opposite color and same color bishops and of course this makes the result even more disappointing.

[Sven]

I get these numbers when excluding promotions and taking the original 1-3-5-9 values:

Code: Select all

total:              72900
even:                2550
within one pawn:     5070

No symmetry considerations, no thinking about duplicates. I did just dumb enumeration.

Changing 1-3-5-9 into 100-325-325-500-975 I get:

Code: Select all

total:              72900
even:                 698
within one pawn:     1312

What do you mean exactly by "allowing each side to promote"? Positions where both sides have at least one pawn? Or anything else?

Sven

[rjgibert]

I get these numbers when excluding promotions and taking the original 1-3-5-9 values:

Code: Select all

total:              72900
even:                2550
within one pawn:     5070

No symmetry considerations, no thinking about duplicates. I did just dumb enumeration.

Changing 1-3-5-9 into 100-325-325-500-975 I get:

Code: Select all

total:              72900
even:                 698
within one pawn:     1312

What do you mean exactly by "allowing each side to promote"? Positions where both sides have at least one pawn? Or anything else?

Sven

Each side is allowed to promote one pawn to a Q. So for example: White could have 7 pawns, 2 Knights, 2 Bishops, 2 Rooks, 1 King with Black having say 6 pawns, 2 Knights, 2 Bishops, 2 Rooks, 1 King. No under-promotions, No more than 1 promotion per side.

As for your totals for the no promotion version, my results are quite a bit higher. Note that (9*3*3*3*2)^2 = 236,196 > 72900. My program gets the 236,196 total, so you seem to have a bug with the 72900 total at least.

[rjgibert]

I get these numbers when excluding promotions and taking the original 1-3-5-9 values:

Code: Select all

total:              72900
even:                2550
within one pawn:     5070

No symmetry considerations, no thinking about duplicates. I did just dumb enumeration.

Changing 1-3-5-9 into 100-325-325-500-975 I get:

Code: Select all

total:              72900
even:                 698
within one pawn:     1312

What do you mean exactly by "allowing each side to promote"? Positions where both sides have at least one pawn? Or anything else?

Sven

Each side is allowed to promote one pawn to a Q. So for example: White could have 7 pawns, 2 Knights, 2 Bishops, 2 Rooks, 1 King with Black having say 6 pawns, 2 Knights, 2 Bishops, 2 Rooks, 1 King. No under-promotions, No more than 1 promotion per side.

As for your totals for the no promotion version, my results are quite a bit higher. Note that (9*3*3*3*2)^2 = 236,196 > 72900. My program gets the 236,196 total, so you seem to have a bug with the 72900 total at least.

LOL! I justed noticed my example was missing something crucial. I'll try again:

Each side is allowed to promote one pawn to a Q. So for example: White could have 7 pawns, 2 Knights, 2 Bishops, 2 Rooks, 2 Queens, 1 King with Black having say 6 pawns, 2 Knights, 2 Bishops, 2 Rooks, 2 Queens, 1 King. No under-promotions, No more than 1 promotion per side.

[Sven]

As for your totals for the no promotion version, my results are quite a bit higher. Note that (9*3*3*3*2)^2 = 236,196 > 72900. My program gets the 236,196 total, so you seem to have a bug with the 72900 total at least.

Not quite a bug but a different interpretation. Since it was unclear for me, I decided to handle bishop and knight as the same "material" as long as their material value is the same. Now I see you want to handle them separately. No problem, so I'll change my program and provide my new numbers as soon as this is done (short of time currently).

Sven

[Sven]

so I'll change my program and provide my new numbers as soon as this is done

New results, now differentiating knight and bishop (still without allowing promotions, that one will follow later):

Code: Select all

total:             236196
even:                2266
within one pawn:     4256

Here "within one pawn" does not include "even".

Sven