Author: Robert Hyatt
Date: 19:09:23 10/15/97
Go up one level in this thread
On October 15, 1997 at 22:00:23, Brian McKinley wrote: >I am writing my first chess program from scratch. At this point the >evaluation of a position is based purely on strength. The program does >a breadth first search of moves with a limit on the number of moves to >search. I am still focused more on the organization of classes than on >the algorithms and speed. I give this back ground so that you will take >my level of experience into account when answering my question. > >There are many references to hash tables in the posts here. I am well >acquainted with the use of hash tables, but have not been able to infer >their application to a chess program from the message contexts. I seem >to be missing something which is obvious to everyone else. Could >someone take the time to give me a brief overview? > >Thanks here is a "short course". the idea here is to avoid doing something twice. In this case, this "something" is searching the same position twice. Here's how to avoid it: When you are searching at a node, there are three possible things that can happen and cause you to return some value to the previous ply: 1. You search all moves, find a value V where alpha < V < beta, so that this V represents and EXACT score. We can store the position and this result, and the depth of search below this node (called the draft) in a table of some sort, then if we ever reach this position again, and the depth we need to search it is not greater than the depth we searched it when we stored this result, we can just return this score and not search here at all. 2. You search all moves, find that the best score == alpha, which means that *every* move at this ply was refuted by a move at the next ply. We then know that "alpha" represents an upper bound on this position, and we store this position with the UPPER flag. Later, if we reach this position again, we check the draft as above, and if sufficient, we compare the value in the table to the current value of alpha. If the table value is < alpha, then we know this score can not be higher than the table value, and since that value is <= alpha, we simply return this value and do no more searching. 3. You search one or move moves, and find a move that "fails high" and refutes the move at the previous ply. You again store the position and draft, and the value (beta typically) + the flag LOWER, because we know that this position is >= beta, but we don't know how much better. If we reach this position again, and the table draft is sufficient, and the table value is >= beta, we can fail high without searching here either the bottom line is, of course, that we simply don't search the same position two times if we can avoid it, by simply remembering what we did the last time we searched this position, and do the same thing here without any searching at all...
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.