by Kieran Wild
Chess960, is a chess variant produced by Grandmaster Bobby Fischer by formalizing the rules of Shuffle Chess. Its goal was to create a chess variant in which chess creativity and talent would be more important than memorization and analysis of opening moves. His approach was to create a randomized initial chess position, which would thus make memorizing chess opening move sequences far less helpful. The initial position is set up in a special way and there are 960 such positions, thus the name Chess960.
The starting position for Chess960 must meet certain rules. White pawns are placed on the second rank as in chess. All remaining white pieces are placed randomly on the first rank, but with the following restrictions:
* The king is placed somewhere between the two rooks.
* The 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
Can I suggest a nice little ruby program to generates all 960 possible starting positions and outputs a random one on request.
Output could be as follows.
Starting Position 432:
White
a1 b1 c1 d1 e1 f1 g1 h1
N B B R K R Q N
Black
a8 b8 c8 d8 e8 f8 g8 h8
N B B R K R Q N
Or some better output.
Quiz Summary
There are a surprising number of ways to think about this problem, each leading to a different solution. Let's examine several.
First, you can think of this as a constraints problem. We have the rules of a board setup which are the constraints and any board meeting those rules is one of the 960 positions. Way back when we did the Constraint Processing Ruby Quiz, I learned that the Amb library is a fun way to handle such problems. Here's my solution, using Amb:
setup = Amb.new
count = 0
seen = Hash.new
begin
squares = Array.new(8) { setup.choose(*%w[r n b q k b n r]) }
%w[r n b].each do |piece|
setup.assert(squares.select { |s| s == piece }.size == 2)
end
%w[k q].each do |piece|
setup.assert(squares.select { |s| s == piece }.size == 1)
end
king = squares.index("k")
setup.assert(squares.index("r") < king)
setup.assert(squares.rindex("r") > king)
setup.assert((squares.index("b") + squares.rindex("b")) % 2 == 1)
board = squares.join(' ')
setup.assert(seen[board].nil?)
puts "#{count += 1}: #{board}"
seen[board] = true
setup.failure
rescue
# do nothing, we're done
end
What I really love above this approach is that it requires almost no thought. All I am doing here is translating the rules to code. Ruby and Amb do the rest.
The above code works by building an Amb object that is considering piece placement in eight squares. After that, I define the rules for placement.
Since I gave it all eight pieces as possible choices for each square, the first two rules have to establish the allowed counts for each piece. This prevents Amb from building a position of eight rooks or similar wrong setups.
For the next two rules I locate the king and verify that we have a rook to the left of him as well as to the right. The following rule adds the locations of the two bishops and verifies that we got an odd number. This ensures the bishops are on different colors, since an even plus an odd will be odd but even plus even or odd plus odd both yield even numbers. This group of rules covers the constraints from the quiz description.
The final rule prevents duplicate positions being found. It's needed because positions like the following example seem different to the computer, but not to a chess player:
N1 B1 B2 R1 K R2 Q N2
N2 B2 B1 R2 K R1 Q N1
With the rules in place, Amb will have found a viable solution. I print that out, then manually trigger a failure(), to cause it to find another. When it fails to find one an Exception will be thrown. I catch that and exit quietly since we will have seen all 960 positions at that point.
The downside of this approach is that Amb uses Ruby's continuations to under the hood to backtrack and find new solutions. Those are a bit on the slow side and this simple script of mine takes about six and a half minutes to complete, on my box. One solution to this is just to generate the positions once and cache them for future runs but there were other solutions that could think a lot faster.
For a faster solution, let's shift how we are thinking about the problem. Another approach is to think of this challenge as a permutations problem. We really just need to examine all possible permutations of the eight pieces and select those that match the quiz rules. Multiple solutions did this, including the following code from David Tran:
return [pieces] if pieces.length <= 1
result = []
pieces.uniq.each do |p|
_pieces = pieces.dup
_pieces.delete_at(pieces.index(p))
permutation(_pieces).each do |perm|
result << (perm << p)
end
end
result
end
results = permutation("RNBKQBNR".split(//)).select do |position|
r1 = position.index('R')
r2 = position.rindex('R')
b1 = position.index('B')
b2 = position.rindex('B')
k = position.index('K')
r1 < k && k < r2 && ((b1+b2) % 2 != 0)
end
puts "Total positions = #{results.length}"
puts results[rand(results.length)].join(' ')
The permutation() method here is a recursive generator of all possible permutations. It works by adding each() uniq() piece to all possible smaller permutations. Those are found by removing one piece from the set each time and recursing.
The rest of the code calls that method and then select()s the positions matching the quiz rules. Those rules are almost identical to my implementation of them that we examined earlier.
This code does the same thing as mine but runs in under a second on my box.
Shifting the approach again, several methods have been developed to help players create positions using these rules as needed, some using dice. Bodlaender's dice-rolling method is a pretty easy system to translate into code and Jamie Macey did just that:
attr_reader :board_id, :board
def initialize
@board = generate_board(bodlaender_line)
end
def generate_board(white)
# Black's starting line is mirror of white's
black = white.map{|piece| piece.downcase}
# middle of board is always the same
middle = [
%w(p p p p p p p p),
%w(_ _ _ _ _ _ _ _),
%w(_ _ _ _ _ _ _ _),
%w(_ _ _ _ _ _ _ _),
%w(_ _ _ _ _ _ _ _),
%w(P P P P P P P P)
]
# add back rows
[black] + middle + [white]
end
def bodlaender_line
free = (0...8).to_a
white = []
dark_bishop = rand(4) * 2
light_bishop = rand(4) * 2 + 1
white[dark_bishop] = 'B'
white[light_bishop] = 'B'
free.delete(dark_bishop)
free.delete(light_bishop)
queen = rand(6)
white[free[queen]] = 'Q'
free.delete_at(queen)
knight1 = rand(5)
white[free[knight1]] = 'N'
free.delete_at(knight1)
knight2 = rand(4)
white[free[knight2]] = 'N'
free.delete_at(knight2)
white[free[0]] = 'R'
white[free[1]] = 'K'
white[free[2]] = 'R'
white
end
end
The first two methods are trivial with initialize() kicking off the process and generate_board() building a board representation. The interesting stuff happens in bodlaender_line().
This algorithm works with a collection of free indices and an Array of the final piece arrangement. As pieces are placed in the Array, those indices are pulled from the free list so they won't be reused.
The first step is to place both bishops. That's done by choosing a random number between one and four and placing it on the selected light or dark square. After that, a random selection places the queen on one of the six remaining squares. The same technique is used to place the knights on the remaining five and then four squares. That leaves us three empty squares which must be R, K, and R, in that order, to satisfy the rules.
Making one more leap of thought with regard to this problem, there has been an effort to enumerate all 960 positions. This has a lot of value to chess players since we can record the game using our usual techniques and just add a note like, "Started from Chess960 position #351." Even better, once you have a system for enumerating the positions, you can use that system to build the entire list or select a position. Morton Goldberg gave us the code for that:
BISHOP_TABLE = [
"BB------", #0
"B--B----", #1
"B----B--", #2
"B------B", #3
"-BB-----", #4
"--BB----", #5
"--B--B--", #6
"--B----B", #7
"-B--B---", #8
"---BB---", #9
"----BB--", #10
"----B--B", #11
"-B----B-", #12
"---B--B-", #13
"-----BB-", #14
"------BB" #15
]
N5N_TABLE = [
"NN---", #0
"N-N--", #1
"N--N-", #2
"N---N", #3
"-NN--", #4
"-N-N-", #5
"-N--N", #6
"--NN-", #7
"--N-N", #8
"---NN" #9
]
# ...
The official numbering scheme, invented by Reinhard Scharnagl, works by using simple charts to position the pieces. Above you can see Morton's translation of the two charts he will use, giving piece placements and their indices. The knight charts are narrower because they are placed after the bishops and queen, taking three squares out of consideration.
Here's the main algorithm from Morton's code (with a minor fix from me):
def initialize(number)
q, @bishop_index = number.divmod 16
@knight_index, @queen_index = q.divmod 6
@white_pieces = BISHOP_TABLE[@bishop_index].split('')
@white_pieces[nth_dash(@queen_index)] = 'Q'
knights = N5N_TABLE[@knight_index]
m = knights.index('N')
n = knights.index('N', m + 1)
m, n = nth_dash(m), nth_dash(n)
@white_pieces[m] = 'N'
@white_pieces[n] = 'N'
@white_pieces[@white_pieces.index('-')] = 'R'
@white_pieces[@white_pieces.index('-')] = 'K'
@white_pieces[@white_pieces.index('-')] = 'R'
end
def nth_dash(n)
dashes = []
@white_pieces.each_with_index { |ch, i| dashes << i if ch == '-' }
dashes[n]
end
# ...
Most of the clever work is done in initialize(). First, a little math is used to find the lookup index on the bishop's chart, an index for the queen, and an index on the knight's chart. The row selected from the bishop's chart becomes the basis for the final arrangement of pieces and nth_dash() is used to properly slot the queen in that template. The knight's are then pulled from their chart by index and nth_dash() is again used to place them. The three squares left then must be a rook, king, and rook in that order.
The rest of Morton's code (again with minor changes by me) is just for displaying the results:
def inspect
@white_pieces.join
end
def to_s
white_pieces = @white_pieces.join + "\n"
white_pawns = 'P' * 8 + "\n"
black_pieces = white_pieces.downcase
black_pawns = 'p' * 8 + "\n"
empty = ('.' * 8 + "\n") * 4
black_pieces + black_pawns + empty + white_pawns + white_pieces
end
end
if __FILE__ == $0
begin
if ARGV.empty? then n = rand(960)
else
n = ARGV.first.to_i
raise StandardError unless (0..959).include?(n)
end
puts "Initial position #{n}"
print Chess960.new(n).to_s
rescue StandardError
puts "Usage: #{$PROGRAM_NAME} [<integer>]"
puts "where <integer> is in 0..959"
puts "Omitting <integer> produces a random initial position"
end
end
If you want to read more about the systems for assigning pieces, check out:
and:
There were a lot more creative elements in the solutions I didn't cover. Jamie Macey even built a complete Camping application to display the positions. Definitely take the time to look over them. It's worth it.
My thanks to all for another great quiz. I'm a big chess nut some problems like this always thrill me.
There will be no Ruby Quiz tomorrow. I'll be busy having a merry Christmas and I wish the same for others. See you in a week!
