Zobrist key random numbers

hgm · Post by **hgm** » Thu Jan 22, 2009 10:34 pm

bob wrote:Got an email from someone that is more familiar with this stuff. He first told me that it is possible to produce 788 numbers with a min hamming distance of 28. But that this will be a linear code where XORing any two of the numbers will produce another number in the set. Which is not so desirable. So I am taking that data point and trying to decide what it means with respect to Zobrist numbers...

Well, that illustrates my point in an even more dramatic way than I ever could have imagined. So maximum hamming distance actually produces a totally useless set of keys.

I guess we'd better get back to basics, and look for keys that makes the smallest difference that must exist between two positions before they can collide as large as possible. I.e. analyze the set in terms of dependent sub-sets, and make the smallest subset of keys that could combine to zero as large as possible.

For a 64-bit key this will be hard: in a randomly chosen set will in general not be any dependent sets of 7 or smaller. We have about 3*2^8 keys, so the number of combinations of 8 keys is about (3*2^8)^8/8! = 0.16*2^64. As each 64-bit result only has a 1/2^64 probability of being zero, this means there is a fair chance none of the combinations of 8 keys hits zero.

The number of 9-key subsets is ~768/9 times as large, or about 15*2^64. Thes means that the probability of 0 nort being hit by any of them is only exp(-15) = 1/2^22. So only after several million tries you would find one. But fortunately the 1/2^22 probability of 0 being hit is the same for any other 64-bit number, i.e. 1 in 4 million numbers will not occur amongst the 9-key "products". It is just a matter of finding one that doesn't. Then you can transform the set by XORing every key in the set with that number. As 9 is odd, this means that every product of 9 keyys will also be XORed with that number. This maps the number that could not be made by combining any 9 keys onto zero, so that in the transformed set no sub-set of 9 keys is dependent.

One problem is that making all combinations of 9 keys out of 788 is totally undoable. I could not go farther than 4, and even that took a full night.

Dann Corbit · Post by **Dann Corbit** » Fri Jan 23, 2009 3:17 am

Here is a set of 999 unsigned long long integers with a hamming distance between any two values in the set of at least 23, together with the verification program:

Code: Select all

static const unsigned long long hv&#91;&#93; =
&#123;
    7266447313870364031,
    4946485549665804864,
    16945909448695747420,
    16394063075524226720,
    4873882236456199058,
    14877448043947020171,
    6740343660852211943,
    13857871200353263164,
    5249110015610582907,
    1235879089597390050,
    17320312680810499042,
    16489141110565194782,
    13520575722002588570,
    14226945236717732373,
    9383926873555417063,
    11510704754157191257,
    15864264574919463609,
    6489677788245343319,
    5112602299894754389,
    10828930062652518694,
    15942305434158995996,
    236502320419669032,
    14931360615268175698,
    8904234204977263924,
    12836915408046564963,
    12120302420213647524,
    15755110976537356441,
    17251681303478610375,
    18286145806977825275,
    13075804672185204371,
    12903857913610213846,
    560691676108914154,
    1074659097419704618,
    14266121283820281686,
    11696403736022963346,
    12893913769120703138,
    2511068401785704737,
    3774730664208216065,
    5083371700846102796,
    9583498264570933637,
    17119870085051257224,
    5217910858257235075,
    10949279256701751503,
    15596196964072664893,
    14097948002655599357,
    5636498760852923045,
    17618792803942051220,
    13212228678420887626,
    6210242862396777185,
    1012818702180800310,
    15299383925974515757,
    974125122787311712,
    1861591264068118966,
    997568339582634050,
    17981867688435687790,
    9460108917638135678,
    16172980638639374310,
    15773550354402817866,
    16475327524349230602,
    13554353441017344755,
    6788940719869959076,
    11670856244972073775,
    2488756775360218862,
    2061695363573180185,
    3566345954323888697,
    6864898938209826895,
    7198730565322227090,
    10827695224855383989,
    11016608897122070904,
    3956319990205097495,
    5804870313319323478,
    8017203611194497730,
    3310931575584983808,
    5009341981771541845,
    14415278059151389495,
    6715939435439735925,
    411419160297131328,
    4522402260441335284,
    3381955501804126859,
    9219789505504949817,
    11628184459157386459,
    7242398879359936370,
    13965005347172621081,
    5806488997649497146,
    10724207982663648949,
    957364844878149318,
    8197027112357634782,
    12052913535387714920,
    2889379661594013754,
    10511508162402504492,
    6801855569284252424,
    16465954421598296115,
    5975570403614438776,
    3688303938005101774,
    2210483654336887556,
    6558785204455557683,
    16822351800343061990,
    7444710627467609883,
    3200233909833521327,
    3612068790453735040,
    18266943104929747076,
    1620389818516182276,
    3906668377244742888,
    5770016989916553752,
    6384853777489155236,
    10311708346636548706,
    17771199061862790062,
    12121348462972638971,
    1257976447679270605,
    3664184785462160180,
    10718876134480663664,
    3611366553819264523,
    14492630642488100979,
    2903980458593894032,
    12026985381690317404,
    15535375191850690266,
    10333316143274529509,
    16565481511572123421,
    14237704570091006662,
    6454343485137106900,
    18107191819981188154,
    3559348759319842667,
    18059264986425101074,
    3139684427605102737,
    4715785502295754870,
    11077531235278014145,
    10637177623943913351,
    10137911902863059694,
    13719113891065284171,
    13776316799690285717,
    8687650838094264665,
    3028124591188972359,
    3982930188609442149,
    13815150225221307677,
    16924127046922196149,
    5437280487207382147,
    10760687291786964354,
    216630713752669403,
    10655207865433859491,
    1524477318846038424,
    3443401252003315103,
    16860120454903458341,
    15362920279125264094,
    14358245326238118181,
    4224273587485638227,
    13919998707305829132,
    14473305049457001422,
    12955027028676000544,
    17930425515478182741,
    7466411836095405617,
    10879629128927506091,
    11502219301371200635,
    4978473890680876319,
    845759387067546611,
    9092379465737744314,
    7562781050481886043,
    3514744284158856431,
    14980707022065991200,
    18294903201142729875,
    8979482998667235743,
    16495638000603654629,
    17504300515449231559,
    1406052433297386355,
    3296968762229741153,
    6214378374180465222,
    11439178472613251620,
    10972816599561388940,
    10020049344596426576,
    9381977959648494876,
    15282520250746126790,
    4891472444796201742,
    4564628942836375772,
    12627401038822728242,
    8515217303152165705,
    2836463788873877488,
    5327734953288310341,
    4193447453292207765,
    8727015815475533844,
    1794828640516310551,
    839109216263472222,
    11003569267662299508,
    14818712892121773001,
    11341937060697364828,
    16294497818497013091,
    7938847863410484112,
    12460847944021797729,
    8608832166868962581,
    17282690963297781165,
    5236305832299547005,
    13653613720566641032,
    12795694179935286147,
    3619745730869440312,
    7023474619158759074,
    6411707388950674382,
    11610566205662556902,
    12720426256176311341,
    963006111335524252,
    12602026180005991793,
    10977961698003017025,
    14314905386630121264,
    593861932304949197,
    1759320944513001478,
    9844433545111928009,
    7516448510961597387,
    6979677882708694852,
    2623982553786190271,
    10956409229583802704,
    10773480483945135813,
    15589196139318714477,
    13992302356379003709,
    4144556090023237143,
    2683982833995814204,
    14174237260119144415,
    5498804830346368935,
    10015422821119519276,
    14006884420982275271,
    15325155849418805462,
    2337041946913300563,
    17100624240218191776,
    9703324598394127586,
    17019689424591946956,
    5780649476454802027,
    14414929270030064142,
    18404798721277276349,
    13727527782081926783,
    14049840052842737870,
    13090081540345862947,
    9489259826421593604,
    11339178955354061847,
    2431380992571392509,
    13011028955371218345,
    17577910823749512297,
    6646205212361830820,
    6563389574948647110,
    5615534989929158531,
    5753528745081333993,
    1974805642753365513,
    2848156987029842825,
    17613615095014857579,
    2011506583012245120,
    2444313452813434980,
    295943014965754495,
    9882162289524262117,
    12675922461078850762,
    3834401558737001127,
    866051294803417039,
    2724626095286417021,
    18307426813116457025,
    17948009628770529172,
    6685233615168851649,
    13500066391123604136,
    12479713940936428223,
    9424117665582424405,
    6039353791193701794,
    6601976231243625663,
    15224447585169584601,
    2728973181524205713,
    3462528993083828381,
    11340412255977527276,
    16097257884801829806,
    15873188707503643756,
    13772224761560358678,
    13111754990776650992,
    96905898085114986,
    11176895769597467160,
    600926880159025491,
    17204915804540124261,
    1144214061925539673,
    6442316514250842898,
    12890767762330780561,
    1678595440397729949,
    17555837092409264409,
    11850798096946224952,
    18347395534780169545,
    2902301657143828160,
    4513207106323818436,
    7208587791955414370,
    14036122687726750680,
    5845312298939252013,
    8658865064369425702,
    17865168032283289844,
    4257028217766215264,
    6122026574733783975,
    9170295234685582608,
    4625842927060587645,
    10364408876534383966,
    3160614275850263182,
    4048844641307615001,
    9202228564570972667,
    10244349660455576579,
    4365624743606344104,
    7914034060710558862,
    14082118313143494030,
    13893540545824007220,
    12557303001492689466,
    18034204128425921887,
    340230915844217824,
    13885363215660853141,
    182790206115731779,
    10275690770029126957,
    2207732794522698303,
    4015366832566852941,
    3344126814245426647,
    3418909431246792130,
    18170060564269107324,
    16825303559054309655,
    3076199647024046233,
    8592572442492131294,
    13847613594546126389,
    8025098507225669679,
    9851016542364179299,
    10069389887474709588,
    6112305132354510512,
    18059298976380052840,
    6186105518604848851,
    2104877594513762728,
    3056571032953733,
    1344029458328294184,
    11681380657174477138,
    5579944120707736744,
    38527987932692056,
    5019284574311325165,
    11861800887103445942,
    17678318898574268818,
    17331386544906712071,
    14625477349934894239,
    9197216899815357998,
    15895416949726083115,
    1591794355990697234,
    11846598379562363642,
    1968673912932124150,
    7694531300856204513,
    12056737119287626344,
    16294510520227781408,
    1849214443991414572,
    5204647870090191978,
    14004367337513854673,
    5094632487920517113,
    6933045759333815331,
    14735964389804262666,
    1431787135216247150,
    3027992589588197224,
    15666375125344846699,
    4967011828356632134,
    9679911049165960321,
    5759747806256240828,
    3841970197407798734,
    538876215104951112,
    16738327113730050814,
    4796759719169426917,
    17526144157780855210,
    4406271885088510609,
    272679168754122071,
    14117891565238258794,
    6239715909555052601,
    7331448258562910929,
    11606443195551224899,
    8233214365892470430,
    3170421326472746759,
    2532665202646579370,
    5465487865142825507,
    4288533736509213790,
    11640137442758811293,
    16473912850801955436,
    1612487638443769146,
    15199712313667690185,
    15106844553931914257,
    6143426764259491757,
    972664709081254460,
    8017518460018236671,
    11529724129963821248,
    13568352186393728922,
    13655575427028990950,
    9369396776556321785,
    6740149707310754612,
    12655055223902686386,
    316739669461445705,
    6378569413102905018,
    3632760136062488749,
    8236711185392647459,
    14695725533898965208,
    2917914788653649637,
    14904065006021498857,
    266141044306879911,
    7789385148154111845,
    9276496317333538947,
    3649103956926581942,
    8720151215550917497,
    4068307906424987783,
    15743036865071709307,
    899343666030374137,
    12803792226239136366,
    8248569087391634204,
    14570577633538746290,
    18024782582587949048,
    17994440334793743113,
    6447785911588669456,
    3796105823204027729,
    7666445045503776980,
    12454886681445086127,
    1412939819494326923,
    17743268430580248211,
    12945634703337535830,
    5730300706238953677,
    17663059373094704715,
    2805561707037079926,
    376290161476154776,
    18122210988913566163,
    10080823601656395959,
    14090238559147233762,
    17941097701698322371,
    15544416989640379719,
    14256466529909301342,
    13476108746956868517,
    560073126797980624,
    15840078975005802326,
    17723856983309373632,
    10960957671863881057,
    14715668988943444743,
    14853791396081808224,
    18103339564082223846,
    8695438280450667241,
    14502185569048036116,
    6773610541650113645,
    9345536836128693432,
    16870200170094625047,
    9948947958385916645,
    7609902932318462874,
    10560240575947025563,
    11912847058379669493,
    11032566756363179838,
    7150777503809066368,
    1113352174879837739,
    16433621322552428267,
    1932875827204412222,
    10122216141432847859,
    15200026780478921060,
    955438079876855847,
    4390726732378888763,
    4448489696876757548,
    10483378997497959924,
    12895655159111645470,
    15055313665129522508,
    9746481362587815484,
    15593856518331513408,
    12024766416872403891,
    13319421147871442929,
    7593615777716483669,
    1316310554514291685,
    6300303343646765998,
    14990138932076746755,
    12575731278303794469,
    8616043469741522133,
    5832251812528047834,
    93558474256533534,
    18067818861367010250,
    14797889806118094651,
    415543360438799158,
    8194481953080600754,
    5680356099160703410,
    17502533412824746877,
    6100828799957981067,
    7168482564972963076,
    3466436653047686102,
    5424122980892706297,
    3984433389958159180,
    15910815059630032243,
    8181619872058048777,
    1661718840207068211,
    13411569453877055172,
    10911778211788973168,
    6523296957524480156,
    8757115845172666540,
    15662809124003336360,
    7090540720100204813,
    7444425877460386815,
    4829814737671235249,
    13798208304107335546,
    7007177217067526641,
    14204094315557980993,
    7739365733068891583,
    10243365164320531876,
    14898424495793766951,
    11356786232039989287,
    14252160528052174991,
    9160514444749429801,
    5414672451498595302,
    7065189374087547575,
    795488996564666104,
    10198305958935766197,
    10668714513951143326,
    3419453460176799224,
    9568203776865882506,
    3384466374186365972,
    1737271475564685705,
    500593126082111186,
    7660625790259624634,
    11640848311215376089,
    6537455579313128620,
    142340399285261373,
    11134370432859116258,
    8842208967633864131,
    7808693772246775283,
    11818747394676272348,
    13562795926694249981,
    5093343192598484846,
    6570900311512235738,
    13122173297186705187,
    4860828980266768693,
    10983886834137974504,
    8274301297846729936,
    1797959588777595638,
    375263153417117750,
    16808921818031018405,
    12622248215401065289,
    13577234596739432319,
    2424796270238574506,
    13125995887770919878,
    2977392890624223832,
    4093525481259338150,
    16298403536256340045,
    15427825321755958043,
    15494035220426340476,
    17147049047817936382,
    1979110379897059036,
    11000661401608450307,
    6611566949761648413,
    3401463964417309033,
    4369308028240848393,
    4629081379435499768,
    8990137430054332707,
    15390525649802769016,
    8074132056979870755,
    1502161945191883513,
    15167823569568572156,
    1452783030375940330,
    7909335555924414126,
    11228236778200373849,
    333233094234370048,
    3318643278058236428,
    7350236101554952157,
    2658937705804712956,
    9157021194503811342,
    4635767814692501546,
    9472003490482701807,
    14356234451316843385,
    5666566728962373778,
    6240960044712709557,
    4853952732146413086,
    12952526968311338701,
    3753748956078835983,
    3872709083526657846,
    13018369927512579537,
    16928459174379279888,
    12522125007431924253,
    3383918517187096671,
    2391045522916219463,
    7748575613834223204,
    4875548245595043864,
    7270052715795133625,
    6639863592001348421,
    2012415473511352736,
    11510402350156337009,
    5789823010686330324,
    18432989548752008190,
    12284635513482943602,
    16410340887848707921,
    15553439284678492869,
    13581209645191346986,
    4096124489634445925,
    8883900193884873096,
    8246194633265787216,
    17378232394989440181,
    10543506148110863377,
    6755989823836673353,
    3854356919633216030,
    10224221529230178237,
    14956254920679686223,
    11801122998951810396,
    3832732292965167475,
    3707192126699181012,
    6952415589146728859,
    8750388019701674489,
    17530209217594959360,
    14341608797835247858,
    10249335584835312966,
    15866751467596828883,
    7845691477505129009,
    15107198132661562823,
    5600819723908136519,
    14302607041357787669,
    12592339570245237590,
    556013807694270877,
    531019300009435734,
    17405486901069728290,
    10665301228830556232,
    16596696244711642791,
    2214265345799230874,
    8211244747951370630,
    1322702445802452360,
    713957012861037567,
    10160909976287599756,
    7473839231027950791,
    12009676050495040019,
    17652896452431720200,
    10012325529988667694,
    17960546758549620300,
    8618667949242292449,
    9887427400366272555,
    12810530938231017467,
    16984140304864748092,
    3849244442929899044,
    9046295126901750094,
    13058665224411221464,
    10218436031304141519,
    1280781496668643066,
    13488117173221050851,
    1839141432307921563,
    7973005670583750543,
    14198182450678473889,
    7206447910448861965,
    4583829617955212159,
    1589777889987744679,
    313752729175327821,
    7334685460893112382,
    8598844999483354885,
    3148068724384283718,
    13335650041995798543,
    1567783345244299062,
    14203279090208532847,
    12790517611662709259,
    11976962690517602127,
    4240796256825381958,
    16602097298936107154,
    15325889890686687508,
    5069060527078086642,
    13186007042316633541,
    11582242001616736704,
    12352777335890633799,
    18351815285787232877,
    7546946471898304015,
    12095073432274003250,
    8944390674545152846,
    12109793112259472258,
    9364617114955433729,
    6010702723051052021,
    13930995795140946314,
    3167987672766580849,
    632596638386808620,
    7779860973604876093,
    7947654306390904990,
    1675030658236680377,
    11624999461433824079,
    13440803808148012466,
    7751032689193916523,
    17117428786174840120,
    6319126687835161224,
    10826961732146985546,
    11748002111746880620,
    12131345684254666224,
    9875426906550439942,
    2333163570371212717,
    12969390694073338316,
    9212931111128487440,
    15835166439425734989,
    17508316415391944531,
    7381706450201278935,
    12470544854420395865,
    12090754068074150285,
    2191357356032384464,
    17645697804267529825,
    1816601009880919192,
    4561120550537314832,
    13507503391516994871,
    2660396017750569835,
    17755187334285783028,
    2646529208403087750,
    10388257665652935600,
    14453582192751123442,
    18110353644471153527,
    3716954225262189308,
    1686024430943572105,
    5702968287454907620,
    1956902727697937167,
    17133775405710140992,
    1068264636956363649,
    6478024642121015779,
    16238687947785625011,
    9037794509879725763,
    9492872233752812516,
    3013075772257500841,
    17861131227795523840,
    3207568859556488759,
    12647523883169324699,
    2138904502201427544,
    3275011697176927090,
    15358214018396172571,
    12992112402073705045,
    16845554512649653215,
    18742449639875519,
    13596859891559196740,
    13426075886730108038,
    11498193401679392747,
    16554918849778015914,
    6693259110504680952,
    11068007414114481498,
    15031600615271110846,
    16915039384378332941,
    16965971652048442808,
    2805228884283956864,
    13266457154030204801,
    9113356832988394628,
    4752139457708102565,
    9374187400479837644,
    7987308013595423555,
    11335557882091649491,
    6564107756504388667,
    16676671079038635603,
    14389610754465776508,
    12208907610723030280,
    1404207627336892455,
    18129093985541615599,
    3011957003813591363,
    5103731539216620120,
    11985408831071816364,
    8886212782077038379,
    15499287571778887269,
    6115644674788544842,
    6940921379544017100,
    12008303302613859394,
    4327726256281669977,
    17396637511609480109,
    17522490609682186116,
    10764289495492126947,
    15846495635508069559,
    4006579737119843560,
    8501453419409626034,
    14902345471454293510,
    8209387058803615393,
    5879028109713426756,
    14379486780292781325,
    3662741253618663411,
    15089075459218275296,
    8982422692653457875,
    15825534325394635716,
    4160847737723961071,
    7522695362760546344,
    6944892085190875384,
    9006190430756193652,
    16537475877644756205,
    10391543545289139615,
    9468957811727775505,
    2874535243372953467,
    16610417466473455962,
    5432043386984263822,
    11300736915872747595,
    11175465018812210620,
    5346505397788459142,
    17382992222512285672,
    18416667481474744028,
    15729805885816281093,
    528619548661104339,
    4193727026216190840,
    8540759065024435797,
    12809588388077246964,
    4157381666307796279,
    13439545384268686349,
    10476601131560645152,
    14635021400113324010,
    7385869810852767216,
    17489804380727317749,
    473178655303644430,
    6824661581052651634,
    14493986231731557855,
    17888886488826311210,
    14413582266175909482,
    2437572569965628929,
    12774941764325664375,
    11201369941043626547,
    11495541249571049899,
    12839439816503949388,
    14846618736338472665,
    16650820008437737103,
    9948580981250172830,
    5184041577668404165,
    10379222904510705383,
    13832791432129388436,
    12276909775202651292,
    7410127810410338732,
    12130683480226924607,
    14017496135319544031,
    6860653085190953429,
    3443041819506891188,
    693572503710819543,
    3531472405562073275,
    15668286819122906112,
    15427477814700549439,
    12073839964796618661,
    17507605560077946920,
    2455365195181918791,
    5964998669248654874,
    15447880721255769419,
    4469176972055685202,
    15211694042356568608,
    3759814231605665372,
    18168445266382181794,
    6509891475561581108,
    12124751967199354237,
    17848311530842249744,
    17627624472618765247,
    1223563903634178192,
    2918849287364629264,
    2746577282574245190,
    18249210529947804762,
    1387152020856480609,
    3855972378689829637,
    14111119528432513185,
    6580174121676077055,
    18265787066455576602,
    10691648861204636862,
    6833173963338540739,
    8454814670236484282,
    15036345140247192881,
    9105289581939367919,
    16703249455563584555,
    10569135442141345919,
    397017240905668054,
    126198906736958735,
    16591722875182706201,
    5736319088835606273,
    15916827908810835259,
    16321683770365590218,
    4536445586451618173,
    9199827198413403170,
    2588029247400550403,
    1504353623037103694,
    16291177629896936087,
    17607652200238400897,
    8608613475795573363,
    11073999877499529823,
    6137426931543344516,
    9904132037255723930,
    8387063053307637544,
    12799167212889110256,
    1582138086466835469,
    2152637828481304815,
    9518572228217762038,
    2667365841612231331,
    4468008077840874014,
    5701303945024779477,
    1133342182672443762,
    206906033204807862,
    15966052328639450609,
    5260887676802211741,
    15828710583586904656,
    3898888340173174836,
    4579391617260611811,
    14117269767630916245,
    17192661558883417988,
    14689134343744909693,
    4822657501955836659,
    150346449052704908,
    10942678315341981259,
    7179430164587258733,
    8204158981571868481,
    640897296224571805,
    6929256402430803646,
    744710678740529997,
    17038755122004887380,
    539869924635637454,
    8370976664958749397,
    8831157006671597648,
    7530916665077962181,
    17900183066115623108,
    17313061461089263906,
    13278934098831202435,
    4649693218485093387,
    6506128976922509898,
    7156327130993769728,
    13710825350502898857,
    3847028599720329555,
    15300029126015513489,
    5307296276797954524,
    10307862905187684465,
    1021419217831496571,
    14814729549411911689,
    9651103809455346390,
    13705974836122304959,
    2934250012830850394,
    1712853947982808748,
    3971845847600813666,
    4312331471581529866,
    18158963739227916677,
    4912383497125342902,
    11767805446709862191,
    5837791797322372300,
    4280839750317586285,
    11441089604893336260,
    15007142198094502655,
    78558308018194092,
    6157522927310358922,
    10748914372014524199,
    1087519451361903051,
    8697875628307095161,
    12370526051357691561,
    14580162363352312186,
    6906234220114905800,
    4001992502751114884,
    6835942929231201244,
    10773061762698089520,
    3739093069289124478,
    17226616569160696743,
    3746396185392507714,
    11749010227716021739,
    18329875333055196402,
    9328805024168215232,
    18326846329182336830,
    7864113836212088352,
    8632906575615437655,
    9929602338341296210,
    5488280487079477228,
    14851515617797053839,
    1067030296549639338,
    8968692861934042231,
    2264068556491491655,
    1291626804503605983,
    926535429656165596,
    11543054245283292106,
    7742218487250056129,
    5071309935390453142,
    16569502904543228770,
    2351075752826326858,
    17251784061974976237,
    11936111316835082317,
    6410718887407613269,
    8743682305927613281,
    13223740406949177527,
    6725775953712621434,
    12088678151477776184,
    7320987977551321563,
    9708960639464774335,
    7750510303021212946,
    319807175517368100,
    9008098909015705346,
    8161326682307968782,
    12040500502698228123,
    3723361754840518673,
    12043010603003157382,
    8186709246103764519,
    4688644908017068344,
    12405068012272178438,
    7647822692436387928,
    4174323561165921234,
    11840856079710028784,
    10598095989775503487,
    4531327690212076505,
    11130170404728345283,
    7251550486653591614,
    16403556223928989197,
    1692227212702948779,
    5821715994935656416,
    2348166903701185144,
    2456420171697933448,
    7398215173361784370,
    5614728521334926184,
    3097952821735941358,
    606973936486796656,
    15730454819296692121,
    1213589577758184919,
    983310842898567098,
    1022998234853242898,
    17252118354085148356,
    8771981983160803190,
    13212782050966421171,
    12569040577016007049,
    7689723821800275588,
    15893022330228492985,
    4836043071250634654,
    5976005588719377421,
    17756007855636702326,
    679258052061662094,
    18326605743438352635,
    3521322379055091096,
    7903820533464214228,
    13236630304901299465,
    2302890026693203808,
    2780201394556298152,
    8416250861538231629,
    18097311394382489158,
    13895470892158899718,
    11960304351885790173,
    3657991612441973492,
    16614898857769705685,
    1447976981583137012,
    3047035707044200937,
    5779039202666699403,
    641739833565391248,
    16580648647756784598,
    16754708488282152628
&#125;;

unsigned long long hamdist&#40;unsigned long long x, unsigned long long y&#41;
&#123;
    unsigned long long dist = 0,
                    val = x ^ y;
    while &#40;val&#41; &#123;
        ++dist;
        val &= val - 1;
    &#125;
    return dist;
&#125;

#include <stdio.h>
#include <stdlib.h>

int             main&#40;void&#41;
&#123;
    unsigned long long i,
                    j;
    unsigned long long maxbad = 211,
                    totbad = 0;
    unsigned long long len = sizeof hv / sizeof hv&#91;0&#93;;
    for &#40;i = 0; i < len; i++) &#123;
        unsigned long long badcount = 0;
        for &#40;j = 0; j < len; j++) &#123;
            unsigned long long hd;

            if &#40;j == i&#41;
                continue;
            hd = hamdist&#40;hv&#91;i&#93;, hv&#91;j&#93;);
            if &#40;hd < 23&#41; &#123;
                badcount++;
                printf&#40;"(%llu,%llu&#41;, hamdist&#40;%llu,%llu&#41;=%llu\n", i, j, hv&#91;i&#93;, hv&#91;j&#93;, hd&#41;;
            &#125;
        &#125;
        if (&#40;len - badcount&#41; < 788&#41; &#123;
            printf&#40;"hv&#91;%llu&#93;=%llu is bad\n", i, hv&#91;i&#93;);
            totbad++;
        &#125;
    &#125;
    if &#40;totbad > maxbad&#41;
        printf&#40;"Too many bad values.\nMaximum 211 bad values can be tolerated but there were %llu.\n", totbad&#41;;
    return 0;
&#125;

Dann Corbit · Post by **Dann Corbit** » Fri Jan 23, 2009 3:37 am

Here is the data reformatted a bit together with an interface:

Code: Select all

static const unsigned long long ham23bit&#91;999&#93; = &#123;
    0x64d79b552a559d7fULL,
    0x44a572665a6ee240ULL,
    0xeb2bf6dc3d72135cULL,
    0xe3836981f9f82ea0ULL,
    0x43a38212350ee392ULL,
    0xce77502bffcacf8bULL,
    0x5d8a82d90126f0e7ULL,
    0xc0510c6f402c1e3cULL,
    0x48d895bf8b69f77bULL,
    0x1126b97be8c91ce2ULL,
    0xf05e1c9dc2674be2ULL,
    0xe4d5327a12874c1eULL,
    0xbba2bbfbecbc239aULL,
    0xc5704350b17f0215ULL,
    0x823a67c5f88337e7ULL,
    0x9fbe3cfcd1f08059ULL,
    0xdc29309412e352b9ULL,
    0x5a0ff7908b1b3c57ULL,
    0x46f39cb43b126c55ULL,
    0x9648168491f3b126ULL,
    0xdd3e72538fd39a1cULL,
    0x0348399b7d2b8428ULL,
    0xcf36d95eae514f52ULL,
    0x7b9231d5308d7534ULL,
    0xb225e28cfc5aa663ULL,
    0xa833f6d5c72448a4ULL,
    0xdaa565f5815de899ULL,
    0xef6a48be001729c7ULL,
    0xfdc570ba2fe979fbULL,
    0xb57697121dfdfe93ULL,
    0xb313b667a4d999d6ULL,
    0x07c7fa1bd6fd7deaULL,
    0x0ee9f4c15c57e92aULL,
    0xc5fb71b8f4bf5f56ULL,
    0xa251f93a4b335492ULL,
    0xb2f0624214f522a2ULL,
    0x22d91b683f251121ULL,
    0x3462898a2ae7b001ULL,
    0x468bc3a10a34890cULL,
    0x84ff6ce56552b185ULL,
    0xed95ff232c511188ULL,
    0x4869be47a8137c83ULL,
    0x97f3a778e242d0cfULL,
    0xd870d281b293af3dULL,
    0xc3a5f903a836fafdULL,
    0x4e38ddc2719162a5ULL,
    0xf48286b4f22cad94ULL,
    0xb75b43fb4c81784aULL,
    0x562f36fae610a2e1ULL,
    0x0e0e413e555bd736ULL,
    0xd452549efe08402dULL,
    0x0d84c9a356858060ULL,
    0x19d5b3643bc029b6ULL,
    0x0dd8131e97ffc842ULL,
    0xf98c6d63ff48a16eULL,
    0x83490ef054537f7eULL,
    0xe071f833e55ebfe6ULL,
    0xdae6e879b8eab74aULL,
    0xe4a41f17e70d3e0aULL,
    0xbc1abca3fbeeb2f3ULL,
    0x5e37299d89089ba4ULL,
    0xa1f735eb8235b32fULL,
    0x2289d719e7b146eeULL,
    0x1c9c9d0284d96719ULL,
    0x317e34c009a07a39ULL,
    0x5f45053666f3f84fULL,
    0x63e7074f03c73d92ULL,
    0x9643b3707db2cfb5ULL,
    0x98e2db6c665e7178ULL,
    0x36e7ac11d1f3a617ULL,
    0x508f0acb609bd756ULL,
    0x6f42d435193a1ac2ULL,
    0x2df2cab9d65e0b00ULL,
    0x4584c1fde5f1ad55ULL,
    0xc80d5b04f6337337ULL,
    0x5d33cf557e6c4475ULL,
    0x05b5a78be74ccd40ULL,
    0x3ec2cce5290785f4ULL,
    0x2eef1e9c4b36828bULL,
    0x7ff345b4eb7f3639ULL,
    0xa15f9c2826cb34dbULL,
    0x64822b68adefa772ULL,
    0xc1cdaa5f9ca79b19ULL,
    0x5094cafab11cbc3aULL,
    0x94d40a57481346b5ULL,
    0x0d493e410b68b6c6ULL,
    0x71c1b0ba9e52a2deULL,
    0xa7448d0059484568ULL,
    0x2819237e5e8cb03aULL,
    0x91e060fb399ecf2cULL,
    0x5e650b9a3cb34308ULL,
    0xe482d24e5b239833ULL,
    0x52ed7d9f45c6b578ULL,
    0x332f7ce3e077ecceULL,
    0x1ead372c068ebb04ULL,
    0x5b057c64bda94a33ULL,
    0xe974ffd57219e5e6ULL,
    0x6750ecdf35c8471bULL,
    0x2c6983c911c958afULL,
    0x3220a56d67450e80ULL,
    0xfd8137f8b59bd084ULL,
    0x167cc7f46a511504ULL,
    0x36374630d0ecb4e8ULL,
    0x501337e1a7f1e218ULL,
    0x589b8eaea60d54a4ULL,
    0x8f1a8c1b84b3ba62ULL,
    0xf69ffb64131633aeULL,
    0xa837ae34963616fbULL,
    0x11753aea03bb0ecdULL,
    0x32d9cca610dceb34ULL,
    0x94c1190da321d470ULL,
    0x321e26bf321fb60bULL,
    0xc9202ac8ba71c873ULL,
    0x284d02d7552a3e90ULL,
    0xa6e86f7ba2779a5cULL,
    0xd798bd6d52ad26daULL,
    0x8f675048b7b012e5ULL,
    0xe5e469aac68eaf1dULL,
    0xc5967cdf353aeac6ULL,
    0x59926f3401f437d4ULL,
    0xfb49ab0635d66c3aULL,
    0x316558d69efc8f6bULL,
    0xfa9f65d2b4848b12ULL,
    0x2b92665a263a5091ULL,
    0x4171d5edd5468876ULL,
    0x99bb4bf79b0a46c1ULL,
    0x939ed8b0d7e91f87ULL,
    0x8cb11929a65b6aeeULL,
    0xbe6415659e12c64bULL,
    0xbf2f4f23a6c92295ULL,
    0x7890bc68793bb959ULL,
    0x2a060f45a1719347ULL,
    0x374635e7713ed165ULL,
    0xbfb945ef1cf94d1dULL,
    0xeade93e19d60d4b5ULL,
    0x4b7519cb9028ac83ULL,
    0x9555a4144e05ad82ULL,
    0x0301a07c84aaccdbULL,
    0x93dee719932225a3ULL,
    0x1528080b61f54198ULL,
    0x2fc96b31dccafd9fULL,
    0xe9fb2e3998d16a25ULL,
    0xd5340e98fde806deULL,
    0xc742bc0d0c55f125ULL,
    0x3a9fa27258257e53ULL,
    0xc12dc512aedc530cULL,
    0xc8db824276c083ceULL,
    0xb3c98071a3d13b20ULL,
    0xf8d5ab01c1ad6b55ULL,
    0x679e0601953d1e31ULL,
    0x96fc350ccdb76eabULL,
    0x9fa0178362df447bULL,
    0x451717a061972d1fULL,
    0x0bbcbdae779cfbf3ULL,
    0x7e2e9ef35a5aafbaULL,
    0x68f4654bcc07435bULL,
    0x30c6e14df59f8cefULL,
    0xcfe629aa56717e20ULL,
    0xfde48d87e844ec93ULL,
    0x7c9d88364238519fULL,
    0xe4ec475d296a69e5ULL,
    0xf2ebc493b909d8c7ULL,
    0x13834d3d0e43ab73ULL,
    0x2dc12f9f04435661ULL,
    0x563de834c4e56a46ULL,
    0x9ec02036a6688a24ULL,
    0x9847468f925dc38cULL,
    0x8b0e5dca588e3f50ULL,
    0x82337b3f1764851cULL,
    0xd4166b32a26fc1c6ULL,
    0x43e20045bcb06b0eULL,
    0x3f58d1d6cd3aa0dcULL,
    0xaf3d8a578b6d6232ULL,
    0x762c21058ba50349ULL,
    0x275d24c9aa1607f0ULL,
    0x49efeab6642e9e45ULL,
    0x3a321e3dadbf9e95ULL,
    0x791c96a57ea29814ULL,
    0x18e883239eac0617ULL,
    0x0ba51d62eb24045eULL,
    0x98b487f3146aa174ULL,
    0xcda6a4dccb6b73c9ULL,
    0x9d66a7aa1fb4595cULL,
    0xe221af6f18e45563ULL,
    0x6e2c7411e8736390ULL,
    0xacedd32f47936b61ULL,
    0x7778b73e852e4d15ULL,
    0xefd873dd0e37c5adULL,
    0x48ab18694d85497dULL,
    0xbd7b6156c2c63188ULL,
    0xb193700fe9937383ULL,
    0x323beb9061b5af38ULL,
    0x617864f443ee06a2ULL,
    0x58faf5e64a26fbceULL,
    0xa1210472d9abf2e6ULL,
    0xb0880848c6f0ec2dULL,
    0x0d5d48f4beaf279cULL,
    0xaee3640ad56e1571ULL,
    0x98598e0027505d41ULL,
    0xc6a8c29b036a0730ULL,
    0x083dd247f0a9dfcdULL,
    0x186a5d13e79a2806ULL,
    0x889e7426b755fcc9ULL,
    0x684fca18cc613bcbULL,
    0x60dccc0ded809744ULL,
    0x246a423aef3f89bfULL,
    0x980cfc250f276150ULL,
    0x9583176b78273ec5ULL,
    0xd857f34b29fba06dULL,
    0xc22ea4dbd5d4eb3dULL,
    0x39846bce19845617ULL,
    0x253f6c2acb91153cULL,
    0xc4b501b09381f7dfULL,
    0x4c4faddbf9ff57a7ULL,
    0x8afdedfde82b6a2cULL,
    0xc262732b5299fcc7ULL,
    0xd4ade40c841b90d6ULL,
    0x206ed744bef46053ULL,
    0xed519f24bba3b7a0ULL,
    0x86a9224fd39784e2ULL,
    0xec32155b844684ccULL,
    0x5038fe125722e26bULL,
    0xc80c1dcc2a85da0eULL,
    0xff6afaec984bb0bdULL,
    0xbe81f9c9474c967fULL,
    0xc2fb0f16bcbf30ceULL,
    0xb5a94fce85369b23ULL,
    0x83b09f892f3e7604ULL,
    0x9d5cdb2eae76bc17ULL,
    0x21be002177dac1fdULL,
    0xb49075e6473925a9ULL,
    0xf3f148c32f156c69ULL,
    0x5c3c106d732d31a4ULL,
    0x5b15d80b4950f0c6ULL,
    0x4dee63522a811783ULL,
    0x4fd8a3e8ff9268e9ULL,
    0x1b67eb44e4c05609ULL,
    0x2786afb08475eb89ULL,
    0xf470219ba4d19b6bULL,
    0x1bea4e946fcdfe80ULL,
    0x21ebf22282a74064ULL,
    0x041b669aa8caba7fULL,
    0x89247e3e8fdac4e5ULL,
    0xafe9ec5185000ccaULL,
    0x353687e6f2b91aa7ULL,
    0x0c04d510680657cfULL,
    0x25cfd0ff7b4e767dULL,
    0xfe110bb08b44a041ULL,
    0xf91423aa2c286f94ULL,
    0x5cc6b88d98a3cec1ULL,
    0xbb59dedb371cb2a8ULL,
    0xad30d9b57c018abfULL,
    0x82c93115f2862155ULL,
    0x53d0184675025da2ULL,
    0x5b9eee674ed934bfULL,
    0xd3481a6a879631d9ULL,
    0x25df42a65e516091ULL,
    0x300d5fc62140a89dULL,
    0x9d613cdcdc06d7ecULL,
    0xdf64f2c261780baeULL,
    0xdc48e5079b7f1c6cULL,
    0xbf20c573c7a4df16ULL,
    0xb5f64fb1ef328cf0ULL,
    0x01584766a000e46aULL,
    0x9b1c4f7c166c5a18ULL,
    0x0856ebd04bdcc953ULL,
    0xeec423c4c81e3c65ULL,
    0x0fe110a084141f59ULL,
    0x5967b4bca28de312ULL,
    0xb2e534fb4bc88391ULL,
    0x174b91a8d27f409dULL,
    0xf3a2dcd21bae4919ULL,
    0xa4767e14b95adf38ULL,
    0xfe9f0b07bc28fd49ULL,
    0x28470bfae915dec0ULL,
    0x3ea221f3823327c4ULL,
    0x640a0c676fb84d62ULL,
    0xc2ca5337c9c10bd8ULL,
    0x511eb890eb7efd2dULL,
    0x782a77e63fc78d26ULL,
    0xf7edd3abf0e8e8f4ULL,
    0x3b14009bfec4fe60ULL,
    0x54f5cebbdc8233a7ULL,
    0x7f436eedfce43d10ULL,
    0x40324ba22633147dULL,
    0x8fd5c6f5d0bcc55eULL,
    0x2bdcc1f030155a8eULL,
    0x383062bfe3e25f19ULL,
    0x7fb4e21fbd34a1fbULL,
    0x8e2b3dbd42592403ULL,
    0x3c95d093014fd9a8ULL,
    0x6dd44c0c40febc8eULL,
    0xc36dbbfedbf0e58eULL,
    0xc0cfc583ea53a434ULL,
    0xae44808c64eb123aULL,
    0xfa465d1b01b5cd5fULL,
    0x04b8be3720801be0ULL,
    0xc0b2b846debda795ULL,
    0x028966b957f2d943ULL,
    0x8e9a964ff958a52dULL,
    0x1ea371479081823fULL,
    0x37b972dc22085d4dULL,
    0x2e68b99e9ef515d7ULL,
    0x2f72680378b2a5c2ULL,
    0xfc2905d06898087cULL,
    0xe97f7c71538c3917ULL,
    0x2ab0db47d30ce099ULL,
    0x773ef31c6d8dd7deULL,
    0xc02c9b3249cabe35ULL,
    0x6f5ee092d2b4202fULL,
    0x88b5d75a341d1b63ULL,
    0x8bbda8c0b3d73454ULL,
    0x54d345222cc99eb0ULL,
    0xfa9f84bc9bb56568ULL,
    0x55d976319b868ed3ULL,
    0x1d36070524abe9a8ULL,
    0x000adbef66a66385ULL,
    0x12a6f3abdf519328ULL,
    0xa21c99d12d00f952ULL,
    0x4d6ff19d2d5064a8ULL,
    0x0088e1003aa37e58ULL,
    0x45a814ba1e6c9dedULL,
    0xa49d950f7036dbb6ULL,
    0xf556015fdf981992ULL,
    0xf085743caa263407ULL,
    0xcaf8222921640c9fULL,
    0x7fa3140a9bb6be2eULL,
    0xdc97dd7f8d25782bULL,
    0x16173088784c1512ULL,
    0xa4679275d2886afaULL,
    0x1b52227e4ae5c5f6ULL,
    0x6ac8777364a88ce1ULL,
    0xa7522287d967ca68ULL,
    0xe221bafc730adb20ULL,
    0x19a9babd3fa1372cULL,
    0x483a9fa995b8246aULL,
    0xc25981e52898a6d1ULL,
    0x46b3c54157aabff9ULL,
    0x60372062a09ed423ULL,
    0xcc80a989bd16c50aULL,
    0x13debad04489e16eULL,
    0x2a0597379ceb6f68ULL,
    0xd96a252c2832036bULL,
    0x44ee5ef1085c4e46ULL,
    0x8655f3d016ea7481ULL,
    0x4feebc1d03bd18bcULL,
    0x35516b89f62115ceULL,
    0x077a7910033cd348ULL,
    0xe84a7bd3942b4afeULL,
    0x4291838cddff05e5ULL,
    0xf3395f4106d0c9aaULL,
    0x3d2638ef1e7dd291ULL,
    0x03c8c0425f3cfd57ULL,
    0xc3ecd3942b828c6aULL,
    0x5697ec8f7061e039ULL,
    0x65be8958f4cc6ad1ULL,
    0xa1125e97c0949443ULL,
    0x724240d826a9e69eULL,
    0x2bff996618bb1707ULL,
    0x2325d5954abdf8aaULL,
    0x4bd95041860bd223ULL,
    0x3b83eeb633e90c5eULL,
    0xa18a1355045cde9dULL,
    0xe49f18748ccb126cULL,
    0x1660b4f6be263d3aULL,
    0xd2f039d1584b1ec9ULL,
    0xd1a64b151227fc11ULL,
    0x5541d617c3507fadULL,
    0x0d7f99664658ca3cULL,
    0x6f43f28f8d861cffULL,
    0xa001cf0254be48c0ULL,
    0xbc4c786ce164979aULL,
    0xbd825980239dbbe6ULL,
    0x8206c8ba22545bf9ULL,
    0x5d89d272ad35eb34ULL,
    0xaf9fc9ad41abccb2ULL,
    0x0465490d1c862c49ULL,
    0x58853b160b2ba6baULL,
    0x326a2818b83450adULL,
    0x724ead2ee2d0bd23ULL,
    0xcbf1b48304af80d8ULL,
    0x287e840a5e8f4ee5ULL,
    0xced5e028693dd7e9ULL,
    0x03b185dea61025a7ULL,
    0x6c197485b66de765ULL,
    0x80bcbc406ae28883ULL,
    0x32a438b70d14ccb6ULL,
    0x79043354469a6b79ULL,
    0x3875887c6f5fe087ULL,
    0xda7a809e5c7a7c7bULL,
    0x0c7b1c4ca0bcecf9ULL,
    0xb1b035313ee4426eULL,
    0x7278cde1d73f131cULL,
    0xca351728d35427b2ULL,
    0xfa24e4426ccd7ff8ULL,
    0xf9b9182557579b09ULL,
    0x597b231ff002c810ULL,
    0x34ae7a2231de2d51ULL,
    0x6a64af267b4e58d4ULL,
    0xacd8a572ad4733afULL,
    0x139bc5479df6c28bULL,
    0xf63cc0a137236e93ULL,
    0xb3a8222c7c673956ULL,
    0x4f861e21c38af8cdULL,
    0xf51fcaeabbf1964bULL,
    0x26ef5b820f623976ULL,
    0x0538d9e87f42b598ULL,
    0xfb7f06e0fadfa1d3ULL,
    0x8be647a7bc1a78b7ULL,
    0xc38a9550f67b91e2ULL,
    0xf8fb954dbe4e3fc3ULL,
    0xd7b8dce4ec0fcd47ULL,
    0xc5d924c6637d605eULL,
    0xbb04c18180e60ba5ULL,
    0x07c5c78a9b0933d0ULL,
    0xdbd343e7475abf56ULL,
    0xf5f7ca0573fb50c0ULL,
    0x981d24edcd8a0d61ULL,
    0xcc388efa7e34ab07ULL,
    0xce2344937335b360ULL,
    0xfb3bfb6afd655ae6ULL,
    0x78ac670bb09872e9ULL,
    0xc9421cf06de78314ULL,
    0x5e00b2e645e5746dULL,
    0x81b2043cd8c75cb8ULL,
    0xea1efdac2c398117ULL,
    0x8a11c374d470bae5ULL,
    0x699bce65e00ba39aULL,
    0x928d82da6ffd2c9bULL,
    0xa552ef485a46fff5ULL,
    0x991b8d0309cf973eULL,
    0x633caa40d664d580ULL,
    0x0f736be77d9f0e2bULL,
    0xe40ff3861805c6ebULL,
    0x1ad2f452f375533eULL,
    0x8c7955f369d47df3ULL,
    0xd2f157d2daded964ULL,
    0x0d4265df1bf0f827ULL,
    0x3ceefeb335415a3bULL,
    0x3dbc35cf6953022cULL,
    0x917c71a7a7a815f4ULL,
    0xb2f6920b08c8791eULL,
    0xd0ef38031021254cULL,
    0x8742752903030e3cULL,
    0xd86881e2358f3a40ULL,
    0xa6e08d58a0b9f3b3ULL,
    0xb8d816f6f4b3f7f1ULL,
    0x6961f1512f97b655ULL,
    0x12447979a7ebfbe5ULL,
    0x576f2c82b74573aeULL,
    0xd007abf004301803ULL,
    0xae85f8f7f2111525ULL,
    0x779255e2cf447cd5ULL,
    0x50f0521f765cc6daULL,
    0x014c62efc7c9c81eULL,
    0xfabdc986e9e223caULL,
    0xcd5caa60470b073bULL,
    0x05c44e7c13ba0b36ULL,
    0x71b8a5eb8bb7e8b2ULL,
    0x4ed4adc6c03281b2ULL,
    0xf2e57d6814d30b7dULL,
    0x54aa7f7850f7d78bULL,
    0x637b90e99fcb6504ULL,
    0x301b41c51d4d23d6ULL,
    0x4b465b1ce62485f9ULL,
    0x374b8d0ec7a95b4cULL,
    0xdcce91ff642f0573ULL,
    0x718af3ecf14c0109ULL,
    0x170f9c7b231dcc33ULL,
    0xba1f775c5ad24ec4ULL,
    0x976e6c7875876470ULL,
    0x5a8768055da2109cULL,
    0x79878676c87620acULL,
    0xd95d79e9c4f750a8ULL,
    0x6266a937b703e10dULL,
    0x674fe9e4aec083ffULL,
    0x4306f2ea19d726b1ULL,
    0xbf7d1558b729af7aULL,
    0x613e7e8da58529f1ULL,
    0xc51f148602fa8b41ULL,
    0x6b67c0211a66e5bfULL,
    0x8e27be5863efa5a4ULL,
    0xcec1d624c8c40227ULL,
    0x9d9b68e83eca6027ULL,
    0xc5c9d87d3464c08fULL,
    0x7f20af5a5f1fdc29ULL,
    0x4b24c7e80eaad3e6ULL,
    0x620c984d815a4ab7ULL,
    0x0b0a250716f806f8ULL,
    0x8d87a93c991da4b5ULL,
    0x940ee3533e1cb59eULL,
    0x2f7456ce13d185f8ULL,
    0x84c916a3faa4518aULL,
    0x2ef80a3c53a1f414ULL,
    0x181c0733db73a989ULL,
    0x06f276cbc12066d2ULL,
    0x6a500291899efabaULL,
    0xa18c99dcfa32c6d9ULL,
    0x5ab9b53663dac4acULL,
    0x01f9b1d6c895d43dULL,
    0x9a853aea902e12e2ULL,
    0x7ab5d635419705c3ULL,
    0x6c5e0d9d1692f5f3ULL,
    0xa404a02315c0acdcULL,
    0xbc38bb095bb9c5fdULL,
    0x46af30a5e1fc976eULL,
    0x5b308704ea30bedaULL,
    0xb61b5316ebee0f23ULL,
    0x437522342ab99935ULL,
    0x986e9ae169e246e8ULL,
    0x72d43930f6b53cd0ULL,
    0x18f3a2b8519892f6ULL,
    0x053533d98cb86036ULL,
    0xe9454956050d51a5ULL,
    0xaf2b3be059c9eb49ULL,
    0xbc6c06ee32cc3f7fULL,
    0x21a69b5c544327aaULL,
    0xb628e7b725d2e3c6ULL,
    0x2951d30f226e2a58ULL,
    0x38cf1fbc9d7909a6ULL,
    0xe22f8fa9e087904dULL,
    0xd61aa563d80a5b1bULL,
    0xd705def12ae7387cULL,
    0xedf68e4291635dfeULL,
    0x1b7736679d0d76dcULL,
    0x98aa3342c138f103ULL,
    0x5bc1011c7941871dULL,
    0x2f346d743362b969ULL,
    0x3ca2e680898ee609ULL,
    0x403dccfd19a0d0f8ULL,
    0x7cc3625c6054e923ULL,
    0xd596218937083278ULL,
    0x700d1453c5e11423ULL,
    0x14d8c0549245a2f9ULL,
    0xd27eef2c87eea2fcULL,
    0x142952780d4600eaULL,
    0x6dc39ac85c3dceaeULL,
    0x9bd2b5dc2a9c1a59ULL,
    0x049fe1bbd13e7000ULL,
    0x2e0e307a7ce62a0cULL,
    0x660148ca886f57ddULL,
    0x24e671c17a61cbfcULL,
    0x7f144642ab1f710eULL,
    0x40558e441fef782aULL,
    0x837350fd617b45efULL,
    0xc73b972bbef72379ULL,
    0x4ea3b06acfd97892ULL,
    0x569c58183a81cdb5ULL,
    0x435cb44ae41fae1eULL,
    0xb3c09ea6f9dd56cdULL,
    0x3417fec98f12890fULL,
    0x35bea0649a08f736ULL,
    0xb4aa8a798c03ddd1ULL,
    0xeaedf7eda3945610ULL,
    0xadc786596503fa1dULL,
    0x2ef617f66dcdb05fULL,
    0x212eb33c1b359a47ULL,
    0x6b88787791d7de64ULL,
    0x43a96d4c2ff8b818ULL,
    0x64e46a6d375534b9ULL,
    0x5c2588c1e64a2345ULL,
    0x1bed8935ff24c9a0ULL,
    0x9fbd29f3e6e3cf71ULL,
    0x5059955a385765d4ULL,
    0xffcf225519d9f3feULL,
    0xaa7bcae9a84c9c72ULL,
    0xe3bd3e177f4a6751ULL,
    0xd7d8ea9faede02c5ULL,
    0xbc7a263749bd3b2aULL,
    0x38d85b8568707a65ULL,
    0x7b49f4284c882188ULL,
    0x72705e54288a3150ULL,
    0xf12be24a17880cb5ULL,
    0x92520efad54b8c11ULL,
    0x5dc218f333f05549ULL,
    0x357d6d32784e821eULL,
    0x8de3bb4f82aa77bdULL,
    0xcf8f4a9bd54d004fULL,
    0xa3c602d7af37155cULL,
    0x353099b6b95b7173ULL,
    0x33729799020793d4ULL,
    0x607bf12491fa999bULL,
    0x796f9f8ad926f1f9ULL,
    0xf347d0678506a600ULL,
    0xc707a1376e9640f2ULL,
    0x8e3cf4693de11d46ULL,
    0xdc320664e58450d3ULL,
    0x6ce17ed49e00ba31ULL,
    0xd1a78ca908bcadc7ULL,
    0x4dba1bdd4e8bbe47ULL,
    0xc67d11535e21b215ULL,
    0xaec0fa1f3f8ffb56ULL,
    0x07b75b9cb9d4519dULL,
    0x075e8f3d69f06256ULL,
    0xf18cb61e48f9ca22ULL,
    0x9402c2f5defb8048ULL,
    0xe6534f4d2f18d6a7ULL,
    0x1ebaa699aed2159aULL,
    0x71f43397dd6ef186ULL,
    0x125b2eddd1987588ULL,
    0x09e87c1ed87b2bffULL,
    0x8d02cdc9e3585c8cULL,
    0x67b8692eb9ccb4c7ULL,
    0xa6aaf0bce945ea13ULL,
    0xf4fbafcb5ff22f08ULL,
    0x8af2ed059e8c992eULL,
    0xf940ae1e2b24c64cULL,
    0x779ba8d60fa198e1ULL,
    0x893732d5b54bb02bULL,
    0xb1c82603e5694ffbULL,
    0xebb3c99f16dba23cULL,
    0x356b436d3a7ba624ULL,
    0x7d8ae57d1453794eULL,
    0xb539b2d575c70dd8ULL,
    0x8dcf2d6e4def8acfULL,
    0x11c63ffc3fd3defaULL,
    0xbb2f6b1b1eafc9e3ULL,
    0x1985f163746ab29bULL,
    0x6ea5ce6a2351cf8fULL,
    0xc50a13b6b4e024a1ULL,
    0x6402723172a9130dULL,
    0x3f9d08c059228b7fULL,
    0x16100691647d53a7ULL,
    0x045aac71e1ce044dULL,
    0x65ca0990dbc1983eULL,
    0x77553bf7e8d96f05ULL,
    0x2bb02fd35d713c46ULL,
    0xb911bf0ed215280fULL,
    0x15c1e2a5620f5f36ULL,
    0xc51c2f14919ce96fULL,
    0xb1810c003088920bULL,
    0xa636b81c40688f4fULL,
    0x3ada55ba14e21446ULL,
    0xe6667f881d8f1092ULL,
    0xd4b07fa7d1215914ULL,
    0x4658ebb13d7197f2ULL,
    0xb6fe1b8ae31505c5ULL,
    0xa0bc63bc30f991c0ULL,
    0xab6de18a0741e447ULL,
    0xfeaebec534ee8a6dULL,
    0x68bc23d4ac62ce0fULL,
    0xa7da553446f4e532ULL,
    0x7c20dbedd894934eULL,
    0xa80ea0acd7b2ab82ULL,
    0x81f5cda672764701ULL,
    0x536a4e47d1ee5bf5ULL,
    0xc154d6ddb8d6298aULL,
    0x2bf6f400f0118871ULL,
    0x08c76f4a7d26e72cULL,
    0x6bf79e5605a4af3dULL,
    0x6e4bbd7bb208909eULL,
    0x173ee7824c1608b9ULL,
    0xa1544b6b14ded34fULL,
    0xba8753d9e0613db2ULL,
    0x6b91332a01d8186bULL,
    0xed8d52c9fbff4d38ULL,
    0x57b20c3e0f1b0288ULL,
    0x96411854e95e7a4aULL,
    0xa30949ad5336346cULL,
    0xa85b32a00d77adf0ULL,
    0x890c907302461006ULL,
    0x20610fe7d6dbb5adULL,
    0xb3fc881f197f89ccULL,
    0x7fdae8088af55610ULL,
    0xdbc1cffa7528794dULL,
    0xf2fa09044a93cf53ULL,
    0x667116e81074f9d7ULL,
    0xad1046792b4d9759ULL,
    0xa7cafcc3ee2b398dULL,
    0x1e6943e7ae3fddd0ULL,
    0xf4e21ca97d41a661ULL,
    0x1935dcfe64916c98ULL,
    0x3f4c5af99082c210ULL,
    0xbb744ac4cdc12d37ULL,
    0x24eba0152fe2f36bULL,
    0xf66718cf3c9e6ff4ULL,
    0x24ba5c4b0a8fd186ULL,
    0x902a814ebc78cbb0ULL,
    0xc895706d0ad79bf2ULL,
    0xfb54e6afd7677377ULL,
    0x3395462cb323dafcULL,
    0x1765f64979059089ULL,
    0x4f2503711b114ce4ULL,
    0x1b2850a9a86db30fULL,
    0xedc765f3eead6640ULL,
    0x0ed33d0703e54b81ULL,
    0x59e6911707d9a1e3ULL,
    0xe15b68a6fa2dddb3ULL,
    0x7d6cb238f25b4ec3ULL,
    0x83bd75004f015be4ULL,
    0x29d098736ebe7ea9ULL,
    0xf7df7c3827638900ULL,
    0x2c8392e222782637ULL,
    0xaf8507f658939e9bULL,
    0x1daeea4ff6332658ULL,
    0x2d732dc96d7adb72ULL,
    0xd523564746edb11bULL,
    0xb44d4164ff8cda55ULL,
    0xe9c76e93e2f60bdfULL,
    0x004296289d0163bfULL,
    0xbcb1c00839246844ULL,
    0xba5300e273fc5c86ULL,
    0x9f91c9fa91d72febULL,
    0xe5bee2fb6e6fdeaaULL,
    0x5ce33bb2d7474df8ULL,
    0x9999761a31aef55aULL,
    0xd09af91e66c718beULL,
    0xeabe4ab34b9cd70dULL,
    0xeb733d53f5b1d5b8ULL,
    0x26ee2cceb9691e80ULL,
    0xb81bec7e2de8f781ULL,
    0x7e7925c145a6f484ULL,
    0x41f2fda8abcf13a5ULL,
    0x8217cdc62f8b0dccULL,
    0x6ed89e51ddfc7343ULL,
    0x9d4ffdd5dcf3b9d3ULL,
    0x5b186539f5d4943bULL,
    0xe76f6ffd5620ce53ULL,
    0xc7b22abde412c37cULL,
    0xa96ec0c950b59508ULL,
    0x137cbf65b24f4027ULL,
    0xfb977aed83e0efefULL,
    0x29cc9eefdb0f1943ULL,
    0x46d418cb4ff6da58ULL,
    0xa654b9d497dd8aacULL,
    0x7b522b71b23ccf2bULL,
    0xd71887ed8381de65ULL,
    0x54df226dfd47d14aULL,
    0x60531b3859a2a8ccULL,
    0xa6a6103b2372fc42ULL,
    0x3c0f2c19ceccd159ULL,
    0xf16d45a53db7f3adULL,
    0xf32c645f12397f84ULL,
    0x95627043b646e8e3ULL,
    0xdbea0fd2793c84b7ULL,
    0x379a3b0b0b4e64e8ULL,
    0x75fb3ad7a270d3b2ULL,
    0xcecfc440122f2e06ULL,
    0x71ed9a08e7ada6a1ULL,
    0x519680ead8014944ULL,
    0xc78e330a77c6d50dULL,
    0x32d4abc39e1bfff3ULL,
    0xd1672a2f4fc4fbe0ULL,
    0x7ca7f9d91a0461d3ULL,
    0xdb9f979f25e5fbc4ULL,
    0x39be4cf8eb863eefULL,
    0x6865fb9352d21828ULL,
    0x6061368e4d3958f8ULL,
    0x7cfc6a7adcbec574ULL,
    0xe580eab1009b64edULL,
    0x90362dcc34f6659fULL,
    0x83687ef60931b711ULL,
    0x27e46692eb95ff7bULL,
    0xe6840eae1418215aULL,
    0x4b627eae25b4f08eULL,
    0x9cd44859e2bd104bULL,
    0x9b173a39761b1dbcULL,
    0x4a329a5510e3c086ULL,
    0xf13ccb53cc3907e8ULL,
    0xff95257fabca3edcULL,
    0xda4b7f1cf1ed9805ULL,
    0x075608adc345bed3ULL,
    0x3a331c82d2924378ULL,
    0x7686df1e66fa9655ULL,
    0xb1c4ccc5565019f4ULL,
    0x39b1fc9947ff6d37ULL,
    0xba82db523c13640dULL,
    0x91645d38c420b220ULL,
    0xcb1a0a6c79fe9feaULL,
    0x667fe176012925f0ULL,
    0xf2b8446b585294f5ULL,
    0x0691117ae0abb50eULL,
    0x5eb6118ca2e62872ULL,
    0xc924fbaf71c315dfULL,
    0xf842177b71c6f22aULL,
    0xc80754b46448ee6aULL,
    0x21d3ff566b098e01ULL,
    0xb149b5d9a0eee677ULL,
    0x9b73429d2da4c233ULL,
    0x9f885ddc498851abULL,
    0xb22eda7ca1b9784cULL,
    0xce09c914771d0ed9ULL,
    0xe7139893ede5e68fULL,
    0x8a1075b14e9fa79eULL,
    0x47f16a5941c7e3c5ULL,
    0x900a683d7bf56ee7ULL,
    0xbff7f284ac239f94ULL,
    0xaa6058650a798c9cULL,
    0x66d60ffba7c059acULL,
    0xa858d85aa9a0083fULL,
    0xc28826779a21e0dfULL,
    0x5f35efa1b5fe99d5ULL,
    0x2fc8244af685d9b4ULL,
    0x09a0108475a964d7ULL,
    0x31024f713b9f20bbULL,
    0xd970efd90cc18400ULL,
    0xd61969558d72253fULL,
    0xa78ee57a609e07a5ULL,
    0xf2f7827f64199028ULL,
    0x221335a2ccad0a47ULL,
    0x52c7eeaf8e3e6e1aULL,
    0xd661e5ab6b0e254bULL,
    0x3e05b4c701bc2852ULL,
    0xd31acb22f296d220ULL,
    0x342d8b1f90505e5cULL,
    0xfc2348b58fd655a2ULL,
    0x5a57c7ce5f310a34ULL,
    0xa843c5acaaa2dd7dULL,
    0xf7b1f0c5dc5c5a10ULL,
    0xf4a1e7100c6c8bbfULL,
    0x10faf8e33c1b0090ULL,
    0x2881d5f64e455310ULL,
    0x261dcd7c8bfedd46ULL,
    0xfd423849dcdb645aULL,
    0x13402769dc9da361ULL,
    0x35832a72d7867b05ULL,
    0xc3d4c4727b4c30a1ULL,
    0x5b5179801ab877ffULL,
    0xfd7d1c8f8702501aULL,
    0x94605dfe134fe4beULL,
    0x5ed44f84153de6c3ULL,
    0x75558925a53502baULL,
    0xd0abd43d349ae531ULL,
    0x7e5c7ca2048f9fefULL,
    0xe7cddce1d99ab42bULL,
    0x92ad1cafdbd3787fULL,
    0x05827d13bde355d6ULL,
    0x01c0593caf195d0fULL,
    0xe641a40c5afcee19ULL,
    0x4f9b7fd1a856b701ULL,
    0xdce3eea6efb1853bULL,
    0xe28244e9c4e63acaULL,
    0x3ef4b139cb56597dULL,
    0x7fac5a181c687422ULL,
    0x23ea86e377a1a003ULL,
    0x14e089a655b2ce4eULL,
    0xe215e3bd72cc0a97ULL,
    0xf45af26303d5c581ULL,
    0x7777f058896f9a73ULL,
    0x99aec0374d142a5fULL,
    0x552c8546d98e8584ULL,
    0x89728b9d11317b9aULL,
    0x7464d56911346f28ULL,
    0xb19fc6c46914f6f0ULL,
    0x15f4e2350578d40dULL,
    0x1ddfb4b328b248efULL,
    0x8418c3028fd170f6ULL,
    0x25046319c34ed2a3ULL,
    0x3e018dac9d47fa1eULL,
    0x4f1f19bb2fbc34d5ULL,
    0x0fba70b5df282972ULL,
    0x02df13f0e30ec8b6ULL,
    0xdd92d00049da4df1ULL,
    0x49026d77fb069f9dULL,
    0xdbaae0696329da50ULL,
    0x361ba249c6ef3834ULL,
    0x3f8d4469ca3868e3ULL,
    0xc3ea9e0ea2008a95ULL,
    0xee989a98e0c27f84ULL,
    0xcbda49dbf8e7f17dULL,
    0x42ed85724d734af3ULL,
    0x0216234c8107208cULL,
    0x97dc33f37554264bULL,
    0x63a275b249f2a36dULL,
    0x71db0720516bf741ULL,
    0x08e4ecb1fef9519dULL,
    0x6029a9fc387d3ebeULL,
    0x0a55be6aaac4f34dULL,
    0xec75d1821df80754ULL,
    0x077e00d60ad2f6ceULL,
    0x742baeece9f34ad5ULL,
    0x7a8e9282125cd050ULL,
    0x688330ce6f0a95c5ULL,
    0xf86a39a8ce48c8c4ULL,
    0xf04459ab9abb2122ULL,
    0xb848403544a7d883ULL,
    0x40870758da58c40bULL,
    0x5a4a69d56457824aULL,
    0x6350619c1b5fbd00ULL,
    0xbe46a30362255ca9ULL,
    0x3563642107194153ULL,
    0xd4549f6d5548f391ULL,
    0x49a74dd8304b99dcULL,
    0x8f0ce2b2e9235071ULL,
    0x0e2ccf5ded9a8b7bULL,
    0xcd987e088c2e0809ULL,
    0x85ef9bc7ed0152d6ULL,
    0xbe35677eff8341bfULL,
    0x28b88cd720f7dd5aULL,
    0x17c5479731a406acULL,
    0x371ed4c130db5662ULL,
    0x3bd87aa02d5ac70aULL,
    0xfc01994f7de10985ULL,
    0x442c4ac382a5aeb6ULL,
    0xa34fa4b48d0c5f2fULL,
    0x510400b5b016d4ccULL,
    0x3b689912720d376dULL,
    0x9ec6ea60cf14e2c4ULL,
    0xd044145163329affULL,
    0x0117185d6b9486acULL,
    0x5573ea7a7aa8498aULL,
    0x952bd0abd1044727ULL,
    0x0f17a52dd8c101cbULL,
    0x78b50fccf5c59e79ULL,
    0xabacefe6dfe40ea9ULL,
    0xca57246ba322697aULL,
    0x5fd7df6eb1988ac8ULL,
    0x3789eefa5041b684ULL,
    0x5ede25e031ab43dcULL,
    0x95819a9854f69430ULL,
    0x33e3ed56011a727eULL,
    0xef113c7fc6ae83a7ULL,
    0x33fddf7b3a32eb42ULL,
    0xa30cde8d9d71ddebULL,
    0xfe60cc7fe3f32cf2ULL,
    0x817692be4c6d02c0ULL,
    0xfe5609a2f815b73eULL,
    0x6d22f1de40a7ee20ULL,
    0x77ce3eca9ab12b57ULL,
    0x89cd08b7a9b89852ULL,
    0x4c2a4a065c147fecULL,
    0xce1b2ec486f59d8fULL,
    0x0eceda66be6bc4aaULL,
    0x7c7732a3c728fc77ULL,
    0x1f6b965b48ce8947ULL,
    0x11ecc7bc40cf72dfULL,
    0x0cdbb71074783cdcULL,
    0xa0312aada92ce3caULL,
    0x6b71e2b1b20073c1ULL,
    0x4660e9846cdb6d96ULL,
    0xe5f2b31a4a1a3362ULL,
    0x20a0b2f0cf3f4f4aULL,
    0xef6aa63353c396edULL,
    0xa5a596009f79a04dULL,
    0x58f772dcd6d17555ULL,
    0x7957ccbb31af0b61ULL,
    0xb78429d6762f68b7ULL,
    0x5d56c1985fe7a77aULL,
    0xa7c39cbaeedbcf38ULL,
    0x65995fc6feda19dbULL,
    0x86bd2842e58c1abfULL,
    0x6b8f580e7f95a512ULL,
    0x04702eee85556f24ULL,
    0x7d03323b15770702ULL,
    0x7142db6082e23f0eULL,
    0xa7187369f53d799bULL,
    0x33ac09c9ef8b5011ULL,
    0xa7215e563a441b86ULL,
    0x719d08af2d6bbe27ULL,
    0x411169b3cc4d2938ULL,
    0xac27a7a1de0b5506ULL,
    0x6a22863807d7a858ULL,
    0x39ee2d2990d69bd2ULL,
    0xa4532bde73a403f0ULL,
    0x93140026ce0f907fULL,
    0x3ee28286b7fb6bd9ULL,
    0x9a764f034f6612c3ULL,
    0x64a2aebf4bcc603eULL,
    0xe3a52379d46f760dULL,
    0x177bffaf24689dabULL,
    0x50cae3da45597fe0ULL,
    0x20965d5b98702278ULL,
    0x2216f521a928cc88ULL,
    0x66abbd80b4225632ULL,
    0x4deb85d7906c2b68ULL,
    0x2afe23ad7e7d64eeULL,
    0x086c679450374d70ULL,
    0xda4dcd508b82c799ULL,
    0x10d7894a856495d7ULL,
    0x0da56c0076c24fbaULL,
    0x0e326b797a477812ULL,
    0xef6bd63cc63df6c4ULL,
    0x79bc5723426d1f76ULL,
    0xb75d3b456282beb3ULL,
    0xae6e33cfa8828989ULL,
    0x6ab76312f343be84ULL,
    0xdc8f5b9ac09ecab9ULL,
    0x431d138d0462179eULL,
    0x52ef096bb35e1c0dULL,
    0xf66a0311c0456476ULL,
    0x096d359977f58b8eULL,
    0xfe552ed33c46d0fbULL,
    0x30de400c07364d98ULL,
    0x6db002e62192aad4ULL,
    0xb7b1f521b2cffd09ULL,
    0x1ff582472dd69760ULL,
    0x269542702e92e3a8ULL,
    0x74cc87913e8fc54dULL,
    0xfb2690d45bcc2646ULL,
    0xc0d6a127b1e95606ULL,
    0xa5fb89708bb60bddULL,
    0x32c3cbfd9af652f4ULL,
    0xe693fa7b4c6820d5ULL,
    0x14183f649e3488f4ULL,
    0x2a493ed4e84d01e9ULL,
    0x5033458942015a8bULL,
    0x08e7eafa81e22990ULL,
    0xe61a4c18db1aa3d6ULL,
    0xe884ae998f479eb4ULL
&#125;;
unsigned long long zobvalh23&#40;unsigned i&#41;
&#123;
    return ham23bit&#91;i % 999&#93;;
&#125;

#ifdef UNIT_TEST
#include <stdio.h>
int             main&#40;void&#41;
&#123;
    unsigned        index;
    for &#40;index = 0; index < 2000; index++)
        printf&#40;"zobvalh23&#40;%u&#41;=%llu\n", index, zobvalh23&#40;index&#41;);
    return 0;
&#125;
#endif

Dann Corbit · Post by **Dann Corbit** » Fri Jan 23, 2009 3:41 am

Considering this post:
http://computer-go.org/pipermail/comput ... 04129.html

I think that the next logical step would be to filter the data to achive the set from this list with largest linear independence.

bob · Post by **bob** » Fri Jan 23, 2009 6:50 am

hgm wrote:
bob wrote:Got an email from someone that is more familiar with this stuff. He first told me that it is possible to produce 788 numbers with a min hamming distance of 28. But that this will be a linear code where XORing any two of the numbers will produce another number in the set. Which is not so desirable. So I am taking that data point and trying to decide what it means with respect to Zobrist numbers...
Well, that illustrates my point in an even more dramatic way than I ever could have imagined. So maximum hamming distance actually produces a totally useless set of keys.

I guess we'd better get back to basics, and look for keys that makes the smallest difference that must exist between two positions before they can collide as large as possible. I.e. analyze the set in terms of dependent sub-sets, and make the smallest subset of keys that could combine to zero as large as possible.

For a 64-bit key this will be hard: in a randomly chosen set will in general not be any dependent sets of 7 or smaller. We have about 3*2^8 keys, so the number of combinations of 8 keys is about (3*2^8)^8/8! = 0.16*2^64. As each 64-bit result only has a 1/2^64 probability of being zero, this means there is a fair chance none of the combinations of 8 keys hits zero.

The number of 9-key subsets is ~768/9 times as large, or about 15*2^64. Thes means that the probability of 0 nort being hit by any of them is only exp(-15) = 1/2^22. So only after several million tries you would find one. But fortunately the 1/2^22 probability of 0 being hit is the same for any other 64-bit number, i.e. 1 in 4 million numbers will not occur amongst the 9-key "products". It is just a matter of finding one that doesn't. Then you can transform the set by XORing every key in the set with that number. As 9 is odd, this means that every product of 9 keyys will also be XORed with that number. This maps the number that could not be made by combining any 9 keys onto zero, so that in the transformed set no sub-set of 9 keys is dependent.

One problem is that making all combinations of 9 keys out of 788 is totally undoable. I could not go farther than 4, and even that took a full night.

This is certainly something I am not an expert in. I understand search and such, completely. But the random numbers we use are a different animal in light of recent discussions. I did notice that the first 768 numbers I generate have a minimum hamming distance of 14. And I now know that the theoretical max is 28. But this info seems (now) to be completely irrelevant, which was yet another case of something I had not expected...

brianr · Post by **brianr** » Fri Jan 23, 2009 2:48 pm

Can someone explain why the Hamming distance is much of an issue at all,
given Bob's prior research and article about the surprising unimportance of hash collisions?
Thanks,
Brian

http://www.cis.uab.edu/hyatt/collisions.html

Aleks Peshkov · Post by **Aleks Peshkov** » Fri Jan 23, 2009 2:58 pm

Considering Hamming distance it is important to notice, that 0 value (empty square) is very frequent in real board (at least 50% of all values and much more in an endgame). I suspect that a set of 64 different keys for all empty squares can improve collision situation significantly.

It is also intuitively obvious that some distance of 32+8 = 40, is not better then 32-8 = 24 distance, so the average should be maximized toward 32, not 64 for 64-bit sets.

Aleks Peshkov · Post by **Aleks Peshkov** » Fri Jan 23, 2009 3:07 pm

I found a one of many sets of deBruijin numbers:

Code: Select all

&#123; 0x218aecf49a8e5bfull, 0x218e6b7b2545d3full, 0x2193f1d16a5737bull, 0x219b1fa2b5272efull, 0x21bf6549d16b8f3ull, 0x21e758da4ca8bf7ull, 0x22bdb9a864e963full, 0x25f915b0e34cf75ull, 0x27e54877a3362d7ull, 0x352b64e23f30bddull, 0x36568fd484ee2f3ull, 0x37ed424574ce58full, &#125;,

they should have a good distance between any rotated pair, and a verified decent distance between any 3 number. I forgot details, but I think those distances are 24/16, with minimum inside single rotation cycle at least 26.

hgm · Post by **hgm** » Fri Jan 23, 2009 3:18 pm

Aleks Peshkov wrote:Considering Hamming distance it is important to notice, that 0 value (empty square) is very frequent in real board (at least 50% of all values and much more in an endgame). I suspect that a set of 64 different keys for all empty squares can improve collision situation significantly.

I think it is easy to prove that this does not offer anything extra at all. Every square is always present, either with a piece on it or empty. Assigning a unique key K for the empty state of that square (rather than the usual 0) is equivalent to XORing all other keys for that square with K. (And later XORing the complete hash key with the XOR of an empty board, but such an overall factor will never affect collision rate.)

bob · Post by **bob** » Fri Jan 23, 2009 5:37 pm

brianr wrote:Can someone explain why the Hamming distance is much of an issue at all,
given Bob's prior research and article about the surprising unimportance of hash collisions?
Thanks,
Brian

http://www.cis.uab.edu/hyatt/collisions.html

For me it was related to book moves. Since some use _very_ deep books, that is a harsher test of the Zobrist random numbers since you use way more of them to produce keys for book moves.

Zobrist key random numbers

Re: Zobrist key random numbers

Re: Zobrist key random numbers

Re: Zobrist key random numbers

Re: Zobrist key random numbers

Re: Zobrist key random numbers

Re: Zobrist key random numbers

Re: Zobrist key random numbers

Re: Zobrist key random numbers

Re: Zobrist key random numbers

Re: Zobrist key random numbers