Author: Dann Corbit
Date: 08:51:24 01/26/05
Go up one level in this thread
On January 26, 2005 at 01:45:26, Les Fernandez wrote: >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> Actually, the scheme I was discussing encodes the chess position in 2 bits (win/loss/draw/broken) for proof search. The 153 bits is just the address to find the answer. I think it will be very, very hard to reduce the physical address to less than 153 bits and also keep it totally general so that you can encode any possible position.
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.