Author: Dann Corbit
Date: 14:16:26 05/11/01
Go up one level in this thread
On May 11, 2001 at 15:49:19, Angrim wrote:
>On May 11, 2001 at 03:29:43, Dann Corbit wrote:
>
>>On May 11, 2001 at 01:49:03, Angrim wrote:
><snip>
>>>If your goal is to determine how hard it is to solve chess, then yes.
>>>Rather then go into a lengthy rant here, let me give an example.
>>>The following position has pawns advanced a total of 4 squares, so
>>>subtract 4*50 from the max depth, and your math suggests that there are
>>>38^(5900 -200) total games of chess that can result from this position.
>>>However, the position is trivial. No need for sqrt(38^(5900 -200))
>>>positions to be searched or stored...
>>>
>>>[D]rnbqkbnr/pppp1ppp/4p3/8/6P1/5P2/PPPPP2P/RNBQKBNR b KQkq g3 0 2
>>
>>Yet there are many quintillions of quintillions of qintillions of games that can
>>sprout from here.
>>
>My point being that if your goal is to solve this position, then all
>but 1 of those games is totally irrelevant.
Of course, this position is only 1/400 possible at this point, and the only one
which ends so simply. However, you do bring up an excellent point. Games
terminate when we achieve a checkmate or a draw. All we have to do is
ennumerate them all and work backwards. Sounds absurd, but I am quite sure it
would be much easier than solving chess by forward search from the root. Not
sure how to get started on that one. Of course, the 50 move rule and 3-peat
stuff would have to get factored in somehow.
>>Unless we assume optimal play.
>We only need to assume optimal play for one side, unless chess turns out
>to be a draw. I'm not actually good enough at chess to determine whether
>or not the game is a theory draw :-) .
I don't think it is easy to do that. Sometimes, optimal play will mean ignoring
the 50 move rule, and sometimes you should apply it. And what happens in a game
*if* the opponent could apply it and does not?
The position you play has only one mating choice, and so it is a no-brainer on
what a program that plays to win ought to do. We can assume that we will make
such a move, but not that the opponent will. It is also possible that the exact
position above could be drawn with a different half-move clock (just imagine a
bit of useless knight dancing). So the position by itself without the game
state data would not be enough to decide.
>>Positions like this one are intensely interesting, however. We could formally
>>trim all forward branches from here. Unless I am missing something.
>>
>>Which brings up another thought. What percentage of moves are so horrible that
>>they are not even worth considering. Is it 99.99999999999999999999999999%?
>
>not of moves, but of the set of all possible games, the percentage that contain
>an error of that magnitude is roughly 99.999<insert 2 pages of 9s>99%
>Even if you define such an error as "any move which can be shown to lose
>with a 1 second search" rather than the possibly unsound "any move which
>crafty would score as 10 points lower than the favorite after a 1 second
>search".
I don't think that such a percentage can really be quite so high. I notice in
the middle game that there are usually about 35 choices that can be made. Super
GM's will usually pick about 3 different options in such an example. So that's
about ten percent from a given node. Now, it is interesting that it is a sort
of exponential trimming, since (.10)^k grows towards zero quickly. But then,
that's just another way of saying that the average branching factor is about 3,
which means we are right back in exponential-ville.
>Angrim
>ps. so much for my attempt to avoid a lengthy rant. But at least I
>left out the 2 pages of 9s ;)
I wouldn't mind looking at them. Look at what fun a big string of 9's can be:
C:\cygwin>factor
9999999999999999999999999999999999999999999999999999999999999999999999999999999
first trying brute force division by small primes
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 317
PRIME FACTOR 6163
PRIME FACTOR 10271
now trying 1000 iterations of brent's method
PRIME FACTOR 307627
now trying william's (p+1) method
phase 1 - trying all primes less than 10000
phase 2 - trying last prime less than 1000000
now trying pollard's (p-1) method
phase 1 - trying all primes less than 100000
phase 2 - trying last prime less than 5000000
now trying lenstra's method using 10 curves
curve 1 phase 1 - trying all primes less than 20000
phase 2 - trying last prime less than 2000000
curve 2 phase 1 - trying all primes less than 20000
phase 2 - trying last prime less than 2000000
curve 3 phase 1 - trying all primes less than 20000
phase 2 - trying last prime less than 2000000
curve 4 phase 1 - trying all primes less than 20000
phase 2 - trying last prime less than 2000000
curve 5 phase 1 - trying all primes less than 20000
phase 2 - trying last prime less than 2000000
curve 6 phase 1 - trying all primes less than 20000
phase 2 - trying last prime less than 2000000
curve 7 phase 1 - trying all primes less than 20000
phase 2 - trying last prime less than 2000000
curve 8 phase 1 - trying all primes less than 20000
phase 2 - trying last prime less than 2000000
curve 9 phase 1 - trying all primes less than 20000
phase 2 - trying last prime less than 2000000
curve 10 phase 1 - trying all primes less than 20000
phase 2 - trying last prime less than 2000000
finally - the multiple polynomial quadratic sieve - with large prime (*)
using multiplier k= 1 and 3845 small primes as factor base
working... 3783
trying...
working... 3783
trying...
working...* 3785
trying...
working... 3785
trying...
PRIME FACTOR 49172195536083790769
PRIME FACTOR 3660574762725521461527140564875080461079917
Hmmm....
Maybe I should go and watch a movie.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.