# Chess960 (#106)

The three rules of Ruby Q.:

1. Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.

2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

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.

Ruby Q. [email protected] writes:

a8 b8 c8 d8 e8 f8 g8 h8
N B B R K R Q N

Or some better output.

Let me suggest that another potential output format is an html page
that when viewed in a browser looks like the opening format. I happen
to think that the chess boards shown on
PmWiki | Cookbook / ChessMarkup
look particularly nice, and shouldn’t be too hard to duplicate.
(they’re done as 8x8 tables, with the colors of the squares done by
CSS and the pieces being .png images with transparency) Presumably
some enterprising person could then churn out a Rails page that showed
a given starting position.

There’s also this basic ascii art method: (black is the lowercase
letters)

nbbrkrqn
pppppppp

PPPPPPPP
NBBRKRQN

(It’s traditional to show the place where white starts at the bottom,
and to number the rows upwards - that is, row “8” is at the top of the
diagram)

Then there’s a FEN string inside PGN notation:

[Event “Starting Position 432”]
[SetUp “1”]
[FEN “nbbrkrqn/pppppppp/8/8/8/8/PPPPPPPP/NBBRKRQN w KQkq - 0 1” ]

The advantage of that format is that you can feed it right into
X-Board, WinBoard, or any other chess program that accepts PGN
notation, and it’ll start play from that setup. (More on what that
FEN string means at
Forsyth–Edwards Notation - Wikipedia )

On Dec 15, 2006, at 1:25 PM, Daniel M. wrote:

NBBRKRQN
Or with a touch more window dressing:

±–±--±–±--±–±--±–±--+
| n | b | b | r | k | r | q | n |
±–±--±–±--±–±--±–±--+
| p | p | p | p | p | p | p | p |
±–±--±–±--±–±--±–±--+
| | . | | . | | . | | . |
±–±--±–±--±–±--±–±--+
| . | | . | | . | | . | |
±–±--±–±--±–±--±–±--+
| | . | | . | | . | | . |
±–±--±–±--±–±--±–±--+
| . | | . | | . | | . | |
±–±--±–±--±–±--±–±--+
| P | P | P | P | P | P | P | P |
±–±--±–±--±–±--±–±--+
| N | B | B | R | K | R | Q | N |
±–±--±–±--±–±--±–±--+

James Edward G. II

On Dec 15, 2006, at 9:25 PM, Daniel F. wrote:

Also, is the range of the numbers 0-956 or 1-960? I’ve seen things
saying that both are acceptable with no definitive answer.

James Edward G. II

On Dec 16, 2006, at 12:07 AM, James Edward G. II wrote:

On Dec 15, 2006, at 9:25 PM, Daniel F. wrote:

Also, is the range of the numbers 0-956 or 1-960? I’ve seen
things saying that both are acceptable with no definitive answer.

I don’t see how the Ruby interpreter can answer this question. How
the starting positions are to be numbered is a problem-domain-
specific issue. The interpreter knows nothing about the problem domain.

Ruby arrays being zero-based might make the range 0…959 more
convenient to use, but this certainly doesn’t preclude the 1…960

Regards, Morton

Quoting Morton G. [email protected]:

the starting positions are to be numbered is a problem-domain-
specific issue. The interpreter knows nothing about the problem domain.

Ruby arrays being zero-based might make the range 0…959 more
convenient to use, but this certainly doesn’t preclude the 1…960

Regards, Morton

I believe the comment was meant to say, “write a correct Ruby program to
solve
the problem and the correct number will emerge.”

Is that the real starting position 432? Or was that just a made up
number?

http://img308.imageshack.us/img308/9290/positions400479up0.jpg Gives
BBRNNQKR as number 432 as does my program.

Also, is the range of the numbers 0-956 or 1-960? I’ve seen things
saying that both are acceptable with no definitive answer.

Thanks,
Dan

Ruby Q. wrote:

``````Starting Position 432:
``````

On Dec 15, 2006, at 11:35 PM, Morton G. wrote:

the starting positions are to be numbered is a problem-domain-
specific issue. The interpreter knows nothing about the problem
domain.

Ruby arrays being zero-based might make the range 0…959 more
convenient to use, but this certainly doesn’t preclude the 1…960

0-959 was not an option in Daniel’s email (look again) and I’m
confident of Ruby’s ability to count to 960.

James Edward G. II

Yeah, that was my typo.

I made my program 0 based because that is what most of the things online
seem to use, but that doesn’t make it correct.

Dan

On 12/15/06, Daniel M. [email protected] wrote:

PmWiki | Cookbook / ChessMarkup
look particularly nice, and shouldn’t be too hard to duplicate.
(they’re done as 8x8 tables, with the colors of the squares done by
CSS and the pieces being .png images with transparency) Presumably
some enterprising person could then churn out a Rails page that showed
a given starting position.

I haven’t bothered generating the full table, I’m just randomly
generating the layouts. I thought the app was a bit too lightweight
for Rails, but I stole the images from pmwiki.org and set up a camping
app here: http://www.tracefunc.com:3301/ - just refresh for a
different layout.

If I can find more time this weekend, I’ll see about doing the table
lookup and adding that info to the page.

• Jamie

Attached is my solution.

-Chunyun

Sample output:

Generated 960 starting positions.

Starting position 93:

|+++++++++++++++++++++++++++++++|
| b | n | r | b | k | q | r | n |
|+++++++++++++++++++++++++++++++|
| p | p | p | p | p | p | p | p |
|+++++++++++++++++++++++++++++++|
| | | | | | | | |
|+++++++++++++++++++++++++++++++|
| | | | | | | | |
|+++++++++++++++++++++++++++++++|
| | | | | | | | |
|+++++++++++++++++++++++++++++++|
| | | | | | | | |
|+++++++++++++++++++++++++++++++|
| P | P | P | P | P | P | P | P |
|+++++++++++++++++++++++++++++++|
| B | N | R | B | K | Q | R | N |
|+++++++++++++++++++++++++++++++|

At the risk of being a spoiler (hint: don’t go to the linked
Wikipedia article), the position 960 can also be called position 0:

``````  The accurate sequence of White's Chess960 starting array
could be derived from its number as follows:
a) Divide the number by 960, determine the

remainder (0 ... 959) and use that number

thereafter.
``````

-Rob

On Dec 16, 2006, at 10:57 AM, Daniel F. wrote:

James Edward G. II

Ruby Q. wrote:

The starting position for Chess960 must meet certain rules. White pawns are

Can I suggest a nice little ruby program to generates all 960 possible starting
positions and outputs a random one on request.

which = ( ARGV.first || rand(960) + 1 ).to_i
count = 0

(1…6).each{|k|
(0…k).each{|r1|
(k+1…7).each{|r2|
((0…7).to_a - [k,r1,r2]).each{|q|
used = [k,r1,r2,q]
((0…7).select{|i| i % 2 == 0} - used).each{|b1|
((0…7).select{|i| i % 2 == 1} - used).each{|b2|
count += 1
if which == count
puts “Position #{ count }”
s = ‘N’ * 8
[k,q,r1,r2,b1,b2].zip(%w(K Q R R B B)).each{|i,p|
s[i] = p }
puts s.downcase,‘p’*8,(’.’*8+"\n")*4,‘P’*8,s
end } } } } } }

This is not a very elegant or concise or even efficient solution. I
tried
finding the weirdest solution I could think of. The idea is to reduce
(or in
this case, enlarge the problem to the exact-cover problem. So I
formalized 6 constraints that need to be satisfied by a solution:

1. all the pieces need to be placed
2. all the columns need to be occupied
3. the left rook must appear to the left of the king and the right rook
to
the right
4. the left bishop must appear to the left of the right one
5. the left knight must appear to the left of the right knight
6. each color must be occupied by exactly one bishop

The program constructs rows of a DLX matrix (if you don’t know this
algorithm, it’s described here:
It then uses a DLX solver that I wrote to find legal combinations of
piece
placements. The enumeration order is not the same as the one on the
internet
but is deterministic.

The file ‘dlx.rb’ contains the DLX solver.

Mushfeq.

## Here is my solution to #106 I thaught I’ll make a more readable amb based soluytion but I did not succeed so far :(, maybe I’ll come up with it before not too long.

#!/usr/bin/ruby
class Chess960
class ::Range
class << self
def free= args
@@free = args
end
end
def each_free
each do
|ele|
next unless @@free.include? ele
@@free.delete ele
yield ele
@@free.unshift ele
end
end #def each_free
end

``````N = 8
def initialize
@solutions = []
Range.free = [*1..N]
init
generate
end
def [] sol_nb
@solutions[ sol_nb ]
end

private
def init
@sol="Q " * N
end
def generate
(1..N-1).each_free do
|@b1|
(@b1.succ..N).each_free do
|@b2|
next if @b1 & 1 == @b2 & 1
(1..N-2).each_free do
|@r1|
(@r1.succ..N-1).each_free do
|@k|
(@k.succ..N).each_free do
|@r2|
(1..N-1).each_free do
|@n1|
(@n1.succ..N).each_free do
|@n2|
save_solution
end
end
end #(@k.succ..N).each_free do
end
end #(1..N-2).each_free do
end
end
end
def save_solution
@sol[2*(@b1-1)]= ?B
@sol[2*(@b2-1)]= ?B
@sol[2*(@r1-1)]= ?R
@sol[2*(@r2-1)]= ?R
@sol[2*(@n1-1)]= ?N
@sol[2*(@n2-1)]= ?N
@sol[2*(@k-1)] = ?K

@solutions << @sol
init
end
``````

end

## Cheers Robert

“The real romance is out ahead and yet to come. The computer revolution
hasn’t started yet. Don’t be misled by the enormous flow of money into
incomplete ideas.”

• Alan Kay

#!/usr/bin/ruby

# and there is a fix of the “place 2 Knights instead of 1 Queen” error.

class Amb
class ExhaustedError < RuntimeError; end

def initialize
@fail = proc { fail ExhaustedError, “amb tree exhausted” }
end

def choose(*choices)
prev_fail = @fail
callcc { |sk|
choices.each { |choice|
callcc { |fk|
@fail = proc {
@fail = prev_fail
fk.call(:fail)
}
sk.call(choice)
}
}
@fail.call
}
end

def assert(cond)
choose unless cond
end
end

class Chess960
N = 8
Queen = ?Q
King = ?K
Rook = ?R
Bishop = ?B
def initialize
@amb = Amb.new
@solutions = []
init
generate
raise RuntimeError, “Illegal Number of solutions
#{@solutions.length}”
unless
@solutions.length == 960
end
def [] sol_nb
@solutions[ sol_nb ]
end

``````private
def init
@sol="N " * N
end
def generate
@b1 = @amb.choose( *1..N-1 )
@b2 = @amb.choose( *@b1.succ..N )
@amb.assert @b1 & 1 != @b2 & 1
@r1 = @amb.choose( *1..N-2 )
@k = @amb.choose( *@r1.succ..N-1 )
@r2 = @amb.choose( *@k.succ..N )
@q = @amb.choose( *1..N )
# This late check makes the whole thing more readable
# we can easily afford the additional computations
@amb.assert [@b1,@b2,@r1,@k,@r2,@q].uniq.length == 6
save_solution
rescue Amb::ExhaustedError
end
def save_solution
@sol[2*(@b1-1)]= Bishop
@sol[2*(@b2-1)]= Bishop
@sol[2*(@r1-1)]= Rook
@sol[2*(@r2-1)]= Rook
@sol[2*(@q-1)]= Queen
@sol[2*(@k-1)] = King
@solutions << @sol
init
@amb.choose
end
``````

end

c = Chess960.new
puts %<enter a number to show a specific solution (0 based) or
enter r for a random solution or
enter q to go back to work>
until (n = gets.strip) =~ /^q/i
i = n.to_i
i = rand(960) if n =~ /^r/i
puts “Solution #{i}”
puts c[i]
end

## Cheers Robert

“The real romance is out ahead and yet to come. The computer revolution
hasn’t started yet. Don’t be misled by the enormous flow of money into
incomplete ideas.”

• Alan Kay

On Dec 17, 2006, at 1:28 PM, Robert D. wrote:

Here goes my second solution, looks a little bit better, using Jim
Weirich’s Amb class

I decided to try it with Amb too. It’s slow but works:

#!/usr/bin/env ruby -w

require “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

END

James Edward G. II

On 12/15/06, Ruby Q. [email protected] wrote:

The starting position for Chess960 must meet certain rules. White pawns are

Can I suggest a nice little ruby program to generates all 960 possible starting
positions and outputs a random one on request.

I just did up a random generator using the die-rolling method
mentioned on Wikipedia. As such, it’s not deterministic, so my boards
can’t be referenced by number.

After my Chess360 class is a Camping app to host it - my current code
is live at http://tracefunc.com:3301/ - the images were shamelessly
stolen from
PmWiki | Cookbook / ChessMarkup, and the whole thing
Index - set_trace_func - I’d’ve attached it but ruby-talk
rejected it as too large a message.

• Jamie

class Chess960

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)
]

[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

###########

require ‘rubygems’
require ‘camping’
require ‘chess960’

Camping.goes :Chess

module Chess::Controllers

# main page

class Index < R ‘/’
def get
@chess = Chess960.new
render :index
end
end

# image passthrough

class Images < R ‘/images/(.+)’
MIME_TYPES = {‘.png’ => ‘image/png’}
PATH = FILE[/(.*)//, 1]

``````def get(path)
``````

“text/plain”
unless path =~ /../ # sample test to prevent directory traversal
attacks
else
“404 - Invalid path”
end
end
end
end

module Chess::Views
def layout
html do
body do
style :type => ‘text/css’ do
"#chess { border-collapse: collapse;
float: left; margin-right: 2em; } " +
".dark { background-color: #888; } " +
".light { background-color: #ddd; } " +
".thin { width: 50em; } "
end
self << yield
end
end
end

def index
c = 0
table.chess! do
@chess.board.each do |row|
c = 1 - c
tr do
row.each do |tile|
c = 1 - c
td :class => c==0 ? ‘light’ : ‘dark’ do
img :src => “images/#{tile}.png”
end
end
end
end
end
h1 “Chess 960”
div.thin do
text “

Randomly created board, using the #{a ‘Bodlaendar’, :href
=>
Fischer random chess - Wikipedia”}
method for generating piece order.

p “Result was #{@chess.board.last.join(”, “)}.”
end
end
end

Here’s my solution. I hadn’t realized that there was an official
numbering scheme to the Chess960 starting positions. So my program
uses an ad hoc numbering scheme.

The program uses a simple recursive descent technique. Seen positions
(full and parital) are memorizeed so as not to revisit them again. All
possible board positions are generated and placed in an array, and the
number chosen is used as an index into this array.

## Eric

Considering Ruby Training? Visit http://learnruby.com .

# is between the rooks.

def good?(layout)
bishop1 = layout.index(:b)
bishop2 = layout.rindex(:b)
return false if bishop1 != bishop2 && bishop1 % 2 == bishop2 % 2

rook1 = layout.index(:r)
rook2 = layout.rindex(:r)
king = layout.index(:k)
!(rook1 != rook2 && (king.nil? || king < rook1 || king > rook2))
end

# avoid duplicate efforts.

def generate(pieces, layout, layout_set, seen_layouts)
if pieces.empty? : layout_set << layout.dup # complete layout
elsif seen_layouts[layout] : return # layout already seen
else # partial layout; do
next square
seen_layouts[layout.dup] = true
pieces.each_index do |i|
layout.push(pieces.delete_at(i))
generate(pieces, layout, layout_set, seen_layouts) if
good?(layout)
pieces.insert(i, layout.pop)
end
end
end

# Generates a string that describes a given layout.

def display(layout)
[[“White”, 1], [“Black”, 8]].map do |color, rank|
color << “\n” <<
(‘a’…‘h’).map { |file| file + rank.to_s }.join(" “) << “\n” <<
layout.map{|sym| sym.to_s.upcase}.join(” “) << “\n”
end.join(”\n")
end

layouts = []

generate([:r, :n, :b, :q, :k, :b, :n, :r], [], layouts, {})

if ARGV.size > 1
\$stderr.puts “Usage: #{\$0} [layout-index]”
exit 1
elsif ARGV.size == 1
layout_index = ARGV[0].to_i
if layout_index < 1 || layout_index > layouts.size
\$stderr.puts “Error: layout-index must be from 1 to
#{layouts.size}.”
exit 2
end
else
layout_index = rand(layouts.size) + 1
end

puts “Layout ##{layout_index}:\n\n”
puts display(layouts[layout_index - 1])

D:\Docs\ruby>ruby chess960.rb
[Event “Starting Position 787”]
[SetUp “1”]
[FEN “bbrnkrqn/pppppppp/8/8/8/8/PPPPPPPP/BBRNKRQN w KQkq - 0 1” ]

``````a b c d e f g h
``````

±----------------+
8 | b b r n k r q n | 8
7 | p p p p p p p p | 7
6 | . . . . . . . . | 6
5 | . . . . . . . . | 5
4 | . . . . . . . . | 4
3 | . . . . . . . . | 3
2 | P P P P P P P P | 2
1 | B B R N K R Q N | 1
±----------------+
a b c d e f g h

D:\Docs\ruby>cat chess960.rb
class Array
def permute
if empty?
[]
elsif size == 1
[self]
else
ret = []
tails = dup
ret.concat tails.permute.map {|tail| [head, *tail] }
end
ret
end
end
end

module Chess960

def all
_all.dup
end

def random
_all[rand(960)].dup
end

def ascii_board_showing(n)
top_row = _all[n].join(’ ')
bottom_row = top_row.upcase
<<-END
a b c d e f g h
±----------------+
8 | #{ top_row } | 8
7 | p p p p p p p p | 7
6 | | 6
5 | | 5
4 | | 4
3 | | 3
2 | P P P P P P P P | 2
1 | #{ bottom_row } | 1
±----------------+
a b c d e f g h
END
end

def fen_notation_for(n)
“#{all[n]}/pppppppp/8/8/8/8/PPPPPPPP/#{all[n].join.upcase} w KQkq -
0 1”
end

def pgn_notation_for(n)
<<-END
[Event “Starting Position #{n}”]
[SetUp “1”]
[FEN “#{fen_notation_for(n)}” ]
END
end

private

``````def _all
@all ||= %w[r n b q k b n r].permute.select {|x|
``````

valid_position?(x) }
end

``````def valid_position?(array)
# array.sort == %w [b b k n n q r r] &&
(array.index("b") + array.rindex("b")) % 2 == 1 &&
array.grep(/[rk]/) == %w[r k r]
end
``````

extend self
end

if \$0 == FILE

n = rand(960)
puts Chess960.pgn_notation_for(n)
puts
puts Chess960.ascii_board_showing(n)
end