Computer Chess Club Archives


Search

Terms

Messages

Subject: Exponential explosion of alpha-beta trees

Author: Omid David

Date: 14:36:11 07/05/02

Go up one level in this thread


On July 05, 2002 at 11:37:30, Uri Blass wrote:

>On July 05, 2002 at 11:02:43, Sune Fischer wrote:
>
>>On July 05, 2002 at 10:54:06, Dann Corbit wrote:
>>
>>>On July 05, 2002 at 10:51:59, Sune Fischer wrote:
>>>
>>>>On July 05, 2002 at 06:59:51, Uri Blass wrote:
>>>>
>>>>>On July 05, 2002 at 05:59:30, stuart taylor wrote:
>>>>>
>>>>>>On July 04, 2002 at 21:47:11, Omid David wrote:
>>>>>>
>>>>>>>Computers are like a blind person, they can do very well in the radius of their
>>>>>>>stick, but can't see farther.
>>>>>>
>>>>>>Isn't that radius almost complete now? How much is left?
>>>>>>S.Taylor
>>>>>
>>>>>A lot is left.
>>>>>The radius of their stick is clearly less than a half of
>>>>>the radius that is needed.
>>>>
>>>>Define "needed".
>>>>Kicking GM butts is not enough? :)
>>>
>>>Until the radius is clear to the end of the game tree, there will always be room
>>>for improvement.  If not against humans, then against other programs.
>>
>>Yes, but since Uri said "half" I assumed he didn't mean distance to solve the
>>game, in that case we need more than 30 times the depth. The longest known mate
>>is 260 something IIRC, and that is a simple 6 man position.
>>
>>-S.
>
>I said less than a half.
>I did not say half.
>
>I thought about solving the game but I do not know how much is needed to
>practically solve the game.
>
>It is possible that some program can solve practically the game by searching to
>depth of 50 plies.
>
>I do not know how much is needed but I believe that we do not need to search to
>the end of the game and the number of plies that is needed is a function of the
>quality of the evaluation.
>
>
>I believe that it is easier to solve chess than to prove that the game is
>solved.
>
>I believe that it is possible that we will see  in 50 years that all the
>comp-comp games between top programs are drawn without proving that chess is a
>draw.
>
>Uri

If as you pointed out the programs reach the depth of 50 plies, I believe most
of the games will end in a draw.

But I don't see alpha-beta based programs reach even the depth of 20 plies in
next 50 years!!! No matter how fast the hardware will be, it won't match the
exponential explosion of alpha-beta trees.




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.