Author: Dann Corbit
Date: 15:16:22 01/25/05
Go up one level in this thread
On January 25, 2005 at 18:04:51, Robert Hyatt wrote: >On January 25, 2005 at 16:32:58, Duncan Roberts wrote: > >>On January 25, 2005 at 16:25:28, Robert Hyatt wrote: >> >>>On January 25, 2005 at 16:13:01, Duncan Roberts wrote: >>> >>>>My understanding of dann corbit is that a 32 piece tablebase needs a 2.5 * 2.5 >>>>cube of crystal. >>>> >>>>http://www.talkchess.com/forums/1/message.html?407489 >>>> >>>> >>>>This is considerably less than a galaxy and perhaps could be slipped pass >>>>greenpeace, although I think you were referring to all games. >>>> >>>>anyway is this calculation anywhere near right ? >>>> >>>> >>>>duncan >>> >>> >>>I honestly have no idea. First, I really don't know how big the actual game >>>tree for chess will be. It could be _very_ big if the game goes on and on with >>>every 50th move being a pawn push or capture to restart the 50 move rule. Or it >>>might be that it is a forced win or draw or loss inside 50 move, with best play. >>> Until we know how big the tree really is, it is hard to predict how much >>>storage will be required to hold it. For the worst case, where some 5500 moves >>>are possible before it becomes a forced draw (forced in that I assume one side >>>will claim the draw if the other side will not, otherwise the game becomes >>>infinite and all bets are off) that is so big that it is impossible to estimate >>>anything about it. There are positions with a branching factor of one (one >>>legal move) as well as positions with a branching factor of over 200. When >>>talking about W^D where D is big and W can get big, I personally lose focus. :) >> >> >>but to store a 32 piece tablebase would be a lot 'smaller'. >> >>might a 2.5 by 2.5 kilometre crystal do the trick ? >> >> >>duncan > >The size of that is easy to compute. you start off with one piece on any of 64 >squares. That takes 6 bits. Another piece on any of the remaining 63 squares. >This turns into 64*63*62*61...*33... which is about 2e55 if I did my math >right. Or another way is 6 bits * 32 pieces = 192 bits = 2^192 = 6e57. > >Both are big numbers. If you can store that many _values_ in a crystal of that >size, then you are set. note that win/lose/draw is not good enough here, you >need a mate in N value, not just win/lose/draw or you can't play the game and >win when you should. There are things that can reduce the piece on board placements, like king placement, etc. Uri Blass wrote a program that calculated 3.70106e+046 distinct board postions (so you would need 155 bits to encode a chess position.) But you can also reduce that value by 4 via reflection and color reversal giving 153 bits. If we did a proof search, maybe we only need 2 bits per position, and we use the actual positions as a 153 bit number index (so we never store the positions anywhere -- the only value of the position is to give us the address of the answer in the crystal). At any rate, I calculate the crystal as 100,000 KM on an edge. That's a lot of crystal. What's that -- about the volume of Jupiter?
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.