Statistics on Chess Games

My diurnal age today, 27004, turns up in an online table of statistics for chess games. Figure 1 shows the table.

Figure 1: source

A ply is a half-move in chess so what the table is saying is that after five plies there are 27004 different ways in which a king can be placed in check. Figure 2 shows such a situation for white checking the black king.

Figure 2: generated by ChessX

The white queen can move to F7 via F3 or H5. Note that we are not interested in the quality of the chess moves here but merely how a check (but not checkmate) can be achieved on the fifth ply. Figure 3 shows a situation where white achieves checkmate (using a variation of fool's mate) on the fifth ply. Looking at the table in Figure 1, it can be seen that mate by White can be achieved in 347 different ways.

Figure 3: generated by ChessX

Since White moves first, the fifth ply must always be made by White. Likewise, mate on the fourth ply can only be achieved by black and in eight ways, each a variation of fool's mate. Figure 4 shows one such configuration.

Figure 4: generated by ChessX

The number 27004 is a member of OEIS A089956:

A089956

Number of chess games that end in check (but not checkmate) after exactly \(n\) plies.

The initial members of the sequence are:

• 0 ways after 0 plies
• 0 ways after 1 ply
• 0 ways after 2 plies
• 12 ways after 3 plies
• 461 ways after 4 plies
• 27004 ways after 5 plies
• 798271 ways after 6 plies

The website displaying these statistics also alerted me to some rules of Chess that I wasn't aware of, namely the automatic draws by 5-fold repetition and the 75-move rule. 

I am ignoring the draw by 3-fold repetition because it is a pain to take into account. Actually, a draw by 3-fold repetition isn't automatic: one of the players must make a correct claim for the draw to occur. So if it's legal to ignore the repetition of position, then I believe that it's ok to enumerate those games. Draw by 5-fold repetition (a rule introduced in 2014) is automatic and should affect the number of games. Initially, the rule was not very clear, with one interpretation suggesting that the earliest it can apply is at ply 22. In 2017, the rule was modified, and it is now clear that the earliest draw by 5-fold repetition occurs at ply 16, reducing the number of games at ply 17 by 16^4*20 = 1310720. Draw by the 50-move rule (not automatic), draw by the 75-move rule (automatic), and draw by impossibility of checkmate (automatic) don't apply before even more moves. For the complete rules of chess (including past versions since 2009), look for Laws of Chess in the FIDE Handbook, section E.01.

The Trapped Knight

THE TRAPPED KNIGHT: PART ONE (A REVIEW)

I've already written about a trapped knight in a post from May 23rd 2020 titled Knight Tours in which the Knight gets trapped on an infinite chess board if it follows these rules:

Suppose we devise a Knight Tour such that the Knight starts on square 0 and then moves always to the unvisited square closest to the origin. "Closest to the origin" is meant in the sense of Euclidean distance, and in case of a tie, the square coming earliest on the spiral is chosen.

On the first move, the Knight could move to squares 9, 11, 13, 15, 17, 19, 21 or 23. All these squares are the same distance from the 0 square but 9 is chosen because it comes first in the spiral. From 9, subsequent squares are 2, 5, 8, 3, 6, 1, 4, 7, 10, 13 and so on. 

 Figure 1 depicts the situation:

Figure 1

As I wrote in my post at the time:

The initial terms are of the sequence are:

0, 9, 2, 5, 8, 3, 6, 1, 4, 7, 10, 13, 28, 31, 14, 11, 26, 23, 44, 19, 22, 43, 40, 17, 34, 37, 18, 15, 32, 29, 52, 25, 46, 21, 76, 47, 50, 27, 12, 33, 16, 39, 20, 45, 24, 51, 48, 77, 114, 73, 70, 105, 38, 35, 60, 93, 30, 53, 84, 49, 78, 115, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 124, 81, ...

What's really interesting about this tour is that the knight gets trapped at the 22325th move, where it can't reach any unvisited square. The square on which the Knight is stuck is 25983. 

Of course, if the numbering began from one instead of zero, then the square on which the knight becomes stuck would be 25984. 

THE TRAPPED KNIGHT: PART TWO

Yesterday I turned 26943 days old and this number is also associated with a trapped knight that gets trapped following a different set of rules. To begin with, the infinite chessboard is numbered slightly differently. See Figure 2.

Figure 2: screenshot from Numberphile video

As can be seen, the numbering starts from one, not zero. The rule for the knight's movements is that it must move to the lowest available square and not the square that is closest to the origin. The numbers of the squares that the knight moves to are listed in OEIS A316667: 

A316667

Squares visited by a knight moving on a spirally numbered board always to the lowest available unvisited square.

The initial terms are:

1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 29, 32, 15, 12, 27, 24, 45, 20, 23, 44, 41, 18, 35, 38, 19, 16, 33, 30, 53, 26, 47, 22, 43, 70, 21, 40, 17, 34, 13, 28, 25, 46, 75, 42, 69, 104, 37, 62, 95, 58, 55, 86, 51, 48, 77, 114, 73, 108, 151, 68, 103, 64, 67, 36

As the OEIS comments state: 

This sequence is finite: At step 2016, square 2084 is visited, after which there are no unvisited squares within one knight move.

The number of steps required to become trapped, 2016,  is far less than the number required in the PART 1 example where 22325 steps were required. Figure 3 shows the path of the knight as it starts at 1 and ends up at 2084. The path was generated by Python code that I found on this site. I pasted the code into SageMathCell and it worked just fine. Here is the permalink. This graphic always appears in the Numberphile video.

Figure 3

If 2084 is the end of the knight's tour and  26943 is never visited, then how can this number  be involved? The answer is that we can continue the tour if we repeatedly block the squares where the knight would not have any available moves. Thus when we get to 2467, the square before 2084, we block the latter and move instead to the next lowest number and the tour continues. See Figure 4:

Figure 4: screenshot from Numberphile video

Eventually the knight gets trapped again once it moves to square 2720. Again we block that square and allow the knight to move to the next lowest square. These blocked squares constitute OEIS A323714:

A323714

Squares where knight moving to a lowest unvisited square on a spirally numbered board will have no available moves.

The initial members of the sequence are:

2084, 2720, 3325, 3753, 7776, 5632, 7411, 8562, 14076, 8469, 9231, 22702, 14661, 21710, 21078, 25809, 27112, 24708, 19844, 26943, 26737, 32449, 31366, 45036, 37853, 37188, 43318, 62095, 67401, 68736

It's more useful to put these terms in ascending order, in which case the sequence appears as:

2084, 2720, 3325, 3753, 5632, 7411, 7776, 8469, 8562, 9231, 14076, 14661, 19844, 21078, 21710, 22702, 24708, 25809, 26737, 26943, 27112, 31366, 32449, 37188, 37853, 43318, 45036, 62095, 67401, 68736

Now we can see that the next number in the sequence is 27112 and this occurs on June 26th 2023. After this, there is a considerable gap before 31366 is reached.

Non-attacking Queens

 I came across this interesting tweet today. Figure 1 shows a snapshot of it.

Figure 1

Here is the Python code that was used:

from itertools import permutations

col = range(8)

for vec in permutations(col):

    if (8 == len(set(vec[i]+i for i in col) == len(set(vec[i]-i for i in col))):

        print(vec)

The algorithm works perfectly well. Here is the output:

(0, 4, 7, 5, 2, 6, 1, 3)

(0, 5, 7, 2, 6, 3, 1, 4)

(0, 6, 3, 5, 7, 1, 4, 2)

(0, 6, 4, 7, 1, 3, 5, 2)

(1, 3, 5, 7, 2, 0, 6, 4)

(1, 4, 6, 0, 2, 7, 5, 3)

(1, 4, 6, 3, 0, 7, 5, 2)

(1, 5, 0, 6, 3, 7, 2, 4)

(1, 5, 7, 2, 0, 3, 6, 4)

(1, 6, 2, 5, 7, 4, 0, 3)

(1, 6, 4, 7, 0, 3, 5, 2)

(1, 7, 5, 0, 2, 4, 6, 3)

(2, 0, 6, 4, 7, 1, 3, 5)

(2, 4, 1, 7, 0, 6, 3, 5)

(2, 4, 1, 7, 5, 3, 6, 0)

(2, 4, 6, 0, 3, 1, 7, 5)

(2, 4, 7, 3, 0, 6, 1, 5)

(2, 5, 1, 4, 7, 0, 6, 3)

(2, 5, 1, 6, 0, 3, 7, 4)

(2, 5, 1, 6, 4, 0, 7, 3)

(2, 5, 3, 0, 7, 4, 6, 1)

(2, 5, 3, 1, 7, 4, 6, 0)

(2, 5, 7, 0, 3, 6, 4, 1)

(2, 5, 7, 0, 4, 6, 1, 3)

(2, 5, 7, 1, 3, 0, 6, 4)

(2, 6, 1, 7, 4, 0, 3, 5)

(2, 6, 1, 7, 5, 3, 0, 4)

(2, 7, 3, 6, 0, 5, 1, 4)

(3, 0, 4, 7, 1, 6, 2, 5)

(3, 0, 4, 7, 5, 2, 6, 1)

(3, 1, 4, 7, 5, 0, 2, 6)

(3, 1, 6, 2, 5, 7, 0, 4)

(3, 1, 6, 2, 5, 7, 4, 0)

(3, 1, 6, 4, 0, 7, 5, 2)

(3, 1, 7, 4, 6, 0, 2, 5)

(3, 1, 7, 5, 0, 2, 4, 6)

(3, 5, 0, 4, 1, 7, 2, 6)

(3, 5, 7, 1, 6, 0, 2, 4)

(3, 5, 7, 2, 0, 6, 4, 1)

(3, 6, 0, 7, 4, 1, 5, 2)

(3, 6, 2, 7, 1, 4, 0, 5)

(3, 6, 4, 1, 5, 0, 2, 7)

(3, 6, 4, 2, 0, 5, 7, 1)

(3, 7, 0, 2, 5, 1, 6, 4)

(3, 7, 0, 4, 6, 1, 5, 2)

(3, 7, 4, 2, 0, 6, 1, 5)

(4, 0, 3, 5, 7, 1, 6, 2)

(4, 0, 7, 3, 1, 6, 2, 5)

(4, 0, 7, 5, 2, 6, 1, 3)

(4, 1, 3, 5, 7, 2, 0, 6)

(4, 1, 3, 6, 2, 7, 5, 0)

(4, 1, 5, 0, 6, 3, 7, 2)

(4, 1, 7, 0, 3, 6, 2, 5)

(4, 2, 0, 5, 7, 1, 3, 6)

(4, 2, 0, 6, 1, 7, 5, 3)

(4, 2, 7, 3, 6, 0, 5, 1)

(4, 6, 0, 2, 7, 5, 3, 1)

(4, 6, 0, 3, 1, 7, 5, 2)

(4, 6, 1, 3, 7, 0, 2, 5)

(4, 6, 1, 5, 2, 0, 3, 7)

(4, 6, 1, 5, 2, 0, 7, 3)

(4, 6, 3, 0, 2, 7, 5, 1)

(4, 7, 3, 0, 2, 5, 1, 6)

(4, 7, 3, 0, 6, 1, 5, 2)

(5, 0, 4, 1, 7, 2, 6, 3)

(5, 1, 6, 0, 2, 4, 7, 3)

(5, 1, 6, 0, 3, 7, 4, 2)

(5, 2, 0, 6, 4, 7, 1, 3)

(5, 2, 0, 7, 3, 1, 6, 4)

(5, 2, 0, 7, 4, 1, 3, 6)

(5, 2, 4, 6, 0, 3, 1, 7)

(5, 2, 4, 7, 0, 3, 1, 6)

(5, 2, 6, 1, 3, 7, 0, 4)

(5, 2, 6, 1, 7, 4, 0, 3)

(5, 2, 6, 3, 0, 7, 1, 4)

(5, 3, 0, 4, 7, 1, 6, 2)

(5, 3, 1, 7, 4, 6, 0, 2)

(5, 3, 6, 0, 2, 4, 1, 7)

(5, 3, 6, 0, 7, 1, 4, 2)

(5, 7, 1, 3, 0, 6, 4, 2)

(6, 0, 2, 7, 5, 3, 1, 4)

(6, 1, 3, 0, 7, 4, 2, 5)

(6, 1, 5, 2, 0, 3, 7, 4)

(6, 2, 0, 5, 7, 4, 1, 3)

(6, 2, 7, 1, 4, 0, 5, 3)

(6, 3, 1, 4, 7, 0, 2, 5)

(6, 3, 1, 7, 5, 0, 2, 4)

(6, 4, 2, 0, 5, 7, 1, 3)

(7, 1, 3, 0, 6, 4, 2, 5)

(7, 1, 4, 2, 0, 6, 3, 5)

(7, 2, 0, 5, 1, 4, 6, 3)

(7, 3, 0, 2, 5, 1, 6, 4)

In this output, 0 represents the first or bottom row, 1 the second and so on. The case of [0, 6, 3, 5, 7, 1, 4, 2], shown in the tweet, is highlighted above in bold red. I use the Mathematics specific SageMathCell which is built on top of Python and when using this the permutation function is built in (so no need to import) but it uses a capital P. Similarly, the set function uses a capital S. I've modified the code accordingly and have outputted the number of acceptable configurations. Here is the code (permalink):

L=[]
count=0
col = range(8)
for vec in Permutations(col):
    if (8 == len(Set(vec[i]+i for i in col)) == len(Set(vec[i]-i for i in col))):
        count+=1
        L.append(vec)
print("There are",count,"number of ways to arrange 8 non-attacking queens on a chessboard. They are:")
print()
for n in L:
    print(n)

The output is the same as for the Python code except that it displays the fact that there are 92 possible configurations (out of a total of 40320).

So what's going on in this algorithm. Well, let's start with col = 0, 1, 2, 3, 4, 5, 6, 7. Whatever our permutation, the elements in this range get added and subtracted sequentially to the elements in our permutation. Let's use [5, 2, 4, 6, 3, 0, 7, 1] as an example of a permutation that does equate to a successful configuration. This is shown in Figure 2 (created using a Google Worksheet). Note how the top row (Added) and the bottom row (Subtracted) each contain eight distinct numbers so that the set of both rows has a length of 8.

Figure 2

Let's now consider the permutation [5, 2, 4, 6, 3, 0, 7, 1] that does not lead to a successful configuration. This is shown in Figure 3 where it can be noted that both the top and bottom rows each contain duplicate numbers so that the length of the set is not equal to 8.

Figure 3

 It's quite a succinct and clever algorithm and it's easily modifiable to accommodate any size chess board. To investigate this further it's best to modify the algorithm slightly so that it's more flexible. Here we replace the number 8 with a variable called "size". Here is the modified algorithm with size = 7 (permalink).

L=[]
size=7
count=0
col = range(size)
for vec in Permutations(col): 

    if (size == len(Set(vec[i]+i for i in col))== len(Set(vec[i]-i for i in col))):
        count+=1
        L.append(vec)
print("There are",count,"number of ways to arrange",size,"non-attacking queens on a chessboard. They are:")
print()
for n in L:
    print(n)

The output reveals that there are 40 ways (out of a total of 5040) in which 7 non-attacking queens can be placed on a 7 x 7 chessboard. Here is the output:

 There are 40 number of ways to arrange 7 non-attacking queens on a chessboard. They are:

[0, 2, 4, 6, 1, 3, 5]

[0, 3, 6, 2, 5, 1, 4]

[0, 4, 1, 5, 2, 6, 3]

[0, 5, 3, 1, 6, 4, 2]

[1, 3, 0, 6, 4, 2, 5]

[1, 3, 5, 0, 2, 4, 6]

[1, 4, 0, 3, 6, 2, 5]

[1, 4, 2, 0, 6, 3, 5]

[1, 4, 6, 3, 0, 2, 5]

[1, 5, 2, 6, 3, 0, 4]

[1, 6, 4, 2, 0, 5, 3]

[2, 0, 5, 1, 4, 6, 3]

[2, 0, 5, 3, 1, 6, 4]

[2, 4, 6, 1, 3, 5, 0]

[2, 5, 1, 4, 0, 3, 6]

[2, 6, 1, 3, 5, 0, 4]

[2, 6, 3, 0, 4, 1, 5]

[3, 0, 2, 5, 1, 6, 4]

[3, 0, 4, 1, 5, 2, 6]

[3, 1, 6, 4, 2, 0, 5]

[3, 5, 0, 2, 4, 6, 1]

[3, 6, 2, 5, 1, 4, 0]

[3, 6, 4, 1, 5, 0, 2]

[4, 0, 3, 6, 2, 5, 1]

[4, 0, 5, 3, 1, 6, 2]

[4, 1, 5, 2, 6, 3, 0]

[4, 2, 0, 5, 3, 1, 6]

[4, 6, 1, 3, 5, 0, 2]

[4, 6, 1, 5, 2, 0, 3]

[5, 0, 2, 4, 6, 1, 3]

[5, 1, 4, 0, 3, 6, 2]

[5, 2, 0, 3, 6, 4, 1]

[5, 2, 4, 6, 0, 3, 1]

[5, 2, 6, 3, 0, 4, 1]

[5, 3, 1, 6, 4, 2, 0]

[5, 3, 6, 0, 2, 4, 1]

[6, 1, 3, 5, 0, 2, 4]

[6, 2, 5, 1, 4, 0, 3]

[6, 3, 0, 4, 1, 5, 2]

[6, 4, 2, 0, 5, 3, 1]

These numbers (92 for \(n\)=8, 40 for \(n\)=7 etc.) constitute OEIS A000170:

A000170

Number of ways of placing \(n\) nonattacking queens on an \(n \times n\) board.

The initial members of the sequence are:

• \(n=0\) --> \(1\)
• \(n=1\) --> \(1\)
• \(n=2\) --> \(0\)
• \(n=3\) --> \(0\)
• \(n=4\) --> \(2\)
• \(n=5\) --> \(10\)
• \(n=6\) --> \(4\)
• \(n=7\) --> \(40\)
• \(n=8\) --> \(92\)
• \(n=9\) --> \(352\)
• \(n=10\) --> \(724\)
• \(n=11\) --> \(2680\)
• \(n=12\) --> \(14200\)
• \(n=13\) --> \(73712 \)

One might struggle with the concept of a 0 x 0 sized chessboard but I guess it's a bit like 0!=1 and 1!=1. The algorithm, when run on SageMathCell, timed out for the cases of \(n=10\) and above.

Prouhet-Thue-Morse Sequence

I was reminded of this sequence when I rewatched a Numberphile YouTube video that related the sequence to the game of chess.

The Prouhet-Thue-Morse is a simple enough sequence but one with many practical applications. It can be described using formal mathematical notation but it can be described in so-called layman's terms as well. This gif from Wikipedia is an example of the latter:

A close look at this gif and it's clear enough how the sequence is being constructed. My last two posts have focussed on recurrence relations and the Prouhet-Thue-Morse sequence can be described more formally as a recurrence relation:$$ \begin{align} t_0 &= 0\\ t_{2n} &= t_n\\ t_{2n+1} &= 1 - t_n \end{align}$$wikiHow has a variety of algorithms for creating the sequence. One uses the recurrence relation as shown in Figure 1:

Figure 1

I incorporated this approach into SageMathCell as shown in Figure 2 (permalink):

Figure 2: permalink

Another approach, what wikiHow calls the Direct Definition, uses the binary form of the natural (decimal) numbers, calculates their binary sum and then uses the modulus 2 of this sum as the output. What's happening is that decimal numbers with an even number of 1's in their binary form are assigned a ZERO and those with an odd number of 1's are assigned a ONE.

\(t_0 = 0 \text{ and } t_n \equiv s_n \bmod{2} \text{ where }s_n \text{ is the binary sum of }n\)

This algorithm is even easier to implement in SageMathCell. See Figure 3 where the output is shown, for variety, as a string rather than a list of elements (permalink):

Figure 2: permalink

The following is an excellent video that I came across from a mathematician who, unconsciously, used the Thue-Morse sequence (sometimes the Prouhet part of the name is omitted) as a child to cope with his obsessive compulsive disorder. Later he describes how he unwittingly used the sequence to solve the Mathematics problem described in Figure 3:

Figure 3

Of course the sequence can be represented with elements other than 0's and 1's. For example, suppose that two persons want to divide an even number of items of equal value between themselves. If the choosing sequence goes ABABABAB ... or BABABABA ... then the person choosing second will always be behind 50% of the time in terms of what they've accumulated. However, using the Thus-Morse sequence, the lead will alternate and in fact represents the fairest way to share things:

ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABB

Finally, here is a video on the sequence that Stand-up Maths did some years ago:

Knight Tours

I've already made several posts relating mathematics and chess. These are:

• More on the Mathematics of Chess on Thursday, 14th November 2019
• The Mathematics of Chess on Sunday, 6th January 2019
• Hogben Numbers on Wednesday, 28th November 2018
• Chess960 on Monday, 12th February 2018
• The Mathematics of Chess Pairings on Sunday, 11th February 2018

Today I turned 25983 days old and my investigation of the number 25983 revealed an interesting chess connection. Suppose we number the squares on an infinite chess board starting with 0 and then counting in an anticlockwise spiral as shown in Figure 1.

Figure 1

Suppose we devise a Knight Tour such that the Knight starts on square 0 and then moves always to the unvisited square closest to the origin. "Closest to the origin" is meant in the sense of Euclidean distance, and in case of a tie, the square coming earliest on the spiral is chosen.

On the first move, the Knight could move to squares 9, 11, 13, 15, 17, 19, 21 or 23. All these squares are the same distance from the 0 square but 9 is chosen because it comes first in the spiral. From 9, subsequent squares are 2, 5, 8, 3, 6, 1, 4, 7, 10, 13 and so on. 

These numbered squares form OEIS A326924:

A326924

Squares visited by a knight on a spirally numbered board, moving always to the unvisited square closest to the origin.

Figure 2 shows a slightly different depiction of the squares with more squares viewable:

Figure 2

The initial terms are of the sequence are:

0, 9, 2, 5, 8, 3, 6, 1, 4, 7, 10, 13, 28, 31, 14, 11, 26, 23, 44, 19, 22, 43, 40, 17, 34, 37, 18, 15, 32, 29, 52, 25, 46, 21, 76, 47, 50, 27, 12, 33, 16, 39, 20, 45, 24, 51, 48, 77, 114, 73, 70, 105, 38, 35, 60, 93, 30, 53, 84, 49, 78, 115, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 124, 81, ...

What's really interesting about this tour is that the knight gets trapped at the 22325th move, where it can't reach any unvisited square. The square on which the Knight is stuck is 25983!

So nothing in this post of deep mathematical significance but it always strikes me as fascinating how numbers can be associated with such diverse phenomena. In this case, it is a Knight's tour of an infinite, spirally numbered chessboard.

For information on other Knight tours visit https://oeis.org/wiki/Knight_tours. 

More on the Mathematics of Chess

Figure 1: Book Cover

On Sunday, 6 January 2019, I published a post titled The Mathematics of Chess in which I discussed the number 25480 as the number of ways to place 2 non-attacking amazons (superqueens) on an 16 x 16 board. In that post, I made reference to Vaclav Kotesovec's magnum opus Non-attacking Chess Pieces that I have in my Calibre Library. Today I am reminded of its existence yet again because my diurnal age is 25792 and this turns out to be a member of OEIS A035288: the number of ways to place a non-attacking white and black bishop on n x n chessboard. 25792 arises when n=13.

This is a variation on the problem of how to place two non-attacking bishops on an n X n board. This problem is normally colour agnostic as shown in Figure 2.

Figure 2: two non-attacking bishops on an
8 x 8 board with both of the same colour

However, in the case of OEIS A035288, the two bishops are distinguishable because one is white and the other black as shown in Figure 3.

Figure 3: two non-attacking bishops on an 8 x 8 board
but with one white and the other black

OEIS A172123 deals with the number of ways to place 2 non-attacking bishops on an n x n board, where the bishops are not distinguishable from each other. The members of OEIS A035288 are simply twice the value of those in OEIS A172123. In Vaclav's book, it is these situations (where the pieces are indistinguishable) that are investigated. Figure 4 shows the table from page 241 of the book. The value of 12896 x 2 = 25792.

Figure 4: table of values for different numbers of
non-attacking bishops on varying sized boards

The author also provides generating functions for the different number of bishops and differently sized boards. I've just shown the first five in Figure 5 (taken from page 240 of the book).

Figure 5: generating function for two to five non-attacking bishops

In the case of two indistinguishable bishops, the generating function of interest is:$$-\frac{2x^2 \, (x+1) \, (x+2)}{(x-1)^5}$$This generating function can be used to generate the members of OEIS A172123. This is shown in Figure 6 for members of the sequence up to and including 12896:

Figure 6: SageMathCell code generating members of sequence A172123

The OEIS entry also lists a simple formula for determining the members of the sequence. It is:$$a(n) = \frac{n \,(n - 1) \, (3n^2 - n + 2)}{6}$$There is also a recursion formula:$$a(n) = 5 \,a(n-1)-10\, a(n-2)+10 \, a(n-3)-5 \,a(n-4)+a(n-5)$$It was good to be reminded of Vaclav's impressive book again but I also have in my possession another book titled Across the Board: The Mathematics of Chessboard Problems by John J. Watkins.

Figure 7: Book Cover

As the author says in this introduction:

... this book is about the game board itself, the simple grid of squares that forms such a common feature of games played around the world, and, more importantly, about the mathematics that arises from such an apparently simple structure.

The book contains much of interest that hopefully I'll be able to write about in later posts. Vaclav's book is really a reference source for a huge range of non-attacking pieces on various sized boards but Watkins looks a limited number of situations in detail. Figure 8 shows the very first problem that he deals with: Guarini's Problem that dates from 1520.

Figure 8: Guarini's Problem requires the white
and black knights to exchange positions

One solution involves reducing the board to a graph so that the situation is revealed more clearly. This is shown in Figure 9.

Figure 9: Guarini's Problem as a Graph

The graph clearly shows that four steps are involved, each step involving each of the four knights to advance to the next node (either clockwise or anticlockwise). If anticlockwise, then the knight on a will move to d, the knight on c will move to b, the knight on d will move to a and the knight on b will move to c.

The Mathematics of Chess

I've already posted about Chess960, also known as Fischer Random Chess (originally Fischerandom), explaining how the 960 possible starting positions for this variant of chess are obtained. There's a lot more mathematics of course on the chess board than that. Today I turned 25480 days old and the first entry in OEIS for this number is:

A172200: number of ways to place 2 non-attacking amazons (superqueens) on an n X n board. The sequence begins: 0, 0, 0, 20, 92, 260, 580, 1120, 1960, 3192, 4920, 7260, 10340, 14300, 19292, 25480, ... and for the case of 25480, the value of n is 16 so the placements are made on 16 X 16 board.

DIAGRAM 1: 16 X 16 board showing one of the 25480 possible
positions of two non-attacking amazons, represented by
the letter S standing for the German "Springer".

So what is an amazon or superqueen, I asked myself? The simple answer is provided in the comments to the OEIS sequence: an amazon (superqueen) moves like a queen and a knight. The comments also contain a link to a remarkable book that I've now downloaded and added to my Calibre Library.

DIAGRAM 2: cover of the book "Non-attacking chess pieces"

This monumental work is 795 pages in length and on page 347, the sole reference to 25480 can be found:

DIAGRAM 3: table showing the number of ways
in which 2, 3, 4 and 5 non-attacking amazons can be
placed on boards ranging in size from 1 X 1 to 20 X 20

The formula for obtaining this result is shown earlier on page 343:

DIAGRAM 4: page 343 of the text with annotations

One might argue that a so-called superqueen or amazon has no place in standard chess and you'd be right but, like it or not, there are a great many of these alternative pieces. The book mentioned earlier looks not only at the mathematics of standard pieces and boards but also these alternative pieces and even alternative boards. It's best to illustrate by example.

Let's consider another alternative piece, the nightrider, defined by Wikipedia as:

A fairy chess piece that can move any number of steps as a knight in the same direction. The nightrider is often represented by a symbol similar to the knight's icon, but altered in a way to indicate the additional straight-line motion. In this article the nightrider is represented with an inverted knight, and notation N (in which case the knight is abbreviated as S for German Springer). The nightrider was invented by T. R. Dawson in 1925, and is often used in chess problems.

See Figure 1. Note that intervening landing squares must be vacant. For example, a nightrider on b2 can reach empty square c4 and forward to empty squares d6 and e8, but cannot jump over a pawn on f4 to reach h5.:

Figure 1

Now let's consider a toroidal chessboard instead of the standard one:

DIAGRAM 6: toroidal chess board

In this type of board, the standard board is joined side to side to form a cylinder and then each end of the cylinder is joined, thus joining the top and bottom of the board. I won't go into the rules for moving on such a board but a detailed explanation of that can be found here. The reasonable question can then be asked: 

In how many ways can we place two non-attacking nightriders on a 16 X 16 toroidal chessboard?

Impressively, the previously mentioned book provides the answer: 25728 ways.

DIAGRAM 7: table showing no ways that two, three and four non-attacking
nightriders can be placed on boards ranging in size from 1 X 1 to 16 X 16

The formula for obtaining this is somewhat terrifying but I've included it below and must confess to having no idea of how it was arrived at:

DIAGRAM 8: screenshot from page 333 of
the book "Non-attacking chess pieces"

This sequence of terms 2, 18, 72, 200, ... in the column above comprises A196812 in the OEIS. In summary, the different possible positions of standard and fairy chess pieces on standard and non-standard boards provide fertile grounds for mathematical analysis. This post just hints at the range and complexity of content that can be found in Vaclav Kotesovec's remarkable book.

Chess960

Currently an unofficial world championship is underway in Oslo pitting Hikaru Nakamura against Magnus Carlsen. However, the two are not playing traditional chess but instead so-called Chess960 described as follows in Wikipedia:

Chess960, also called Fischer Random Chess (originally Fischerandom), is a variant of chess invented and advocated by former world chess champion Bobby Fischer, publicly announced on June 19, 1996, in Buenos Aires, Argentina. 

It employs the same board and pieces as standard chess, but the starting position of the pieces on the players' home ranks is randomised. The random setup renders the prospect of obtaining an advantage through the memorisation of opening lines impractical, compelling players to rely on their talent and creativity. 

Randomising the main pieces had long been known as Shuffle Chess; however, Chess960 introduces restrictions on the randomisation, "preserving the dynamic nature of the game by retaining bishops of opposite colours for each player and the right to castle for both sides".[3] The result is 960 unique possible starting positions. 

White's pieces (not pawns) are placed randomly on the first rank, with two restrictions:

• The bishops must be placed on opposite-color squares.

• The king must be placed on a square between the rooks.

• Black's pieces are placed equal-and-opposite to White's pieces. (For example, if the white king is randomly determined to start on f1, then the black king is placed on f8.) Pawns are placed on the players' second ranks as in standard chess.

It is the number 960 that is of interest in this mathematics blog and this is explained as follow:

Each bishop can take one of four squares; for each position of two bishops, the queen can be placed on six different squares; and then the two knights can assume five and four possible squares, respectively. This leaves three open squares which the king and rooks must occupy, per setup stipulations, without choice. This means there are 4×4×6×5×4 = 1920 possible starting positions if the two knights were different in some way; however, the two knights are indistinguishable during play (if swapped, there would be no difference), so the number of distinguishable possible positions is half of 1920, or 1920÷2 = 960. (Half of the 960 positions are left–right mirror images of the other half; however, the Chess960 castling rules preserve left–right asymmetry in play.) 

There is another variant called Double Fischer Random Chess which is the same as Chess960, except the White and Black starting positions do not mirror each other. In this form of the game, the number of possible starting positions is 960 x 960 = 921600. In Shuffle Chess, the parent variant of Chess960, there are no restrictions on the back-rank shuffles, with castling possible only when king and rook are on their traditional starting squares. In the case, the number of permutations is 8! but division by 8 is necessary because the pairs of Knights, Bishops and Rooks are indistinguishable. This means 7! or 5040 arrangements are possible.