Author: Keith Evans
Date: 16:22:56 04/05/02
Go up one level in this thread
On April 05, 2002 at 14:53:59, Robert Hyatt wrote:
>>
>>Here's where my ignorance may come shining through...
>>
>>In Marc Boule's move generator there is a way for software for force a
>>particular move to be made - there is no reason why an on-chip state machine
>>couldn't do the same. Couldn't you just force the move generator to make the
>>hash move first? We could implement a hash move stack which would keep track of
>>the hash move made (if any) so that during the remaining move generation we
>>wouldn't make it again after returning to the node.
>
>It would make it more complex. It is easier to design a finite state
>machine to use a finite-state-generator... first stuffing a specific move
>would be an interesting problem. And then disabling that move from ever
>being generated would be yet another interesting problem. You _could_
>just search the move a second time (assuming it didn't cutoff the first time)
>and let the hash table handle it.. but that might tend to make you search
>extra stuff if that particular table entry didn't survive long enough...
I don't think that it's as difficult as you believe. Actually stuffing a
specific move is not much different than normal operation. A Thompson style move
generator first finds a move, and then basically stuffs the move. I'm just
suggesting an alternate method of finding a move.
find_move
find_victim + find aggressor
or
get_hash_move
And checking each generated move against a saved hash move to see if it's
already been done would be a 32-bit compare at most. I would use a stack to hold
the executed hash move information. The stack comes practically "for free" with
the Xilinx Virtex parts due to the availability of the Block Select RAMs.
Keep in mind that this kind of thing can sit to the side of the move generator.
Since there's no known way of pipelining a Thompson style move generator to
increase its performance, then it's absolutely critical to avoid putting
anything in the "silicon chessboard" area since that could have the effect of
decreasing the operating frequency due to the poor routing available in the
Virtex parts.
Anyhow adding hash moves is a lot less scary to me than adding the eval ;-)
>It is certainly doable, but if you read Hsu's description of the DB2 chips,
>he had to shrink the "pads" on the silicon to something smaller than the
>standard for the fab process he used, otherwise the chip didn't have enough
>room for the hardware he had... It _barely_ fit because of all the routing
>problems he had to work around, and even after that they had cross-coupling
>problems that required software work-arounds to prevent the hardware from
>producing bogus results... So I can see why he didn't try that. And I can
>see advantages in trying to do both hash (and killer) moves in hardware, if
>space is no problem...
My guess is that IBM gave Hsu some kind of a waiver, because they're normally
anal about what types of chips they will build. For instance thou shall have
full scan. I'm from the world of Japanese manufactured ASICs so I'm not used to
hearing terms like cross-coupling, metal migration, problems with testability,
ground bounce,... They won't let us screw that up. (Knock on wood.)
I haven't thought much about the complexity of doing killer moves. Marc has a
way to do these, but his software has to some work. I don't completely
understand how it works quite yet, something to ponder. The killer moves don't
affect the "silicon chessboard" part of the generator which is good news.
Funny thing is that I could actually see implementing killer moves before the
hash moves because the former don't require an SDRAM DIMM to be present.
Regards,
Keith
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.