Author: Dann Corbit
Date: 12:04:27 01/13/05
Go up one level in this thread
On January 13, 2005 at 02:12:10, Russell Reagan wrote:
>On January 12, 2005 at 19:56:25, Dann Corbit wrote:
>
>>>I recon about 300 years before a computer will solve chess. This assumes
>>>
>>>1) 10^120 possible positions
>
>>This is far, far too large. Chess positions have been encoded in 162 bits,
>>which puts an absolute upper limit at 10^58 (and it is probably much less than
>>that).
>
>
>As I'm sure you know, 10^120 is the estimated number of unique paths (or games),
>while 10^40 through 10^58 are estimates on the number of unique positions. It
>seems incorrect to me that we would only need to visit sqrt(unique positions)
>nodes. Alpha-beta doesn't deal with unique positions. It deals with total nodes,
>with unique positions often revisited during a single search via different
>paths. It seems like the number of total nodes visited should actually be larger
>than 10^120, since 10^120 only counts the paths to leaf nodes, and not all nodes
>visited leading to each leaf node. Or am I confusing the situation in my mind?
I am thinking of solving the problem in a different way than normal.
Ignore (for the moment) the square root thing, and assume [hypothetically] that
I have a hash table with every possible board position in it {perhaps 10^43 of
them}
I will never have a hash table miss, because every position is in the tree.
Now, the half move clock and 3-way repetition I will have to track myself.
Given this scenario, it is clear that I do not need to store more positions than
this because I have stored them all. The question is: "How many positions will
I have to actually visit in the search of the root node to the end of the game
to complete the search as won, lost or drawn?"
I think that I will not have to store them all, because the bad nodes trim that
branch and I do not have to search further.
For example, there are plenty of board positions with KQQQQQQQk on them, but I
will never have to search them in practice.
I thnk also that we can achieve many reductions in positions that we have to
search using not only transpositions but also reflections and rotations, as is
done in tablebase files. For instance, all of these positions:
1kr4r/pppnnpqp/3p2p1/8/4P3/1BPP1Q2/P1PN2PP/1RK1R3 w - -
1rk1r3/p1pn2pp/1bpp1q2/4p3/8/3P2P1/PPPNNPQP/1KR4R b - -
2r3nk/2r3pp/r1P1rr2/2r5/2r5/8/6PP/6NK b - -
3r1kr1/pp2np1p/2q1ppb1/3p4/8/1P2P3/PQPNNPPP/R4RK1 b - -
6nk/6pp/8/2R5/2R5/R1p1RR2/2R3PP/2R3NK w - -
kn3r2/pp3r2/2rr1P1r/5r2/5r2/8/PP6/KN6 b - -
kn6/pp6/8/5R2/5R2/2RR1p1R/PP3R2/KN3R2 w - -
r4rk1/pqpnnppp/1p2p3/8/3P4/2Q1PPB1/PP2NP1P/3R1KR1 w - -
are contained in these two positions:
6nk/6pp/8/2R5/2R5/R1p1RR2/2R3PP/2R3NK w -
-r4rk1/pqpnnppp/1p2p3/8/3P4/2Q1PPB1/PP2NP1P/3R1KR1 w - -
by obvious means.
I believe that the "sensible" positions -- those that you ought to make are
proportional to the square root of the total number of positions. Therefore,
those are the only ones we will really need to store in the tree.
But there are clearly a lot of ifs ands ors and buts to my idea (maybe a few
butts too).
;-)
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.