Author: Bruce Moreland
Date: 19:09:49 12/05/00
Go up one level in this thread
On December 05, 2000 at 18:00:19, Scott Gasch wrote: >Hi, > >I have become convinced that my search code is buggy and have thus pulled >everything out of it. It now is a simple PVS with no null move, futility, etc. > >I am adding things back one at a time and testing the search tree size in four >positions to evaluate the newly added code and hopefully find bugs. Add null move back in first. It is easy and you should notice a big improvement. >This brings me to the hash table. When I re-added hashing, I found that if I do >not stuff the PV moves/positions/score back into the hash table every time I >update the PV, the tree size grows larger. I am not just talking about at the >end of a depth N search in my Think() routine. I am saying everytime I get a >value between alpha and beta in any depth of search I have to stuff the move and >the PV from that depth down back into the table. This concerns me. Since it sounds like you are messing with some data structures in the search that shouldn't be messed with. When you return from an iteration of search, pull the PV out and use *that* to seed your search. You shouldn't be messing with that during the search. And all the PV does is determine which moves will combine the extreme left edge of the tree (the first line that you search). It isn't used for anything else. Some people try to search Nf3 first in any ply 3 position, if Nf3 is in ply 3 of the PV, but I don't think that makes any sense. You just want to try to search the best line *first*. Also, since you are doing something weird here, are you getting the PV out correctly? >I attribute this to hash collisions that are wiping out the PV nodes and messing >up my move ordering. But this doesn't make sense, does it? There can't be that >many collisions and what are the odds that a position that collides with a PV >position in the hash table will also have a move stored at it that was legal at >the PV node? This cannot be. No, there's a rabid animal running around in your search code if the PV thing is as broken is it sounds, and you should get rid of it. >But without hash code my move order of winning capt, even, normal moves, losing >capts produces smaller trees than with hash code order of hash move, winning >capt, even, normal, losing if I fail to stuff. When I stuff the tree sizes >between no hash move first and hash move first are nearly the same. This is confusing. >My questions for you more experience chess programmers are: ANY hash entry that >has an attached move (an EXACT or an LOWER hash entry) but not enough depth to >be useful should causes said move to be promoted to the front of the search >list, right? This makes sense to me, but I just want to verify. Yes. >When storing a hash position the depth you store with it is the depth you used >to search and arrive at this position, correct? What do you do with extensions >-- count them or not? I think they should be counted in because, after all, >they were part of the depth that search was called with to return the score...? You store the draft (depth remaining) under the node. Meaning, you say, "Hey, I searched this before, to a depth of 6 plies under here, and my score was 34." If you are in iteration 8, you do not store an "8" in every case. That will cause mass destruction as essentially every search is regarded equally. >I am not taking en-passant square, castling perms, or 50 move count into account >with my positional hash signatures. Only what piece is on which square and >whose move it is. Is this going come back to haunt me later on? If so, these are dings in the paint, not a machine gun bullet through the engine block. Maybe these will bite you eventually, but they are not the cause of extremely common coarse bugs. >Also, Bob mentioned position FINE70 in his response to a hash question below. >This is one of my four test positions for re-evaluating my search "tricks". >With my hash code in place I am able to get to depth 17 much more quickly and >with fewer nodes (5500676 vs. 8094320) but it is not "instant". Does this >indicate more bugs than just this move order thing in my hash? I've seen other >programs do FINE70 in _WAY_ less nodes than this... It sounds like your program is about ready to explode. I think you should check what I said in here and see if I'm on drugs, before trying to make progress with new code. Fine 70 should finish in a second or two if you are efficient and your hash table isn't broken. I've had some versions of mine half-break on this, but normally it is pretty smooth. If your search is really simply it should be *easier* to do Fine 70 than if you are doing a lot of excess crap. The only major gotcha is that you can't be doing null move in K+P endings if you want to find this. bruce
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.