1 #include "chess.h"
2 #include "data.h"
3 /* last modified 08/15/15 */
4 /*
5 *******************************************************************************
6 * *
7 * History() is used to maintain the two killer moves for each ply. The *
8 * most recently used killer is always first in the list. *
9 * *
10 * History() also maintains two counter-moves. These are moves that are *
11 * directly used to refute a specific move at the previous ply, rather than *
12 * just a plain killer that has caused cutoffs previously. *
13 * *
14 * History() finally remembers two moves that were played after a specific *
15 * move at ply-2 (ie the two moves together create some sort of "plan".) *
16 * *
17 * History() also maintains the history counters. Each time a move fails *
18 * high, it's history count is increased, while all other moves that were *
19 * searched will have their counts reduced. The current counter is a *
20 * saturating counter in the range 0 <= N <= 2047. *
21 * *
22 *******************************************************************************
23 */
History(TREE * RESTRICT tree,int ply,int depth,int side,int move,int searched[])24 void History(TREE * RESTRICT tree, int ply, int depth, int side, int move,
25 int searched[]) {
26 int i, index, mindex;
27 /*
28 ************************************************************
29 * *
30 * Now, add this move to the current killer moves if it is *
31 * not already there. If the move is already first in the *
32 * list, leave it there, otherwise move the first one down *
33 * to slot two and insert this move into slot one. *
34 * *
35 * If the best move so far is a capture or a promotion, *
36 * we skip updating the killers (but still update history *
37 * information) since we search good captures first, which *
38 * happens before killers are tried, making capture moves *
39 * useless here. *
40 * *
41 * The update value does not depend on depth. I used a *
42 * function of depth for years, but as I examined more and *
43 * more trees, that seemed to be lacking because it gives *
44 * a really large bias towards moves that work near the *
45 * root, while most of the nodes searched are near the *
46 * tips. One unusual characteristic of this counter is *
47 * that it is a software-based saturating counter. That *
48 * is, it can never exceed 2047, nor can it ever drop *
49 * below zero. *
50 * *
51 ************************************************************
52 */
53 if (!CaptureOrPromote(move)) {
54 if (tree->killers[ply].move1 != move) {
55 tree->killers[ply].move2 = tree->killers[ply].move1;
56 tree->killers[ply].move1 = move;
57 }
58 /*
59 ************************************************************
60 * *
61 * Set the counter-move for the move at the previous ply *
62 * to be this move that caused the fail-high. *
63 * *
64 ************************************************************
65 */
66 if (tree->counter_move[tree->curmv[ply - 1] & 4095].move1 != move) {
67 tree->counter_move[tree->curmv[ply - 1] & 4095].move2 =
68 tree->counter_move[tree->curmv[ply - 1] & 4095].move1;
69 tree->counter_move[tree->curmv[ply - 1] & 4095].move1 = move;
70 }
71 /*
72 ************************************************************
73 * *
74 * Set the move-pair for the move two plies back so that *
75 * if we play that move again, we will follow up with this *
76 * move to continue the "plan". *
77 * *
78 ************************************************************
79 */
80 if (ply > 2) {
81 if (tree->move_pair[tree->curmv[ply - 2] & 4095].move1 != move) {
82 tree->move_pair[tree->curmv[ply - 2] & 4095].move2 =
83 tree->move_pair[tree->curmv[ply - 2] & 4095].move1;
84 tree->move_pair[tree->curmv[ply - 2] & 4095].move1 = move;
85 }
86 }
87 /*
88 ************************************************************
89 * *
90 * Adjust the history counter for the move that caused the *
91 * fail-high, limiting the max value to 2048. *
92 * *
93 ************************************************************
94 */
95 if (depth > 5) {
96 mindex = HistoryIndex(side, move);
97 history[mindex] += (2048 - history[mindex]) >> 5;
98 /*
99 ************************************************************
100 * *
101 * Adjust the history counters for the moves that were *
102 * searched but did not cause a fail-high, limiting the *
103 * min value to 0. *
104 * *
105 ************************************************************
106 */
107 for (i = 1; i <= searched[0]; i++) {
108 index = HistoryIndex(side, searched[i]);
109 if (index != mindex)
110 history[index] -= history[index] >> 5;
111 }
112 }
113 }
114 }
115