Author: Robert Hyatt
Date: 14:02:22 12/30/97
Go up one level in this thread
On December 30, 1997 at 14:24:47, Don Dailey wrote: >On December 30, 1997 at 13:15:25, John Scalo wrote: > >>Maybe it's because I don't have any sort of SEE, only a >> >> >> >><small takes big>/<equal exchange>/<big takes small> >> >> >> >>ordering, but I see a *huge* explosion in my qsearch which is captures >>only (no checks). I regularly hit depths of 20+ not including plies in >>the regular search. First off, I'm wondering if the pros around here hit >>those depths in their qsearch? >> >> >> >>I'm also wondering if anyone has experimented with limiting the qsearch. >>After examining the qsearch dives to ply 10 and beyond, I found that the >>exchanges are just garbage combinations that would never get played. So >>I limited my qsearch to a depth of five ply and don't consider "big >>takes small" captures at the final ply, since those will most likely be >>bad moves. In this scheme, the program is three or four times faster and >>in initial testing doesn't appear to be any worse in strength! >> >> >>Has anyone else tried this? What are the possible negative effects >>besides the occasional tactical miss? > > >There are many ideas here. 5 ply is too severe in my humble opinion. >I believe you will miss too many tactics. Keep in mind that you only >need to miss one a game to be losing consistantly. My first question >is how do you test and my second is what is your move ordering? I >don't believe you should be getting this much speedup simply by stopping >after 5 ply. I'll bet your move ordering is buggy or poor but it's >hard to say what is going on without knowing your program. > >I have experimented a lot with this kind of stuff over the years and >have found a few good ideas. I think limiting the search in some >way is very good. In my case it helps certain bad case positions a >lot but most positions only a little. What I do is impose a limit >on the captures and then only do recaptures after this. My limit >I think is 7-10 (I no longer remember for sure) and it's check >extended so that each check extends this limit 1 ply. After this >I only do recaptures which is always very quickly terminating. A >popular algorithm also is recaptures and up-captures after a certain >depth to pick up captures by pinned pieces but I'm not convinced this >does much. All these ideas are subject to problems occasionally. > >Also I have used various other enhancements to speed things up, >they are all speculative in the sense that it is possible to miss >something. One simple thing to do is to prune out down-captures >of pawn defended material, it can save a lot and is relatively >safe if you start doing this at least a ply or two into the capture >search. > >Another popular idea that I think just about everyone uses is the >"insufficient capture" algorithm. Basically you do not play a capture >move if you see that the opponent will "stand pat" immediately >afterwards. But one problem with this is the fact that the potential >capture could be a checking move or mate, and the question is does >your program stand pat in check during the quies search? I think >a lot of programs simply avoid the issue altogether by not doing >check testing in the quies search. or at least not deep in the quies >search. My program does full testing and usually prefers to play >it safe. But you can still do insufficient capture as long as you >know in advance if a move is (or might be) a checking move. > >Based primarily on superstition, I always begin applying limiting >algorithms to the computers side. I start the restriction tricks >on the computers turn "just in case." By doing this, if I do miss >something, it will be for the computer and I will have more >confidence that the score returned at the root of the whole search >is a lower bound, or errors on the side of safety for the computer. > >Is this an enhancement? I do not know. I have no easy way to test >whether it makes any sense but it gives me a little more peace of >mind. Perhaps that is its only value? > >But this by no means covers the field. Probably every programmer >has his own bag of tricks that he believes is good and I doubt >any 2 are the same. In my discussions with others I find that >works for some does not work for others. Whatever you do has to >be implemented well and integrated into the whole structure of >all your other algorithms to reap maximum benefit. > >I sort of take Bob's point of view and just >try to get out as quickly as possible, not really trusting the >the thing that much anyway! Take a look at Bob's postings too, >he does some exchange evaluation stuff he claims is a two or three >times speedup. > >By the way, what is your move ordering? My move ordering is based >on the classic (and quite good) algorithm of highest victim first, >then lowest attacker. You should definitely start with this since >it's a good starting point. There are some enhancements to this >too but you are unlikely to do a lot better. > > >-- Don Best starting point is to write a SEE module. You can use this in the following ways: 1. ordering captures. It is more accurate than MVV/LVA (most valuable victim, least valuable attacker) because MVV/LVA looks at ugly captures first... IE it would try a QXR where R is defended before it would try NXP where the P is hanging. I found a significant benefit of using SEE in both Cray Blitz and Crafty. 2. If your SEE is "good" you can use it to toss losing captures in the q-search and not even try them. IE QxP where the P is defended such that this is a losing capture. But the point is that if you leave losers out, it saves a lot of worthless search. I found that doing this cut the size of my tree by just over 50%. That is, using SEE ordering was 10% better than using MVV/LVA, based on extensive testing for a big argument in r.g.c.c last year, and then you can save 50% more by tossing captures (q-search only) that appear to be losing... MVV/LVA is "ok", but is really a hardware-based algorithm where SEE can't be done in a single cycle, while hardware can pick the MVV part in one cycle, and the LVA part in the next. But SEE is more accurate, the only issue being how much time does it take to execute. Using bitmaps it is very fast...
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.