Author: Don Dailey
Date: 11:24:47 12/30/97
Go up one level in this thread
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
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.