Author: Graham Laight
Date: 05:01:16 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. Given the application of the 50 move rule, one can easily estimate an absolute limit to the number of possible chess games. Number of pieces which can be taken: 30 Number of possible pawn pushes: 6 * 16 = 96 Total number of 50 move rule avoidence events: 96 + 30 = 126 Maximum possible number of moves: 126 * 49 = 6,174 Maximum possible number of plies: 6,174 * 2 = 12,348 Average number of possible moves per position: 37 (you could work with a maximum possible if you prefer) Maximum possible number of games: 37 ^ 12,248 = 1.4 e+19,364 -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.