Author: Mike Hood
Date: 03:09:09 10/11/05
Go up one level in this thread
On October 11, 2005 at 05:11:57, Uri Blass wrote: >On October 11, 2005 at 04:39:01, chandler yergin wrote: > >>On October 11, 2005 at 04:08:58, Bruce Moreland wrote: >> >>>On October 10, 2005 at 23:37:41, chandler yergin wrote: >>> >>>>http://chess.verhelst.org/1997/03/10/search/ >>>> >>>>"Tree search is one of the central algorithms of any game playing program. The >>>>term is based on looking at all possible game positions as a tree, with the >>>>legal game moves forming the branches of this tree. The leaves of the tree are >>>>all final positions, where the outcome of the game is known. The problem for >>>>most interesting games is that the size of this tree is tremendously huge, >>>>something like W^D, where W is the average number of moves per position and D is >>>>the depth of the tree, Searching the whole tree is impossible, mainly due to >>>>lack of time, even on the fastest computers. All practical search algorithms are >>>>approximations of doing such a full tree search." >>> >>>It's true for chess. Some aspects are not true for tic-tac-toe, and some others >>>are not true for other games that aren't like chess. >>> >>>I don't know where you are going with this. It's possible to make a lot of >>>assertions about chess programs that people will agree with unless they don't >>>understand the assertion. That the chess tree is too big to search to its >>>limits with any sane hardware is obvious. Someone might mention quantum >>>computers here, but that doesn't fall into the category of sane. >>> >>>bruce >> >> Thanks Bruce for your response... >>Where am I going? I'm trying to get a consensus of opinion before I embarrass >>myself.. But on the other hand I'm used to that. >>No, this is strictly about chess.. not Tic tac toe or other games. >>I expected a negative response from Uri, and he has Posted that Programs do not >>evaluate every move in a position. > >programs do not evaluate every move in a position that they search >and it does not contradict your post. > >programs have pruning rules. >It is written also in your post that >"Searching the whole tree is impossible, mainly due to >lack of time, even on the fastest computers." > >>Well, you know that is not true. >>Rather than have a long thread and dialog with him, I was hoping that other >>Programmers would agree about the Tree ..search function analysis mode etc. >>I think that is a given, so we'll start from here. >>It should be obvious that he who runs the fastest wins the race. >>The Program/Engine that searches the deepest & faster in the alloted time, >>finds the 'best' moves. >>Would you agree? > >No > >A program may search deeper but still lose because of inferior evaluation. > >Searching deeper is a clear advantage but computer chess is not only about >searching deeper. > >Uri Uri, if I understood Chandler's original post correctly, he was talking in theoretical terms about the maximum tree which is the sum of all possible chess games, or sub-trees which are the sum of all possible chess games starting from a particular position. Programs use pruning because the tree is too big to search, as Chandler pointed out. I would like to add to this that position/material evaluations are also used because the tree is too big to search. A perfect program running on infinitely fast hardware would follow every branch of the tree until it reaches a win, a loss or a drawn position. The perfect program would never evaluate a position as (for instance) +1.55; it would only give evaluations of the type "Mate in 135", "Lose in 88" or "Draw". But until we reach this utopian state we shall continue to need our imperfect chess programs with their pruning and their evaluations.
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.