src/eval.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include "amazons.h"
   4 #include "unit-test.h"
   5
   6
   7 /* local protos */
   8 static void tt_copy(state *s, state_t *t, short alpha, short beta);
   9
  10
  11 /* Globals */
  12 int black_misc = 0, white_misc = 0;     //miscellaneous heuristic values
  13
  14
  15 /* Heuristic Weights */
  16 #define QUEEN_LOSS      15      //point deduction when losing a queen
  17 #define QUEEN_DANGER    10      //point deduction when queen in danger
  18 #define QUEEN_CLUSTER    5      //point deduction when a queen isn't in
  19                                 //  a quadrant
  20 #define OWN_VALUE        1.5    //Value of owning a square
  21
  22
  23
  24 /*==============================================================================
  25  * get_forward_diag
  26  *
  27  * This gets a stream of bits from the given bit board in a "forwards" diagonal
  28  * starting at the position diag, and returns the stream.
  29  */
  30 int get_forward_diag(ull board_l, ull board_u, int diag)
  31 {
  32    int len = GET_FDIAG_LEN(diag);
  33    int i;
  34    ushort res = 0;
  35    ull *board;
  36    int pos=diag;
  37    ushort mask = 0x1;
  38
  39    for (i=0; i<len; i++)
  40      {
  41       if (pos > 49)
  42          board = &board_u;
  43       else
  44          board = &board_l;
  45
  46       res |= (*board >> (pos % 50)) & mask;
  47       pos +=10;
  48       mask <<= 1;
  49      }
  50
  51    return res;
  52 }
  53
  54
  55 /*==============================================================================
  56  * get_back_diag
  57  *
  58  * This gets a stream of bits from the given bit board in a "backwards" diagonal
  59  * starting at the position diag, and returns the stream.
  60  */
  61 int get_back_diag(ull board_l, ull board_u, int diag)
  62 {
  63    int len = GET_BDIAG_LEN(diag);
  64    int i;
  65    ushort res = 0;
  66    int pos=diag;
  67    ushort mask = 0x1;
  68
  69    for (i=0; i<=len; i++)
  70      {
  71       //This needs some funky footwork to get bits in the early 50's
  72       if (pos + i > 49)
  73         {
  74          if (pos > 49)
  75            {
  76            res |= (board_u >> (pos % 50)) & mask;
  77            }
  78          else
  79            {
  80             res |= (board_u << (50 - pos)) & mask;
  81            }
  82         }
  83       else
  84          res |= (board_l >> pos) & mask;
  85
  86       pos +=8;
  87       mask <<= 1;
  88      }
  89
  90    return res;
  91 }
  92
  93 /*==============================================================================
  94  * put_forward_diag
  95  *
  96  * This takes a stream of bits and stores them on the given bit board in a
  97  * "forward" diagonal starting at the position diag.
  98  */
  99 void put_forward_diag(ull *board_l, ull *board_u, ushort stream, int diag)
 100 {
 101    int len = GET_FDIAG_LEN(diag);
 102    int i;
 103    ull *board;
 104    int pos=diag;
 105    ushort mask = 0x1;
 106
 107    for (i=0; i<len; i++)
 108      {
 109       if (pos > 49)
 110          board = board_u;
 111       else
 112          board = board_l;
 113
 114       *board |= ((ull) (stream & mask ) << (pos % 50));
 115       pos +=10;
 116       mask <<= 1;
 117      }
 118 }
 119
 120
 121 /*==============================================================================
 122  * put_back_diag
 123  *
 124  * This takes a stream of bits and stores them on the given bit board in a
 125  * "backwards" diagonal starting at the position diag.
 126  */
 127 void put_back_diag(ull *board_l, ull *board_u, ushort stream, int diag)
 128 {
 129    int len = GET_BDIAG_LEN(diag);
 130    int i;
 131    int pos=diag;
 132    ushort mask = 0x1;
 133
 134    for (i=0; i<len; i++)
 135      {
 136       //This needs some funky footwork to get bits in the early 50's
 137       if (pos + i > 49)
 138         {
 139          if (pos > 49)
 140             *board_u |= ((ull) (stream & mask ) << (pos % 50));
 141          else
 142             *board_u |= ((ull) (stream & mask ) >> (50 - pos));
 143         }
 144       else
 145          *board_l |= ((ull) (stream & mask ) << pos);
 146
 147       pos +=8;
 148       mask <<= 1;
 149      }
 150 }
 151
 152
 153 /*==============================================================================
 154  * heval
 155  *
 156  * This calculates the heuristic evaluation for a given state.  It currently
 157  * bases it's evaluation on the number of squares the queens can move to and the
 158  * number of squares each side "owns".
 159  */
 160 int heval(state *s)
 161 {
 162    int p1=0, p2=0;
 163    float own1L0 = 0, own2L0= 0;
 164    float own1L1 = 0, own2L1= 0;
 165    ull board_u, board_l;
 166    ull web_board_u=0, web_board_l=0;
 167    ull white_web1_u=0, white_web1_l=0, black_web1_u=0, black_web1_l=0;
 168    ull res1_l=0, res1_u=0, res2_l=0, res2_u=0;
 169    ull dirs_l=0, dirs_u=0;
 170
 171         //Generates quads that look like:
 172         // 1 1 1 1 1 0 0 0 0 0
 173         // 1 1 1 1 1 0 0 0 0 0
 174         // 1 1 1 1 1 0 0 0 0 0
 175         // 1 1 1 1 1 0 0 0 0 0
 176         // 1 1 1 1 1 0 0 0 0 0
 177         ull low_quad = 0x07c1f07c1f, high_quad = 0xf83e0f83e0;
 178
 179    int i;
 180    int black_q_pos[4];
 181    int white_q_pos[4];
 182
 183    ++heval_calls;
 184    white_misc = black_misc = 0;
 185
 186    //establish queen positions
 187    for (i=0; i<4; i++)
 188      {
 189       black_q_pos[i] = XY_TO_POS(s->black_q_x[i], s->black_q_y[i]);
 190       white_q_pos[i] = XY_TO_POS(s->white_q_x[i], s->white_q_y[i]);
 191      }
 192    //printf("heval:\n");
 193    //pboard(*s);
 194
 195    board_u = s->white_bd[1] | s->black_bd[1] | s->blocks_bd[1];
 196    board_l = s->white_bd[0] | s->black_bd[0] | s->blocks_bd[0];
 197
 198    //pvec(board_u);
 199    //pvec(board_l);
 200    //pbvec(board_l, board_u);
 201
 202    //calculate moves
 203    /*
 204    for (i=0; i<4; i++)
 205      {
 206       p1 += calc_moves(board_l, board_u, white_q_pos[i]);
 207       p2 += calc_moves(board_l, board_u, black_q_pos[i]);
 208      }
 209      */
 210
 211    //make webs for queens & count # of moves
 212    for (i=0; i<4; i++)
 213      {
 214       if (!(p1 += gen_web_board_count(&white_web1_l, &white_web1_u, board_l, board_u, white_q_pos[i])))
 215          white_misc -= QUEEN_LOSS;  //white queen is trapped.
 216
 217       if (!(p2 += gen_web_board_count(&black_web1_l, &black_web1_u, board_l, board_u, black_q_pos[i])))
 218          black_misc -= QUEEN_LOSS;  //black queen is trapped.
 219      }
 220
 221    /* look for queens in trouble */
 222    for (i=0; i<4; i++)
 223      {
 224       //check white queens
 225       gen_dirs_board(&dirs_l, &dirs_u, white_q_pos[i]);
 226       res1_l = white_web1_l & dirs_l;
 227       res1_u = white_web1_u & dirs_u;
 228
 229       if (count_bits(res1_l, res1_u) < 3)
 230         {
 231          res2_l = res1_l & black_web1_l;
 232          res2_u = res1_u & black_web1_u;
 233          if (!((res1_l ^ res2_l) || (res1_u ^ res2_u)))
 234             white_misc -= QUEEN_DANGER;
 235         }
 236
 237       //check black queens
 238       gen_dirs_board(&dirs_l, &dirs_u, black_q_pos[i]);
 239       res1_l = black_web1_l & dirs_l;
 240       res1_u = black_web1_u & dirs_u;
 241       if (count_bits(res1_l, res1_u) < 3)
 242         {
 243          res2_l = res1_l & white_web1_l;
 244          res2_u = res1_u & white_web1_u;
 245          if (!((res1_l ^ res2_l) || (res1_u ^ res2_u)))
 246             black_misc -= QUEEN_DANGER;
 247         }
 248      }
 249
 250    /* Encourage queens to spread out a bit */
 251    for (i=0; i<2; i++)
 252      {
 253       if (!(s->white_bd[i] & low_quad))
 254          white_misc -= QUEEN_CLUSTER;
 255       else if (!(s->black_bd[i] & low_quad))
 256          white_misc += QUEEN_CLUSTER;  //give bonus points for owning a quadrant
 257       if (!(s->white_bd[i] & high_quad))
 258          white_misc -= QUEEN_CLUSTER;
 259       else if (!(s->black_bd[i] & high_quad))
 260          white_misc += QUEEN_CLUSTER;  //give bonus points for owning a quadrant
 261       if (!(s->black_bd[i] & low_quad))
 262          black_misc -= QUEEN_CLUSTER;
 263       else if (!(s->white_bd[i] & low_quad))
 264          black_misc += QUEEN_CLUSTER;
 265       if (!(s->black_bd[i] & high_quad))
 266          black_misc -= QUEEN_CLUSTER;
 267       else if (!(s->white_bd[i] & high_quad))
 268          black_misc += QUEEN_CLUSTER;
 269      }
 270
 271    /*
 272     *calculate square ownership
 273     */
 274
 275 #ifdef DEBUG_HEVAL
 276    printf("white moves = %d, black moves = %d\n", p1, p2);
 277 #endif
 278
 279 #ifdef DEBUG_WEB
 280       printf("White's web board:\n");
 281       pbvec(white_web1_l, white_web1_u);
 282
 283       printf("Blacks's web board:\n");
 284       pbvec(black_web1_l, black_web1_u);
 285 #endif
 286    //make webs for each empty square
 287    for (i=0; i<100; i++)
 288      {
 289       if (i > 49)
 290         {
 291          if (board_u & ((ull)0x1 << (i % 50)))
 292             continue;
 293         }
 294       else
 295         {
 296          if (board_l & ((ull)0x1 << (i % 50)))
 297             continue;
 298         }
 299
 300       web_board_l = web_board_u = 0;
 301       gen_web_board(&web_board_l, &web_board_u, board_l, board_u, i);
 302
 303 #ifdef DEBUG_WEB
 304       printf("web board for square %d:\n", i);
 305       pbvec(web_board_l, web_board_u);
 306 #endif
 307
 308       if (s->turn == WHITE_PLAYER) //player 1 moves next
 309         {
 310          if ((web_board_l & s->white_bd[0]) || (web_board_u & s->white_bd[1]))
 311            {
 312             //printf("Square %d is owned by white - level 0\n", i);
 313             ++own1L0;
 314             if ((web_board_l & s->black_bd[0]) || (web_board_u & s->black_bd[1]))
 315                own1L0 -= .5;
 316            }
 317          else if ((web_board_l & s->black_bd[0]) || (web_board_u & s->black_bd[1]))
 318            {
 319             //printf("Square %d is owned by black - level 0\n", i);
 320             ++own2L0;
 321            }
 322          else if ((web_board_l & white_web1_l) || (web_board_u & white_web1_u))
 323            {
 324             //printf("Square %d is owned by white - level 1\n", i);
 325             ++own1L1;
 326             if ((web_board_l & black_web1_l) || (web_board_u & black_web1_u))
 327                own1L1 -= .5;
 328            }
 329          else if ((web_board_l & black_web1_l) || (web_board_u & black_web1_u))
 330            {
 331             //printf("Square %d is owned by black - level 1\n", i);
 332             ++own2L1;
 333            }
 334          else
 335            {
 336             //printf("Square %d is not owned by anyone\n", i);
 337            }
 338         }
 339      else
 340         {
 341          if ((web_board_l & s->black_bd[0]) || (web_board_u & s->black_bd[1]))
 342            {
 343             //printf("Square %d is owned by black - level 0\n", i);
 344             ++own2L0;
 345             if ((web_board_l & s->white_bd[0]) || (web_board_u & s->white_bd[1]))
 346                own2L0 -= .5;
 347            }
 348          else if ((web_board_l & s->white_bd[0]) || (web_board_u & s->white_bd[1]))
 349            {
 350             ++own1L0;
 351             //printf("Square %d is owned by white - level 0\n", i);
 352            }
 353          else if ((web_board_l & black_web1_l) || (web_board_u & black_web1_u))
 354            {
 355             //printf("Square %d is owned by black - level 1\n", i);
 356             ++own2L1;
 357             if ((web_board_l & white_web1_l) || (web_board_u & white_web1_u))
 358                own2L1 -= .5;
 359            }
 360          else if ((web_board_l & white_web1_l) || (web_board_u & white_web1_u))
 361            {
 362             //printf("Square %d is owned by white - level 1\n", i);
 363             ++own1L1;
 364            }
 365          else
 366            {
 367             //printf("Square %d is not owned by anyone\n", i);
 368            }
 369         }
 370      }
 371
 372
 373 #ifdef DEBUG_HEVAL
 374    printf("Direct white squares = %d, direct black squares = %d\n", own1L0, own2L0);
 375    printf("Indirect white squares = %d, indirect black squares = %d\n", own1L1, own2L1);
 376    printf("white squares = %d, black squares = %d\n", own1, own2);
 377 #endif
 378 //      printf("own1 = %d p1 = %d own2 = %d p2 = %d\n", own1,p1,own2,p2);
 379    return (((own1L0 + own1L1) * OWN_VALUE + p1 + white_misc) - (p2 + (own2L0 + own2L1) * OWN_VALUE + black_misc));
 380
 381 }
 382
 383 /*==============================================================================
 384  * calc_moves
 385  *
 386  * This receives a complete bit board with all occupied square bits set.  From
 387  * the given position, it calculates all possible moves in every direction.
 388  *
 389  * Returns the number of moves possible.
 390  */
 391 int calc_moves(ull board_l, ull board_u, int pos)
 392 {
 393    ushort stream;
 394    int row, col, fdiag, bdiag;
 395    int diag;
 396
 397
 398    //count row moves
 399    if (pos < 50)
 400       stream = GET_ROW(board_l, GET_COL_POS(pos));
 401    else
 402       stream = GET_ROW(board_u, GET_COL_POS(pos));
 403    row = calc_stream_moves(stream, GET_ROW_POS(pos), 10);
 404    //printf("%d row moves\n", row);
 405
 406
 407    //count col moves
 408    stream = GET_COL(board_l, board_u, GET_ROW_POS(pos));
 409    col = calc_stream_moves(stream, GET_COL_POS(pos), 10);
 410    //printf("%d col moves\n", col);
 411
 412    //count forw diag moves
 413    diag = GET_FDIAG(pos);
 414    stream = get_forward_diag(board_l, board_u, diag);
 415    fdiag = calc_stream_moves(stream, GET_FDIAG_POS(pos), GET_FDIAG_LEN(diag));
 416    //printf("%d fdiag moves\n", fdiag);
 417
 418    //count back diag moves
 419    diag = GET_BDIAG(pos);
 420    stream = get_back_diag(board_l, board_u, diag);
 421    bdiag = calc_stream_moves(stream, GET_BDIAG_POS(pos), GET_BDIAG_LEN(diag));
 422    //printf("%d bdiag moves\n", bdiag);
 423
 424    //printf("%d total moves\n", row+col+fdiag+bdiag);
 425    return (row+col+fdiag+bdiag);
 426
 427
 428 }
 429
 430 /*==============================================================================
 431  * calc_stream_moves
 432  *
 433  * Calculates the number of empty bits in either direction from the given position
 434  * in the given stream.
 435  *
 436  * Returns the number of moves in that stream.
 437  */
 438 int calc_stream_moves(ushort stream, ushort pos, ushort len)
 439 {
 440    int i;
 441    int moves = 0;
 442    int before=0, after=0;
 443
 444    //psvec(stream, len);
 445    //error check
 446    if (pos > len)
 447      {
 448       printf("duh, the position %d can't be greater than the length %d\n", pos, len);
 449       return 0;
 450      }
 451
 452 //   printf("stream len = %d\n", len);
 453    for (i=0; i<pos; i++)
 454      {
 455       if (stream & 0x1)
 456          before = 0;// (pos - (i+1));
 457       else
 458          ++before;
 459       stream >>= 1;
 460      }
 461
 462    ++i;
 463    stream >>= 1;
 464
 465    for ( ; i<len; i++)
 466      {
 467       if (stream & 0x1)
 468          break;
 469       else
 470          ++after;
 471       stream >>= 1;
 472      }
 473    moves = before + after;
 474    //printf("Pos = %d, before = %d, after = %d\n", pos, before, after);
 475
 476    return moves;
 477 }
 478
 479
 480 /*==============================================================================
 481  * gen_web_stream
 482  *
 483  * This generates a stream of 1 bits (the 'web') in both directions, starting
 484  * from the given position pos, and stops when it hits a set bit in the given
 485  * stream or comes to the end of the stream.
 486  *
 487  * Returns the generated web.
 488  */
 489 ushort gen_web_stream(ushort stream, int pos, int len)
 490 {
 491    ushort web = 0;
 492    int i;
 493
 494    web |= 0x1 << pos;
 495
 496    for (i=pos-1; i>=0; i--)
 497      {
 498       if (stream & (0x1 << i))
 499          break;
 500       else
 501          web |= 0x1 << i;
 502      }
 503
 504    for (i=pos+1; i<len; i++)
 505      {
 506       if (stream & (0x1 << i))
 507          break;
 508       else
 509          web |= 0x1 << i;
 510      }
 511
 512    return web;
 513 }
 514
 515 /*==============================================================================
 516  * gen_web_stream_plus
 517  *
 518  * This generates a stream of 1 bits (the 'web') in both directions, starting
 519  * from the given position pos, and stops when it hits a set bit in the given
 520  * stream or comes to the end of the stream.  This differs from gen_web_stream
 521  * in that it includes a set bit on the square that it ran into.  This enables
 522  * me to & the generated web stream with a queen board and see if they coincide.
 523  *
 524  * Returns the generated web.
 525  */
 526 ushort gen_web_stream_plus(ushort stream, int pos, int len)
 527 {
 528    ushort web = 0;
 529    int i;
 530
 531    web |= 0x1 << pos;
 532
 533    for (i=pos-1; i>=0; i--)
 534      {
 535       if (stream & (0x1 << i))
 536         {
 537          web |= 0x1 << i;
 538          break;
 539         }
 540       else
 541          web |= 0x1 << i;
 542      }
 543
 544    for (i=pos+1; i<len; i++)
 545      {
 546       if (stream & (0x1 << i))
 547         {
 548          web |= 0x1 << i;
 549          break;
 550         }
 551       else
 552          web |= 0x1 << i;
 553      }
 554
 555    return web;
 556 }
 557
 558 /*==============================================================================
 559  * gen_web_board
 560  *
 561  * This takes the bit boards, board_l & board_u that represent all the occupied
 562  * squares.  Then, from the given position pos, generates a stream of 1's in
 563  * every direction until they hit an occupied square.  The result is stored
 564  * in the given web_u & web_l
 565  */
 566 void gen_web_board(ull *web_l, ull *web_u, ull board_l, ull board_u, int pos)
 567 {
 568    ushort row, col, fdiag, bdiag;
 569    ushort web_row, web_col, web_fdiag, web_bdiag;
 570    int diag;
 571
 572    //row web
 573    if (pos > 49)
 574       row = GET_ROW(board_u, GET_COL_POS(pos));
 575    else
 576       row = GET_ROW(board_l, GET_COL_POS(pos));
 577
 578    web_row = gen_web_stream_plus(row, GET_ROW_POS(pos), 10);
 579    //printf("Row for pos %d:", pos);
 580
 581 #ifdef DEBUG_WEB
 582    printf("Generating web for row "); psvec(row, 10);
 583    printf("Web generated for row at pos %d:", pos);
 584    psvec(web_row, 10);
 585 #endif
 586
 587    if (pos > 49)
 588       PUT_ROW(*web_u, pos/10, web_row);
 589    else
 590       PUT_ROW(*web_l, pos/10, web_row);
 591 #ifdef DEBUG_WEB
 592    printf("web board after row inserted:\n");
 593    pbvec(*web_l, *web_u);
 594 #endif
 595
 596    //col web
 597    col = GET_COL(board_l, board_u, pos%10);
 598    web_col = gen_web_stream_plus(col, GET_COL_POS(pos), 10);
 599
 600 #ifdef DEBUG_WEB
 601    printf("Generating web for col "); psvec(col, 10);
 602    printf("Web generated for col at pos %d:", pos);
 603    psvec(web_col, 10);
 604 #endif
 605
 606    PUT_COL(*web_l, *web_u, pos%10, web_col);
 607 #ifdef DEBUG_WEB
 608    printf("web board after col inserted:\n");
 609    pbvec(*web_l, *web_u);
 610 #endif
 611
 612    //fdiag web
 613    diag = GET_FDIAG(pos);
 614    fdiag = get_forward_diag(board_l, board_u, diag);
 615    web_fdiag = gen_web_stream_plus(fdiag, GET_FDIAG_POS(pos), GET_FDIAG_LEN(diag));
 616
 617 #ifdef DEBUG_WEB
 618    printf("Generating web for fdiag "); psvec(fdiag, GET_FDIAG_LEN(diag));
 619    printf("Web generated for fdiag at pos %d:", pos);
 620    psvec(web_fdiag, 10);
 621 #endif
 622
 623    put_forward_diag(web_l, web_u, web_fdiag, diag);
 624 #ifdef DEBUG_WEB
 625    printf("web board after fdiag inserted:\n");
 626    pbvec(*web_l, *web_u);
 627 #endif
 628
 629    //bdiag web
 630    diag = GET_BDIAG(pos);
 631    bdiag = get_back_diag(board_l, board_u, diag);
 632    web_bdiag = gen_web_stream_plus(bdiag, GET_BDIAG_POS(pos), GET_BDIAG_LEN(diag));
 633
 634 #ifdef DEBUG_WEB
 635    printf("Generating web for bdiag "); psvec(bdiag, GET_BDIAG_LEN(diag));
 636    printf("Web generated for bdiag at pos %d:", pos);
 637    psvec(web_bdiag, 10);
 638 #endif
 639
 640    put_back_diag(web_l, web_u, web_bdiag, diag);
 641 #ifdef DEBUG_WEB
 642    printf("web board after bdiag inserted:\n");
 643    pbvec(*web_l, *web_u);
 644 #endif
 645
 646
 647 }
 648 /*==============================================================================
 649  * gen_web_board_count
 650  *
 651  * This takes the bit boards, board_l & board_u that represent all the occupied
 652  * squares.  Then, from the given position pos, generates a stream of 1's in
 653  * every direction until they hit an occupied square.  The result is stored
 654  * in the given web_u & web_l
 655  */
 656 int gen_web_board_count(ull *web_l, ull *web_u, ull board_l, ull board_u, int pos)
 657 {
 658    ushort row, col, fdiag, bdiag;
 659    ushort web_row, web_col, web_fdiag, web_bdiag;
 660    int diag;
 661    int row_count, col_count, fdiag_count, bdiag_count;
 662
 663 #ifdef DEBUG_HEVAL
 664    printf("Counting moves for queen on position %d\n", pos);
 665 #endif
 666    //row web
 667    if (pos > 49)
 668       row = GET_ROW(board_u, GET_COL_POS(pos));
 669    else
 670       row = GET_ROW(board_l, GET_COL_POS(pos));
 671
 672    web_row = gen_web_stream(row, GET_ROW_POS(pos), 10);
 673    row_count = count_contig_bits(web_row, 10);
 674    //printf("Row for pos %d:", pos);
 675
 676 #ifdef DEBUG_HEVAL
 677    printf("Counting moves for queen on position %d\n", pos);
 678    printf("  Row moves: %d\n", row_count);
 679 #endif
 680
 681 #ifdef DEBUG_WEB
 682    printf("Generating web for row "); psvec(row, 10);
 683    printf("Web generated for row at pos %d:", pos);
 684    psvec(web_row, 10);
 685 #endif
 686
 687    if (pos > 49)
 688       PUT_ROW(*web_u, pos/10, web_row);
 689    else
 690       PUT_ROW(*web_l, pos/10, web_row);
 691 #ifdef DEBUG_WEB
 692    printf("web board after row inserted:\n");
 693    pbvec(*web_l, *web_u);
 694 #endif
 695
 696    //col web
 697    col = GET_COL(board_l, board_u, pos%10);
 698    web_col = gen_web_stream(col, GET_COL_POS(pos), 10);
 699    col_count = count_contig_bits(web_col, 10);
 700
 701 #ifdef DEBUG_HEVAL
 702    printf("  Col moves: %d\n", col_count);
 703 #endif
 704
 705 #ifdef DEBUG_WEB
 706    printf("Generating web for col "); psvec(col, 10);
 707    printf("Web generated for col at pos %d:", pos);
 708    psvec(web_col, 10);
 709 #endif
 710
 711    PUT_COL(*web_l, *web_u, pos%10, web_col);
 712 #ifdef DEBUG_WEB
 713    printf("web board after col inserted:\n");
 714    pbvec(*web_l, *web_u);
 715 #endif
 716
 717    //fdiag web
 718    diag = GET_FDIAG(pos);
 719    fdiag = get_forward_diag(board_l, board_u, diag);
 720    web_fdiag = gen_web_stream(fdiag, GET_FDIAG_POS(pos), GET_FDIAG_LEN(diag));
 721    fdiag_count = count_contig_bits(web_fdiag, GET_FDIAG_LEN(diag));
 722
 723 #ifdef DEBUG_HEVAL
 724    printf("  Fdiag moves: %d\n", fdiag_count);
 725 #endif
 726
 727 #ifdef DEBUG_WEB
 728    printf("Generating web for fdiag "); psvec(fdiag, GET_FDIAG_LEN(diag));
 729    printf("Web generated for fdiag at pos %d:", pos);
 730    psvec(web_fdiag, 10);
 731 #endif
 732
 733    put_forward_diag(web_l, web_u, web_fdiag, diag);
 734 #ifdef DEBUG_WEB
 735    printf("web board after fdiag inserted:\n");
 736    pbvec(*web_l, *web_u);
 737 #endif
 738
 739    //bdiag web
 740    diag = GET_BDIAG(pos);
 741    bdiag = get_back_diag(board_l, board_u, diag);
 742    web_bdiag = gen_web_stream(bdiag, GET_BDIAG_POS(pos), GET_BDIAG_LEN(diag));
 743    bdiag_count = count_contig_bits(web_bdiag, GET_BDIAG_LEN(diag));
 744
 745 #ifdef DEBUG_HEVAL
 746    printf("  Bdiag moves: %d\n", bdiag_count);
 747 #endif
 748 #ifdef DEBUG_WEB
 749    printf("Generating web for bdiag "); psvec(bdiag, GET_BDIAG_LEN(diag));
 750    printf("Web generated for bdiag at pos %d:", pos);
 751    psvec(web_bdiag, 10);
 752 #endif
 753
 754    put_back_diag(web_l, web_u, web_bdiag, diag);
 755 #ifdef DEBUG_WEB
 756    printf("web board after bdiag inserted:\n");
 757    pbvec(*web_l, *web_u);
 758 #endif
 759
 760    return (row_count + col_count + fdiag_count + bdiag_count - 4);
 761 }
 762
 763 /*==============================================================================
 764  * count_contig_bits
 765  *
 766  * This counts the number of contiguous bits in a stream.  It starts looking at
 767  * the 0th bit, and starts counting when it finds the first set bit, and stops
 768  * counting on the next unset bit.
 769  *
 770  * Returns the number of contiguous set bits.
 771  */
 772 int count_contig_bits(ushort stream, int len)
 773 {
 774    int i;
 775    int count = 0;
 776
 777    for (i=0; i<len; i++)
 778      {
 779       if (stream & (0x1 << i))
 780          ++count;
 781       else if (count)
 782          return count;
 783      }
 784
 785    return count;
 786 }
 787
 788
 789
 790 /*==============================================================================
 791  * pbvec
 792  *
 793  * This prints out a bit board with the same ordering as pboard.
 794  *
 795  */
 796 int pbvec(ull l, ull u)
 797 {
 798     int i,j;
 799
 800 //   pvec(u);
 801     for (i=4; i>=0; i--)
 802       {
 803        for (j=0; j<10; j++)
 804          {
 805           printf("%d ", (int)((u >> (i*10 + j)) &0x1));
 806          }
 807        printf("\n");
 808       }
 809
 810
 811 //    pvec(l);
 812     for (i=4; i>=0; i--)
 813       {
 814        for (j=0; j<10; j++)
 815          {
 816           printf("%d ", (int)((l >> (i*10 + j)) &0x1));
 817          }
 818        printf("\n");
 819       }
 820
 821     return 0;
 822 }
 823
 824 /*==============================================================================
 825  * tt_lookup
 826  *
 827  * This looks a given state up in the transposition table (TT).  If it's found, it
 828  * returns a pointer to the tt entry and lets the caller decide if it's usable.
 829  *
 830  * Otherwise, it returns NULL.
 831  *
 832  * Note: this also allocates the initial TT.  On first run, if the TT hasn't been
 833  * created yet, this will create it.  This means that it MUST be called before
 834  * tt_store, otherwise very bad things will happen.
 835  *
 836  */
 837 state_t * tt_lookup(state *s)
 838 {
 839    ull board_u, board_l;
 840    int hash_index;
 841    int found = 0;
 842    int max = 0;
 843
 844    if (tt == NULL)
 845       tt = (state_t **) calloc(TT, sizeof(state_t *));
 846
 847
 848    board_u = s->white_bd[1] | s->black_bd[1] | s->blocks_bd[1];
 849    board_l = s->white_bd[0] | s->black_bd[0] | s->blocks_bd[0];
 850
 851    hash_index = (board_u ^ board_l) % TT;
 852
 853    while(tt[hash_index] && !found && (max < MAX_TT_SEARCH) && (hash_index < TT))
 854      {
 855       found = tt_compare(s,tt[hash_index]);
 856       ++hash_index;
 857       ++max;
 858      }
 859
 860    ++tt_lookups;
 861    if (found)
 862      {
 863       ++tt_lookup_finds;
 864       return (tt[--hash_index]);
 865       /*
 866       s->value = tt[--hash_index]->value;
 867       s->depth = tt[hash_index]->depth;
 868       return TRUE;
 869       */
 870      }
 871    else
 872       return NULL;
 873
 874 }
 875
 876 /*==============================================================================
 877  * tt_compare
 878  *
 879  * This compares a state to a state_t.  Returns TRUE if they're equivalent, FALSE
 880  * if not.
 881  */
 882 int tt_compare(state *s, state_t *t)
 883 {
 884    if ((s->white_bd[0] == t->white_bd[0]) && (s->white_bd[1] == t->white_bd[1]) &&
 885        (s->black_bd[0] == t->black_bd[0]) && (s->black_bd[1] == t->black_bd[1]) &&
 886        (s->blocks_bd[0] == t->blocks_bd[0]) && (s->blocks_bd[1] == t->blocks_bd[1]) &&
 887        (s->turn == t->turn))
 888       return TRUE;
 889    else
 890       return FALSE;
 891 }
 892
 893 /*==============================================================================
 894  * tt_store
 895  *
 896  * tt_store takes a state and stores the necessary components into the TT.  If
 897  * the calculated hash index is already occupied (collision), it will proceed on
 898  * to the next one, etc etc...  If it doesn't find an empty spot withint
 899  * MAX_TT_SEARCH, it will go back to the initial hash index it calculated, free
 900  * whatever was there, and replace it with the new one.
 901  *
 902  */
 903 void tt_store(state *s, short alpha, short beta)
 904 {
 905    ull board_u, board_l;
 906    int hash_index;
 907    int max = 0;
 908
 909    board_u = s->white_bd[1] | s->black_bd[1] | s->blocks_bd[1];
 910    board_l = s->white_bd[0] | s->black_bd[0] | s->blocks_bd[0];
 911
 912    hash_index = (board_u ^ board_l) % TT;
 913
 914    ++tt_stores;
 915
 916    //looks at a max of MAX_TT_SEARCH items before freeing the first one and storing there
 917    while(tt[hash_index] && (max < MAX_TT_SEARCH) && (hash_index < TT))
 918      {
 919       ++hash_index;
 920       ++max;
 921      }
 922
 923    if (max == MAX_TT_SEARCH)
 924      {
 925       hash_index -= max;
 926       ++tt_overwrite;
 927      }
 928
 929    if (tt[hash_index])
 930       free(tt[hash_index]);
 931
 932    tt[hash_index] = (state_t *) malloc(sizeof(state_t));
 933    tt_copy(s, tt[hash_index], alpha, beta);
 934
 935 }
 936
 937 /*==============================================================================
 938  * tt_copy
 939  *
 940  * Copies a state struct into a state_t struct.
 941  */
 942 static void tt_copy(state *s, state_t *t, short alpha, short beta)
 943 {
 944
 945    t->white_bd[0] = s->white_bd[0];
 946    t->white_bd[1] = s->white_bd[1];
 947
 948    t->black_bd[0] = s->black_bd[0];
 949    t->black_bd[1] = s->black_bd[1];
 950
 951    t->blocks_bd[0] = s->blocks_bd[0];
 952    t->blocks_bd[1] = s->blocks_bd[1];
 953
 954    t->turn = s->turn;
 955    t->value = s->value;
 956    t->depth = s->depth;
 957    t->alpha = alpha;
 958    t->beta = beta;
 959 }
 960
 961
 962 /*==============================================================================
 963  * tt_update
 964  *
 965  * This is used to update the value and depth members of a TT entry that already
 966  * exists.  Sometimes, if the value stored in the TT isn't accurate to a very deep
 967  * level, it's desireable to go ahead and search deeper and update the entry with
 968  * a more accurate reading.
 969  *
 970  * Of course, it's possible in the meantime for the original entry to have been
 971  * overwritten, so if it isn't found, it recreates the entire entry.
 972  */
 973 void tt_update(state *s, short alpha, short beta)
 974 {
 975    ull board_u, board_l;
 976    int hash_index;
 977    int found = 0;
 978    int max = 0;
 979
 980    if (tt == NULL)
 981       tt = (state_t **) calloc(TT, sizeof(state_t *));
 982
 983    board_u = s->white_bd[1] | s->black_bd[1] | s->blocks_bd[1];
 984    board_l = s->white_bd[0] | s->black_bd[0] | s->blocks_bd[0];
 985
 986    hash_index = (board_u ^ board_l) % TT;
 987
 988    while(tt[hash_index] && !found && (max < MAX_TT_SEARCH) && (hash_index < TT))
 989      {
 990       found = tt_compare(s,tt[hash_index]);
 991       ++hash_index;
 992       ++max;
 993      }
 994
 995    if (found)
 996      {
 997       tt[--hash_index]->value = s->value;
 998       tt[hash_index]->depth = s->depth;
 999       ++tt_updates;
1000      }
1001    else //create a new one
1002      {
1003       hash_index-= MAX_TT_SEARCH;
1004       if (tt[hash_index])
1005          free(tt[hash_index]);
1006
1007       tt[hash_index] = (state_t *) malloc(sizeof(state_t));
1008       tt_copy(s, tt[hash_index], alpha, beta);
1009
1010       ++tt_overwrite;
1011      }
1012
1013 }
1014
1015 /*==============================================================================
1016  * gen_dirs_board
1017  *
1018  * This function generates a bitmask board that completely surrounds a single
1019  * position.
1020  *
1021  * The generated mask will look something like:
1022  *
1023  *   1 1 1
1024  *   1 0 1
1025  *   1 1 1
1026  *
1027  * Where the 0 bit is the position passed in.  This gets tricky when the position
1028  * is right next to a border and part of the mask will need to be amputated
1029  * accordingly.
1030  */
1031 void gen_dirs_board(ull *board_l, ull *board_u, int pos)
1032 {
1033    int row = GET_COL_POS(pos);
1034    int row_adj = row % 5;
1035    int pos_adj = pos % 50;
1036    ull *board_ptr = NULL;
1037
1038  /* Generate top row */
1039    if (row < 9) //position is not against top border, generate this row
1040      {
1041       if (pos > 39) //use upper board
1042          board_ptr = board_u;
1043       else
1044          board_ptr = board_l;
1045       //The 2nd half of this expressions is a row bitmask that takes care of
1046       //positions next to the left or right borders, ensuring that the bits
1047       //placed on the board stay in the row
1048       if (pos == 40)
1049          *board_ptr |= 0x3;
1050       else
1051          *board_ptr |= (((ull)0x7 << ((pos_adj + 9) % 50)) & ((ull)0x3ff << (((row_adj + 1)%5) * 10)));
1052      }
1053
1054  /* Generate middle row */
1055    if (pos < 50)
1056       board_ptr = board_l;  //otherwise board_ptr is still pointing to board_u
1057    else
1058       board_ptr = board_u;  //otherwise board_ptr is still pointing to board_u
1059
1060    if (pos_adj == 0)
1061       *board_ptr |= (ull) (0x2); //in bottom left corner of board half, can't shift neg
1062    else
1063       *board_ptr |= (((ull) 0x5 << (pos_adj - 1)) & ((ull) 0x3ff << (row_adj * 10)));
1064
1065  /* Generate bottom row */
1066    if (row > 0) //position is not against bottom border, generate this row
1067      {
1068       if (pos < 60)
1069          board_ptr = board_l;  //otherwise board_ptr is still pointing to board_u
1070       else
1071          board_ptr = board_u;  //otherwise board_ptr is still pointing to board_u
1072       if (pos_adj == 10)
1073          *board_ptr |= (ull) 0x3; //in bottom left corner of board half, can't shift neg
1074       else
1075          *board_ptr |= (((ull) 0x7 << ((pos - 11)%50)) & ((ull) 0x3ff << (((row - 1)%5) * 10)));
1076      }
1077
1078
1079 }
1080
1081 int count_bits(ull board_l, ull board_u)
1082 {
1083    int count = 0;
1084    int i;
1085
1086    for (i=0; i< 64; i++)
1087      {
1088       if (board_l & 0x1)
1089          ++count;
1090       board_l >>= 1;
1091
1092       if (board_u & 0x1)
1093          ++count;
1094       board_u >>= 1;
1095      }
1096    return count;
1097 }