Author: Tony Werten
Date: 00:57:07 12/06/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. > >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. > >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 it can't. It should only happen once in a million ( or so ) or else there's something wrong. > >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. > >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. Maybe I misinterpret the words. I only store moves when EXACT and UPPER. If you have a LOWER node every move failed low. Your best move is just the move you searched first, so don't store it. When you have an UPPER move, it's actually your killer move, store it because hashtables last longer than killertables. > >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...? > As answered before, remaining depth. >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? Most of them not. Except for en-passant. You might want to check how often your hashtable suggests en-passant, but your movegenerator didn't generate it. In my program it happened thousands of times. > >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 Bob has a quad Xeon. Your "instant" might take a bit longer. Tony >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... > >Thanks again, all... >Scott
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.