Generate Chess960 starting position
Chess960 is a variant of chess created by world champion Bobby Fisher. Unlike other variants of the game, Chess960 does not require a different material, but instead relies on a random initial position, with a few constraints:
- as in the standard chess game, all height pawns must be placed on the second rank.
- pieces must stand on the first rank as in the standard game, in random column order but with the two following constraints:
- the bishops must be placed on opposite color squares (i.e. they must be an odd number of spaces apart or there must be an even number of spaces between them)
- the King must be between two rooks (with any number of other pieces between them all)
With those constraints there are 960 possible starting positions, thus the name of the variant.
The purpose of this task is to write a program that randomly generates a Chess960 initial position. You will show the result as the first rank displayed with Chess symbols in Unicode or with the letters King Queen Rook Bishop kNight.
J
Build a table of the starting positions then pick one at random. There are 40320 distinct permutations of 8 items and 5040 distinct permutations of these chess pieces, so little memory is needed to generate the table.
<lang J>row0=: u: 9812+2}.5|i.10 king=: u:9812 rook=: u:9814 bish=: u:9815 pos=: I.@e. bishok=: 1=2+/ .| pos&bish rookok=: pos&rook -: (<./,>./)@pos&(rook,king) ok=: bishok*rookok perm=: A.&i.~ ! valid=: (#~ ok"1) ~.row0{"1~perm 8 gen=: valid {~ ? bind 960</lang>
Example use:
<lang J> gen ♘♗♖♔♗♕♖♘
gen
♗♘♘♗♖♔♖♕
gen
♖♗♔♘♘♕♗♖
gen
♖♔♕♗♗♘♖♘</lang>
Java
Regex inspired by (original) Python Regexp, prints ten examples. <lang java5>import java.util.Arrays; import java.util.Collections; import java.util.List;
public class Chess960{
private static List<Character> pieces = Arrays.asList('R','B','N','Q','K','N','B','R');
public static List<Character> generateFirstRank(){ do{ Collections.shuffle(pieces); }while(!check(pieces.toString().replaceAll("[\\[\\],\\s]", ""))); //List.toString adds some human stuff, remove that
return pieces; }
private static boolean check(String rank){ if(!rank.matches(".*R.*K.*R.*")) return false; //king between rooks if(!rank.matches(".*B(..|....|......|)B.*")) return false; //all possible ways bishops can be placed return true; }
public static void main(String[] args){ for(int i = 0; i < 10; i++){ System.out.println(generateFirstRank()); } } }</lang>
- Output:
[R, N, K, N, R, B, B, Q] [B, B, Q, R, N, K, N, R] [R, K, Q, N, N, R, B, B] [N, B, B, N, R, K, Q, R] [R, Q, B, B, K, N, N, R] [R, K, B, Q, N, B, N, R] [N, N, R, K, Q, B, B, R] [R, N, K, Q, N, B, B, R] [N, R, B, K, Q, B, N, R] [N, Q, N, R, K, B, B, R]
Perl
Directly generates a configuration by inserting pieces at random appropriate places. Each config has an equal chance of being produced. <lang perl>{my @s; sub insert {
my ($c, $p, $step) = @_; $step //= 1; $p += int(rand((@s - $p + 1) / $step)) * $step; splice @s, $p, 0, $c; $c, $p + 1;
}
sub chess960 {
@s = qw/R K R/; insert('Q'); insert(insert('N')); insert(insert('B'), 2); @s
}}
print "@{[chess960]}\n" for 0 .. 10;</lang>
- Output:
R N N B K Q B R N N Q R K R B B Q R B B K N N R B R N N Q B K R N N B R K B R Q R K Q N R B B N Q R K R N N B B Q R K N R N B B R K B R Q B N N R N B B K N R Q Q R N B B N K R
Perl 6
First we keep generating a random piece order until the two bishops are on opposite colors. Then we sort the King and the two rooks. <lang perl6>my enum Pieces < King Queen R1 R2 B1 B2 N1 N2 >; my @order = ^8; @order = Pieces.pick(*) until one(@order[B1, B2]) %% 2; @order[R1, King, R2] .= sort;
(my @squares)[@order] = < K Q R R B B N N >; say @squares;</lang>
- Output:
B N R B K Q N R
Here's a more idiomatic solution that avoids side effects by defining an infinite sequence of random boards via list comprehension with regex filters. <lang perl6>constant chess960 = gather
take $_ if / '♜' .*? '♚' .*? '♜' / and / '♝' .*? '♝' <?{ $/.chars %% 2}> / for < ♚ ♛ ♜ ♜ ♝ ♝ ♞ ♞ >.pick(*).join xx *;
.say for chess960[^10];</lang>
- Output:
♛♝♜♚♝♞♞♜ ♞♛♝♞♜♝♚♜ ♜♝♚♜♝♛♞♞ ♝♜♞♝♛♞♚♜ ♜♚♞♛♜♝♝♞ ♝♜♞♚♛♜♞♝ ♛♝♝♞♜♞♚♜ ♞♝♜♛♝♚♞♜ ♜♚♞♞♝♜♛♝ ♝♝♛♞♜♚♜♞
Python
Python: Indexing
This uses indexing rather than regexps. Rooks and bishops are in upper and lower case to start with so they can be individually indexed to apply the constraints. This would lead to some duplication of start positions if not for the use of a set comprehension to uniquify the, (upper-cased), start positions.
<lang python>>>> from itertools import permutations >>> pieces = 'KQRrBbNN' >>> starts = {.join(p).upper() for p in permutations(pieces)
if p.index('B') % 2 != p.index('b') % 2 # Bishop constraint and ( p.index('r') < p.index('K') < p.index('R') # King constraint or p.index('R') < p.index('K') < p.index('r') ) }
>>> len(starts) 960 >>> starts.pop() 'QNBRNKRB' >>> </lang>
Python: Regexp
This uses regexps to filter permutations of the start position pieces rather than indexing. <lang python>>>> import re >>> pieces = 'KQRRBBNN' >>> bish = re.compile(r'B(|..|....|......)B').search >>> king = re.compile(r'R.*K.*R').search >>> starts3 = {p for p in (.join(q) for q in permutations(pieces))
if bish(p) and king(p)}
>>> len(starts3) 960 >>> starts3.pop() 'QRNKBNRB' >>> </lang>
Python: Correct by construction
Follows Perl algorithm of constructing one start position randomly, according to the rules.
<lang python>>>> from random import choice >>> start = ['R', 'K', 'R'] # Subsequent order unchanged by insertions. >>> for piece in ['Q', 'N', 'N']: start.insert(choice(range(len(start))), piece)
>>> bishpos = random.choice(range(len(start)))
>>> start.insert(bishpos, 'B')
>>> start.insert(random.choice(range(bishpos % 2, len(start), 2)), 'B')
>>> start
['R', 'K', 'B', 'Q', 'N', 'B', 'N', 'R']
>>> </lang>
Ruby
Ruby: shuffle untill all regexes match
Translation of Tcl. <lang ruby>pieces = %i(♔ ♕ ♘ ♘ ♗ ♗ ♖ ♖) regexes = [/♗(..)*♗/, /♖.*♔.*♖/] row = pieces.shuffle.join until regexes.all?{|re| re.match(row)} puts row</lang>
- Output:
♕♖♗♘♔♖♘♗
Ruby: Construct
Uses the Perl idea of starting with [R,K,R] and inserting the rest: <lang ruby>row = [:♖, :♔, :♖] [:♕, :♘, :♘].each{|piece| row.insert(rand(row.size), piece)} [[0, 2, 4, 6].sample, [1, 3, 5, 7].sample].sort.each{|pos| row.insert(pos, :♗)}
puts row.join(" ") </lang>
- Output:
♗ ♘ ♕ ♘ ♖ ♗ ♔ ♖
Tcl
Using regular expressions to filter a random permutation.
<lang tcl>package require struct::list
proc chess960 {} {
while true {
set pos [join [struct::list shuffle {N N B B R R Q K}] ""] if {[regexp {R.*K.*R} $pos] && [regexp {B(..)*B} $pos]} { return $pos }
}
}
- A simple renderer
proc chessRender {position} {
string map {P ♙ N ♘ B ♗ R ♖ Q ♕ K ♔} $position
}
- Output multiple times just to show scope of positions
foreach - {1 2 3 4 5} {puts [chessRender [chess960]]}</lang>
- Output:
♕♖♘♔♗♗♘♖ ♖♔♘♘♗♕♖♗ ♘♖♗♗♕♔♘♖ ♘♕♗♖♔♖♘♗ ♘♘♖♔♗♗♕♖