Author: Bruce Moreland
Date: 01:10:21 01/02/99
Go up one level in this thread
On January 02, 1999 at 02:40:35, Horace Ho wrote: >Hi, > > I am new to chess programming and have started >a simple chess program. > > I have some questions (please point me to a FAQ >if these are some of them): > > 1. What's the alternative to a hash table to > eliminate repeated board position? I want my > program to run on a limit memory device, say, > only 32k max for a hash table. Is such a small > hash table meaningful? If you want to catch repetitions you can do it by means other than a huge transposition table. You can make a small hash table of a few hundred or perhaps a few thousand elements, and enter a hash element when you open a node and close it when you close a node. The number of positions that you need to have in the hash table at any one time can't be more than 100, due to the 50-move rule, so the table can't get very full. The reason you may wish to use a huge table is that you can store more information in it other than just that you have the position in the game history or above this node in the search. You can store bounds (score) information, which may let you cut off, a move that you think has a good chance of being best in this position, in order that you can search it first, etc. In practice you end up searching a lot less nodes if you use a hash table in this way. > 2. When should I return from a quiesce search? > Sometimes there is a long capture, recapture > path down the tree. Should I return at certain > depth? The classic quiescent search works as follows. The first thing you do when you open a quiescent node is call your eval function. If the score returned is greater than or equal to beta, you return beta right away. What has happened if this is the case is that the position is great for the side to move, and will probably only get better if you find a nice capture, so why bother? You can still make mistakes, but you are way out at the tips, so your search depth is zero, so mistakes are unavoidable anyway. If the score from the call to eval wasn't >= beta, but was greater than alpha, you set alpha equal to this score, for reasons similar to those expressed in the previous paragraph. Maybe this position isn't fantastic, but it's the best you've found so far, and even if there isn't a good capture here it's still a good position. In practice you rarely encounter a situation like this though. The other common case is when you call the eval function and it beats neither beta nor alpha. In this case, you check the captures, and if there are some that you will allow, you execute them and recurse. What ends up happening is that if you are in a contentious situation, you may search a series of captures, but if you're wiping your opponent out in a position, you'll fail high (get a score back from eval that's >= beta), so you'll prune, and if you're getting wiped out in a position, your eval will fail low (return <= alpha), and all of the possible captures will also fail low. This form of quiescent search should be called null-move quiescent search, which is accurate although not to be confused with null-move forward pruning that can be used higher up in the tree. > > 3. What's the best sorting algorithm for a move > list (in a memory limited environment)? This question is why I started writing a chess program. I notice that GnuChess simply did a sequential search to find the one with the best sort key (you didn't ask how to compute the sort key so I'm not answering), then moves this candidate to the top of the list, then searches it. I figured this was obviously stupid, since the total time to sort all of the moves was (N^2 + N) / 2, so I wrote my own program and stuck in a quick-sort instead. Eventually I noticed that I was spending a huge amount of time in this sort, even though it was a good sort, and I tried it the GnuChess way and it worked much better. What I hadn't realized is that a huge percentage of the time you don't actually search all of the candidates, so with the supposedly inefficient sequential search you really end up doing some small number times N compares, which is a heck of a lot better than a quick-sort if N is something like 35 and the small number is two or three. I think that a real enhancement to the GnuChess solution is to only do your sequential search the first few times you need to pick a candidate, and otherwise you don't do any form of sorting at all. The reason is that there are essentially two types of nodes. The first type fails high on the first move you select, assuming you select a good one. In this case, the GnuChess system is perfect enough, it does N compares. The other type of node doesn't fail high ever, you are going to have to search all of the candidates. You want to search the best one the first few trips through, in the hopes that you will get lucky and fail high, but after that there isn't much that distinguishes the moves and you may as well just cut your sort overhead to zero. 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.