Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Exponential explosion of alpha-beta trees

Author: Uri Blass

Date: 18:14:00 07/05/02

Go up one level in this thread


On July 05, 2002 at 17:36:11, Omid David wrote:

>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.

I also expect depth that is smaller than 50 in 50 years(but more than 20) but I
also expect better evaluation function so programs will need less plies to get
the same target of always drawing.

Uri



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.