1 /*
2 Sjeng - a chess variants playing program
3 Copyright (C) 2000-2001 Gian-Carlo Pascutto
4 Originally based on Faile, Copyright (c) 2000 Adrien M. Regimbald
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19
20 File: draw.c
21 Purpose: Detect draws
22
23 */
24
25 #include "config.h"
26 #include "sjeng.h"
27 #include "extvars.h"
28 #include "protos.h"
29
is_draw(void)30 bool is_draw (void)
31 {
32 /* GCP: this is straigth from Faile but converted to Sjeng internals */
33
34 /* is_draw () is used to see if a position is a draw. Some notes:
35 * - the 2 repetition trick is attempted first: if we have already seen a
36 * position in the search history (not game history), we haven't found
37 * anything better to do than repeat, and searching the position again would
38 * be a waste of time
39 * - if there is no match on the 2 repetition check, we look for an actual
40 * 3 fold repetition
41 * - we can't check for the 50 move rule here, since the 50 move rule must be
42 * checked at the end of a search node due to mates on the 50th move, yet
43 * we want to check for a draw by repetition before we waste any time
44 * searching the position or generating moves
45 * - is_draw () can be used in both search () and search_root () as the
46 * for loop for the 2 repetition trick will exit immediately at the root */
47
48 int i, repeats = 0, end, start;
49
50 /* Check on the 2 repetition trick. Some notes:
51 * - a position can't possibly have occurred once before if fifty isn't
52 * at least 4
53 * - the end point is picked to look at the least number of positions, ie
54 * if going to the last capture is shorter than looking at the whole search
55 * history, we will do only that much */
56 if (fifty >= 4)
57 {
58 if ((move_number) < (move_number + ply - 1 - fifty))
59 {
60 end = move_number + ply - 1 - fifty;
61 }
62 else
63 {
64 end = move_number;
65 }
66 for (i = (move_number + ply - 3); i >= 0 && i >= end; i -= 2)
67 {
68 if (hash == hash_history[i])
69 {
70 return TRUE;
71 }
72 }
73 }
74
75 /* Check for actual 3 repetition match. Some notes:
76 * - a position can't possibly have occurred twice before if fifty isn't
77 * at least 6
78 * - there is no need for us to consider positions encountered during search,
79 * as if there was a match on any of them, it would have been found above
80 * - we need to adjust the starting point here based on who's turn it is:
81 * if it's the same as at the root, we need to subtract one extra */
82 if (fifty >= 6)
83 {
84 start = move_number - 1 - (ply % 2);
85 end = move_number + ply - 1 - fifty;
86
87 for (i = start; i >= 0 && i >= end; i -= 2)
88 {
89 if (hash == hash_history[i])
90 {
91 repeats++;
92 }
93 if (repeats >= 2)
94 {
95 return TRUE;
96 }
97 }
98 }
99
100 return FALSE;
101
102 };
103