|
| View previous topic :: View next topic |
| Author |
Message |
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
 Posted: Tue Jun 19, 2007 10:35 am Post subject: |
 |
|
| berthier wrote: |
No. Precison of the statistics on percentages are totally independent on the size of the population. See any elementary textbook on statistics (section on estimation of percentages and on confidence intervals).
And 10,000 is a rather large sample size, much larger than any sample used in practice for ordinary statistics.
It allows very good statistics except for rare events.
|
I (re)learn something every day
that was the one grad class I consistently skipped
to the point of coming in on exam day and not knowing it was
| berthier wrote: |
For instance, for the 97% evaluation of the percentage of puzzles solved by SudoRules without T&E, it gives for the width of the confidence interval :
1% at the risk level of 5%
1,6% at the risk level of 5%
Which means that I can state that SudoRules solves the following proportions of randomly generated puzzles:
between 96% and 98% with a risk of error of 5%,
between 95,4% and 98,6% with a risk of error of 1%.
Of course, this supposes that the suexco generator is random, which is, as I said previously, the only question that can rationally be debated.
|
there are two questions
the other: "are the sudoku properties being measued normally distributed"
there are indications that the low clue end of minimal sudoku is different from the high end
| berthier wrote: |
... but this is a mixture of random and non random generators or collections. By definition, catalogs top-something are not random.
Could you tell me which genrator(s) (one or two, preferably based on different generation principles) YOU would accept as random? It'd be a pleasure for me to run my solver on other random collections. |
given the variance in clue distribution for a few popular generators, and the unknown nature of the sudoku distribution,
I can't accept any as being random
the -g option in my solver at least attempts (but sacrifices correctness for speed) to generate an unbiased
pseudo random sample of solution grids, from which puzzles are generated
(based on the unbiased grid generation discussions in the players forum)
if you use -gp -m1 then at least the solution grid for each puzzle will come close to being random
RedEd has a better unbiased grid generator
the distribution of the number and size of minimal puzzles each solution grid holds is not known, but it does vary from grid to grid
for example, some grids are known to not contain 17 clue puzzles,
so generating puzzles from solution grids adds bias
generating minimal and/or symmetric puzzles probably skews the solution methods too |
|
| Back to top |
|
 |
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Tue Jun 19, 2007 11:32 am Post subject: |
|
|
| gsf wrote: | there are two questions
the other: "are the sudoku properties being measued normally distributed"
there are indications that the low clue end of minimal sudoku is different from the high end
|
Normality is pointless here.
| gsf wrote: |
given the variance in clue distribution for a few popular generators, and the unknown nature of the sudoku distribution,
I can't accept any as being random
the -g option in my solver at least attempts (but sacrifices correctness for speed) to generate an unbiased
pseudo random sample of solution grids, from which puzzles are generated
(based on the unbiased grid generation discussions in the players forum)
if you use -gp -m1 then at least the solution grid for each puzzle will come close to being random
RedEd has a better unbiased grid generator
|
Thanks a lot, I'll try one of these as soon as I have time. |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Tue Jun 19, 2007 3:21 pm Post subject: |
|
|
| berthier wrote: | | gsf wrote: | there are two questions
the other: "are the sudoku properties being measued normally distributed"
there are indications that the low clue end of minimal sudoku is different from the high end
|
Normality is pointless here.
|
I'm ready for some more tutoring
why is normality pointless?
isn't the standard deviation based on a normal population? |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Tue Jun 19, 2007 3:52 pm Post subject: |
|
|
| gsf wrote: | | why is normality pointless? |
I may have been too sketchy. Normality is pointless wrt the problem under discussion (percentage estimation).
(Technically this is because, for sufficiently large samples, the law of the samples is always nearly normal, whatever the original law is).
| gsf wrote: | | isn't the standard deviation based on a normal population? |
No. The standard deviation can be defined for any square integrable law (and a fortiori for any law on a finite set). |
|
| Back to top |
|
|
| Red Ed
| | Joined: 04 Nov 2006 | | Posts: 21 | | : | |
Items |
|
| Posted: Fri Jun 22, 2007 6:34 pm Post subject: |
|
|
| berthier wrote: | | gsf wrote: | there are limits to the random sample principle based on the reasonable expectation of the size of the whole population
|
No. Precison of the statistics on percentages are totally independent on the size of the population. |
Only when sampling with replacement 
| with typo corrected, berthier wrote: | For instance, for the 97% evaluation of the percentage of puzzles solved by SudoRules without T&E, it gives for the width of the confidence interval :
1% at the risk level of 5%
1,6% at the risk level of 1% |
When you ditch the normal approximation and calculate those intervals properly, they're even tighter. But as has been pointed out, that's only a tight interval for your particular puzzle generator.
My unbiased solution grid generator was mentioned / asked-for. It's pointless me handing that over because it can't generate puzzles, only solution grids. Instead, I think that it's much better just to compare stats on the popular puzzle lists that gsf listed earlier, provided that you give separate stats for each collection (so we can see which collections are "harder" and see if other solving techniques are similarly affected). |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Fri Jun 22, 2007 7:50 pm Post subject: |
|
|
| Red Ed wrote: | | berthier wrote: | | gsf wrote: | there are limits to the random sample principle based on the reasonable expectation of the size of the whole population
|
No. Precison of the statistics on percentages are totally independent on the size of the population. |
Only when sampling with replacement
|
Replacement is irrelevant when the population is very large.
| Red Ed wrote: | | with typo corrected, berthier wrote: | For instance, for the 97% evaluation of the percentage of puzzles solved by SudoRules without T&E, it gives for the width of the confidence interval :
1% at the risk level of 5%
1,6% at the risk level of 1% |
When you ditch the normal approximation and calculate those intervals properly, they're even tighter. |
Using the normal approximation for such a large sample is standard practice. The difference is infinitesimal.
| Red Ed wrote: | But as has been pointed out, that's only a tight interval for your particular puzzle generator.
|
I already answered this.
Wrong. I had still better results for the 36,628 puzzles in the Royle17 collection.
| Red Ed wrote: | | My unbiased solution grid generator was mentioned / asked-for. It's pointless me handing that over because it can't generate puzzles, only solution grids. Instead, I think that it's much better just to compare stats on the popular puzzle lists that gsf listed earlier, provided that you give separate stats for each collection (so we can see which collections are "harder" and see if other solving techniques are similarly affected). |
I can't see any rationality in doing stats on non random samples.
The only interesting thing that could come out of lists of unsolvables or of top-something is a few examples to which SudoRules could bring an original solution. I'm trying to do this with Ruud's list.
But what I'm mainly looking for remains another random generator in order to do real stats.
Finally, all these debates initiated and indefinitely repeated about statistics are totally irrelevant to the threads on the global conceptual framework I've developed and described in "The Hidden Logic of Sudoku". |
|
| Back to top |
|
|
| Red Ed
| | Joined: 04 Nov 2006 | | Posts: 21 | | : | |
Items |
|
| Posted: Fri Jun 22, 2007 9:10 pm Post subject: |
|
|
| berthier wrote: | | Red Ed wrote: | | berthier wrote: | | gsf wrote: | there are limits to the random sample principle based on the reasonable expectation of the size of the whole population
|
No. Precison of the statistics on percentages are totally independent on the size of the population. |
Only when sampling with replacement |
Replacement is irrelevant when the population is very large. |
Yes, but not when it is small. I was gently pointing out a corner case; a mild counterexample to your use of the strong phrase "totally independent". As mathematicians, we shouldn't say "totally" unless we really mean it
| Quote: | | Red Ed wrote: | | When you ditch the normal approximation and calculate those intervals properly, they're even tighter. |
Using the normal approximation for such a large sample is standard practice. The difference is infinitesimal. |
I was supporting your stance that 97% was a good estimate, by saying that the confidence interval was even tighter than you said previously ... so it's strange that you should wish to pick an argument, and stranger still that you should use such a strong term as "infinitesimal". As mathematicians, can we really let that go? Let's see. There's a probability p that your solver can crack a "random" puzzle, and a sample of size 10000 in which it solved 9700(?) of them. At the top end of the 1% confidence interval, we ask: what would the success probability, p, have to be for 99.5% of experiments to have scored >9700 out of 10000? That is, we need Pr(Bin(10000,p) > 9700) = 0.995. Solving this gives p = 0.97422 to 5 s.f. The Normal approximation has Pr(N(10000p,10000p(1-p)) > 9700) = 0.995, which implies p = 0.97409 to 5 s.f. Yes, very close -- but not "infinitesimal".
| Quote: | | Red Ed wrote: | | But as has been pointed out, that's only a tight interval for your particular puzzle generator. |
I already answered this.
Wrong. I had still better results for the 36,628 puzzles in the Royle17 collection. |
"Wrong", full stop. How rude. Perhaps you are having a bad day, Denis. I was merely qualifying my statements about precision of the estimate by reminding the reader, should he not be following the details of our delightful conversation, that I was analysing the results from a single dataset. I wasn't maligning your solver or your methods, although I might start doing so if you are so keen to confront.
| Quote: | I can't see any rationality in doing stats on non random samples.
The only interesting thing that could come out of lists of unsolvables or of top-something is a few examples to which SudoRules could bring an original solution. I'm trying to do this with Ruud's list.
But what I'm mainly looking for remains another random generator in order to do real stats. |
Understood. I think that most readers will be more interested in the stats from those popular lists (it's good that you are tackling Ruud's) than an estimate of the success% on "all" puzzles. If you really want the latter then I think that the best you can do is just to report stats for several different puzzle generators in turn. It might even reveal something interesting about which puzzle generators make the most difficult puzzles! ( I can just imagine the debate that would cause  )
| Quote: | | Finally, all these debates initiated and indefinitely repeated about statistics are totally irrelevant to the threads on the global conceptual framework I've developed and described in "The Hidden Logic of Sudoku". |
There's board etiquette, dear chap, and there's real life. You shouldn't expect us to stay on-topic all the time. And when we stray ... what's the phrase ... PDNFTT, I think it is.  |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Fri Jun 22, 2007 11:07 pm Post subject: |
|
|
| berthier wrote: |
Finally, all these debates initiated and indefinitely repeated about statistics are totally irrelevant to the threads on the global conceptual framework I've developed and described in "The Hidden Logic of Sudoku". |
hold on
you opened the door by announcing your book
you may be championing one part of it
but the whole book is in scope
(actually for me only whatever you posted to the forums is in scope because I didn't buy the book -- nothing against
your book, my bookshelf has the C programming language, the kornshell book, and the crc tables)
I'm boning up on my statistics, including sample quality, and random combinatorial structures
so there will be more posts on the "97% of random" subtopic
you may be sure the statement (and implications drawn from it) is final and absolute
perhaps I'm a slow learner, and I do know that intuition fails badly in some statsitical matters,
but I'm not convinced, not because of basic statstics (which I re-learned here, sincere thank you),
but because of the data domain and the matter in which the data was sampled |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Sat Jun 23, 2007 3:44 am Post subject: |
|
|
gsf, Red Ex, if you are so eager to debate about stats, why don't you open a thread on that topic and bring content to the subject?
I'm not sure anybody is interested in the difference between the probabilities 0.97422 and 0.97409, which no statitician would consider as significant in the context of a problem of estimation.
But I think everybody would be interested in:
- a random generator of puzzles (not only complete grids),
- or a collection generated by it,
- or your explanations why you think that it is impossible to have one,
- or your criticism of the suexco generator (what are your criteria to assert it is not random wrt to the complexities of the puzzles?)
Red Ex, you say you might start "maligning [my] solver and [my] methods". You'd be most welcome to do so; at least, you'd be in topic. May I suggest that you first try to understand them? And why not start with xyt-chains, the topic of this thread? |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Sat Jun 23, 2007 6:34 am Post subject: |
|
|
| berthier wrote: | | gsf, Red Ex |
you can continue the redex discussion over on eureka
I will start a new thread on this forum starting with 3 100K pseudo random catalogs generated by a documneted publicly available generator
and trust that RedEd and the other forum denizens will offer some insight on any statistical differences between them |
|
| Back to top |
|
|
| Red Ed
| | Joined: 04 Nov 2006 | | Posts: 21 | | : | |
Items |
|
| Posted: Sat Jun 23, 2007 6:43 am Post subject: |
|
|
| berthier wrote: | | gsf, Red Ex, if you are so eager to debate about stats, why don't you open a thread on that topic and bring content to the subject? |
Not keen at all, "Xenis", just sticking up for gsf when you try to fob him off with overly-assertive use of inaccurate terms like "infinitesimal" and "totally independent". My initial remarks were just in passing; it's only grown into a longer exchange because of your participation.
| Quote: | - a random generator of puzzles (not only complete grids),
- or your explanations why you think that it is impossible to have one, |
Not just random, but unbiased - that's the key. It depends what you mean by "unbiased". Let S, M, Mk be random variables sampling in an unbiased way from the sets ...... (for S) of all 6.67e21 solution grids
... (for M) of all 2^81 81-bit values
... (for Mk) of all choose(81,k) 81-bit values with k ones . I can simulate S, M and Mk very nearly perfectly, up to the limit of the Mersenne Twister PRNG. Now let sub(S,M) or sub(S,Mk) be the sub-grid, with possibly many solutions, derived by clearing the cells in S corresponding to zero bits in M or Mk. What can we do with this? Well, we can get an unbiased sample from the following spaces:- All puzzles. (By "puzzle" I mean a uniquely-solvable sub-grid.) Sadly this is not interesting, as the vast majority of puzzles have ~40 clues. Actually, this is my motivation for suggesting you stick with the popular puzzle lists instead, because any half-decent solver will score ~100% on the set of all puzzles ... but no-one would be impressed by that.
- Puzzles with k clues, for k > 24ish. Below k = 25ish, we find that sub(S,Mk) has a unique solution only rather rarely, so it costs us a lot of samples of sub(S,Mk) to make a k-clue puzzle.
- Minimal puzzles. Well, no, I don't think so. The probability that sub(S,M) or sub(S,Mk) is a minimal puzzle is very low, so random sampling of sub(S,M) or sub(S,Mk) doesn't work.
For minimal and low-clue puzzles, you might think of starting with a uniquely-solvable sub(S,M) and then removing clues "at random" until you're left with a minimal or low-clue puzzle. It seems very likely that this will introduce bias, however, since there is (very likely to be) an unequal number of wanted puzzles down each branch of your random clue-removal process. I think that this is the real sticking point when it comes to unbiased samples of interesting puzzles. There may be a way round it, but I've not seen one proved to do the job.
| Quote: | | Red Ex, you say you might start "maligning [my] solver and [my] methods". You'd be most welcome to do so; at least, you'd be in topic. May I suggest that you first try to understand them? And why not start with xyt-chains, the topic of this thread? |
I'll be honest with you; I'm not that interested in xyt-chains. |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Sat Jun 23, 2007 7:18 am Post subject: |
|
|
| Red Ed wrote: | Not just random, but unbiased - that's the key. It depends what you mean by "unbiased". Let S, M, Mk be random variables sampling in an unbiased way from the sets ...... (for S) of all 6.67e21 solution grids
... (for M) of all 2^81 81-bit values
... (for Mk) of all choose(81,k) 81-bit values with k ones . I can simulate S, M and Mk very nearly perfectly, up to the limit of the Mersenne Twister PRNG. Now let sub(S,M) or sub(S,Mk) be the sub-grid, with possibly many solutions, derived by clearing the cells in S corresponding to zero bits in M or Mk. What can we do with this? Well, we can get an unbiased sample from the following spaces:- All puzzles. (By "puzzle" I mean a uniquely-solvable sub-grid.) Sadly this is not interesting, as the vast majority of puzzles have ~40 clues. Actually, this is my motivation for suggesting you stick with the popular puzzle lists instead, because any half-decent solver will score ~100% on the set of all puzzles ... but no-one would be impressed by that.
- Puzzles with k clues, for k > 24ish. Below k = 25ish, we find that sub(S,Mk) has a unique solution only rather rarely, so it costs us a lot of samples of sub(S,Mk) to make a k-clue puzzle.
- Minimal puzzles. Well, no, I don't think so. The probability that sub(S,M) or sub(S,Mk) is a minimal puzzle is very low, so random sampling of sub(S,M) or sub(S,Mk) doesn't work.
For minimal and low-clue puzzles, you might think of starting with a uniquely-solvable sub(S,M) and then removing clues "at random" until you're left with a minimal or low-clue puzzle. It seems very likely that this will introduce bias, however, since there is (very likely to be) an unequal number of wanted puzzles down each branch of your random clue-removal process. I think that this is the real sticking point when it comes to unbiased samples of interesting puzzles. There may be a way round it, but I've not seen one proved to do the job. |
Red Ed, sorry for the "Red Ex", it was only a typo.
This is a very interesting post and it would fit perfectly in the thread on stats gsf is going to open. I propose we continue this discussion on this thread as soon as it is open.
I can't understand why a random unbiased sample of all puzzles is not interesting, if it is used to show that a solver based on a limited set of rules and on general symmetry principles performs statistically as well as solvers with more complex (or at least other types of) rules. And I'd be personnally very interested in knowing, on such a sample, how the puzzles are stratified according to my levels.
You mention the number of clues as a possible source of bias. But it does not seem there is much correlation between the number of clues (within some bounds) and the complexity of a puzzle (however you define it).
In any case, since it seems easy for you to do so, I'd be very grateful if you could make such a sample available to the Sudoku community. That would allow to compare the results with those obtained on the collection generated with the suexco software.
As for the top-something, since several people asked for my trying it, and although I think it does not prove anything, I have just launched SudoRules on the Ruud top1000 collection.
| Red Ed wrote: | | I'll be honest with you; I'm not that interested in xyt-chains. |
That's your strictest right. |
|
| Back to top |
|
|
| berthier
| | Joined: 13 Jun 2007 | | Posts: 43 | | : | | Location: Paris, France |
Items |
|
| Posted: Sun Jun 24, 2007 5:25 am Post subject: Solution to Ruud's top1000 |
|
|
Several people on this forum have requested SudoRules solution to Ruud's top1000. SudoRules can solve 7.6% of the first 1000 puzzles in this list. I didn't consider useful to go further.
More interestingly, most of the puzzles in the solved list are very far from being the most complex ones in my classification;
they range from my levels 5 to 15.
Unfortunately, in the first run, I forgot to put the trace feature on and I got only the final results.
To make things more interesting, I run SudoRules again on a few cases of varied complexities with the trace feature on.
As described in the result file:
1) Trial and Error has been turned off.
The reason is that it can prove nothing, since it can solve everything.
2) Uniqueness rules have been turned off.
3) c-chains of length > 4 have been turned off.
The reason is that the current implementation of c-chains in SudoRules is inefficient and computations would have been too long.
As a result, apart from c4-chains, only chains that can be seen as built on ordinary links (opposed to conjugacy links),
in the appropriate 2D space (rc, rn or cn) are used: xy-, xyt-, xyzt- chains and their hidden counterparts.
It is thus a good illustration of the effectiveness of these spaces.
4) The inference engine used is Jess instead of the safer (but very slow) Clips I used for all the results given in "The Hidden Logic of Sudoku".
The consequence is that some solutions may have been missed (but no wrong one can have appeared).
As this is too long to be posted here, you can get the results from my online supplements page:
http://www.carva.org/denis.berthier/HLS/HLS-Supplements.html
You'll notice the constant interplay in these solutions between the three rc-, rn- and cn- spaces.
Ruud, could you say how you defined your classification or give an address where this is done? |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Sun Jun 24, 2007 6:21 am Post subject: Re: Solution to Ruud's top1000 |
|
|
for another data point, here's the counts for the "hardest" constraint (method) required to solve for my solver with default constraint order:
| Code: |
237 G
37 O
9646 K
80 Y
|
~5m40s @2Ghz to solve
where
| Code: |
G guessing (constraint methods foiled, backtracking kicked in)
K y-knots (contradictory Y edges)
O rookery template overlays
Y XY cycles
|
y-knots are fallout from the XY cycle Y edge construction process (basically Y edges gone bad)
and for the first 1000
|
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Mon Jun 25, 2007 2:24 am Post subject: |
|
|
| wapati wrote: | | gsf wrote: |
I don't dispute that bias can be removed from generating random solution grids,
|
We do not have a reliable random generator.
They all need to be accepted for their limited bias. |
solution grids -- i.e., grids with 81 clues
see the posts by Red Ed on unbiased grid generation in the player's forum
of course computer results would be modulo underlying (pseudo) random number generator bias |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
