A mind-blowing way to celebrate Chesstalk's return

[Paul Bonham]

Re: A mind-blowing way to celebrate Chesstalk's return

Operationally the answer is simple.

If you could complete and record the results of the analysis, your environs would immediately collapse into a black hole. This is a consequence of the Bekenstein Bound, a theorem in physics which you can look up if curious.

This may, alas, be the only watertight defense against players cheating with "Houdini 3000" or whatnot.

I am glad for ChessTalk's return, anyway! :)

I'm going to present some pseudocode that will show how simple it is to generate each and every possible position in which White and Black each have their King plus 1 Queen, 1 Rook, 1 Bishop, 1 Knight, and 1 Pawn, with the addition that
- if the Pawn is White and on White's 8th rank, it becomes (in turn) a Queen, a Rook, a Bishop, then a Knight
- if the Pawn is Black and on Black's 8th rank, it becomes (in turn) a Queen, a Rook, a Bishop, then a Knight

First you set up an array of BoardSquares, starting at a1, moving across to h1, then up to h2, then across to a2, then up to a3, across to h3, etc. The array ends at a8. Assume that the values "a1", "a2", etc are actually variables that are instances of a BoardSquare object template:

BoardSquare ChessBoardArray[64] =
{
	a1, b1, c1, d1, e1, f1, g1, h1,
	h2, g2, f2, e2, d2, c2, b2, a2,
	a3, b3, c3, d3, e3, f3, g3, h3,
	h4, g4, f4, e4, d4, c4, b4, a4,
	a5, b5, c5, d5, e5, f5, g5, h5,
	h6, g6, f6, e6, d6, c6, b6, a6,
	a7, b7, c7, d7, e7, f7, g7, h7,
	h8, g8, f8, e8, d8, c8, b8, a8
};

Logically, the array is equivalent to starting at a1 and following the path shown:

a8 <- b8 <- c8 <- d8 <- e8 <- f8 <- g8 <- h8
                                          |
a7 -> b7 -> c7 -> d7 -> e7 -> f7 -> g7 -> h7
 |
a6 <- b6 <- c6 <- d6 <- e6 <- f6 <- g6 <- h6
                                          |
a5 -> b5 -> c5 -> d5 -> e5 -> f5 -> g5 -> h5
 |
a4 <- b4 <- c4 <- d4 <- e4 <- f4 <- g4 <- h4
                                          |
a3 -> b3 -> c3 -> d3 -> e3 -> f3 -> g3 -> h3
 |
a2 <- b2 <- c2 <- d2 <- e2 <- f2 <- g2 <- h2
                                          |
a1 -> b1 -> c1 -> d1 -> e1 -> f1 -> g1 -> h1

Here now are the for loops that will populate the board, where the function
firstAvailableEmptySquare()
starts at a1 and follows the path shown above until it finds the first empty square:

for( WK.square = firstAvailableEmptySquare();   WK square <= lastAvailableEmptySquare();   ++WK.square )
{
	for( WQ.square = firstAvailableEmptySquare();   WQ.square <= lastAvailableEmptySquare();   ++WQ.square )
	{
		for( WR.square = firstAvailableEmptySquare();   WR.square <= lastAvailableEmptySquare();   ++WR.square )
		{
			for( WB.square = firstAvailableEmptySquare();   WB.square <= lastAvailableEmptySquare();   ++WB.square )
			{
				for( WN.square = firstAvailableEmptySquare();   WN.square <= lastAvailableEmptySquare();   ++WN.square )
				{
					for( WP.square = firstAvailableEmptySquare();   WP.square <= lastAvailableEmptySquare();   ++WP.square )
					{
						for( BK.square = firstAvailableEmptySquare();   BK.square <= lastAvailableEmptySquare();   ++BK.square )
						{
							for( BQ.square = firstAvailableEmptySquare();   BQ.square <= lastAvailableEmptySquare();   ++BQ.square )
							{
								for( BR.square = firstAvailableEmptySquare();   BR.square <= lastAvailableEmptySquare();   ++BR.square )
								{
									for( BB.square = firstAvailableEmptySquare();   BB.square <= lastAvailableEmptySquare();   ++BB.square )
									{
										for( BN.square = firstAvailableEmptySquare();   BN.square <= lastAvailableEmptySquare();   ++BN.square )
										{
											for( BP.square = firstAvailableEmptySquare();   BP.square <= lastAvailableEmptySquare();   ++BP.square )
											{
												//---- CHECK IF WHITE PAWN PROMOTABLE
												if( WP.square.isOnWhite8thRank() )
												{
													for( enum PromotedPawnValue WPValue = QUEEN;   WPValue >= KNIGHT;   --WPValue )
													{
														WP.setPromotedValue( WPValue );
														
														//---- CHECK IF BLACK PAWN ALSO PROMOTABLE
														if( BP.square.isOnBlack8thRank() )
														{
															for( enum PromotedPawnValue BPValue = QUEEN;   BPValue >= KNIGHT;   --BPValue )
															{
																BP.setPromotedValue( BPValue );
																ChessPosition position( WK, WQ, WR, WB, WN, WP, BK, BQ, BR, BB, BN, BP );
																processPosition( &position );
															}
														}
														else  //---- Black pawn not promotable
														{
															ChessPosition position( WK, WQ, WR, WB, WN, WP, BK, BQ, BR, BB, BN, BP );
															processPosition( &position );
														}
													}
												}
												//---- CHECK IF BLACK PAWN PROMOTABLE
												else if( BP.square.isOnBlack8thRank() )
												{
													for( enum PromotedPawnValue BPValue = QUEEN;   BPValue >= KNIGHT;   --BPValue )
													{
														BP.setPromotedValue( BPValue );
														ChessPosition position( WK, WQ, WR, WB, WN, WP, BK, BQ, BR, BB, BN, BP );
														processPosition( &position );
													}
												}
												else  //---- no promoted pawn
												{
													ChessPosition position( WK, WQ, WR, WB, WN, WP, BK, BQ, BR, BB, BN, BP );
													processPosition( &position );
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
}

Given the above for loops, what would the very first position be? It would be this, where X, Y are each any positive integer (realistically, Y would be quite high, say 60 or more):

8/8/8/8/8/8/4pnbr/KQRBNPkq w - - X Y



If you try and import that FEN (with any values for X and Y) into any chess software that accepts legal FEN positions, it won't accept this one because it's illegal: there's a White Pawn specified on White's first rank.

As a matter of fact, given the order that the for loops move the pieces along the path of squares, the first 87,426,773,280 positions are going to be illegal because the White Pawn is on the first rank (I'll leave that as an exercise for the interested reader).

That's right: the first 87.4 BILLION positions aren't even legal.

The first LEGAL chess position (the 87,426,773,281st one set up) would be this:

8/8/8/8/8/8/4pnbP/KQRBNkqr w - - X Y



And guess what? This position, with White to move, leads to a very interesting mate in 7!

1.Bxe2+ Kxe2 2.Qb5+ Ke3 3.Qg5+ Ke2 4.Rc2+ Kf1 5.Qb5+ Nd3 6.Qxd3+ Kxe1 7.Qe2#

What would be the very last position analyzed?

KQRBNNkq/4pnbr/8/8/8/8/8/8 b - - X Y



If you're wondering about the missing White Pawn and why it is replaced with a White Knight on f8, it's because a White Pawn on White's 8th rank gets promoted in turn to Queen, then Rook, then Bishop, and finally Knight. Note that replacing the White Pawn on f8 with a Queen or Rook would create an illgal position even if it were Black to move: the pawn must have just promoted to Queen or Rook, yet there is no empty square from which it could have promoted. Whereas with the promotion to Bishop or Knight, that could have happened any number of moves ago, and the empty square from which it promoted has been occupied by Black pieces. Legal because the Black King is not in check.

This position does not have any pretty mate, and in fact is evaluated as almost even (about +0.2 for White) as the following engine-calculated line shows:

1...Bxf8 2.Qg3+ Rg7 3.Nxg7 Qh1+ 4.Ka7 Qa1+ 5.Kb6 Qb1+ 6.Ka6 Qf1+ 7.Ka5 Qa1+ 8.Kb4 Qb2+ 9.Qb3 Qd2+ 10.Qc3 Qd6+ 11.Kb3 Qd1+ 12.Qc2 Qf3+ 13.Ka2 Qd5+ 14.Qb3 Qg2+ 15.Ka3 Kxg7 16.Qe6

However, if it's White to move (penultimate position analyzed), very big difference: it's winning for White:

1.Bxe7 Rh5 2.Qg3 Ra5+ 3.Kb8 Ra8+ 4.Kxa8 Qh1+ 5.Ka7 Qa1+ 6.Ba3 Qd4+ 7.Bc5 Qa1+ 8.Kb7 Qh1+ 9.Kc7 Qa1 10.Nf6+ Qxf6 11.Nd7+ Qd8+ 12.Rxd8+ Nxd8 13.Kxd8

Now, as we determined earlier, if each position takes 1 millionth of a second to evaluate, these last couple of positions won't get evaluated until about 13.75 million years into the future, give or take a few hundred thousand years. That's approximately how long it will take to get through the entirety of the for loops if we can limit the time spent in the innermost for loop to 1 millionth of a second.

In a later post, I'll fill in pseudocode for what the function processPosition(&position) would do.