Author: Uri Blass
Date: 13:02:36 07/21/02
Go up one level in this thread
On July 21, 2002 at 14:54:40, Miguel A. Ballicora wrote: >On July 20, 2002 at 15:53:15, Uri Blass wrote: > >>On July 20, 2002 at 15:37:00, Christophe Theron wrote: >> >>>On July 19, 2002 at 23:12:28, Ricardo Gibert wrote: >>> >>>>On July 19, 2002 at 23:08:16, Robert Hyatt wrote: >>>> >>>>>On July 19, 2002 at 22:15:31, Ricardo Gibert wrote: >>>>> >>>>>>On July 19, 2002 at 21:43:40, Robert Hyatt wrote: >>>>>> >>>>>>>On July 19, 2002 at 15:50:44, Uri Blass wrote: >>>>>>> >>>>>>>>On July 19, 2002 at 15:25:48, Christophe Theron wrote: >>>>>>>> >>>>>>>>>On July 18, 2002 at 12:14:10, Robert Hyatt wrote: >>>>>>>>> >>>>>>>>>>On July 18, 2002 at 05:58:56, Vincent Diepeveen wrote: >>>>>>>>>> >>>>>>>>>>>On July 17, 2002 at 13:18:40, Christophe Theron wrote: >>>>>>>>>>> >>>>>>>>>>>>On July 16, 2002 at 11:01:23, Vincent Diepeveen wrote: >>>>>>>>>>>> >>>>>>>>>>>>>On July 15, 2002 at 13:11:09, Christophe Theron wrote: >>>>>>>>>>>>> >>>>>>>>>>>>>>On July 15, 2002 at 08:37:34, Omid David wrote: >>>>>>>>>>>>>> >>>>>>>>>>>>>>>I don't think using double null-move is a good idea in practice, since in >>>>>>>>>>>>>>>midgame the chance of zugzwang is negligible and thus it's superfluous (I doubt >>>>>>>>>>>>>>>if even DIEP uses it). However the contribution of double null-move is that it >>>>>>>>>>>>>>>gives legitimacy to the null-move pruning idea, proving that it _is_ a correct >>>>>>>>>>>>>>>search method (anyway, no one doubts null-move nowadays). >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>>Why does double null move prove that null move is a correct search method???? >>>>>>>>>>>>>> >>>>>>>>>>>>>>Doing two null moves in a row means going back to standard search (a search not >>>>>>>>>>>>>>involving an illegal move like null move is). >>>>>>>>>>>>>> >>>>>>>>>>>>>>I fail to see how it legitimates null move. >>>>>>>>>>>>> >>>>>>>>>>>>>Double nullmove legitimates (duh can't you use easier to spell words) >>>>>>>>>>>>>itself, for the obvious reason that it is provable now that a search >>>>>>>>>>>>>depth of n ply, where i may pick n, is going to solve any problem you >>>>>>>>>>>>>give it. >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>>OK, I see now. >>>>>>>>>>>> >>>>>>>>>>>>However, it is not true. >>>>>>>>>>>> >>>>>>>>>>>>Due to a nasty interaction with the hash table algorithms, just allowing 2 null >>>>>>>>>>>>moves in a row will NOT solve any problem. >>>>>>>>>>> >>>>>>>>>>>What you refer to is a practical impossibility (assuming you have >>>>>>>>>>>a efficient search) : >>>>>>>>>>> >>>>>>>>>>> your assumption is that from a root position r >>>>>>>>>>> with transition of some moves to position p, side stm to move and >>>>>>>>>>> depthleft=d: >>>>>>>>>>> >>>>>>>>>>> r ==> p(stm,d) >>>>>>>>>>> >>>>>>>>>>> that you visit this position with properties that >>>>>>>>>>> before this move you have made 1 nullmove or less. >>>>>>>>>>> >>>>>>>>>>> so ==> r , nullmove , p >>>>>>>>>>> >>>>>>>>>>> Now a major problem for such an event to occur is that >>>>>>>>>>> after 1 nullmove, sides change the side to move. >>>>>>>>>> >>>>>>>>>>Why is this a problem? IE in my case, position P reached thru a path >>>>>>>>>>with a null-move and position P reached thru a path without null-move >>>>>>>>>>are _unique_ positions... >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>>If so, your programs loses a lot of opportunities to prune because it detects >>>>>>>>>less transpositions. But maybe it avoids some problems and is benefical in the >>>>>>>>>end, I do not know. >>>>>>>> >>>>>>>>How much do programs earn by pruning based on hash tables? >>>>>>>> >>>>>>>>Today I do not use hash tables to prune the tree. >>>>>>>>I am interested to know how much rating programs earn from >>>>>>>>using hash tables to prune the tree. >>>>>>>> >>>>>>>>1)Did someone do the experiment of comparing the rating of >>>>>>>>a chess program when hash tables are used only for things like order >>>>>>>>of moves and the rating of the same program when hash tables are used also for >>>>>>>>also to prune the tree. >>>>>>>> >>>>>>>>2)How much speed improvement do programs get in middle game >>>>>>>>from pruning based on hash tables? >>>>>>>> >>>>>>>>Uri >>>>>>> >>>>>>> >>>>>>>Try position fine 70 with and without. Without you might get to depth 15 >>>>>>>or so. With it you can reach depth 40. A _significant_ gain... >>>>>> >>>>>>You're trying to drive Uri crazy aren't you? >>>>>> >>>>>>Did you really think Uri could not think of an example of a position where >>>>>>having hash tables makes a significant difference? >>>>>> >>>>>>Do you really think being able to search a position like Fine 70 to a depth of >>>>>>40 instead of 15 will make a difference in a programs playing strength? >>>>>> >>>>>>Don't you realize people are liable to react to such a reply as yours above as a >>>>>>troll? >>>>>> >>>>>>Please try to be a bit more thoughtful. >>>>> >>>>> >>>>>There was _no_ troll involved. Point by point. >>>>> >>>>>fine 70 _is_ an important hash test. It represents a near-best-case for >>>>>hashing. Which is the best you can do. It increases the search depth by >>>>>at least a factor of 3x in terms of plies searched. >>>>> >>>>>Will that help the program? Clearly in king and pawn endings I see 20+ ply >>>>>searches _all_ the time. And _that_ definitely helps for those positions where >>>>>K+P endings are reached. >>>>> >>>>>But if you want to take a middlegame position, hashing is worth at least a >>>>>factor of 2x based on tests I have run in the past. I can always run them >>>>>again. >>>>> >>>>>So to summarize, fine 70 was and is legitimate. It _clearly_ shows that >>>>>hashing makes a significant difference. I hardly see why _your_ post wouldn't >>>>>be considered a "troll" in fact. As it attacks a legitimate point in a >>>>>utterly simplistic and wrong context... >>>>> >>>>>Perhaps you should follow your own advice and try to be more thoughtful. >>>>>_prior_ to posting??? >>>> >>>>I did. You didn't...again. >>> >>> >>> >>>Bob's post (the one you originally responded to) was perfectly fine. He just >>>gave a meaningful information. >>> >>>Your posts are really borderline. I really fail to see what is the problem with >>>Bob's post. >>> >>>Please don't start a war here. There is really no point. >>> >>> >>> >>> Christophe >> >>I asked simple questions. >> >>I got a response but not to the questions that I asked. >> >>I asked: >>1)How much speed do you earn from using hash table >>to prune the tree in the middle game relative >>to using hash tables but not using them to >>prune the tree(not how much speed >>I can get from hash tables in the middle game). >> >>2)How much rating can I expect from using >>the hash tables to prune the tree. >> >>The response that I got are: >> >>1)Using hash tables to prune the tree is very important >>in some endgames. >> >>2)Using hash tables help to get factor of more than 2 >>in the middle game. >> >>Nothing of these responses answered my questions. >> >>I have no problem with not getting a reply >>because people may not know the right reply to >>my questions but I prefer to >>get replies to the questions that I ask and not to the >>questions that I did not ask. >> >>The fact that I got from Robert hyatt only >>informationa that I did not ask is the reason that >>Ricardo Gibert said that Hyatt did not follow the thread. >> >>Uri > >Uri, > >I understand your question but unfortunately I cannot give you numbers :-) >I believe that in the _middlegame_ the contribution of the hashtables as >_pruninig_ is not so big. CT says 10% and BH say 2x which sounds to much to me, >but it might depend on the program. Anyway, the biggest contribution on the >middlegame I believe comes from the move ordering. I played a little bit with >this a while ago and there are very rudimentary experiments that seems to >suggest that once you have a good ordering the pruning by the hashtable do not >seem to be huge. It is in an article by T. Marsland "Computer Chess and Search" >in the Encyclopaedia of Artificial intelligence (page 234). This article is on >the web somewhere, I remember the reference and I suggested it here in the >group. You can do a search and find it. BUT, this experiment is very old and >limited to short depth (6). > >However, the answer about how many elo points this could give you is difficult >to answer because the real strength will be shown in the endgame. The answer to >this point cannot be separated from this fact. > >My real suggestion is that you do experiments. Just can easily add the pruning >in the code with a compiler switch so you can choose to compile it with and >without. This is really easy. If you want I will be interested in comparing >several middlegame positions side by side. I have this switch in Gaviota. > >Regards, >Miguel Thanks for your reply. 1)How do I add a code with compiler switch? 2)I guess that I may try the option of using hash tables to prune the tree. It seems more simple than teaching my program to use hash tables to save generating moves that I still did not do. I do not like the fact that I may prune based on scores that I may not get if I search but this problem can happen also to chess programs with normal evaluation because they do repetition detection in the search. Another problem is that the real depth that I search may be dependent on previous positions so even if my evaluation is based only on the leaf position I still may get a different score. Uri
This page took 0.01 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.