Chess960 starting position

From Wikipedia, the free encyclopedia

Chess960 is a variant of chess in which the arrangement of pieces on the first rank is randomly generated. There are 960 possible starting positions, hence the name. The starting position can be generated before the game either by a computer program or using dice, coin, cards etc.

1 Rules
2 Methods for creating the starting position
3 Starting position IDs in Chess960

[edit] Rules

The starting position for Chess960 must meet the following rules:

White pawns are placed on their orthodox home squares.
All remaining white pieces are placed on the first rank.
The white king is placed somewhere between the two white rooks.
The white bishops are placed on opposite-colored squares.
The black pieces are placed equal-and-opposite to the white pieces. For example, if the white king is placed on b1, then the black king is placed on b8.

Note that the king never starts on file a or h, because there would be no room for a rook.

[edit] Methods for creating the starting position

There are many procedures for creating the starting position for a game of Chess960. The methods that are presented below fall into two general categories:

There is a separate randomization event for each placement of a piece, or at least most of them. The die and coins methods fall into this category. The main problems are the placements of the King and Rooks. Analysis of the 960 starting positions shows that the Knights, Bishops and Queen are spread evenly across the 8 files; however, the King should stand on the files b through g with the respective probabilities 9/80, 14/80, 17/80, 17/80, 14/80, 9/80, and the Rook's probabilities for the files a through h are, respectively, 30/80, 21/80, 16/80, 13/80, 13/80, 16/80, 21/80, 30/80. It is very doubtful that any simple method can achieve these numbers unless the King and rooks are placed last (when there is only one choice) and proper balance is maintained for the previous placements of the Knights, Bishops and Queen.
There is a single randomization event for the placement of all 8 pieces. The cards and drawing methods are in this category. The difficulty here is how to cope when the Bishops start out on squares of the same color. There are 5040 distinct arrangements of the pieces. 2880 of these have the Bishops on squares of different colors, and 2160 of these have Bishops on squares of the same color. Thus it is imposssible to get a proper balance by linking each of the latter arrangements to its own single arrangement with the Bishops on different colored squares. Some further randomization is needed. David Wheeler's suggestion of having a randomly selected Bishop move to a randomly selected square of the opposite color is a very handy way to do this. It involves an 8 way choice, and gives equal probabilities to all 2880 positions.

[edit] Bodlaender's dice-rolling method

Hans L. Bodlaender has proposed the following procedure using one six-sided die to create an initial position:

Roll the die, and place a white bishop on the black square indicated by the die, counting from the left. Thus 1 indicates the first black square from the left (a1 in algebraic notation), 2 indicates the second black square from the left (c1), 3 indicates the third (e1), and 4 indicates the fourth (g1). Since there are no fifth or sixth positions, re-roll 5 or 6 until another number shows.
Roll the die, and place a white bishop on the white square indicated (1 indicates b1, 2 indicates d1, and so on). Re-roll 5 or 6.
Roll the die, and place a queen on the first empty position indicated (always skipping filled positions). Thus, a 1 places the queen on the first (leftmost) empty position, while a 6 places the queen on the sixth (rightmost) empty position.
Roll the die, and place a knight on the empty position indicated. Re-roll a 6.
Roll the die, and place a knight on the empty position indicated. Re-roll a 5 or 6.
This leaves three empty squares. Place a white rook on the first empty square of the first rank, the white king on the second empty square of the first rank, and the remaining white rook on the third empty square of the first rank.
Place all white and black pawns on their usual squares, and place Black's pieces to exactly mirror White's (so Black should have on a8 exactly the same type of piece that White has on a1, except that bishops would be on opposite colors).

This procedure generates any of the 960 possible initial positions with an equal chance; on average, this particular procedure uses 6.7 die rolls - an optimal procedure would use on average somewhere between 4 and 4.45 die rolls. Note that one of these initial positions is the standard chess position, at which point a standard chess game begins.

It is also possible to use this procedure to see why there are exactly 960 possible initial positions. Each bishop can take one of four positions, the queen one of six, and the two knights can have five or four possible positions, respectively. (That leaves three open squares and the king must occupy the middle of those three squares, with rooks taking the last two squares, with no choice.) This means that there are 4×4×6×5×4 = 1920 possible positions if the two knights were different in some way. However, the two knights are indistinguishable during play; if they were swapped, there would be no difference. This means that the number of distinguishable positions is half of 1920, or 1920/2 = 960 possible distinguishable positions.

[edit] Rovida's dice-rolling method

This method does not give equal probabilities to the starting positions. For example, there are 108 starting postitions with the King on b1, so the totality of these positions should have probability 108/960 = 9/80. This method, however, gives probability 1/6 to the totality of these positions.

Roberto Rovida's method is more complicated than Bodlaender's, but uses fewer die rolls (4-6). When each piece is placed, there will be one, two, three, or six possible spaces for it. If one, there is no need to roll a die; if two, assign them the ranges 1-3 and 4-6; if three, assign them the ranges 1-2, 3-4, and 5-6.

Place the king on a square that isn't a corner (1 roll).

Place a rook on the side the king is closer to (0 or 1 roll).

Place the queen on an empty square (1 roll).

If the king, rook, and queen are all on the same color, place the bishop on the fourth square of that color, then place the other rook (1 roll) and then the other bishop (1 roll). If not, place one bishop (1 roll), then the other bishop (1 roll), then the other rook (0 or 1 roll).

Place both Knights on the remaining two squares.

Place the opponent's pieces symmetrically and place all pawns.

[edit] Coin-tossing methods

The two coins method does not produce all legal starting positions with equal probability. The positions that arise when the King occupies the center two of the four possibilities are two thirds as likely as the others.

Edward Northam has developed the following approach for creating initial positions using only two distinguishable coins.

First, two coins (small and large) are used to randomly generate numbers with equal probability. He suggests doing this by declaring that tails on the smaller coin counts as 0, tails on the larger coin counts as 1, and heads on either coin counts as 2. To create numbers in the range 1 through 4, toss both coins and add their values together. To create numbers in the range 1 through 3, do the same but retoss whenever 4 is the result. To create numbers in the range 1 through 2, just toss the larger coin (tails is 1, heads is 2).

Any other technique that randomly generates numbers from 1 to 4 (or at least 1-2) will work as well, such as the selection of a closed hand that may hold a white or black Pawn.

As with a die, the coin tosses can build a starting position one piece at a time. Before each toss there will be at most 4 vacant squares available to the piece at hand, and they can be numbered counting from the a-side (as with the die procedure described above). Place the white pieces on white's back rank as follows:

Place a Bishop on one of the 4 light squares.
Place a Bishop on one of the 4 dark squares.
Place the King. There 6 vacant squares, but only the middle 4 are available to the King, since there must be room for a Rook on each side of the King.
Place a Rook on the a-side of the King.
Place a Rook on the h-side of the King.
Place the Queen on one of the 3 vacant squares that remain.
Place Knights on the two squares that are left.

The average number of tosses needed to complete the process is 6.

There is a way of using coins and making all starting positions equally likely. It uses a third coin for which tails counts for 0, and heads counts for 4. Tossing all 3 coins makes the numbers 1 through 8 equally likely. The method follows the piece placements used for a die. Two coins are used for the Bishops as before. Then six squares are available for the Queen. All 3 coins are tossed and retossed until a number in the range 1...6 comes up. Then 5 squares are available for the first Knight. Now the 3 coins should be tossed and retossed until a number in the range 1...5 shows up. For the second Knight, only a four way choice is needed, so a single toss of two coins will do the job. The average number of tosses needed for this method is 5 + 14/15.

[edit] Drawing methods

The Coffin and Scharnagl methods below do not give equal probabilities to all 960 starting positions.

David J. Coffin suggests the following procedure, which has the advantage of not requiring computers, dice, or lookup tables:

Place the eight white pieces in a bag. Draw them one by one and place them on squares a1, b1, ... h1.
If the bishops are on the same color, look at the following pairs: a1-b1, c1-d1, and e1-f1. Swap the leftmost pair that contains a bishop.
If the king is not between his rooks, swap the king with the closer rook.

However, while all positions can be generated this way, not all positions have the same probability to be generated. Mathematical analysis shows that positions with the bishops on a pair a1-b1, c1-d1, e1-f1, or g1-h1 actually have half the probability to be generated of the other positions.

R. Scharnagl also has a method for correcting same color Bishop positions when the pieces are drawn from a bag. He acknowledges that it does not produce all positions with equal probability, but makes the point that this is not necessary to achieve the main objective of Chess960. See the external reference.

In order to move a randomly selected Bishop to a randomly selected square of the opposite color, as suggested in the Introd., a choice involving a white Pawn and a black Pawn could be used to select the a-side or h-side Bishop, which would be removed from the board. Then the black pieces could be put in the bag and mixed up. One would be drawn out, and the numbering of the square of opposite color could, for example, be given by R=1, N=2, B=3, K, Q=4.

A much quicker method is to simply gather the 8 pieces into a circle on the table, then squash the circle flat into a line. If the bishops would be on the same colour, gather the pieces and try again. Once the bishops are right, swap the king and rook (as above), and start the game.

[edit] Eight cards method

This method produces all legal starting positions with equal probability.

This method makes use of eight cards marked with the numbers 1 through 8. These numbers are associated with piece names according to the starting position in standard chess, ie. 1,8=R, 2,7=N, 3,6=B, 4=Q, 5=K. After the cards are shuffled and dealt in a row, the white pieces should be placed on the back rank as designated by the piece labels. If the Bishops are on squares of the same color, the Coffin or Scharnagl Bishop adjustments of the previous section could correct this immediately, but there is a very easy way to move a randomly selected Bishop to a randomly selected square of the opposite color. The cards should be put face down, mixed up, and one selected at random. A number in the range 1...4 indicates that the a-side Bishop should move to the indicated square of the opposite color. A number in the range 5...8 should be diminished by 4 and the h-side Bishop should be moved to the indicated square of the opposite color.

After the Bishops are on squares of different colors, attention is given to the King and Rooks. If the King is not between the Rooks, it must trade places with the nearest Rook.

-OR-

This method does not produce all legal starting positions with equal probabilities. The problem is discussed in the Introduction.

Using a deck of playing cards, you can select the King, Queen, 2 Jacks, 2 Aces, and 2 Tens. You can separate these out in seconds, and decide on which minor pieces are represented by which cards (as the King & Queen are obvious.) Shuffle. Cut the deck. Deal. You have to take care as to keep the Bishops on opposite colors, and the King between the Rooks. To deal with a card that would be illegal, just hold that piece to the side until it is legal to place. When a legal square opens, place the held piece. Sometimes, two pieces are held but it is not confusing and quite a speedy and random method.

[edit] Multisided dice

The starting position specified by the shown roll.

This method produces all starting positions with equal probability.

If one has polyhedral dice shaped like each of the Platonic solids, one never needs to reroll any dice.

Roll the dice.
Place a white bishop on one of the eight squares as indicated by the octahedron (d8).
Place the other white bishop on one of the four squares of opposite colour as indicated by the tetrahedron (d4).
Place the white queen on the one of the remaining six squares indicated by the cube (d6).
Take the number of the icosahedron (d20). Subtract one, divide by four, and add one to both the quotient and remainder. These results determine the positions of each of the knights on the remaining five squares.
Place the white rooks and the white king between the rooks. If desired, use the dodecahedron to decide who plays white (even numbers for one player, odd for the other).
Place the white pawns and mirror the position for black.

A matched Platonic-solids set of five dice, (from left) tetrahedron (d4), cube (d6), octahedron (d8), dodecahedron (d12) and icosahedron (d20).

[edit] Starting position IDs in Chess960

[edit] Preliminaries

Both methods take account of the positions of the Bishops first, and ignore the distinction between the King and Rooks. Once the positions of the Bishops, Knights and Queen are known, there is only one possibility for the remaining 3 squares. In the places where division of whole numbers is done, it is always done giving a quotient (designated q1,q2,..) and a remainder (designated r1,r2 ..).

There are 16 ways to put 2 Bishops on opposite colored squares. These are shown and numbered in the small table below. The entries actually can be calculated using simple arithmetic, but the table method seems less error prone. For the standard SP the Bishop's code is 6.

               Scharnagl's Bishop's Table
-
  0  BB------   4 -BB-----   8 -B--B---  12 -B----B-
  1  B--B----   5 --BB----   9 ---BB---  13 ---B--B-
  2  B----B--   6 --B--B--  10 ----BB--  14 -----BB-
  3  B------B   7 --B----B  11 ----B--B  15 ------BB

In any SP, when looking at the arrangement of the other pieces around the Bishops, it is helpful to write down the NQ-skeleton for that SP. This is done by ignoring the Bishops and replacing the "K" and "R" by a common symbol, say "-". The NQ-skeleton for the standard SP is -NQ-N-. The sections below showing Scharnagl's Methods and the Fritz9 Methods are independent, and may be read in any order.

[edit] Scharnagl's methods

The methods described below are appropriate for the idn range 0-959. For the idn range 1-960, he recommends conversion by dividing by 960 and working with the remainder. This has the effect of assigning to idn 0 the SP that was at idn 960, and leaving the other idn SP matchups unchanged. If this calculation is applied in the idn range 0-959, nothing is changed.

For any SP, after skipping over the Bishop's, the Queen may occupy any one of 6 possible squares, and they are numbered from left to right (from White's perspective) 0,1,2,3,4,5. The two Knights, then, can appear in any of the remaining 5 squares (skipping over Bishops and Queen) in 10 ways. These are shown and numbered in the N5N table below.

             Scharnagl's N5N Table
-
  0 NN---   2 N--N-   4 -NN--   6 -N--N   8 --N-N
  1 N-N--   3 N---N   5 -N-N-   7 --NN-   9 ---NN

For any SP, both the Queens position and the N5N configuration are immediately available from the NQ-skeleton. The Queen's position is the number of characters to the left of the "Q" , giving 2 for the standard SP. The N5N configuration is obtained by omitting the "Q", giving -N-N- for the standard SP, so its N5N code is 5. In general

idn = (Bishop's code) + 16* (Queen's position) + 96* (N5N code)

For the standard SP, idn = 6 + 16*2 + 96*5 = 518

Going the other way, starting with an idn, divide it by 16 and get

idn = q1*16 + r1. r1 gives the Bishop's code, so put the Bishops on the board. Then divide q1 by 6.

q1 = q2*6 + r2. r2 gives the Queen's position, so put it on the board.

q2 gives the N5N code, so put the Knights on the board (of course skipping over the Bishops and Queen).

Starting with idn = 518, we get 518 = 32*16 + 6, and 32 = 5*6 + 2 so the Bishops code is 6, the Queens position is 2 and the N5N code is 5 with configuration -N-N-. If asterisks denote blank squares, the first rank fills up as: **B**B** **BQ*B** *NBQ*BN*

All of the multiplication and division can be eliminated by using the NQ-skeleton table below. It contains all of the 60 possible NQ-skeletons, and directly refers to all of the SPs with Bishop's code 0, ie. with Bishops on a1 and b1.

              Scharnagl's NQ-skeleton Table
-
  0 QNN---  192 QN--N-  384 Q-NN--  576 Q-N--N  768 Q--N-N
 16 NQN---  208 NQ--N-  400 -QNN--  592 -QN--N  784 -Q-N-N 
 32 NNQ---  224 N-Q-N-  416 -NQN--  608 -NQ--N  800 --QN-N
 48 NN-Q--  240 N--QN-  432 -NNQ--  624 -N-Q-N  816 --NQ-N
 64 NN--Q-  256 N--NQ-  448 -NN-Q-  640 -N--QN  832 --N-QN
 80 NN---Q  272 N--N-Q  464 -NN--Q  656 -N--NQ  848 --N-NQ  
-
 96 QN-N--  286 QN---N  480 Q-N-N-  672 Q--NN-  864 Q---NN
112 NQ-N--  304 NQ---N  496 -QN-N-  688 -Q-NN-  880 -Q--NN
128 N-QN--  320 N-Q--N  512 -NQ-N-  704 --QNN-  896 --Q-NN
144 N-NQ--  336 N--Q-N  528 -N-QN-  720 --NQN-  912 ---QNN
160 N-N-Q-  352 N---QN  544 -N-NQ-  736 --NNQ-  928 ---NQN
176 N-N--Q  368 N---NQ  560 -N-N-Q  752 --NN-Q  944 ---NNQ

Given an SP, extract the Bishop's code, the NQ-skeleton and its N5N configuration. The 6 skeletons in each of the 10 blocks in the table all have the same N5N configuration, and the blocks are arranged according to the N5N table above. It is easy, then, to find the appropriate block, and look inside for the entry with the "Q" in the desired place, say at No. M. Then idn = (Bishop's code) + M. For the standard SP, we extract 6 -NQ-N- and -N-N-. The desired block is the middle one in the second row, and the desired skeleton is at No. 512. We get idn = 6 + 512 = 518.

Going the other way, given an idn, locate, in the table, the largest number, say M, that is less than or equal to idn. Then idn - M gives the Bishop's code, and the skeleton at M shows how to fill in the rest of the pieces. Given idn = 518 we locate 512, with NQ-skeleton -NQ-N-, in the table, and get Bishops code = 518 - 512 = 6.

[edit] Fritz9 methods

Upon entry to Chess960, Fritz9 prompts the user to enter a position idn or to "Draw Lots". If the user wishes to choose the first rank configuration of pieces, he/she must know how to get at the idn, but, unfortunately, Fritz9 does not use the standard method described above. The table below shows a quick way to get the Fritz9 idn for any SP.

For any SP, after ignoring the Bishops, attention is given first to the Knights (rather than to the Queen). After taking account of the arrangement of the two Knights in 6 squares (skipping over Bishops), the Queen is left with 4 possibilities: 0,1,2,3 (counting from the a-side of the board and skipping over Bishops and Knights). The Queen's position is the number of hyphens to the left of the "Q" in the NQ-skeleton for the SP.

In the table below, the columns correspond to the Queen's position, and, in each column, the ordering is alphabetic with "-" last.

Given an SP, extract the Bishop's code, the NQ-skeleton and its Queen's position. Then, locate, in the appropriate column, the NQ-skeleton at hand, say at No. M. The Fritz9 idn = (Bishop's code) + M. For the standard SP, we extract 6 -NQ-N- and 1 and get Fritz9 idn = 6 + 353 = 359.

          Fritz9 NQ-skeleton Table
-
  1 NNQ---  241 NN-Q--  481 NN--Q-  721 NN---Q
 17 NQN---  257 N-NQ--  497 N-N-Q-  737 N-N--Q
 33 NQ-N--  273 N-QN--  513 N--NQ-  753 N--N-Q
 49 NQ--N-  289 N-Q-N-  529 N--QN-  769 N---NQ
 65 NQ---N  305 N-Q--N  545 N--Q-N  785 N---QN
 81 QNN---  321 -NNQ--  561 -NN-Q-  801 -NN--Q
 97 QN-N--  337 -NQN--  577 -N-NQ-  817 -N-N-Q
113 QN--N-  353 -NQ-N-  593 -N-QN-  833 -N--NQ
129 QN---N  369 -NQ--N  609 -N-Q-N  849 -N--QN
145 Q-NN--  385 -QNN--  625 --NNQ-  865 --NN-Q
161 Q-N-N-  401 -QN-N-  641 --NQN-  881 --N-NQ
177 Q-N--N  417 -QN--N  657 --NQ-N  897 --N-QN
193 Q--NN-  433 -Q-NN-  673 --QNN-  913 ---NNQ
209 Q--N-N  449 -Q-N-N  689 --QN-N  929 ---NQN
225 Q---NN  465 -Q--NN  705 --Q-NN  945 ---QNN

Anyone with Fritz9 can verify this table by entering in the idns. It directly refers to just those SPs with Bishop's code 0 ie. with the Bishops on a1 and b1.

Retrieved from "http://en.wikipedia.org../../../c/h/e/Chess960_starting_position.html"

Category: Chess variants