Author: Guido
Date: 07:27:34 10/08/01
Go up one level in this thread
On October 07, 2001 at 17:34:46, Bob Green wrote: >I am working on a non-chess game. I've got it playing ok, but humans kill it in >the endgame...even "won" games it just doesn't see deep enough to play them >well. > >I can see that if I had a tablebase for the common (at least) endings that the >program would strengthen significantly. I am asking for some tips and tricks in >construction of tablebases. > >I have RTFI (read the internet.) However, I RTFI before my first couple >attempts at writing this program and still missed some important concepts - I >was way off base on bitboards, for example, in the beginning. If anyone could >help me avoid the stupid tablebase errors I can't see because of ignorance I'd >be much appreciated. > >Best regards, > >Bob Green I solved the problem in subject for chess and draughts, so I can you suggest some ideas and tips about it. Considering by example a particular ending in chess: you have to define some important things before starting writing the program: - How many position are for that ending? Consider the necessity of eliminating positions duplicated by symmetry. In chess there is an 8-fold symmetry (only pieces) or a 2-fold symmetry (with pawns), in draughts there is a 4-fold symmetry or no symmetry. This fact depends on the game you want to apply tablebases to. - Wich algorithm must be used to convert a position into an index and an index into a position? (don't associate an hash value, instead of an index, to a position, because the cost in memory space is higher). In chess it is convenient for the index to associate the 2 Kings; moreover, if you have duplicate or triplicate, etc. men, it is convenient to consider them together (you need of tables for indexing and inverting indexation or you have to solve diophantine equations) , and the pawns before pieces. - Which coding must be used for victory, loss, draw or illegal position? Do you want to keep the number of moves for victory and loss or only the result? Is one byte sufficient for any position? - When you compute an ending in chess, you must have computed all the ending obtained by capture or promotion, so you have to follow a correct sequence in computing endings. This is not a very easy problem, because if your program accepts a command like this: "compute KPPKP", you need a recursive procedure, that produce all the ending to compute in a correct order. - For the ending to compute, I follow this procudure: I allocate a vector in RAM, with each byte corresponding to a position, and examine each position, setting illegal positions and initializing with an undefined code the legal position. In my program undefined code correspond to draw, but doing so I cannot set stalemates at the first (or zero) cycle (stalemates are obtained at the end together with draws). To check illegal position in chess I use two different ways: the first refers generally to a check control, the second, more restrictive and time expending, considers also the existence of a backmove (e.g. White: Ka1, Pd2; Black: Ke3 with move to W. or B. are both illegal endings, but the second is found only with backmove). Now you have to execute the computation. Use of disk files, instead of RAM, is practically impossible in generating tablebases, for I/O time reasons. I don't explain the method to you, suggesting you to find a very clear message of Nalimov about the algorithm to use, but I don't remember when he sent this message (one year ago or more). He explained the normal method with a forward move, instead of the backmove method described by Bruce Moreland, that IMHO has a lot of problems. Reading the Nalimov message you can understand why it is necessary compute two endings at the same time, i.e. with move to White and move to Black. If you compute one ending at a time, you multiply the cpu time by 10-20. Excuse for my english ... Ciao Guido
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.