| 1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ |
| 2 | * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * |
| 3 | * http://www.gnu.org/software/gnugo/ for more information. * |
| 4 | * * |
| 5 | * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, * |
| 6 | * 2008 and 2009 by the Free Software Foundation. * |
| 7 | * * |
| 8 | * This program is free software; you can redistribute it and/or * |
| 9 | * modify it under the terms of the GNU General Public License as * |
| 10 | * published by the Free Software Foundation - version 3 or * |
| 11 | * (at your option) any later version. * |
| 12 | * * |
| 13 | * This program is distributed in the hope that it will be useful, * |
| 14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of * |
| 15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * |
| 16 | * GNU General Public License in file COPYING for more details. * |
| 17 | * * |
| 18 | * You should have received a copy of the GNU General Public * |
| 19 | * License along with this program; if not, write to the Free * |
| 20 | * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * |
| 21 | * Boston, MA 02111, USA. * |
| 22 | \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ |
| 23 | |
| 24 | #ifndef _HASH_H_ |
| 25 | #define _HASH_H_ |
| 26 | |
| 27 | #include "config.h" |
| 28 | #include <limits.h> |
| 29 | |
| 30 | /* |
| 31 | * This file, together with engine/hash.c implements hashing of go positions |
| 32 | * using a method known as Zobrist hashing. See the Texinfo documentation |
| 33 | * (Reading/Hashing) for more information. |
| 34 | */ |
| 35 | |
| 36 | /* Hash values and the compact board representation should use the |
| 37 | * longest integer type that the platform can handle efficiently. |
| 38 | * Typically this would be a 32 bit integer on a 32 bit platform and a |
| 39 | * 64 bit integer on a 64 bit platform. |
| 40 | * |
| 41 | * Our current assumption is that unsigned long has this |
| 42 | * characteristic. Should it turn out to be false for some platform |
| 43 | * we'll add conditional code to choose some other type. |
| 44 | * |
| 45 | * At the few places in the code where the actual size of these types |
| 46 | * matter, the code should use sizeof(type) to test for this. Notice |
| 47 | * that ISO C guarantees a long to be at least 32 bits. |
| 48 | * |
| 49 | * On (future) platforms with word length 128 bits or more, it might |
| 50 | * be a waste to use more than 64 bit hashvalues, since the decreased |
| 51 | * risk for hash collisions probably isn't worth the increased storage |
| 52 | * cost. |
| 53 | */ |
| 54 | typedef unsigned long Hashvalue; |
| 55 | #define SIZEOF_HASHVALUE SIZEOF_LONG |
| 56 | #define HASHVALUE_PRINT_FORMAT "%0*lx" |
| 57 | |
| 58 | /* for testing: Enables a lot of checks. */ |
| 59 | #define CHECK_HASHING 0 |
| 60 | |
| 61 | /* Dump (almost) all read results. */ |
| 62 | #define TRACE_READ_RESULTS 0 |
| 63 | |
| 64 | /* How many bits should be used at least for hashing? Set this to 32 for |
| 65 | * some memory save and speedup, at the cost of occasional irreproducable |
| 66 | * mistakes (and possibly assertion failures). |
| 67 | * With 64 bits, there should be less than one such mistake in 10^9 games. |
| 68 | * Set this to 96 if this is not safe enough for you. |
| 69 | */ |
| 70 | #define MIN_HASHBITS 64 |
| 71 | |
| 72 | #define NUM_HASHVALUES (1 + (MIN_HASHBITS - 1) / (CHAR_BIT * SIZEOF_HASHVALUE)) |
| 73 | |
| 74 | /* This struct is maintained by the machinery that updates the board |
| 75 | * to provide incremental hashing. Examples: trymove(), play_move(), ... |
| 76 | */ |
| 77 | |
| 78 | typedef struct { |
| 79 | Hashvalue hashval[NUM_HASHVALUES]; |
| 80 | } Hash_data; |
| 81 | |
| 82 | extern Hash_data board_hash; |
| 83 | |
| 84 | Hash_data goal_to_hashvalue(const signed char *goal); |
| 85 | |
| 86 | void hash_init_zobrist_array(Hash_data *array, int size); |
| 87 | void hash_init(void); |
| 88 | #define INIT_ZOBRIST_ARRAY(a) \ |
| 89 | hash_init_zobrist_array(a, (int) (sizeof(a) / sizeof(a[0]))) |
| 90 | |
| 91 | void hashdata_clear(Hash_data *hd); |
| 92 | void hashdata_recalc(Hash_data *hd, Intersection *board, int ko_pos); |
| 93 | void hashdata_invert_ko(Hash_data *hd, int pos); |
| 94 | void hashdata_invert_stone(Hash_data *hd, int pos, int color); |
| 95 | void hashdata_invert_komaster(Hash_data *hd, int komaster); |
| 96 | void hashdata_invert_kom_pos(Hash_data *hd, int kom_pos); |
| 97 | void hashdata_calc_orientation_invariant(Hash_data *hd, Intersection *board, |
| 98 | int ko_pos); |
| 99 | |
| 100 | char *hashdata_to_string(Hash_data *hashdata); |
| 101 | |
| 102 | |
| 103 | |
| 104 | /* ---------------------------------------------------------------- */ |
| 105 | |
| 106 | /* There is no need to involve all bits in the remainder computation |
| 107 | * as long as we only use it to compute a key into a hash table. 32 |
| 108 | * random bits are sufficient to get an even distribution within any |
| 109 | * hashtable of reasonable size. By never using more than 32 bits we |
| 110 | * also reduce the platform dependency of the GNU Go engine. |
| 111 | */ |
| 112 | #define hashdata_remainder(hd, num) \ |
| 113 | (((hd).hashval[0] & 0xffffffffU) % (num)) |
| 114 | |
| 115 | #if NUM_HASHVALUES == 1 |
| 116 | |
| 117 | #define hashdata_is_equal(hd1, hd2) \ |
| 118 | ((hd1).hashval[0] == (hd2).hashval[0]) |
| 119 | |
| 120 | #define hashdata_is_smaller(hd1, hd2) \ |
| 121 | ((hd1).hashval[0] < (hd2).hashval[0]) |
| 122 | |
| 123 | #define hashdata_xor(hd1, hd2) \ |
| 124 | (hd1).hashval[0] ^= (hd2).hashval[0] |
| 125 | |
| 126 | #elif NUM_HASHVALUES == 2 |
| 127 | |
| 128 | #define hashdata_is_equal(hd1, hd2) \ |
| 129 | ((hd1).hashval[0] == (hd2).hashval[0] \ |
| 130 | && (hd1).hashval[1] == (hd2).hashval[1]) |
| 131 | |
| 132 | #define hashdata_is_smaller(hd1, hd2) \ |
| 133 | ((hd1).hashval[0] < (hd2).hashval[0] \ |
| 134 | || ((hd1).hashval[0] == (hd2).hashval[0] \ |
| 135 | && (hd1).hashval[1] < (hd2).hashval[1])) |
| 136 | |
| 137 | #define hashdata_xor(hd1, hd2) \ |
| 138 | do { \ |
| 139 | (hd1).hashval[0] ^= (hd2).hashval[0]; \ |
| 140 | (hd1).hashval[1] ^= (hd2).hashval[1]; \ |
| 141 | } while (0) |
| 142 | |
| 143 | #else |
| 144 | |
| 145 | int hashdata_is_equal_func(Hash_data *hd1, Hash_data *hd2); |
| 146 | int hashdata_is_smaller_func(Hash_data *hd1, Hash_data *hd2); |
| 147 | |
| 148 | #define hashdata_is_equal(hd1, hd2) \ |
| 149 | hashdata_is_equal_func(&(hd1), &(hd2)) |
| 150 | |
| 151 | #define hashdata_is_smaller(hd1, hd2) \ |
| 152 | hashdata_is_smaller_func(&(hd1), &(hd2)) |
| 153 | |
| 154 | #define hashdata_xor(hd1, hd2) \ |
| 155 | do { \ |
| 156 | int i; \ |
| 157 | for (i = 0; i < NUM_HASHVALUES; i++) \ |
| 158 | (hd1).hashval[i] ^= (hd2).hashval[i]; \ |
| 159 | } while (0) |
| 160 | |
| 161 | #endif |
| 162 | |
| 163 | #endif |
| 164 | |
| 165 | |
| 166 | /* |
| 167 | * Local Variables: |
| 168 | * tab-width: 8 |
| 169 | * c-basic-offset: 2 |
| 170 | * End: |
| 171 | */ |