Author: Graham Laight
Date: 04:16:32 05/10/01
Go up one level in this thread
On May 10, 2001 at 05:46:24, Jesper Antonsson wrote: >On May 09, 2001 at 18:28:13, Robert Hyatt wrote: > >It seems I cannot restrain myself, I just have to answer one more time. :-) > >>I am not sure what you mean. There is no "linear" list of chess positions >>in any way I can think of using "linear". The complexity issue simply asks >>"how hard will it be to compute this function if I increase the number of >>inputs by 1?" In the case of chess, an "input" is a "ply"... > >Yes, agreed. > >>How do you define "deep enough?" If we could prove that white wins within 80 >>plies, then that would do it. but so far, we have not proven that. And since >>the game isn't over until mate or stalemate occurs, unless the two players >>decide to call it a draw for various reasons, I'm not ready to say it is >>"finite" until someone offers reasonable proof that it is... > >Great, then, hopefully, this is *the* point where we disagree. Now, the 3-fold >repetition rule and 50-move rule are not mandatory, but they are there. How do >you handle these positions in the search in Crafty (your "algorithm")? I would >assume that you label them a draw and search no deeper. Perhaps you do not >always *claim* the draw when such a position is at the root, but, as I said, you >probably treat them as draws in the search. This is because mini-max "assumes" >best play from both sides, and either the position is a draw whether 3/50 rules >are used or not, in which case it is safe to return draw-score, or the player >that is losing, using "best play", should claim the draw, in which case minimax >should also return a draw score. > >So, from a search perspective, or solving-chess-perspective, we should treat >these positions as draws, and when we do, a "good" chess algorithm in theory >stops it's exponential behaviour at a certain depth. I find myself siding with Jesper here. Given application of the 50 move rule and draws by repetition (which I think is sensible - if not strictly within the theoretical letter of the law), here is a simple reason why eventually chess search stops being exponential. Simply put: Beyond a certain depth of search, the number of extra nodes to be looked at with every additional search level will start to decrease, because an increasingly high proportion of the search tree branches will terminate in ended games. Having said that, with up to 49 moves between each pawn push or piece taken, the search tree is still going to be quite big - so while I agree with Jesper that the tree will eventually start to thin out, it's not actually offering us the prospect of solving chess by crunching out all possible games. -g
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.