home *** CD-ROM | disk | FTP | other *** search
/ Dream 57 / Amiga_Dream_57.iso / Amiga / Jeux / Reflexion / Crafty-15.19.lha / crafty-15.19 / src / lookup.c < prev    next >
C/C++ Source or Header  |  1998-09-13  |  6KB  |  158 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "chess.h"
  4. #include "data.h"
  5.  
  6. /* last modified 08/20/98 */
  7. /*
  8. ********************************************************************************
  9. *                                                                              *
  10. *   LookUp() is used to retrieve entries from the transposition table so that  *
  11. *   this sub-tree won't have to be searched again if we reach a position that  *
  12. *   has been searched previously.  a transposition table position contains the *
  13. *   following data packed into 128 bits with each item taking the number of    *
  14. *   bits given in the table below:                                             *
  15. *                                                                              *
  16. *     bits     name  SL  description                                           *
  17. *       3       age  61  search id to identify old trans/ref entried.          *
  18. *       2      type  59  0->value is worthless; 1-> value represents a fail-   *
  19. *                        low bound; 2-> value represents a fail-high bound;    *
  20. *                        3-> value is an exact score.                          *
  21. *       1    threat  58  threat extension flag, 1 -> extend this position.     *
  22. *      16     value  21  unsigned integer value of this position + 65536.      *
  23. *                        this might be a good score or search bound.           *
  24. *      21      move   0  best move from the current position, according to the *
  25. *                        search at the time this position was stored.          *
  26. *                                                                              *
  27. *      16     draft  48  the depth of the search below this position, which is *
  28. *                        used to see if we can use this entry at the current   *
  29. *                        position.  note that this is in units of 1/8th of a   *
  30. *                        ply.                                                  *
  31. *      48       key   0  leftmost 48 bits of the 64 bit hash key.  this is     *
  32. *                        used to "verify" that this entry goes with the        *
  33. *                        current board position.                               *
  34. *                                                                              *
  35. ********************************************************************************
  36. */
  37. int LookUp(TREE *tree, int ply, int depth, int wtm, int *alpha,
  38.            int *beta, int *threat) {
  39.   register BITBOARD temp_hash_key;
  40.   register BITBOARD word1, word2;
  41.   register HASH_ENTRY *htable;
  42.   register int type, draft, avoid_null=WORTHLESS, val;
  43. /*
  44.  ----------------------------------------------------------
  45. |                                                          |
  46. |   first, compute the initial hash address and choose     |
  47. |   which hash table (based on color) to probe.            |
  48. |                                                          |
  49.  ----------------------------------------------------------
  50. */
  51.   tree->hash_move[ply]=0;
  52.   temp_hash_key=HashKey>>16;
  53. #if !defined(FAST)
  54.   tree->transposition_probes++;
  55. #endif
  56. /*
  57.  ----------------------------------------------------------
  58. |                                                          |
  59. |   now, check both "parts" of the hash table to see if    |
  60. |   this position is in either one.                        |
  61. |                                                          |
  62.  ----------------------------------------------------------
  63. */
  64.   htable=((wtm)?trans_ref_wa:trans_ref_ba)+(((int) HashKey) & hash_maska);
  65. # if defined(SMP)
  66.   Lock(lock_hasha);
  67. #endif
  68.   word1=htable->word1;
  69.   word2=htable->word2;
  70. # if defined(SMP)
  71.   UnLock(lock_hasha);
  72. #endif
  73.   if (!Xor(And(word2,mask_80),temp_hash_key)) do {
  74. #if !defined(FAST)
  75.     tree->transposition_hits++;
  76. #endif
  77.     tree->hash_move[ply]=((int) word1) & 07777777;
  78.     type=((int) Shiftr(word1,59)) & 03;
  79.     draft=(int) Shiftr(word2,48);
  80.     val=(((int) Shiftr(word1,21)) & 01777777)-65536;
  81.     *threat=((int) Shiftr(word1,58)) & 01;
  82.     if ((type & UPPER_BOUND) &&
  83.         depth-NULL_MOVE_DEPTH-INCREMENT_PLY <= draft &&
  84.         val < *beta) avoid_null=AVOID_NULL_MOVE;
  85.     if (depth > draft) break;
  86.  
  87.     switch (type) {
  88.       case EXACT_SCORE:
  89.         if (abs(val) > MATE-100) {
  90.           if (val > 0) val-=(ply-1);
  91.           else val+=(ply-1);
  92.         }
  93.         *alpha=val;
  94.         return(EXACT_SCORE);
  95.       case UPPER_BOUND:
  96.         if (val <= *alpha) {
  97.           *alpha=val;
  98.           return(UPPER_BOUND);
  99.         }
  100.         break;
  101.       case LOWER_BOUND:
  102.         if (val >= *beta) {
  103.           *beta=val;
  104.           return(LOWER_BOUND);
  105.         }
  106.         break;
  107.     }
  108.   } while(0);
  109.  
  110.   htable=((wtm)?trans_ref_wb:trans_ref_bb)+(((int) HashKey) & hash_maskb);
  111. # if defined(SMP)
  112.   Lock(lock_hashb);
  113. #endif
  114.   word1=htable->word1;
  115.   word2=htable->word2;
  116. # if defined(SMP)
  117.   UnLock(lock_hashb);
  118. #endif
  119.   if (!Xor(And(word2,mask_80),temp_hash_key)) {
  120. #if !defined(FAST)
  121.     tree->transposition_hits++;
  122. #endif
  123.     if (tree->hash_move[ply]==0)
  124.       tree->hash_move[ply]=((int) word1) & 07777777;
  125.     type=((int) Shiftr(word1,59)) & 03;
  126.     draft=Shiftr(word2,48);
  127.     val=(((int) Shiftr(word1,21)) & 01777777)-65536;
  128.     *threat=((int) Shiftr(word1,58)) & 01;
  129.     if ((type & UPPER_BOUND) &&
  130.         depth-NULL_MOVE_DEPTH-INCREMENT_PLY <= draft &&
  131.         val < *beta) avoid_null=AVOID_NULL_MOVE;
  132.     if (depth > draft) return(avoid_null);
  133.  
  134.     switch (type) {
  135.       case EXACT_SCORE:
  136.         if (abs(val) > MATE-100) {
  137.           if (val > 0) val-=(ply-1);
  138.           else val+=(ply-1);
  139.         }
  140.         *alpha=val;
  141.         return(EXACT_SCORE);
  142.       case UPPER_BOUND:
  143.         if (val <= *alpha) {
  144.           *alpha=val;
  145.           return(UPPER_BOUND);
  146.         }
  147.         return(avoid_null);
  148.       case LOWER_BOUND:
  149.         if (val >= *beta) {
  150.           *beta=val;
  151.           return(LOWER_BOUND);
  152.         }
  153.         return(avoid_null);
  154.     }
  155.   }
  156.   return(avoid_null);
  157. }
  158.