Author: Dann Corbit
Date: 14:00:59 01/18/05
Go up one level in this thread
On January 18, 2005 at 16:10:59, Uri Blass wrote: >On January 18, 2005 at 15:13:24, Dann Corbit wrote: > >>On January 18, 2005 at 11:54:39, Uri Blass wrote: >> >>>On January 18, 2005 at 11:25:26, Robert Hyatt wrote: >>> >>>>On January 18, 2005 at 10:36:20, chandler yergin wrote: >>>> >>>>>Only delusional people, disconnected from reality think it can. >>>>> >>>>>End of discussion! >>>>> >>>>>Anyone want to refute this? >>>>> >>>>>http://stuffo.howstuffworks.com/chess1.htm >>>>> >>>>>In this tree, there are 20 possible moves for white. There are 20 * 20 = 400 >>>>>possible moves for black, depending on what white does. Then there are 400 * 20 >>>>>= 8,000 for white. Then there are 8,000 * 20 = 160,000 for black, and so on. If >>>>>you were to fully develop the entire tree for all possible chess moves, the >>>>>total number of board positions is about 1,000,000,000,000,000,000,000,000, >>>>>000,000,000,000,000,000,000,000,000,000,000,000,000,000, >>>>>000,000,000,000,000,000,000,000,000,000,000,000,000,000, >>>>>000,000,000,000, or 10^120, give or take a few. That's a very big number. For >>>>>example, there have only been 10^26 nanoseconds since the Big Bang. There are >>>>>thought to be only 10^75 atoms in the entire universe. When you consider that >>>>>the Milky Way galaxy contains billions of suns, and there are billions of >>>>>galaxies, you can see that that's a whole lot of atoms. >>>> >>>>First, your numbers are wrong. We can store a chess position in about 160 bits, >>>>which means 2^160 positions total. Way less than 10^120. Second, nothing says >>>>we can only store one piece of information per atom. Thirdly, alpha/beta >>>>doesn't require that we even search _every_ possible position, only about >>>>sqrt(P) need be actually searched, which is 2^80 position. >>> >>>I disagree with the last point. >>> >>>By that logic you can solve KRB vs KR with no tablebases by only searching >>>sqrt(P) nodes when P is the number of KRP vs KR position. >>> >>>Can you do it? >> >>The problem is that you must have optimal ordering. This is difficult to >>achieve. But it is theoretically possible. If it is nearly optimal, then you >>can still do quite well. There is also a constant of proportionality which is >>greater than or equal to one. This may be important in practice. >> >>>I do not say that searching all positions is needed but I see no proof that sqrt >>>is enough. >> >>You realize that only one position must be solved to solve chess (the opening >>one). We would therefore make the analogy to solving a single KRBkr position. > >Can you solve some mate in 50 in KRBKR by sqrt() nodes. > >I doubt if it is possible even with perfect order of moves because the number of >relevant different positions in the mate tree may be significantly more than >2^15. > >I suspect that the number of different positions in the tree is more than 2^15 >regardless of the order of moves. > >The point is that positions that are not searched because both sides play >illogical moves may be reached later in the tree. The number of different positions in the tree cannot possibly be more than the number of different legal positions you can make on a chess board with white (king, rook, bishop) + black (king, rook) or positions with some of those chessmen removed. Further, we can rotate the board and reflect the board, etc. to remove combinations through symmetry. For instance, all of these are the same position: [D]6kr/8/8/8/1RK5/2B5/8/8 w - - [D]rk6/8/8/8/5KR1/5B2/8/8 w - - [D]8/8/2b5/1rk5/8/8/8/6KR b - - [D]8/8/5b2/5kr1/8/8/8/RK6 b - - There are no positions besides those, with that set of chess pieces. If we call N the number of all possible legal positions of the format KRBkr (and with pieces removed from that set down to Kk), then n=N/4 is the most we would have to store due to symmetry. So, will we have to store each and every possible one of the n positions in the tree, or will it be something less than that? If something less, then how much less can it be? Formation of a tablebase file solves all of the nodes. So there exists some way to do it efficiently.
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.