Talk:Generate Chess960 starting position
clarifying wording
In the first rule, the wording states ··· all eight pawns must be placed on the second rank.
There are sixteen pawns.
How about A player's eight pawns must be ··· or something similar. -- Gerard Schildberger (talk) 04:53, 8 May 2014 (UTC)
- I don't think that's necessary. There are also two queens, two kings, four rooks and so on. I think it's obvious enough that we're talking about the placing of the pieces for each camp.--Grondilu (talk) 05:52, 8 May 2014 (UTC)
- It doesn't really matter for this task (since we only display pieces for the first rank, for one player). Hypothetically speaking, though, each player could be thought of as having a second rank, which would allow all 16 pawns to be placed. --Rdm (talk) 05:54, 8 May 2014 (UTC)
- There are eight ranks on a chessboard, the 1st rank is where white's major and minor pieces are initially positioned, rank 8 is where black's major and minor pieces are initially positioned. The 2nd rank is where (all 8) white's pawns are initially positioned, the 7th rank is where all the black's pawns are initially positioned. The black player doesn't have a 1st or 2nd rank in that those ranks are occupied by white pieces. Ranks aren't owned by either white or black, the ranks are numbered from the "bottom" of the chessboard, where the "bottom" is occupied by the white player's major and minor pieces. As long as the Rosetta Code task is stating the placement of all the pawns, it should be accurate and conform to the notations and wording of the Fédération Internationale des Échecs (FIDE), aka, the World Chess Federation. -- Gerard Schildberger (talk) 20:28, 8 May 2014 (UTC)
random starting position
A trivial REXX program (of two statements): <lang rexx>if random(0,1) then say 'NBQRBKNR'
else say 'QBNRBKNR'</lang>
would, in the strictest sense, fullfill a random Chess960 starting position (albeit only two random positions).
However, I believe the spirit of the requirement of random be that the random position would produce any of the 960 possible starting positions. -- Gerard Schildberger (talk) 04:53, 8 May 2014 (UTC)
To this end, I wrote a REXX program (2nd programming entry) that randomly generates all possible unique 960 Chess960 starting positions and it shows a log of the results (unique starting positions) after each one-thousand generations.
This would make a good extension to the requirements to verify that the programming examples being used to create a random Chess960 starting position do indeed produce all possible starting positions. -- Gerard Schildberger (talk) 05:42, 8 May 2014 (UTC)
- Modified task description to force entries to be able to produce one of the 960. --Paddy3118 (talk) 05:52, 8 May 2014 (UTC)
- Gerard, I did a similar test (for Ruby) and it usually generates all 960 poisitions in about 7500 tries. I suspect the REXX code is biased towards rooks on the right side, but I could very well be wrong...--Steenslag (talk) 14:20, 12 May 2014 (UTC)
- Yes, the placement is biased to the right because of the requirement (rule) that the king has to be placed between the two rooks, which necessitated (in the REXX code) the shifting of the placement of the 2nd rook to be placed at least two positions to the right. I don't know if the addition of more code which would allow the placement of the 2nd rook to be also placed two positions the left of the 1st rook would provide better randomness of rook placement. I'll be looking into that possibility. Here is a histogram of one million random placements (of both rooks):
(1st one-million trial) file 1=166381 ======================== file 2=166437 ======================== file 3=194882 ============================ file 4=227628 ================================= file 5=269865 ======================================= file 6=324213 =============================================== file 7=243282 =================================== file 8=407312 ============================================================ (2nd one-million trial) file 1=166404 ======================== file 2=166747 ======================== file 3=194618 ============================ file 4=227543 ================================= file 5=269279 ======================================= file 6=325874 =============================================== file 7=240176 =================================== file 8=409359 ============================================================
{file as in rank and file on a chessboard.}
(Follow-up on the random placement of the two rooks.) I re-worked the REXX code and it now has a much more randomness in the (proper) placement of the two rooks. -- Gerard Schildberger (talk) 15:19, 12 May 2014 (UTC)
(1st one-million trial, new code) file 1=269306 =========================================================== file 2=246706 ====================================================== file 3=241984 ===================================================== file 4=240403 ===================================================== file 5=242776 ===================================================== file 6=242128 ===================================================== file 7=245850 ====================================================== file 8=270847 ============================================================ (2nd one-million trial, new code) file 1=269306 =========================================================== file 2=246706 ====================================================== file 3=241984 ===================================================== file 4=240403 ===================================================== file 5=242776 ===================================================== file 6=242128 ===================================================== file 7=245850 ====================================================== file 8=270847 ============================================================
The REXX program to produce the histograhs (shown above) is: <lang rexx>/*REXX program generates a histogram of 100,000 rook placement positions*/ parse arg seed times . /*obtain optional args from C.L. */ if times== then times=100000 /*use default for TIMES? {100k} */ if seed\== then call random ,,seed /*if SEED specified, use the seed*/ rooks.=0 /*zero the rook position counters*/
do t=1 for times /*════════════════════════════════════════════════════*/ r1=random(1 ,8); /*place the first rook on rank1.*/ r1m=r1-1; r1p=r1+1 /*used for faster comparisons. */
do forever; r2=random(1,8) /*place the second rook on rank1.*/ if r2==r1 then iterate /*position is the same as rook1. */ if r2==r1m then iterate /*it's immediately before rook1. */ if r2==r1p then iterate /* " " after " */ leave /*found a good 2nd rook placement*/ end /*forever*/
rooks.r1=rooks.r1+1 /*bump rook (r1) position counter*/ rooks.r2=rooks.r2+1 /* " " (r2) " " */ end /*t ══════════════════════════════════════════════════════════════*/
mx=0; do j=1 for 8; mx=max(mx,rooks.j); end /*find max histo value*/
do k=1 for 8 /*display the eight files numbers*/
say 'file' k"="rooks.k copies('=', 60 * rooks.k % mx)
end /*k*/ /* [↑] display a nice histogram.*/
/*stick a fork in it, we're done.*/</lang>
Many thanks to (user) Steenslag for pointing out the un-randomness of the rook placement in the REXX code.
I've updated the REXX programs.-- Gerard Schildberger (talk) 15:19, 12 May 2014 (UTC)
Even with the new REXX code (of better rook placement), it still takes the same amount of generations to produce all 960 variations. -- Gerard Schildberger (talk) 15:52, 12 May 2014 (UTC)
My own code (in the Construct section) was biased too. The rook positions histogram should look like: {1=>360, 2=>252, 3=>192, 4=>156, 5=>156, 6=>192, 7=>252, 8=>360}, as it does for the 1920 rooks in the 960 startpositions, but it did not. It was not even remotely symmetrical. It appeared I was off by one on a rand call.-Steenslag (talk) 20:47, 12 May 2014 (UTC)
unviewable symbols
When I view the task page, the Chess symbols in Unicode appear as small square boxes with numbers in them (on Firefox Aurora), or empty boxes in Microsoft Internet Explorer, both under Windows/XP. Is there something special that needs to be done to make them viewable? -- Gerard Schildberger (talk) 06:21, 8 May 2014 (UTC)
- I also find them hard to see. Maybe increase the font size. Anyway that's why I also allowed to use roman letters.--Grondilu (talk) 06:27, 8 May 2014 (UTC)
- Er, no. My screen is about two or three miles wide, and I can make the font ... well, ginormous. The symbols (which are in a true square box) are as follows:
┌──┐┌──┐┌──┐┌──┐┌──┐┌──┐┌──┐┌──┐ │26││26││26││26││26││26││26││26│ │58││57││56││54││57││55││56││58│ └──┘└──┘└──┘└──┘└──┘└──┘└──┘└──┘
- They are small in "normal" viewing mode and they occupy "one character", so you can image how small the glyphs are. -- Gerard Schildberger (talk) 06:44, 8 May 2014 (UTC)
- The numbers are the Unicode code points in hex that have no glyph in your current font. For fonts that support these symbols see for example Test for Unicode support in Web browsers.
- In Firefox you would need to change the Sans Serif font (Preferences - Content - Fonts&Colours/Advanced...). --Andreas Perstinger (talk) 09:36, 8 May 2014 (UTC)
As an aside, some languages don't support Unicode characters. -- Gerard Schildberger (talk) 06:44, 8 May 2014 (UTC)
As another aside, the chess symbols have been in Unicode for more than 20 years now. --TimToady (talk) 19:31, 8 May 2014 (UTC)
Python: Correct by construction?
Originally wrong but corrected. This is the check: <lang python>from pprint import pprint as pp
def check(start):
'Check that B/b are on different colours'
assert (start.index('b') % 2) != (start.index('B') % 2), .join(start)
def generate_all_bishpos():
start = list('______') # Should be all-but Bishops but any six chars will do
starts = []
for bishpos in range(len(start)+1):
start2 = start[::]
start2.insert(bishpos, 'B')
for bishpos2 in range(bishpos+1, len(start)+2, 2):
start3 = start2[::]
start3.insert(bishpos2, 'b')
check(start3)
starts.append(tuple(start3))
return starts
starts = sorted(generate_all_bishpos()) print('Generated all separations of Bishops:') pp(starts, width=50)
import re from random import choice
def random960():
start = ['R', 'K', 'R'] # Subsequent order unchanged by insertions.
#
for piece in ['Q', 'N', 'N']:
start.insert(choice(range(len(start)+1)), piece)
#
bishpos = choice(range(len(start)+1))
start.insert(bishpos, 'B')
start.insert(choice(range(bishpos + 1, len(start) + 1, 2)), 'b')
return start
return .join(start).upper()
- print(random960())
def _random960():
"Exact copy of the one above except other pieces are all '_'"
start = ['_', '_', '_'] # Subsequent order unchanged by insertions.
#
for piece in ['_', '_', '_']:
start.insert(choice(range(len(start)+1)), piece)
#
bishpos = choice(range(len(start)+1))
start.insert(bishpos, 'B')
start.insert(choice(range(bishpos + 1, len(start) + 1, 2)), 'b')
return start
return .join(start).upper()
print('\nCheck we can generate all separations of bishops randomly:') s, i = set(), 0 while len(s) < len(starts) and i < 9999:
start = _random960() check(start) s.add(tuple(start)) i += 1
s = sorted(s)
if s == starts:
print(' Generated all the %i separations in %i attempts' % (len(starts), i))
else:
print(' Error! could not do it in %i' % i)
print('\nCheck we can generate all 960 randomly:')
s960, i = set(), 0
while len(s960) < 960 and i < 99999:
start = random960()
check(start)
s960.add(tuple(start))
i += 1
if not i % 500:
print(' @%5i %5i/960' % (i, len(s960)))
s960 = sorted(s960)
if len(s960) == 960:
print(' Generated all the %i separations in %i attempts' % (960, i))
else:
print(' Error! could not do it in %i' % i)</lang>
- Output:
Generated all separations of Bishops:
[('B', '_', '_', '_', '_', '_', '_', 'b'),
('B', '_', '_', '_', '_', 'b', '_', '_'),
('B', '_', '_', 'b', '_', '_', '_', '_'),
('B', 'b', '_', '_', '_', '_', '_', '_'),
('_', 'B', '_', '_', '_', '_', 'b', '_'),
('_', 'B', '_', '_', 'b', '_', '_', '_'),
('_', 'B', 'b', '_', '_', '_', '_', '_'),
('_', '_', 'B', '_', '_', '_', '_', 'b'),
('_', '_', 'B', '_', '_', 'b', '_', '_'),
('_', '_', 'B', 'b', '_', '_', '_', '_'),
('_', '_', '_', 'B', '_', '_', 'b', '_'),
('_', '_', '_', 'B', 'b', '_', '_', '_'),
('_', '_', '_', '_', 'B', '_', '_', 'b'),
('_', '_', '_', '_', 'B', 'b', '_', '_'),
('_', '_', '_', '_', '_', 'B', 'b', '_'),
('_', '_', '_', '_', '_', '_', 'B', 'b')]
Check we can generate all separations of bishops randomly:
Generated all the 16 separations in 117 attempts
Check we can generate all 960 randomly:
@ 500 368/960
@ 1000 573/960
@ 1500 692/960
@ 2000 768/960
@ 2500 831/960
@ 3000 871/960
@ 3500 892/960
@ 4000 909/960
@ 4500 922/960
@ 5000 933/960
@ 5500 941/960
@ 6000 945/960
@ 6500 950/960
@ 7000 951/960
@ 7500 953/960
@ 8000 954/960
@ 8500 954/960
@ 9000 955/960
@ 9500 955/960
@10000 955/960
@10500 955/960
@11000 956/960
@11500 957/960
@12000 959/960
@12500 959/960
@13000 959/960
Generated all the 960 separations in 13166 attempts
"a bit wasteful"
A comment on the main page classified pregenerating the 960 positions as "a bit wasteful", and I'm wondering just how wasteful it winds up being.
I did some measurements myself, and I found that the total memory consumed was a fraction of the resources consumed by the language implementation at startup. And, as a one-time cost this seems reasonable. And for more frequent use? Can we get more efficient than the table lookup approach, for this specific problem? (Approximately 7680 bytes to represent the table, and a bit more for the code, and a few microseconds to generate the values. I could see 7680 bytes being too much on a microcontroller, but not so sure about it being a problem on something bigger, like a phone.)
Anyways, it seems to me that "wasteful" would be not using the computer, but I'm also concerned that I might be overlooking an important issue.
(This is not an entirely idle question - I have been seriously wondering about the value of computers to society - you can't eat them, you can't wear them, they mostly seem fad driven, I've been frequently told how they are destroying civilization, I see billions of dollars invested in just sitting there watching them (ops, security, etc), and the high end systems tend to be unreliable in all sorts of ways. I'm aware of large teams of people basically reinventing the wheel on a daily basis in the name of "code reuse". I'm seriously wondering if I shouldn't have gone into agriculture, instead - at least there the benefits are relatively obvious. Of course, I don't expect this forum here to answer all my questions, but I do have a lot of questions about our criteria. Thanks for bearing with me.)
I suppose another way of looking at this would be to suggest that the problem itself is wasteful? Or are these questions and thoughts too harsh? --Rdm (talk) 17:55, 14 May 2014 (UTC)
- Er, sorry, I see that what I wrote was ambiguous. I wasn't complaining about the pregeneration of the 960 entries, but about the generation of 40320 permutations, only to throw most of them away. Indeed, pregenerating the 960 entries makes perfect sense, especially if you can do it at compile time, and amortize it over many runs. I've clarified my comment, and added a faster way to pregen the 960 entries via construction. Thanks for pointing out the ambiguity in what I wrote. --TimToady (talk) 18:47, 14 May 2014 (UTC)
- I make the opposite view about computers. Every winter I find myself marvelling at the reduction in the amount of cars seen with their hood up left broken down by the side of the road. I put that down to modern engine management systems.
- I also see our double decker busses just going about their business. When I was a lad, they would cough and wheeze belching smoke as they laboured slowly up hills. Now their engines have engine management systems that get more from the fuel and help diagnose problems before they lead to breakdowns.
- As you can see I think of computers as having a net positive effect. (Guided bombs and drones notwithstanding). --Paddy3118 (talk) 19:45, 14 May 2014 (UTC)