2

I'm trying to generate a zobrist key for transposition tables in my chess engine. Here's how I'm generating the 64 bit numbers, as show here: How to generate 64 bit random numbers?

typedef unsigned long long  U64;

std::random_device rd;

std::mt19937_64 mt(rd());

std::uniform_int_distribution<U64> dist(std::llround(std::pow(2,61)), 
std::llround(std::pow(2,62)));

rand function:

U64 ZobristH::random64()
{
    U64 ranUI = dist(mt);
    return ranUI;
}

In order to try and make sure i'm generating random enough numbers I'm using a test distribution function I found online that looks like this (will later input data into excel and look at distribution):

int sampleSize = 2000;

int distArray[sampleSize];
int t = 0;
while (t < 10)
{
   for (int i = 0; i < 10000; i++)
   {
       distArray[(int)(random64() % (sampleSize / 2))]++;
   }
   t++;
}
for (int i = 0; i < sampleSize; i++)
{
    std::cout << distArray[i] << ", ";
}

the results I'm getting look a little something like this:

 416763345, 417123246, 7913280, 7914356, 417726722, 417726718, 19, 83886102, 
 77332499, 14

Are these the decimal representation of binary numbers below 1000? Or am I doing something completely wrong?

Cœur
  • 37,241
  • 25
  • 195
  • 267
Max C
  • 369
  • 5
  • 16
  • 2
    You never gave initial values to `distArray` elements. Try `const int sampleSize = 2000; int distArray[sampleSize] = {};` which will start them off at 0. – M.M Jul 07 '17 at 03:06
  • Thanks for replying. That did something interesting, I now have a bunch of numbers in the 10-25 range ; 25, 22, 16, 16, 18, 14, 18, 19, 19, 14, 20, 24, 23, 18, 22, 21, 17. Then about 700 zeros – Max C Jul 07 '17 at 03:10
  • That suggests a problem with your random number generation, or perhaps with the output. You could try outputting each `random64()` result as it was generated , i.e. debug your program – M.M Jul 07 '17 at 03:12
  • Any suggestions on how to assess the random numbers once output? They're long enough it makes it hard to even make a guess as to whether they're random or not – Max C Jul 07 '17 at 03:16
  • 2
    Just write code or use debugger to find out where things start to diverge from your expectations – M.M Jul 07 '17 at 03:22
  • Throw them in excel, look at them in a graph, there should be an even distribution among all the occurrences of the numbers. – shockawave123 Jul 07 '17 at 03:27
  • That will work for the raw 64 bit numbers that are around 19 digits? – Max C Jul 07 '17 at 03:30
  • @M.M In MSVS 2017 CE if you don't declare your `int` or `unsigned` as a `const` variable with a value for an array it will actually fail to compile. Gave you thumbs up for your comment! – Francis Cugler Jul 07 '17 at 06:05

1 Answers1

3

Okay I did this to check out the distribution of random numbers; you can run this short program to generate a text file to look to see what values you are getting. Instead of using a function call I just used a lambda within the for loop and instead of setting the values into the array I wrote the values out to the text file before and after the post increment.


#include <iostream>
#include <fstream>
#include <iomanip>
#include <random>
#include <functional> // may not need - included in almost all of my apps
#include <algorithm>  // same as above

typedef unsigned long long U64;

int main( int argc, char** argv ) {
    std::random_device rd;
    std::mt19937_64 mt( rd() );

    std::uniform_int_distribution<U64> dist( std::llround( std::pow( 2, 61 ) ),
                                             std::llround( std::pow( 2, 62 ) ) );

    auto lambda = [&] { return dist(mt); };

    const int sampleSize = 2000;
    // int distArray[sampleSize];
    int t = 0;

    std::ofstream file( "samples.txt" );

    while ( t < 10 ) {
        file << "Sample: " << (t+1) << "\n";

        for ( int i = 0; i < 10000; i++ ) {
            auto val = static_cast<int>( (lambda() % (sampleSize / 2)) );
            file << std::setw(5) << i << ": " << std::setw(6) << val << "\t"
                 << std::setw(6) << val++ << "\n";
            // distArray[...]
        }
        file << "\n\n";
        t++;
    }
    file.close();

    /* for ( int i = 0; i < sampleSize; i++ ) {
        std::cout << distArray[i] << "\n";
    }*/

    // Quick & Dirty Way TO Pause The Console
    std::cout << "\nPress any key and enter to quit.\n";
    char c;
    std::cin >> c;

    return 0;
}

Then check out the text file that this program generates and if you scroll through the file you will see the distributions. The first column is the value before the post increment and the second column is after. The largest possible value before the post increment that I have seen is 1,000 and after the post increment is 999. I've built and ran this for both 32 & 64 bit platform versions and have seen similar results for the distributions and that they indeed have a uniform distribution.


Sample.txt - Small Version About 1,000 Entries Out The 1st Sample Set

Sample: 1
    0:    342      341
    1:    517      516
    2:    402      401
    3:    741      740
    4:    238      237
    5:    557      556
    6:     35       34
    7:    572      571
    8:    205      204
    9:    353      352
   10:    301      300
   11:     65       64
   12:    223      222
   13:    647      646
   14:    185      184
   15:    535      534
   16:     97       96
   17:    843      842
   18:    716      715
   19:    294      293
   20:    485      484
   21:    648      647
   22:    406      405
   23:    250      249
   24:    245      244
   25:    915      914
   26:    888      887
   27:    986      985
   28:    345      344
   29:    493      492
   30:    654      653
   31:    860      859
   32:    921      920
   33:    526      525
   34:    793      792
   35:    503      502
   36:    939      938
   37:    802      801
   38:    142      141
   39:    806      805
   40:    540      539
   41:    778      777
   42:    787      786
   43:    884      883
   44:    109      108
   45:    842      841
   46:    794      793
   47:    279      278
   48:    821      820
   49:    112      111
   50:    438      437
   51:    402      401
   52:     69       68
   53:    396      395
   54:    196      195
   55:    655      654
   56:    859      858
   57:    674      673
   58:    417      416
   59:    331      330
   60:    632      631
   61:    210      209
   62:    641      640
   63:    737      736
   64:    838      837
   65:    592      591
   66:    562      561
   67:    883      882
   68:    750      749
   69:    726      725
   70:    253      252
   71:    660      659
   72:     57       56
   73:    401      400
   74:    919      918
   75:    851      850
   76:    345      344
   77:     25       24
   78:    300      299
   79:    781      780
   80:    695      694
   81:    220      219
   82:    378      377
   83:    471      470
   84:    281      280
   85:    945      944
   86:    536      535
   87:    407      406
   88:    431      430
   89:    745      744
   90:     32       31
   91:    389      388
   92:    358      357
   93:    582      581
   94:    820      819
   95:    622      621
   96:    459      458
   97:    233      232
   98:    594      593
   99:    509      508
  100:    260      259
  101:    152      151
  102:    148      147
  103:    137      136
  104:    945      944
  105:    244      243
  106:    968      967
  107:     54       53
  108:    420      419
  109:     58       57
  110:    678      677
  111:    715      714
  112:    780      779
  113:    834      833
  114:    241      240
  115:    669      668
  116:    722      721
  117:    608      607
  118:    805      804
  119:    155      154
  120:    220      219
  121:    520      519
  122:    740      739
  123:    184      183
  124:    198      197
  125:    247      246
  126:    115      114
  127:    520      519
  128:    457      456
  129:    864      863
  130:    659      658
  131:    511      510
  132:    718      717
  133:    119      118
  134:    588      587
  135:    113      112
  136:    518      517
  137:    164      163
  138:    375      374
  139:    866      865
  140:    382      381
  141:    526      525
  142:    621      620
  143:    680      679
  144:    147      146
  145:    712      711
  146:    408      407
  147:    486      485
  148:      7        6
  149:    203      202
  150:    741      740
  151:    290      289
  152:    810      809
  153:    960      959
  154:    449      448
  155:    683      682
  156:    997      996
  157:    454      453
  158:    131      130
  159:    427      426
  160:    157      156
  161:      3        2
  162:    427      426
  163:    554      553
  164:    806      805
  165:    228      227
  166:    431      430
  167:    174      173
  168:    845      844
  169:    121      120
  170:    397      396
  171:    770      769
  172:     17       16
  173:    761      760
  174:    736      735
  175:    629      628
  176:    772      771
  177:    417      416
  178:    739      738
  179:    226      225
  180:    301      300
  181:    217      216
  182:    746      745
  183:    344      343
  184:    607      606
  185:    927      926
  186:    428      427
  187:    385      384
  188:    287      286
  189:    537      536
  190:    705      704
  191:    649      648
  192:    127      126
  193:    252      251
  194:    160      159
  195:    390      389
  196:    282      281
  197:     66       65
  198:    659      658
  199:    844      843
  200:    358      357
  201:    360      359
  202:    872      871
  203:    495      494
  204:    695      694
  205:    988      987
  206:    969      968
  207:    641      640
  208:    799      798
  209:     30       29
  210:    109      108
  211:    675      674
  212:    345      344
  213:    309      308
  214:    807      806
  215:    283      282
  216:    457      456
  217:    193      192
  218:    972      971
  219:    330      329
  220:    914      913
  221:    508      507
  222:    624      623
  223:    254      253
  224:    342      341
  225:     69       68
  226:    918      917
  227:    551      550
  228:    148      147
  229:    645      644
  230:    905      904
  231:    503      502
  232:    980      979
  233:    881      880
  234:    137      136
  235:    202      201
  236:    808      807
  237:    988      987
  238:    497      496
  239:    506      505
  240:    576      575
  241:    671      670
  242:    874      873
  243:    217      216
  244:    808      807
  245:    741      740
  246:     14       13
  247:    206      205
  248:    894      893
  249:    180      179
  250:      4        3
  251:     27       26
  252:     62       61
  253:    203      202
  254:    392      391
  255:    868      867
  256:    673      672
  257:    881      880
  258:    664      663
  259:    831      830
  260:    293      292
  261:    916      915
  262:    860      859
  263:    487      486
  264:    642      641
  265:    161      160
  266:    881      880
  267:    233      232
  268:    423      422
  269:     12       11
  270:    398      397
  271:    993      992
  272:    323      322
  273:    878      877
  274:    114      113
  275:     42       41
  276:     58       57
  277:    398      397
  278:    878      877
  279:     64       63
  280:    873      872
  281:    841      840
  282:    506      505
  283:    412      411
  284:    545      544
  285:    887      886
  286:     17       16
  287:    504      503
  288:    350      349
  289:    772      771
  290:     16       15
  291:    597      596
  292:    553      552
  293:     25       24
  294:    324      323
  295:    242      241
  296:    580      579
  297:    479      478
  298:    702      701
  299:    640      639
  300:    173      172
  301:    918      917
  302:    678      677
  303:    714      713
  304:    258      257
  305:     97       96
  306:    304      303
  307:     80       79
  308:    394      393
  309:    940      939
  310:    985      984
  311:    651      650
  312:     42       41
  313:    179      178
  314:    672      671
  315:    915      914
  316:    160      159
  317:    332      331
  318:    887      886
  319:    370      369
  320:    850      849
  321:    730      729
  322:    395      394
  323:    889      888
  324:    114      113
  325:    505      504
  326:    381      380
  327:    578      577
  328:    762      761
  329:    896      895
  330:    793      792
  331:    295      294
  332:    488      487
  333:    599      598
  334:    182      181
  335:     25       24
  336:    623      622
  337:    396      395
  338:    898      897
  339:    981      980
  340:    645      644
  341:    806      805
  342:    205      204
  343:    404      403
  344:    234      233
  345:     36       35
  346:    659      658
  347:    285      284
  348:     62       61
  349:    608      607
  350:    632      631
  351:    825      824
  352:    585      584
  353:    685      684
  354:     14       13
  355:    828      827
  356:    720      719
  357:    871      870
  358:     88       87
  359:    716      715
  360:    879      878
  361:    650      649
  362:    464      463
  363:    898      897
  364:    930      929
  365:    194      193
  366:    997      996
  367:    105      104
  368:    776      775
  369:    398      397
  370:    962      961
  371:    434      433
  372:    954      953
  373:    548      547
  374:    989      988
  375:    943      942
  376:    229      228
  377:    866      865
  378:    554      553
  379:    567      566
  380:    379      378
  381:    564      563
  382:    738      737
  383:    468      467
  384:    660      659
  385:    693      692
  386:    784      783
  387:    739      738
  388:    662      661
  389:    474      473
  390:    545      544
  391:    958      957
  392:    703      702
  393:    316      315
  394:    571      570
  395:     95       94
  396:    497      496
  397:    672      671
  398:    676      675
  399:    821      820
  400:    368      367
  401:      7        6
  402:    817      816
  403:    221      220
  404:    839      838
  405:    578      577
  406:    635      634
  407:    453      452
  408:     70       69
  409:    764      763
  410:     78       77
  411:    968      967
  412:    295      294
  413:    483      482
  414:    392      391
  415:     23       22
  416:    389      388
  417:    678      677
  418:    150      149
  419:    863      862
  420:    677      676
  421:    676      675
  422:    455      454
  423:    405      404
  424:    126      125
  425:    753      752
  426:    821      820
  427:    328      327
  428:    773      772
  429:    596      595
  430:    645      644
  431:    829      828
  432:    377      376
  433:    444      443
  434:    813      812
  435:    395      394
  436:    794      793
  437:    641      640
  438:     98       97
  439:    827      826
  440:    824      823
  441:    681      680
  442:    736      735
  443:    288      287
  444:    560      559
  445:    781      780
  446:    556      555
  447:    327      326
  448:    820      819
  449:    859      858
  450:    686      685
  451:    919      918
  452:    267      266
  453:    128      127
  454:    583      582
  455:    446      445
  456:    783      782
  457:    712      711
  458:    378      377
  459:    367      366
  460:     52       51
  461:    316      315
  462:    780      779
  463:    398      397
  464:    435      434
  465:    788      787
  466:    380      379
  467:    235      234
  468:    748      747
  469:    429      428
  470:     91       90
  471:    675      674
  472:    853      852
  473:    674      673
  474:    277      276
  475:    179      178
  476:    264      263
  477:    511      510
  478:    514      513
  479:    979      978
  480:    845      844
  481:    728      727
  482:    904      903
  483:    874      873
  484:    750      749
  485:    659      658
  486:    376      375
  487:    713      712
  488:    393      392
  489:    538      537
  490:    896      895
  491:    879      878
  492:    347      346
  493:    819      818
  494:    210      209
  495:    707      706
  496:    869      868
  497:    319      318
  498:    832      831
  499:    498      497
  500:     71       70
  501:    290      289
  502:    861      860
  503:    295      294
  504:    888      887
  505:    515      514
  506:    222      221
  507:    661      660
  508:    813      812
  509:    969      968
  510:    547      546
  511:    900      899
  512:     58       57
  513:    805      804
  514:    428      427
  515:    453      452
  516:     23       22
  517:    969      968
  518:    718      717
  519:    775      774
  520:    395      394
  521:    521      520
  522:    522      521
  523:    465      464
  524:    317      316
  525:    216      215
  526:    254      253
  527:    696      695
  528:    677      676
  529:     21       20
  530:    318      317
  531:    301      300
  532:    142      141
  533:    877      876
  534:    486      485
  535:    981      980
  536:    516      515
  537:    254      253
  538:    328      327
  539:    385      384
  540:      2        1
  541:    405      404
  542:    387      386
  543:    794      793
  544:     48       47
  545:    641      640
  546:    814      813
  547:    981      980
  548:    354      353
  549:    281      280
  550:    561      560
  551:    683      682
  552:    247      246
  553:    739      738
  554:    370      369
  555:    799      798
  556:    680      679
  557:    915      914
  558:    638      637
  559:    254      253
  560:    705      704
  561:    320      319
  562:    640      639
  563:    487      486
  564:     47       46
  565:    852      851
  566:    749      748
  567:    419      418
  568:    300      299
  569:    507      506
  570:    141      140
  571:    972      971
  572:    895      894
  573:    988      987
  574:    279      278
  575:    268      267
  576:    392      391
  577:    530      529
  578:    679      678
  579:    855      854
  580:    246      245
  581:    645      644
  582:    624      623
  583:    417      416
  584:    203      202
  585:     30       29
  586:      9        8
  587:    585      584
  588:    573      572
  589:    471      470
  590:    504      503
  591:    290      289
  592:    588      587
  593:    230      229
  594:    351      350
  595:    651      650
  596:    615      614
  597:    502      501
  598:    352      351
  599:    472      471

  // 600 - 699 omitted to make space to fit answer

  700:    247      246
  701:    894      893
  702:    809      808
  703:    382      381
  704:     81       80
  705:    574      573
  706:    507      506
  707:    508      507
  708:    569      568
  709:    947      946
  710:    384      383
  711:     14       13
  712:    627      626
  713:    951      950
  714:    825      824
  715:    657      656
  716:    206      205
  717:    598      597
  718:    300      299
  719:    266      265
  720:    909      908
  721:    206      205
  722:    126      125
  723:    841      840
  724:    586      585
  725:    348      347
  726:    100       99
  727:    361      360
  728:    695      694
  729:    556      555
  730:     66       65
  731:      5        4
  732:    686      685
  733:    488      487
  734:    149      148
  735:    622      621
  736:    476      475
  737:    488      487
  738:    371      370
  739:    331      330
  740:    965      964
  741:    141      140
  742:    396      395
  743:    917      916
  744:     31       30
  745:    924      923
  746:    283      282
  747:    369      368
  748:    519      518
  749:    830      829
  750:    688      687
  751:    374      373
  752:     41       40
  753:    418      417
  754:    766      765
  755:    854      853
  756:    453      452
  757:    521      520
  758:    640      639
  759:    185      184
  760:     41       40
  761:    125      124
  762:    723      722
  763:    341      340
  764:    142      141
  765:    754      753
  766:    459      458
  767:    899      898
  768:    166      165
  769:    374      373
  770:    572      571
  771:    304      303
  772:    352      351
  773:    235      234
  774:    879      878
  775:    736      735
  776:    576      575
  777:     56       55
  778:    102      101
  779:    170      169
  780:    208      207
  781:    135      134
  782:    919      918
  783:    599      598
  784:     37       36
  785:    997      996
  786:    922      921
  787:    502      501
  788:     29       28
  789:    173      172
  790:     54       53
  791:    601      600
  792:    535      534
  793:     64       63
  794:    723      722
  795:    491      490
  796:    685      684
  797:     58       57
  798:    272      271
  799:    261      260
  800:     81       80
  801:    149      148
  802:    129      128
  803:    712      711
  804:    377      376
  805:    151      150
  806:    514      513
  807:     14       13
  808:    838      837
  809:    347      346
  810:    517      516
  811:    442      441
  812:    264      263
  813:    883      882
  814:    447      446
  815:    140      139
  816:    195      194
  817:    841      840
  818:    218      217
  819:    858      857
  820:     28       27
  821:    222      221
  822:    223      222
  823:    906      905
  824:    873      872
  825:    492      491
  826:    826      825
  827:    738      737
  828:    307      306
  829:    185      184
  830:    525      524
  831:    449      448
  832:    646      645
  833:    686      685
  834:    942      941
  835:    433      432
  836:    881      880
  837:    824      823
  838:    641      640
  839:    290      289
  840:    897      896
  841:      4        3
  842:    124      123
  843:    679      678
  844:    524      523
  845:    424      423
  846:    282      281
  847:    625      624
  848:    414      413
  849:    647      646
  850:    129      128
  851:    395      394
  852:    720      719
  853:    318      317
  854:    262      261
  855:    402      401
  856:    413      412
  857:    139      138
  858:    549      548
  859:    472      471
  860:    162      161
  861:    605      604
  862:     67       66
  863:    980      979
  864:    465      464
  865:    912      911
  866:    219      218
  867:    648      647
  868:    619      618
  869:    331      330
  870:    625      624
  871:    360      359
  872:    425      424
  873:    935      934
  874:     89       88
  875:    641      640
  876:    535      534
  877:    404      403
  878:    966      965
  879:     27       26
  880:    281      280
  881:    637      636
  882:     57       56
  883:    152      151
  884:    156      155
  885:    813      812
  886:    340      339
  887:    181      180
  888:    921      920
  889:    306      305
  890:    101      100
  891:    178      177
  892:    417      416
  893:    845      844
  894:    904      903
  895:    295      294
  896:    346      345
  897:    654      653
  898:    357      356
  899:    929      928
  900:    195      194
  901:    499      498
  902:    377      376
  903:    727      726
  904:    570      569
  905:    853      852
  906:     71       70
  907:    580      579
  908:    642      641
  909:    889      888
  910:    559      558
  911:    134      133
  912:    324      323
  913:    120      119
  914:    991      990
  915:      6        5
  916:    708      707
  917:    347      346
  918:    929      928
  919:    454      453
  920:    636      635
  921:    218      217
  922:    739      738
  923:    715      714
  924:     87       86
  925:    782      781
  926:    670      669
  927:    845      844
  928:     79       78
  929:    730      729
  930:     58       57
  931:    216      215
  932:    711      710
  933:    898      897
  934:    871      870
  935:    388      387
  936:    389      388
  937:    944      943
  938:    927      926
  939:     88       87
  940:    617      616
  941:    940      939
  942:    948      947
  943:    927      926
  944:    646      645
  945:    125      124
  946:    615      614
  947:    846      845
  948:    705      704
  949:    998      997
  950:    304      303
  951:    346      345
  952:    675      674
  953:    783      782
  954:    129      128
  955:     69       68
  956:     17       16
  957:    646      645
  958:    559      558
  959:     62       61
  960:    807      806
  961:    571      570
  962:     54       53
  963:    297      296
  964:    771      770
  965:    972      971
  966:    829      828
  967:    786      785
  968:    650      649
  969:    101      100
  970:    705      704
  971:    690      689
  972:    365      364
  973:    304      303
  974:     82       81
  975:    776      775
  976:    495      494
  977:    586      585
  978:    556      555
  979:     77       76
  980:    640      639
  981:    161      160
  982:    910      909
  983:     46       45
  984:     43       42
  985:    162      161
  986:    514      513
  987:    654      653
  988:    668      667
  989:    126      125
  990:    254      253
  991:    133      132
  992:    398      397
  993:    993      992
  994:    357      356
  995:    298      297
  996:    519      518
  997:    904      903
  998:    382      381
  999:     28       27
 1000:     19       18
 1001:    939      938
 1002:    868      867
 1003:    888      887
 1004:    576      575
 1005:    183      182
 1006:    174      173
 1007:    679      678
 1008:    831      830
 1009:    464      463
 1010:    876      875
 1011:    738      737
 1012:    447      446
 1013:    385      384
 1014:    271      270
 1015:     38       37
 1016:     28       27
 1017:    451      450
 1018:    162      161
 1019:    847      846
 1020:    430      429
 1021:    849      848
 1022:    207      206
 1023:    196      195
 1024:     42       41
 1025:    709      708
 1026:    557      556
 1027:    173      172
 1028:    788      787
 1029:    160      159
 1030:    535      534
 1031:    555      554
 1032:    252      251
 1033:    111      110
 1034:    476      475
 1035:    780      779
 1036:     44       43
 1037:    190      189
 1038:    443      442
 1039:    655      654
 1040:      7        6
 1041:    845      844
 1042:    856      855
 1043:    274      273
 1044:    933      932
 1045:    336      335
 1046:    185      184
 1047:    580      579
 1048:    807      806
 1049:    286      285
 1050:    409      408
 1051:    347      346
 1052:    461      460
 1053:    624      623
 1054:    378      377
 1055:    903      902
 1056:    483      482
 1057:    838      837
 1058:    809      808
 1059:    919      918
 1060:    544      543
 1061:    458      457
 1062:    121      120
 1063:    192      191
 1064:    126      125
 1065:    843      842
 1066:    927      926
 1067:    390      389
 1068:    567      566
 1069:   1000      999 

Entry 1069 is the first occurrence in this sample set to reach 1,000. I've ran this about a dozen times both in 32bit and 64bit modes and I did not see any value go above 1,000.


I'm not sure but I think that this line in your code is what is giving you your problem(s):

 distArray[(int)(random64() % (sampleSize / 2))]++;
Francis Cugler
  • 7,788
  • 2
  • 28
  • 59
  • Yes you're right! It turns out I just need to % with sample size. The way I was generating random numbers was slightly different than the example I was looking at with that function. Also, I some how completely glossed over the ++ at the end and missed what the testDist function was actually supposed to do. Thanks a bunch for looking so in depth! – Max C Jul 07 '17 at 08:01
  • 2
    @MaxC Not a problem at all. I'm self taught with no formal training nor any college courses. Helping out others and working at problems such as yours also helps me to improve my own skill set. – Francis Cugler Jul 07 '17 at 11:04