21 November 2010

Calculate SP Numbers in Your Head

When I started writing Who Says 'Chess960 Array'?, my original objective was to show a simple method for determining the number of a chess960 start position (SP) from the arrangement of its pieces, or vice versa,
e.g. to determine that the traditional start position RNBQKBNR is no.518 in chess960 numbering, or that no.534 represents RNBKQBNR (the traditional start position with King and Queen switched),

without using a printed table. Then, as so often happens, I got sidetracked with another issue, this time it was the problem of jargon. In this post, I'll get back on track with the numbering.

1) Start with the KRN sequence

The first thing to notice about chess960 numbering is that the start positions are grouped according to the sequence of Kings, Rooks, and Knights (KRN). For example, the first 96 positions (SP000 through SP095) all have those pieces in the sequence NNRKR, the next group of 96 positions have the sequence NRNKR, and so on. This implies that there are 10 different sequences of KRN, as shown in the following table.

0 NNRKR 000
1 NRNKR 096
2 NRKNR 192
3 NRKRN 288
4 RNNKR 384
5 RNKNR 480
6 RNKRN 576
7 RKNNR 672
8 RKNRN 768
9 RKRNN 864

Although I've given the complete table, I could have derived it with the help of a description. The table starts with the Knights in the first two positions, NNRKR. Each subsequent entry shifts the rightmost Knight one more step to the right. When the right Knight reaches the end, the left Knight shifts one step to the right and the right Knight joins it on its right side. Right? Right!

It's also worth noting that with the left Knight in the first position, the other Knight has four possible positions. With the left Knight in the second position, the other Knight has three positions, and so on -- four, three, two, one. It adds up to ten just like the pins in a bowling alley.

The numbers in that table are for convenience. The left column is a sequence number, while the right column is that sequence number multiplied by 96, the start position of that particular KRN group. [If you have trouble calculating 96 times 5 in your head, remember that 96 is equal to 100 minus 4, so 96 * 5 = (100 - 4) * 5 = 500 - 20 = 480.]

2) Account for the Q

The second thing to notice is that within each group of 96 positions the Queen shifts through the KRN sequence from left to right, one step at a time. This is shown in the following table, where 'xxxxx' stands for one particular KRN sequence.

0 Qxxxxx 00
1 xQxxxx 16
2 xxQxxx 32
3 xxxQxx 48
4 xxxxQx 64
5 xxxxxQ 80

Since there are six possible positions for the Queen and 96 positions in a KRN group, there are 16 different positions with a specific sequence of KRN&Q. Putting this together means that the first 16 of the 960 positions (SP000-SP015) all have the sequence QNNRKR, the second 16 have the sequence NQNRKR (SP016-SP031), and so on.

3) Finish with the Bs

Now the only pieces missing from the start position are the Bishops. Since one Bishop starts on a light square and the other on a dark square, there is no duplication and we have 4 x 4 = 16 unique positions of the Bishops. The sequence is shown on the following table.

00 BBxxxxxx
01 BxxBxxxx
02 BxxxxBxx
03 BxxxxxxB
[...]
15 xxxxxxBB

The Bishop table could also be derived from a verbal description. The Bishops start on a1 and b1 (or a8 and b8 for Black). Then the light-squared Bishop shifts to d1, f1, and h1. When the light-squared Bishop reaches h1, the dark squared Bishop shifts to the next dark square on the right, while the light-squared Bishop jumps back to b1, then d1, etc. Combining the Bishop table with the 16 different positions having a specific sequence of KRN&Q gives 16 unique chess960 positions, all pieces present and accounted for.

4) Put it all together

Taking the first chess960 position (SP000) as an example, it is represented by the pieces BBQNNRKR. Its KRN sequence is 'NNRKR', placing it in the first group of 96 positions (SP000-SP095); the Queen is in the sequence 'Qxxxxx', placing it in the first group of 16 positions (SP000-SP015); and the Bishops are in the formation 'BBxxxxxx', placing it first overall (SP000). A similar analysis shows why the position RKRNNQBB is numbered as the last of the 960 positions, SP959.

We can also see why the traditional start position (SP518 RNBQKBNR) and its twin (SP534 RNBKQBNR) are exactly 16 numbers apart. They both share the same KRN sequence, 'RNKNR', and have the same formation of Bishops, xxBxxBxx. Only the start position of the Queen is different -- RNQKNR (xxQxxx) vs. RNKQNR (xxxQxx) -- placing them in adjacent groups of 16 positions.

***

Here's a practical test. I've noted in the past that the Random Position Generator on Chessgames.com doesn't use the standard chess960 numbering system. It uses instead some proprietary scheme concocted by its software developer. I just accessed the page and it gave me 'position #334' as RQBBKRNN. What would the standard equivalents be?

First, let's take RQBBKRNN. Its KRN sequence is RKRNN, placing it in the last group of 96 positions, starting at SP864. Its Queen position is xQxxxx, placing it in the second group of 16 positions after SP864 (relative positions 16-31). Its Bishops are in the formation xxBBxxxx, making it the sixth position in the group of 16 (relative position 5). Adding these numbers together gives 864 + 16 + 5 = 885, which is indeed the SP number for RQBBKRNN.

Second, let's take 'position #334'? What does that represent in the standard numbering scheme? Dividing 334 by 96 and discarding the remainder gives 3, which places it in the group of 96 positions starting 288, i.e. NRKRN. Subtracting 288 from 334 gives 46; dividing this by 16 and discarding gives 2, which works out to xxQxxx. Subtracting 32 from 46 gives 14, which is the second to last of the Bishop formations, or xxxxxBBx. Combining NRKRN with xxQxxx gives NRQKRN; combining that with xxxxxBBx gives NRQKRBBN. A table lookup confirms that SP334 is indeed the number for position NRQKRBBN.

***

The title of this post is 'Calculate SP Numbers in Your Head'. Whether or not you can really do this depends on how agile you are with mental arithmetic. I find it helps to jot down the intermediate results -- 864, 16, and 5, as in the first example -- before combining them. The upshot is that if some day you are stranded on a desert island, you will be able to calculate chess960 SP numbers without having a reference table. As helpful as that might be, I suspect that you will have more important things to do on that island than play chess960.

4 comments:

Russell said...

Hello; here is a way to convert to and from Chess960 numbers mathematically, without lookup tables at all: The Chess960 Numbers Decoded.
—Russell

GeneM said...

The "numbering" systems for chess960 are really "naming" systems that use three-digit numbers as the names.

The names are for human convenience, not for computers. Computer do not need these name-numbers.

Therefore, any numbering / naming system that fails to make it obvious to humans when two start positions are mirrors of each other is a partial failure.

Mirror: #271 & #771 should be the same piece sequence on rank 1, just in the reverse sequence of each other.

The commonly used Scharnagl system has nice mathematics, but it fails the mirror test for human usability.

GeneM

P.S. If the "Please prove you're not a robot" challenges make the letters any weirder or harder to guess, I will give up.

Mark Weeks said...

I hadn't realized that word verification was active for comments. I turned it off for all of my blogs. Thanks for the heads-up. - Mark

HarryO said...

Russell really well done on the maths!!!
Cheers
Harry