1 // Java Fhourstones 3.1 Transposition table logic
2 // (http://www.cwi.nl/~tromp/c4/fhour.html)
3 //
4 // implementation of the well-known game
5 // usually played on a vertical board of 7 columns by 6 rows,
6 // where 2 players take turns in dropping counters in a column.
7 // the first player to get four of his counters
8 // in a horizontal, vertical or diagonal row, wins the game.
9 // if neither player has won after 42 moves, then the game is drawn.
10 //
11 // This software is copyright (c) 1996-2008 by
12 // John Tromp
13 // 600 Route 25A
14 // East Setauket
15 // NY 11733
16 // E-mail: john.tromp@gmail.com
17 //
18 // This notice must not be removed.
19 // This software must not be sold for profit.
20 // You may redistribute if your distributees have the
21 // same rights and restrictions.
22
23 #include "Game.c"
24
25 #define LOCKSIZE 26
26 #define TRANSIZE 8306069
27 // should be a prime no less than about 2^{SIZE1-LOCKSIZE}, e.g.
28 // 4194301,8306069,8388593,15999961,33554393,67108859,134217689,268435399
29
30 #define SYMMREC 10 // symmetry normalize first SYMMREC moves
31 #define UNKNOWN 0
32 #define LOSS 1
33 #define DRAWLOSS 2
34 #define DRAW 3
35 #define DRAWWIN 4
36 #define WIN 5
37 #define LOSSWIN 6
38
39 typedef struct {
40 #if (LOCKSIZE<=32)
41 unsigned biglock:LOCKSIZE;
42 unsigned bigwork:6;
43 unsigned newlock:LOCKSIZE;
44 #else
45 uint64 biglock:LOCKSIZE;
46 unsigned bigwork:6;
47 uint64 newlock:LOCKSIZE;
48 #endif
49 unsigned newscore:3;
50 unsigned bigscore:3;
51 } hashentry;
52
53 unsigned int htindex, lock;
54 hashentry *ht;
55
56 uint64 posed; // counts transtore calls
57
trans_init()58 void trans_init()
59 {
60 ht = (hashentry *)calloc(TRANSIZE, sizeof(hashentry));
61 if (!ht) {
62 printf("Failed to allocate %lu bytes\n", TRANSIZE*sizeof(hashentry));
63 exit(0);
64 }
65 }
66
emptyTT()67 void emptyTT()
68 {
69 int i;
70
71 for (i=0; i<TRANSIZE; i++) {
72 ht[i] = (hashentry){0,0,0,0,0};
73 }
74 posed = 0;
75 }
76
hash()77 void hash()
78 {
79 bitboard htmp, htemp = positioncode();
80 if (nplies < SYMMREC) { // try symmetry recognition by reversing columns
81 bitboard htemp2 = 0;
82 for (htmp=htemp; htmp!=0; htmp>>=H1)
83 htemp2 = htemp2<<H1 | (htmp & COL1);
84 if (htemp2 < htemp)
85 htemp = htemp2;
86 }
87 lock = (unsigned int)(SIZE1>LOCKSIZE ? htemp >> (SIZE1-LOCKSIZE) : htemp);
88 htindex = (unsigned int)(htemp % TRANSIZE);
89 }
90
transpose()91 int transpose()
92 {
93 hashentry he;
94
95 hash();
96 he = ht[htindex];
97 if (he.biglock == lock)
98 return he.bigscore;
99 if (he.newlock == lock)
100 return he.newscore;
101 return UNKNOWN;
102 }
103
transtore(int x,unsigned int lock,int score,int work)104 void transtore(int x, unsigned int lock, int score, int work)
105 {
106 hashentry he;
107
108 posed++;
109 he = ht[x];
110 if (he.biglock == lock || work >= he.bigwork) {
111 he.biglock = lock;
112 he.bigscore = score;
113 he.bigwork = work;
114 } else {
115 he.newlock = lock;
116 he.newscore = score;
117 }
118 ht[x] = he;
119 }
120
htstat()121 void htstat() /* some statistics on hash table performance */
122 {
123 int total, i;
124 int typecnt[8]; /* bound type stats */
125 hashentry he;
126
127 for (i=0; i<8; i++)
128 typecnt[i] = 0;
129 for (i=0; i<TRANSIZE; i++) {
130 he = ht[i];
131 if (he.biglock != 0)
132 typecnt[he.bigscore]++;
133 if (he.newlock != 0)
134 typecnt[he.newscore]++;
135 }
136 for (total=0,i=LOSS; i<=WIN; i++)
137 total += typecnt[i];
138 if (total > 0) {
139 printf("- %5.3f < %5.3f = %5.3f > %5.3f + %5.3f\n",
140 typecnt[LOSS]/(double)total, typecnt[DRAWLOSS]/(double)total,
141 typecnt[DRAW]/(double)total, typecnt[DRAWWIN]/(double)total,
142 typecnt[WIN]/(double)total);
143 }
144 }
145