Author: Don Dailey
Date: 18:46:17 10/22/98
Go up one level in this thread
On October 19, 1998 at 07:19:14, Rémi Coulom wrote: >Jean-Christophe Weill wrote in his PhD thesis that the best technique consists >in using BCH codes. This comes from results of the information theory and >error-correcting codes. I guess the idea consists in generating numbers to >maximize the Hamming distance between them with a special technique. According >to what I remember of what is written in his thesis, these codes are >significantly more efficient than random numbers. > >I unfortunately do not know more about them. If someone can explain what BCH >codes are and how they can be generated, I would be very interested. I personaly >use a random generator I found in "The Art of Computer Programming". I think it >is the same as what Bob uses in Crafty. > >Remi Hi Remi, Socrates used a pre-computed table which was created by generating the numbers one at a time and measuring the hamming distance between them. I had my own table generated in a fashion like Ed's table, but when I brought the program to MIT, all the computer nerds there made nice little improvements like this one. It's probably an extremely small improvement, but every little bit helps! From what was explained to me (a long time ago), I think you count the number of bits that are in common with every other random number and try to minimize the worst case. You can generate each random number, and test them one at a time trying for some upper bound of n bits in common and if you fail to create this table, try for only n+1 and so on until you are successful. It was sort of a trail and error process but gives you a better table. For instance if you had a random table with 2 4 bit entries like this: 0010 1011 2 bits in common (bits 1 & 2) Then an improvement would be to try for at least 1 bit in common: 0010 1001 1 bit in common (bit 2) But you can do even better (in this silly tiny example) by getting zero bits in common: 0010 1101 0 bits in common! If you had 3 entries, then you could not do better than 1. The idea is to generate a number, test it, and throw it out if it's not good enough (too similar to another number already in the table) and try again. Don't quote me on this, it was explained to me and I dropped it after this. I may have got it wrong but I think this was the way one of students achieved a quality hamming distance table for generating hash keys in Socrates. I think I'm going to try this now! Cilkchess doesn't currently do this but probably should! - Don
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.