4 * ----------------------------------------------------------------------
5 * Copyright (c) 1993, 1994, 1995 Matthias Mutz
6 * Copyright (c) 1999 Michael Vanier and the Free Software Foundation
8 * GNU SHOGI is based on GNU CHESS
10 * Copyright (c) 1988, 1989, 1990 John Stanback
11 * Copyright (c) 1992 Free Software Foundation
13 * This file is part of GNU SHOGI.
15 * GNU Shogi is free software; you can redistribute it and/or modify it
16 * under the terms of the GNU General Public License as published by the
17 * Free Software Foundation; either version 3 of the License,
18 * or (at your option) any later version.
20 * GNU Shogi is distributed in the hope that it will be useful, but WITHOUT
21 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
22 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
25 * You should have received a copy of the GNU General Public License along
26 * with GNU Shogi; see the file COPYING. If not, see
27 * <http://www.gnu.org/licenses/>.
28 * ----------------------------------------------------------------------
34 #if defined HAVE_GETTIMEOFDAY
42 /****************************************
43 * A variety of global flags.
44 ****************************************/
47 * If hard_time_limit is nonzero, exceeding the time limit means
51 short hard_time_limit = 1;
52 short barebones = 0; /* Suppress printing of statistics
53 * (mainly for xshogi). */
55 short nolist = 0; /* List the game after exit. */
57 short nolist = 1; /* Don't list the game after exit. */
61 * The default display type can be DISPLAY_RAW, DISPLAY_CURSES,
62 * or DISPLAY_X; the default is DISPLAY_X to make life easier for xshogi.
65 display_t display_type = DISPLAY_X;
67 unsigned int ttbllimit;
69 /* .... MOVE GENERATION VARIABLES AND INITIALIZATIONS .... */
72 #define max(a, b) (((a) < (b))?(b):(a))
73 #define odd(a) ((a) & 1)
76 const small_short piece_of_ptype[NO_PTYPE_PIECES] =
78 pawn, lance, knight, silver, gold, bishop, rook, pbishop, prook, king,
79 pawn, lance, knight, silver, gold
83 const small_short side_of_ptype[NO_PTYPE_PIECES] =
85 black, black, black, black, black, black, black, black, black, black,
86 white, white, white, white, white
90 const small_short psweep[NO_PTYPE_PIECES] =
92 false, true, false, false, false, true, true, true, true, false,
93 false, true, false, false, false
97 const small_short sweep[NO_PIECES] =
99 false, false, true, false, false, false, true, true,
100 false, false, false, false, true, true, false
105 * Determine the minimum number of moves for a piece from
106 * square "f" to square "t". If the piece cannot reach "t",
107 * the count is set to CANNOT_REACH.
110 #define csquare(sq) ((side == black) ? sq : (NO_SQUARES - 1 - sq))
111 #define crow(sq) row(csquare(sq))
112 #define ccol(sq) column(csquare(sq))
115 ptype_distance(short ptyp, short f, short t)
118 short colf, colt, rowf, rowt, dcol, drow;
123 piece = piece_of_ptype[ptyp];
124 side = side_of_ptype[ptyp];
126 dcol = (colt = ccol(t)) - (colf = ccol(f));
127 drow = (rowt = crow(t)) - (rowf = crow(f));
132 if ((dcol != 0) || (drow < 1))
138 if ((dcol != 0) || (drow < 1))
144 if (odd(drow) || (odd(drow / 2) != odd(dcol)))
146 else if ((drow == 0) || ((drow / 2) < abs(dcol)))
154 if (odd(drow) == odd(dcol))
156 return max(abs(drow), abs(dcol));
160 if (abs(dcol) <= drow)
163 return (max(abs(drow), abs(dcol)) + 1);
168 if (odd(drow) == odd(dcol))
169 return (max(abs(drow), abs(dcol)));
171 return (max(abs(drow) + 1, abs(dcol)) + 1);
182 return max(drow, abs(dcol));
184 return (abs(dcol) - drow);
187 if (odd(dcol) != odd(drow))
190 return ((abs(dcol) == abs(drow)) ? 1 : 2);
193 if (odd(dcol) != odd(drow))
195 if ((abs(dcol) <= 1) && (abs(drow) <= 1))
197 else if (abs(abs(dcol) - abs(drow)) == 1)
204 return ((abs(dcol) == abs(drow)) ? 1 : 2);
208 if ((dcol == 0) || (drow == 0))
214 if ((dcol == 0) || (drow == 0))
216 else if ((abs(dcol) == 1) && (abs(drow) == 1))
222 return max(abs(drow), abs(dcol));
225 /* should never occur */
226 return (CANNOT_REACH);
233 distance(short a, short b)
235 return (short)computed_distance(a, b);
239 distance(short a, short b)
242 ? (short)(*distdata)[(int)a][(int)b]
243 : (short)computed_distance(a, b));
248 #ifdef SAVE_PTYPE_DISTDATA
250 piece_distance(short side, short piece, short f, short t)
252 return ((f > NO_SQUARES)
254 : (short)ptype_distance(ptype[side][piece], f, t));
258 piece_distance(short side, short piece, short f, short t)
260 return ((f > NO_SQUARES)
262 : (use_ptype_distdata
263 ? (short)(*ptype_distdata[ptype[side][piece]])[f][t]
264 : (short)ptype_distance(ptype[side][piece], f, t)));
270 Initialize_dist(void)
272 short a, b, d, di, ptyp;
273 #ifndef SAVE_DISTDATA
274 for (a = 0; a < NO_SQUARES; a++)
276 for (b = 0; b < NO_SQUARES; b++)
278 d = abs(column(a) - column(b));
279 di = abs(row(a) - row(b));
280 (*distdata)[a][b] = (small_short)((d > di) ? d : di);
284 #ifndef SAVE_PTYPE_DISTDATA
285 for (ptyp = 0; ptyp < NO_PTYPE_PIECES; ptyp++)
287 for (a = 0; a < NO_SQUARES; a++)
288 for (b = 0; b < NO_SQUARES; b++)
289 (*ptype_distdata[ptyp])[a][b] = ptype_distance(ptyp, a, b);
296 * nextpos[ptype][from-square], nextdir[ptype][from-square] gives vector
297 * of positions reachable from from-square in ppos with ptype such that the
300 * ppos = nextpos[ptype][from-square];
301 * pdir = nextdir[ptype][from-square];
308 * if(color[u] != neutral)
313 * will generate the sequence of all squares reachable from sq.
315 * If the path is blocked u = pdir[sq] will generate the continuation of the
316 * sequence in other directions.
321 * ptype is used to separate black and white pawns, like this; ptyp =
322 * ptype[side][piece] piece can be used directly in nextpos/nextdir when
323 * generating moves for pieces that are not white pawns.
326 const small_short ptype[2][NO_PIECES] =
329 ptype_no_piece, ptype_pawn, ptype_lance, ptype_knight,
330 ptype_silver, ptype_gold, ptype_bishop, ptype_rook,
331 ptype_gold, ptype_gold, ptype_gold, ptype_gold,
332 ptype_pbishop, ptype_prook, ptype_king
335 ptype_no_piece, ptype_wpawn, ptype_wlance, ptype_wknight,
336 ptype_wsilver, ptype_wgold, ptype_bishop, ptype_rook,
337 ptype_wgold, ptype_wgold, ptype_wgold, ptype_wgold,
338 ptype_pbishop, ptype_prook, ptype_king
342 const small_short promoted[NO_PIECES] =
344 no_piece, ppawn, plance, pknight, psilver, gold, pbishop, prook,
345 ppawn, plance, pknight, psilver, pbishop, prook, king
348 const small_short unpromoted[NO_PIECES] =
350 no_piece, pawn, lance, knight, silver, gold, bishop, rook,
351 pawn, lance, knight, silver, bishop, rook, king
354 const small_short is_promoted[NO_PIECES] =
356 false, false, false, false, false, false, false, false,
357 true, true, true, true, true, true, false
360 /* data used to generate nextpos/nextdir */
361 #if !defined SAVE_NEXTPOS
364 const small_short direc[NO_PTYPE_PIECES][8] =
366 { 11, 0, 0, 0, 0, 0, 0, 0 }, /* 0 ptype_pawn */
367 { 11, 0, 0, 0, 0, 0, 0, 0 }, /* 1 ptype_lance */
368 { 21, 23, 0, 0, 0, 0, 0, 0 }, /* 2 ptype_knight */
369 { 10, 11, 12, -12, -10, 0, 0, 0 }, /* 3 ptype_silver */
370 { 10, 11, 12, -1, 1, -11, 0, 0 }, /* 4 ptype_gold */
371 { 10, 12, -12, -10, 0, 0, 0, 0 }, /* 5 ptype_bishop */
372 { 11, -1, 1, -11, 0, 0, 0, 0 }, /* 6 ptype_rook */
373 { 10, 12, -12, -10, 11, -1, 1, -11 }, /* 7 ptype_pbishop */
374 { 11, -1, 1, -11, 10, 12, -12, -10 }, /* 8 ptype_prook */
375 { 10, 11, 12, -1, 1, -12, -11, -10 }, /* 9 ptype_king */
376 { -11, 0, 0, 0, 0, 0, 0, 0 }, /* 10 ptype_wpawn */
377 { -11, 0, 0, 0, 0, 0, 0, 0 }, /* 11 ptype_wlance */
378 { -21, -23, 0, 0, 0, 0, 0, 0 }, /* 12 ptype_wknight */
379 { -10, -11, -12, 12, 10, 0, 0, 0 }, /* 13 ptype_wsilver */
380 { -10, -11, -12, 1, -1, 11, 0, 0 }
381 }; /* 14 ptype_wgold */
384 small_short diagonal(short d)
386 return (abs(d) == (NO_COLS+1) || abs(d) == (NO_COLS+3));
390 static const small_short max_steps[NO_PTYPE_PIECES] =
392 1, 8, 1, 1, 1, 8, 8, 8, 8, 1, 1, 8, 1, 1, 1
396 const small_short nunmap[(NO_COLS + 2)*(NO_ROWS + 4)] =
398 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
399 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
400 -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, -1,
401 -1, 9, 10, 11, 12, 13, 14, 15, 16, 17, -1,
402 -1, 18, 19, 20, 21, 22, 23, 24, 25, 26, -1,
403 -1, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1,
404 -1, 36, 37, 38, 39, 40, 41, 42, 43, 44, -1,
405 -1, 45, 46, 47, 48, 49, 50, 51, 52, 53, -1,
406 -1, 54, 55, 56, 57, 58, 59, 60, 61, 62, -1,
407 -1, 63, 64, 65, 66, 67, 68, 69, 70, 71, -1,
408 -1, 72, 73, 74, 75, 76, 77, 78, 79, 80, -1,
409 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
410 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
414 const small_short inunmap[NO_SQUARES] =
416 23, 24, 25, 26, 27, 28, 29, 30, 31,
417 34, 35, 36, 37, 38, 39, 40, 41, 42,
418 45, 46, 47, 48, 49, 50, 51, 52, 53,
419 56, 57, 58, 59, 60, 61, 62, 63, 64,
420 67, 68, 69, 70, 71, 72, 73, 74, 75,
421 78, 79, 80, 81, 82, 83, 84, 85, 86,
422 89, 90, 91, 92, 93, 94, 95, 96, 97,
423 100, 101, 102, 103, 104, 105, 106, 107, 108,
424 111, 112, 113, 114, 115, 116, 117, 118, 119
428 int InitFlag = false;
431 #if defined SAVE_NEXTPOS
434 next_direction(short ptyp, short *d, short sq)
436 short delta, to, sfrom = inunmap[sq];
444 delta = direc[ptyp][*d];
448 to = nunmap[sfrom + delta];
457 next_position(short ptyp, short *d, short sq, short u)
459 if (*d < 4 && psweep[ptyp])
461 short to = nunmap[inunmap[u] + direc[ptyp][*d]];
464 return next_direction(ptyp, d, sq);
470 return next_direction(ptyp, d, sq);
476 first_direction(short ptyp, short *d, short sq)
479 return next_direction(ptyp, d, sq);
485 * This procedure pre-calculates all moves for every piece from every
486 * square. This data is stored in nextpos/nextdir and used later in the
487 * move generation routines.
491 Initialize_moves(void)
493 short ptyp, po, p0, d, di, s, delta;
494 unsigned char *ppos, *pdir;
498 short fpo = inunmap[0], tpo = 1 + inunmap[NO_SQUARES-1];
500 /* pre-fill nextpos and nextdir with source position, probably so
501 * (color[u] == neutral) stops to match once all moves have been seen
503 for (ptyp = 0; ptyp < NO_PTYPE_PIECES; ptyp++)
505 for (po = 0; po < NO_SQUARES; po++)
507 for (p0 = 0; p0 < NO_SQUARES; p0++)
509 (*nextpos[ptyp])[po][p0] = (unsigned char)po;
510 (*nextdir[ptyp])[po][p0] = (unsigned char)po;
515 for (ptyp = 0; ptyp < NO_PTYPE_PIECES; ptyp++)
517 for (po = fpo; po < tpo; po++)
519 if (nunmap[po] >= (small_short)0)
521 ppos = (*nextpos[ptyp])[nunmap[po]];
522 pdir = (*nextdir[ptyp])[nunmap[po]];
524 /* dest is a function of direction and steps */
525 for (d = 0; d < 8; d++)
527 dest[d][0] = nunmap[po];
528 delta = direc[ptyp][d];
534 for (s = 0; s < max_steps[ptyp]; s++)
539 * break if (off board) or (promoted rooks
540 * wishes to move two steps diagonal) or
541 * (promoted bishops wishes to move two steps
544 if ((nunmap[p0] < (small_short)0)
545 || ((ptyp == ptype_prook)
548 || ((ptyp == ptype_pbishop)
550 && !diagonal(delta)))
553 dest[d][s] = nunmap[p0];
562 * Sort dest in number of steps order; currently no sort
563 * is done due to compatibility with the move generation
564 * order in old gnuchess.
569 for (di = d; s > 0 && di > 0; di--)
571 if (steps[sorted[di - 1]] == 0) /* should be: < s */
572 sorted[di] = sorted[di - 1];
581 * update nextpos/nextdir
585 pdir[p0] = (unsigned char)dest[sorted[0]][0];
587 for (d = 0; d < 8; d++)
589 for (s = 0; s < steps[sorted[d]]; s++)
591 ppos[p0] = (unsigned char)dest[sorted[d]][s];
592 p0 = dest[sorted[d]][s];
595 pdir[p0] = (unsigned char)dest[sorted[d + 1]][0];
598 * else is already initialized
612 * Reset the board and other variables to start a new game.
618 short l, c, p, max_opening_sequence;
619 #ifdef HAVE_GETTIMEOFDAY
622 compptr = oppptr = 0;
624 stage2 = -1; /* the game is not yet started */
625 flag.illegal = flag.mate = flag.post = flag.quit
626 = flag.reverse = flag.bothsides = flag.onemove = flag.force
628 flag.material = flag.coords = flag.hash = flag.easy
629 = flag.beep = flag.rcptr
631 flag.stars = flag.shade = flag.back = flag.musttimeout = false;
636 GenCnt = NodeCnt = et0 = dither = XCmore = 0;
645 MaxSearchDepth = MAXDEPTH - 1;
650 CptrFlag[0] = TesujiFlag[0] = false;
653 GameType[0] = GameType[1] = UNKNOWN;
654 Pscore[0] = Tscore[0] = (SCORE_LIMIT + 3000);
655 opponent = player = black;
658 for (l = 0; l < TREE; l++)
659 Tree[l].f = Tree[l].t = 0;
661 gsrand((unsigned int) 1);
665 for (c = black; c <= white; c++)
667 for (p = pawn; p <= king; p++)
669 for (l = 0; l < NO_SQUARES; l++)
671 (*hashcode)[c][p][l].key
672 = (((unsigned long) urand()));
673 (*hashcode)[c][p][l].key
674 += (((unsigned long) urand()) << 16);
675 (*hashcode)[c][p][l].bd
676 = (((unsigned long) urand()));
677 (*hashcode)[c][p][l].bd
678 += (((unsigned long) urand()) << 16);
679 #if SIZEOF_LONG == 8 /* 64-bit long i.e. 8 bytes */
680 (*hashcode)[c][p][l].key
681 += (((unsigned long) urand()) << 32);
682 (*hashcode)[c][p][l].key
683 += (((unsigned long) urand()) << 48);
684 (*hashcode)[c][p][l].bd
685 += (((unsigned long) urand()) << 32);
686 (*hashcode)[c][p][l].bd
687 += (((unsigned long) urand()) << 48);
693 for (c = black; c <= white; c++)
695 for (p = pawn; p <= king; p++)
697 for (l = 0; l < MAX_CAPTURED; l++)
699 (*drop_hashcode)[c][p][l].key
700 = (((unsigned long) urand()));
701 (*drop_hashcode)[c][p][l].key
702 += (((unsigned long) urand()) << 16);
703 (*drop_hashcode)[c][p][l].bd
704 = (((unsigned long) urand()));
705 (*drop_hashcode)[c][p][l].bd
706 += (((unsigned long) urand()) << 16);
707 #if SIZEOF_LONG == 8 /* 64-bit long i.e. 8 bytes */
708 (*drop_hashcode)[c][p][l].key
709 += (((unsigned long) urand()) << 32);
710 (*drop_hashcode)[c][p][l].key
711 += (((unsigned long) urand()) << 48);
712 (*drop_hashcode)[c][p][l].bd
713 += (((unsigned long) urand()) << 32);
714 (*drop_hashcode)[c][p][l].bd
715 += (((unsigned long) urand()) << 48);
722 for (l = 0; l < NO_SQUARES; l++)
724 board[l] = Stboard[l];
725 color[l] = Stcolor[l];
733 #ifdef HAVE_GETTIMEOFDAY
734 gettimeofday(&tv, NULL);
735 time0 = tv.tv_sec*100 + tv.tv_usec/10000;
737 time0 = time((long *) 0);
740 /* resetting reference time */
741 ElapsedTime(COMPUTE_AND_INIT_MODE);
742 flag.regularstart = true;
752 else if (MaxResponseTime == 0)
755 UpdateDisplay(0, 0, 1, 0);
757 GetOpeningPatterns(&max_opening_sequence);
770 hashbd = hashkey = 0;
777 Initialize_data(void)
789 ShowMessage("datatype 'small_short' is unsigned; "
790 "check gnushogi.h\n");
795 n = sizeof(struct leaf) * (size_t)TREE;
800 sprintf(buffer, "Cannot allocate %ld bytes for search tree",
806 n = sizeof(hashcode_array);
807 hashcode = malloc(n);
811 sprintf(buffer, "Cannot allocate %ld bytes for hashcode", (long)n);
816 n = sizeof(drop_hashcode_array);
817 drop_hashcode = malloc(n);
822 "Cannot allocate %ld bytes for drop_hashcode",
828 n = sizeof(struct GameRec) * (size_t)(MAXMOVES + MAXDEPTH);
829 GameList = malloc(n);
834 "Cannot allocate %ld bytes for game record",
840 #if !defined SAVE_NEXTPOS
841 n = sizeof(next_array);
843 for (i = 0; i < NO_PTYPE_PIECES; i++)
845 nextdir[i] = use_nextpos ? malloc(n) : NULL;
851 sprintf(buffer, "cannot allocate %ld space for nextdir %d",
860 nextpos[i] = use_nextpos ? malloc(n) : NULL;
866 sprintf(buffer, "cannot allocate %ld space for nextpos %d",
881 n = sizeof(value_array);
886 ShowMessage("cannot allocate value space");
890 n = sizeof(fscore_array);
895 ShowMessage("cannot allocate fscore space");
905 sprintf(buffer, "Cannot allocate %ld bytes for history table",
906 (long)sizeof_history);
913 n = sizeof(struct etable) * (size_t)ETABLE;
915 for (i = 0; i < 2; i++)
917 etab[i] = use_etable ? malloc(n) : 0;
921 sprintf(buffer, "Cannot allocate %ld bytes for cache table %ld",
934 n = sizeof(struct hashentry)*(ttblsize + rehash);
936 while (doit && ttblsize > MINTTABLE)
938 ttable[0] = malloc(n); /* FIXME: cast to the correct type. */
939 ttable[1] = ttable[0] ? malloc(n) : NULL;
941 if (!ttable[0] || !ttable[1])
949 ttblsize = ttblsize >> 1;
950 n = sizeof(struct hashentry) * (ttblsize + rehash);
958 if (ttblsize <= MINTTABLE)
965 /* CHECKME: is the precedence here correct? */
966 /* ttbllimit = ttblsize << 1 - ttblsize >> 2; */
967 ttbllimit = (ttblsize << 1) - (ttblsize >> 2);
971 sprintf(buffer, "Cannot allocate %ld bytes for transposition table",
974 ttable[0] = ttable[1] = NULL;
978 #if !defined SAVE_DISTDATA
979 n = sizeof(distdata_array);
980 distdata = malloc(n);
984 ShowMessage("cannot allocate distdata space...");
985 use_distdata = false;
989 #if !defined SAVE_PTYPE_DISTDATA
990 n = sizeof(distdata_array);
992 for (i = 0; i < NO_PTYPE_PIECES; i++)
994 ptype_distdata[i] = use_ptype_distdata ? malloc(n) : 0;
996 if (!ptype_distdata[i])
999 "cannot allocate %ld bytes for ptype_distdata %d...",
1001 use_ptype_distdata = false;
1013 gsrand(starttime = ((unsigned int)time((long *)0))); /* init urand */
1020 if (Initialize_data() != 0)
1023 strcpy(ColorStr[0], "Black");
1024 strcpy(ColorStr[1], "White");
1027 MaxResponseTime = 0;
1050 #if !defined SAVE_NEXTPOS
1068 hashfile = fopen(HASHFILE, RWA_ACC);
1072 fseek(hashfile, 0L, SEEK_END);
1073 filesz = ftell(hashfile) / sizeof(struct fileentry) - 1 - MAXrehash;
1074 hashmask = filesz >> 1;
1075 hashbase = hashmask + 1;
1077 #endif /* HASHFILE */
1094 #endif /* HASHFILE */