Author: Duncan Roberts
Date: 09:47:16 01/16/05
Go up one level in this thread
On January 15, 2005 at 01:23:39, Robert Hyatt wrote: >On January 13, 2005 at 15:52:19, Duncan Roberts wrote: > >>On January 13, 2005 at 12:50:52, Robert Hyatt wrote: >> >>>On January 12, 2005 at 21:47:05, Les Fernandez wrote: >>> >>>>On January 12, 2005 at 21:21:34, Dann Corbit wrote: >>>> >>>>>On January 12, 2005 at 21:18:22, chandler yergin wrote: >>>>> >>>>>>On January 12, 2005 at 21:13:08, Dann Corbit wrote: >>>>>> >>>>>>>On January 12, 2005 at 21:09:16, chandler yergin wrote: >>>>>>> >>>>>>>>On January 12, 2005 at 21:02:01, Dann Corbit wrote: >>>>>>>> >>>>>>>>>On January 12, 2005 at 20:57:40, chandler yergin wrote: >>>>>>>>> >>>>>>>>>>On January 12, 2005 at 20:33:25, Dann Corbit wrote: >>>>>>>>>> >>>>>>>>>>>On January 12, 2005 at 20:25:24, Uri Blass wrote: >>>>>>>>>>> >>>>>>>>>>>>On January 12, 2005 at 19:56:25, Dann Corbit wrote: >>>>>>>>>>>> >>>>>>>>>>>>>On January 12, 2005 at 19:37:29, Steve Maughan wrote: >>>>>>>>>>>>> >>>>>>>>>>>>>>Dann, >>>>>>>>>>>>>> >>>>>>>>>>>>>>>Things that seem impossible quickly become possible. >>>>>>>>>>>>>> >>>>>>>>>>>>>>I recon about 300 years before a computer will solve chess. This assumes >>>>>>>>>>>>>> >>>>>>>>>>>>>>1) 10^120 possible positions >>>>>>>>>>>>> >>>>>>>>>>>>>This is far, far too large. Chess positions have been encoded in 162 bits, >>>>>>>>>>>>>which puts an absolute upper limit at 10^58 (and it is probably much less than >>>>>>>>>>>>>that). >>>>>>>>>>>>> >>>>>>>>>>>>>>2) Alpha-beta cutting this down to 10^60 sensible positions >>>>>>>>>>>>> >>>>>>>>>>>>>The incorrect first assumption renders this and all following assumtions as >>>>>>>>>>>>>moot. >>>>>>>>>>>> >>>>>>>>>>>>The second assumption is also not correct. >>>>>>>>>>>> >>>>>>>>>>>>By the same logic alphabeta can cut less than 2^30 positions in KRB vs KR to >>>>>>>>>>>>2^15 positions but it does not happen and solving some KRB vs KR position with >>>>>>>>>>>>no KRB vs KR tablebases is not something that you need 2^15 nodes for it. >>>>>>>>>>> >>>>>>>>>>>No. The second assumption would be true if the first was true. This was >>>>>>>>>>>formally PROVEN by Donald Knuth. In a perfectly ordered alpha-beta solution >>>>>>>>>>>tree, the number of nodes is proportional to the square root of the nodes in the >>>>>>>>>>>full tree. >>>>>>>>>>> >>>>>>>>>>>If there were 10^120 in the full tree, then about 10^60 would be in the solution >>>>>>>>>>>tree. >>>>>>>>>>> >>>>>>>>>>>It can be less than that. >>>>>>>>>> >>>>>>>>>>It "Can't be LESS than that! >>>>>>>>>> >>>>>>>>>> But it cannot be more. >>>>>>>>>> >>>>>>>>>> >>>>>>>>>>It Certainly CAN! >>>>>>>>>> >>>>>>>>>>In any TREE.. the TREE ONLY represents "What HAS Been PLayed." >>>>>>>>>>REFUTE THAT! >>>>>>>>> >>>>>>>>>You do not have to solve every game. Only every position. Look at the two >>>>>>>>>chess games that I posted. The end position for both was identical. In fact, >>>>>>>>>despite the many moves, there are only a very few positions that are distinct. >>>>>>>>>For each of those positions, if you know the best move, you do not care how you >>>>>>>>>got there. >>>>>>>>> >>>>>>>> >>>>>>>>How do you now the "Best Move" until you have calculated them ALL? >>>>>>> >>>>>>>The miracle of alpha beta is that it allows you to prune away huge chunks of the >>>>>>>tree and get EXACTLY the SAME answer you would get if you examined every single >>>>>>>leaf. >>>>>>> >>>>>>>>Hmmm? >>>>>>> >>>>>>>Read a paper on alpha-beta and you will find the answer. >>>>>> >>>>>>Still doesn't come CLOSE to 10^ 120th Power for Solving ANYTHING! >>>>>>Also.. there are positions for "Underpromotion" which you don't take into >>>>>>account. >>>>> >>>>>Underpromotion is also completely irrelevant. Each of the possible outcomes of >>>>>promotion is simply a new position. Those positions have already been counted >>>>>in the set of 10^43 distinct positions. So you see, underpromotion does not >>>>>even complicate things at all. >>>>> >>>>>>That's WHY 7 man EGTB'S will NOT jump the ELO Rating... >>>> >>>>#1 Chandler just because we do not see a measurable advantage that 6 piece >>>>egtb's offer a computer doesnt mean that a larger,ie 10 piece egtb, wouldnt be >>>>measurable. Think about it. With only 6 pieces on the board most GM's I >>>>suspect would know how to handle that even though some of the 6 piece egtb's can >>>>be very tough even for them. Now if that GM was to try and develope a workable >>>>approach to survivng an endgame for which we have perfect information for 10 >>>>pieces I doubt in most cases he could survive (IMHO). I suspect the benefits of >>>>egtb's will become more obvious as we develope large sets. >>>> >>>>#2 In one of the other threads of yours you mentioned the incredible magnitude >>>>of chess positions and that there was 0% chance of solving chess. Well in >>>>support of Dann's statement where he corrected your figure of 10*120 let me just >>>>say that although perfectly ordered alpha-beta solution will reduce this number >>>>I can probably also reduce that number quite a bit further when we talk about >>>>unique positions vs positions. Although the task "seems" unattainable you just >>>>probably have not looked at all kinds of methods that may offer ways of trimming >>>>down that one number that you are baseing all your thoughts on. Keep an open >>>>mind, we see this stuff happen every day in technology. >>>> >>>>Les >>>> >>> >>> >>>This is irrefutable: Each successive generation of tables provides a _higher_ >>>strength improvement than the previous generation, until we get the 32 piece >>>tables done at which point perfect chess will be played. We won't reach there >>>for a long time, if ever (never is such a long way away I try to not use it) but >>>from personal experience, having started off with just 3-4 piece files, then >>>adding all the 5's, I can assure you that the 5 piece files added much more to >>>my program than the 3-4 piece files did. And the 6's have added even more even >>>though all are not done. I can't say it is an exponential growth with so few >>>data points, but I can say without fear of being proven wrong later that it is >>>just as clearly more than a linear growth in playing strength. >> >> >>could you comment about the table base searches slow the software down a lot. >> >>duncan >> > > >1. I really don't see the search slow down a lot. Unless you are in a 7-8 >piece ending and you have 6 piece files. But even if you reach that point, >which would you rather have, a deep stupid search, or a shallower search where >each endpoint is evaluated perfectly? > >2. I assume everyone knows the "probe only after a capture" trick, if not, it >is well worth the simple test. This avoids slowing things down if you have >missing tables as if you probe and miss, you won't probe again in the path since >there will be no point... > >Just ask someone that has actually tested for years with these tables, as to the >effect they have. We are not seeing _great_ effect yet, but with 16 pieces on >the board, I get lots of table hits. I have seen table hits with 20+ pieces on >the board at times. More tables will mean that we hit the tables sooner in the >game, and the sooner we hit them, the sooner we start to play those positions >perfectly. > >I've seen a _lot_ of disinformation about the effect of tablebases on program >playing performance. Here's some tips that anyone can use to make the >tablebases either offer no benefit or actually hurt program performance: > >1. Use crumby disks. IDE disks. CDRoms. Don't use good SCSI drives, >preferably 10K or 15K to minimize latency. Use something dog slow. > >2. Use small drives so you can't get all the tables. Use a subset. But don't >give any thought to which ones to actually use, just grab a few and see what >happens. Never use _all_ the tables. This way, clearly tables on my ftp >machine can't possibly make a program play better since the program can't access >them. > >3. Don't have much memory on your computer. Or if you do, use almost all of it >for hashing, so that there is little memory for the egtb cache, or the operating >system filesystem cache that greatly reduces the I/O activity level for >positions where many probes are needed. > >4. Be sure to get the endings with pawns, but not the ones that have the pawn >promotions to a Q. No reason to make it easy for the program to play the right >moves for the right reason... > >I'm sure there are others... > >But done right, getting _all_ the tables on good disk drives, with enough memory >for a reasonable cache, and they will certainly make the program stronger. >Right now there is no good way to estimate how much the 6 piece tables will >help, since we don't have 'em all done yet. have any tests been done for crafty, about how much a 5 piece tablebase gives an increase in elo ? duncan But eventually they will all be >available, and for those that get the right kind of hardware, their programs are >going to be significantly stronger. For the rest, the tables will be a waste. > > > > > >>> >>> >>> >>> >>>>>>>>>>>tree >>>>> >>>>>That has more to do with disk access time. But I expect that judicious use of >>>>>the data will increase Elo ratings. >>>>> >>>>>>They, can't even be solved yet.. and NOT in your lifetime either.. will they.. >>>>>>or for future generations to come. >>>>>>STOP! The NONSENSE!
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.