Author: chandler yergin
Date: 09:40:36 01/13/05
Go up one level in this thread
On January 13, 2005 at 01:35:44, Uri Blass wrote:
>On January 13, 2005 at 00:50:00, chandler yergin wrote:
>
>>On January 12, 2005 at 22:07:58, Uri Blass wrote:
>>
>>>On January 12, 2005 at 21:33:06, chandler yergin wrote:
>>>
>>>>On January 12, 2005 at 21:17:58, Uri Blass wrote:
>>>>
>>>>>On January 12, 2005 at 20:58:47, chandler yergin wrote:
>>>>>
>>>>>>On January 12, 2005 at 20:55:42, Uri Blass wrote:
>>>>>>
>>>>>>>On January 12, 2005 at 20:33:25, Dann Corbit wrote:
>>>>>>>
>>>>>>>>On January 12, 2005 at 20:25:24, Uri Blass wrote:
>>>>>>>>
>>>>>>>>>On January 12, 2005 at 19:56:25, Dann Corbit wrote:
>>>>>>>>>
>>>>>>>>>>On January 12, 2005 at 19:37:29, Steve Maughan wrote:
>>>>>>>>>>
>>>>>>>>>>>Dann,
>>>>>>>>>>>
>>>>>>>>>>>>Things that seem impossible quickly become possible.
>>>>>>>>>>>
>>>>>>>>>>>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).
>>>>>>>>>>
>>>>>>>>>>>2) Alpha-beta cutting this down to 10^60 sensible positions
>>>>>>>>>>
>>>>>>>>>>The incorrect first assumption renders this and all following assumtions as
>>>>>>>>>>moot.
>>>>>>>>>
>>>>>>>>>The second assumption is also not correct.
>>>>>>>>>
>>>>>>>>>By the same logic alphabeta can cut less than 2^30 positions in KRB vs KR to
>>>>>>>>>2^15 positions but it does not happen and solving some KRB vs KR position with
>>>>>>>>>no KRB vs KR tablebases is not something that you need 2^15 nodes for it.
>>>>>>>>
>>>>>>>>No. The second assumption would be true if the first was true. This was
>>>>>>>>formally PROVEN by Donald Knuth. In a perfectly ordered alpha-beta solution
>>>>>>>>tree, the number of nodes is proportional to the square root of the nodes in the
>>>>>>>>full tree.
>>>>>>>
>>>>>>>The problem is that the number of nodes in the full tree is bigger than the
>>>>>>>number of positions because the same position can happen in many branches of the
>>>>>>>tree.
>>>>>>>
>>>>>>>Even with perfect order of moves you cannot solve KRB vs KR by alpha beta with
>>>>>>>sqrt(2^30) nodes.
>>>>>>>
>>>>>>>Uri
>>>>>>>Uri
>>>>>>
>>>>>>
>>>>>>I think you are on my side...
>>>>>>;)
>>>>>
>>>>>I disagree both with you and Dann.
>>>>>
>>>>>If you want to generate tablebases you cannot use sqrt like Dan suggest.
>>>>>If you want to analyze possibility in games then sqrt is enough.
>>>>>
>>>>>In case that there are 10^120 games and 10^40 positions then chess can be solved
>>>>>by sqrt(10^120) nodes or by 10^40 nodes
>>>>
>>>>
>>>>A NODE, IS a Position! Correct?
>>>
>>>Node is a position that is searched by the chess engine.
>>>
>>>>
>>>>If there are 10^120 Games.. then 'every move' in those 10^120 games ARE
>>>>Positions.
>>>
>>>Yes but not all of them are different so it is possible that there are only
>>>10^40 different positions in a tree of 10^120 positions.
>>>
>>>There are too way to try to solve chess
>>>
>>>1)search(in this case you may search the same node in a lot of branches and you
>>>search both 1.e4 e6 2.d4 d6 or 1.e4 d6 2.e4 e6 or 1.d4 e6 2.e4 d6 or 1.d4 d6
>>>2.e4 e6)
>>>
>>>In 4 plies you can get the same position 4 times and in 80 plies that are 40
>>>moves you may get it trillions of times in different branches of the tree.
>>>
>>>In tree alpha beta help to get sqrt of the number of games but it is not a good
>>>idea to solve chess.
>>>
>>>2)tablebases that seems a better idea and the problem is that today there is not
>>>enough memory.
>>>
>>>In this case you do not build a tree.
>>>
>>>you look at all the position first time and mark all the mates.
>>>you look at all the position second time and mark all positions that you can get
>>>mate in 1(position that is already marked)
>>>
>>>you look at all the position and mark all the positions that you cannot prevent
>>>mate in 1(every move will need to position that is marked as mate in 1)
>>>
>>>There is no mate in 5000 because of the 50 move rule.
>>>so after repeating this process 10,000 times you can continue stop it and every
>>>position was searched only 10,000 times.
>>>
>>>This means that if the number of positions is 10^40 then time of searching
>>>10^40*10,000 positions is going to be enough but you need also memory of 10^40
>>>positions and this is the another problem with using this solution today.
>>>
>>>I do not know if we will be able to use memory of 10^40 positions or search
>>>10^44 nodes in the next 100 years but I cannot say that I am sure that it is
>>>impossible.
>>>
>>>10^40 positions is only an estimate and I do not know the exact number of
>>>positions.
>>>
>>>I remember that I proved that it is less than 10^50 and even less than 10^47 in
>>>the past by a computer program that counted the number of possible positions for
>>>every possible material configuration and part of the positions that I counted
>>>are also illegal because both kings are in check so the estimate of 10^40 seems
>>>to me a good estimate.
>>>
>>>Uri
>>
>>
>>Argue with Dr. Hyatt, Dr. John Nunn & Frederick Freidel!
>>
>>THEY agree with ME!
>
>I need to hear from them that they agree with you.
I agree with them! Same conclusions to the Question.
>
>It is possible that they have the opinion that chess will not be solved in the
>next 100 years(I only said that I do not know) but I believe that they do not
>claim that it is a proved fact.
>
>I do not think that they agree that it is impossible to solve chess if you have
>enough memory
>to store 10^50 positions with distance to mate or conversion and machine that
>can search 10^45 nodes per second.
>
>The question if this will be possible in the next 50 years or in the next 100
>years is an open question.
>
>Uri
Like Evolution, This is not even debateable among Scientists.
Only among delusional Programmers.
;)
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.