Author: Steve Coladonato
Date: 05:34:23 01/21/00
Go up one level in this thread
On January 20, 2000 at 13:04:49, Dave Gomboc wrote: >On January 20, 2000 at 08:56:13, Steve Coladonato wrote: > >>On January 19, 2000 at 13:29:23, José de Jesús García Ruvalcaba wrote: >> >>>On January 19, 2000 at 09:48:11, Steve Coladonato wrote: >>> >>>><snip> >>>> >>>>>>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 >>>> >>>>Dave, >>>> >>>>OK. Now, if the information for the position also contains the best move, >>> >>> It does not. Tablebases only store scores, not moves. >>> >>>>the >>>>program would make that move and then do a hash lookup on the position arising >>>>from the opponent's move. >>> >>> Not quite. After receiving the opponent's move, it does a one ply search and >>>chooses the move which leads to a higher score (I am assuming we are on a root >>>tablebase position). >>> >>>>The assumption is that once a TB position has been >>>>reached, all possible subsequent positions are in the TB. >>>> >>> >>> Most programs assume this, and thus have problems when there are some >>>tablebases missing. >>> >>>>Am I any closer? >>>> >>>>Steve >> >>Jose, >> >>Thanks. But I am curious as to why the best move isn't also stored. It seems a >>waste to have the program do a one ply search to determine the best/next move. >> >>Steve > >It is a trade-off between execution speed and tablebase size. Note that the >tablebases are already quite large, and that the amount of time it takes to play >a move once the root position is a tablebase position is already small. It is >possible to use even more disk space and eliminate the one-ply search. Faster >isn't important here (it's already fast enough), though, so it would just be a >waste of disk space. > >Dave Dave, One last question then. Given that the tablebase position is a mate in 15, how do you know that the one ply search is choosing the correct move? Steve
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.