Author: Les Fernandez
Date: 22:45:26 01/25/05
Go up one level in this thread
On January 25, 2005 at 18:16:22, Dann Corbit wrote: >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. who says we need all those 153 bits!! We can also make a significant reduction other ways (hint hint) <s> > >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.