Author: Dave Gomboc
Date: 13:46:18 01/18/00
Go up one level in this thread
On January 18, 2000 at 14:17:33, Steve Coladonato wrote: >On January 18, 2000 at 13:52:22, Dave Gomboc wrote: > >>On January 18, 2000 at 10:40:30, Steve Coladonato wrote: >> >>>Are tablebases basically a set of finite positions that have pointers to >>>subsequent positions (most probably positions leading to a win)? And if so, is >>>the basic algorithm to go to the next position that in turn will have a pointer >>>to a "won" position? I am also concluding that once a program starts to use a >>>tablebase, it no longer does any "real" processing, just pointer evaluation. Is >>>this basically it or am I way off the mark here? >>> >>>Thanks. >>> >>>Steve >> >>You're on the right track. The tablebases are the set of positions, accompanied >>by the number of ply it will take to win (or lose)... or if the position is a >>draw (or simply impossible to reach by the rules of the game, e.g. both kings in >>check), it notes that too. Once the root position (the position on the board) >>is in tablebase land, the only processing you do is to see, hmm well I had a >>mate in 51, so let's try all of the moves that are legal here and see which one >>is a mate in 50... aha, it's Rg6, let's play that. Of course, if two or more >>moves led to mate in 50, you could choose any of them. >> >>"Pointer" has a specific computer programming meaning, and it wouldn't be >>correct to say that the positions have pointers to the successor positions, but >>if you are thinking in general terms about the number of plies until checkmate >>values as "pointers" that show how to continue playing, it's all good. >> >>Dave > >Dave, > >Thanks. From this and also what Michel posted, I gather that a TB is some kind >of ordered list based on some criteria that, once a root position is reached, is >searched repeatedly for the next move. And it's structure is not like that of a >tree. > >Steve The tablebase is a giagntic, collision-free hash table. You have a hash function that takes a board position (where all the pieces are, whose move it is, is castling legal, et cetera) and tells you the spot in the hash table that contains the data you need for that position (who is to win, and in how many moves.) It is possible to have an ordered list, and use binary search to find information on the position you are interested in, but hashing is faster for looking up stuff, because no searching is involved. You can find more information on "hashing" in books that deal with computer algorithms. It is a general technique that is often used when data retrieval must be fast, and certain other constraints are met. Dave
This page took 0.01 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.