Author: Michel Langeveld
Date: 12:52:31 01/21/00
Go up one level in this thread
On January 21, 2000 at 08:34:23, Steve Coladonato wrote: >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 For example the initial chessposition is mate in 15. Then there are 2 fysical file for tablebases. One file is White-to-move (WTM) and one file is Black-to-move (BTM) COMPLETE.WTM (intial position) 15 COMPLETE.BTM (init+a3) -20 (init+a4) -21 (init+b3) -30 (init+b4) -30 (init+c3) -22 (init+c4) -24 (init+d3) -19 (init+d4) -18 (init+e3) -19 (init+e4) -17 (init+f3) +20 (init+f4) -19 (init+g3) -18 (init+g4) -17 (init+h3) -16 (init+h4) -14 Then we can see that (init+h4) is the position after the init position since it's mate-in-14. Second best move is h3 (mate-in-16) and note that the f3 is a very bad move because it gives away a mate-in 15 to a lost in 20. Note that the positions in a tablebase are stored sequentally so the COMPLETE.BTM will only contain 16 bytes (20, .., -14) The most difficult part to program tablebases is to number your positions sequently. What means is to wrap a3 to position 1 and h4 to position 16. If you really understands tablebases good you might look at bob's chessprogram crafty and look at the egtb.cpp. This file is really difficult to understand.... Michel Langeveld
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.