Author: Robert Hyatt
Date: 10:14:52 01/16/05
Go up one level in this thread
On January 16, 2005 at 12:47:16, Duncan Roberts wrote: >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 Formally, no. However, years ago, when only 4-piece edwards-format files were available, I asked Steven to produce KRBKR and KRNKR because I was seeing those a _lot_ in playing other computers on ICC. He built them and my results changed quite a bit. Now Crafty drew when it should draw, and won when it should win, rather than drawing wins and losing draws. Lots of games against Dave Kittinger's program kept seeing this over and over. One of us would end up a pawn up or down in most every game. And without any 5-piece with pawn tables, we had to play on our own. That often turned into a piece up or down as a piece had to be sacrificed to stop an advanced pawn. But one has to be _very_ careful if you are a piece up, as you can trade into a drawn ending, and one has to be very careful if you are a piece down, as you can trade into a lost ending rather than a drawn one. So the effect was certainly noticable. But I've never played longish-games with tables vs no tables, to see the actual result... > > > 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.