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 * ----------------------------------------------------------------------
35 /* constants and pattern_data are generated by "pat2inc" */
36 #include "pattern.inc"
38 struct Pattern_rec Pattern[MAX_PATTERN];
39 struct OpeningSequence_rec OpeningSequence[MAX_OPENING_SEQUENCE];
41 small_short pattern_data[MAX_PATTERN_DATA];
45 NameOfOpeningValue (short i, char *name)
49 strcpy(name, "CASTLE_?_?");
53 strcpy(name, "ATTACK_?_?");
98 GetOpeningPatterns (short *max_opening_sequence)
107 OpeningSequence[os].opening_type = pattern_data[pindex++];
108 OpeningSequence[os].first_pattern[0] = p;
110 for (i = 1; i < MAX_SEQUENCE; i++)
111 OpeningSequence[os].first_pattern[i] = END_OF_PATTERNS;
115 Pattern[p].reachedGameCnt[black] = MAXMOVES;
116 Pattern[p].reachedGameCnt[white] = MAXMOVES;
117 Pattern[p].first_link = pindex;
119 while (pattern_data[pindex] != END_OF_LINKS)
123 Pattern[p].first_field = pindex;
125 while (pattern_data[pindex] != END_OF_FIELDS)
129 if (pattern_data[pindex] != END_OF_PATTERNS)
130 Pattern[p].next_pattern = p + 1;
132 Pattern[p].next_pattern = END_OF_PATTERNS;
136 while (pattern_data[pindex] != END_OF_PATTERNS);
141 while (pattern_data[pindex] != END_OF_SEQUENCES);
143 *max_opening_sequence = os;
149 ShowOpeningPatterns (short max_opening_sequence)
153 for (os = 0; os < max_opening_sequence; os++)
156 NameOfOpeningValue(OpeningSequence[os].opening_type, name);
157 printf("Opening Type: %s\n", name);
159 for (p = OpeningSequence[os].first_pattern[0], n = 0;
160 p != END_OF_PATTERNS;
161 p = Pattern[p].next_pattern, n++)
163 printf("Pattern %d (%d) with links ", p, n);
165 for (i = Pattern[p].first_link;
166 pattern_data[i] != END_OF_LINKS;
169 printf("%d ", pattern_data[i]);
173 DisplayPattern(stdout, Pattern[p].first_field);
181 set_field (short i, struct PatternField *field)
183 field->piece = pattern_data[i];
184 field->square = pattern_data[i+1];
186 if (field->square < 0)
188 field->square = -(field->square);
200 * piece_to_pattern_distance (side, piece, pside, pattern)
202 * Determine the minimum number of moves from the current position to a
203 * specific pattern for a specific piece. Consider the "side" piece of the
204 * pattern. The pattern should match for "pside".
208 piece_to_pattern_distance(short side, short piece,
209 short pside, short pattern)
211 short nP, P[4], nB, B[4]; /* at most 4 pieces of same kind */
212 short i, j, r, dd, occupied, mindd, c[4], d[4];
213 /* a "side" patternfield must match a "c1" piece on board: */
214 short c1 = side ^ pside;
217 * If pside == white, a black piece in the pattern should match a white
218 * piece on board, and vice versa. Furthermore, if pside == white,
219 * reversed pattern should match board.
222 /* special pawn handling */
226 mindd = occupied = 0;
228 for (i = Pattern[pattern].first_field;
229 pattern_data[i] != END_OF_FIELDS;
232 struct PatternField field;
233 set_field(i, &field);
235 if ((field.side == side) && (field.piece == pawn))
237 short t = field.square;
238 short pcol = column(t);
241 if (PawnCnt[c1][(side == c1) ? pcol : (8 - pcol)])
243 /* there is a pawn on the column */
244 for (j = 0; j <= PieceCnt[c1]; j++)
246 short sq = (short)PieceList[c1][j];
248 if (board[sq] == pawn)
251 sq = NO_SQUARES - 1 - sq;
253 if (column(sq) == pcol)
255 dd = piece_distance (side, pawn, sq, t);
257 printf("update %d pawn "
258 "from %d to %d is %d\n",
268 /* there is no pawn on the column; drop possible? */
269 if (Captured[c1][pawn])
273 printf("update %d pawn drop to %d is %d\n",
281 /* Increment distance if pattern field is occupied */
291 psq = (NO_SQUARES - 1 - t);
295 if ((color[psq] == pc) && (board[psq] != pawn))
298 printf("square %d is occupied\n", psq);
312 return mindd + occupied;
316 * Determine list of "side" "piece"s in pattern.
319 for (occupied = nP = 0, i = Pattern[pattern].first_field;
320 pattern_data[i] != END_OF_FIELDS;
323 struct PatternField field;
324 set_field(i, &field);
326 if ((field.side == side) && (field.piece == piece))
329 P[nP] = field.square;
331 printf("pattern %d piece %d on square %d\n", side, piece, P[nP]);
335 /* Increment distance if pattern field is occupied */
343 psq = NO_SQUARES - 1 - field.square;
347 if ((color[psq] == pc) && (board[psq] != field.piece))
350 printf("square %d is occupied\n", psq);
361 printf("finding in pattern %d pieces %d of side %d\n", nP, piece, side);
365 * Determine list of "side ^ pside" "piece"s captured or on board.
368 for (nB = 0; nB < Captured[c1][piece]; nB++)
369 B[nB] = NO_SQUARES + piece;
371 for (i = 0; i <= PieceCnt[c1]; i++)
373 short sq = PieceList[c1][i];
375 if (board[sq] == piece)
377 B[nB] = (pside == black) ? sq : (NO_SQUARES - 1 - sq);
379 printf("%d piece %d on square %d\n", side, piece, B[nB]);
386 printf("found on board %d pieces %d of side %d\n", nB, piece, side);
394 /* Determine best assignment from board piece to pattern piece */
398 mindd = CANNOT_REACH;
400 while ((r >= 0) && (mindd != 0))
409 for (i = 0; i < r; i++)
417 d[r] = piece_distance (side, piece, B[c[r]], P[r]);
419 printf("update d[%d] from %d to %d is %d\n",
420 r, B[c[r]], P[r], d[r]);
430 for (dd = i = 0; i < nP; i++)
433 if ((dd < mindd) || (mindd < 0))
437 printf("update min %d\n", mindd);
455 return (mindd + occupied);
462 * pattern_distance (pside, pattern)
464 * Determine the minimum number of moves for the pieces from
465 * the current position to reach a pattern.
466 * The result is CANNOT_REACH, if there is no possible sequence
472 pattern_distance (short pside, short pattern)
474 short side, piece, d, n;
477 printf("\nchecking pattern %d for pside=%d\n\n", pattern, pside);
480 for (n = side = 0; side <= 1 && n >= 0; side++)
482 for (piece = pawn; piece <= king; piece++)
484 d = piece_to_pattern_distance (side, piece, pside, pattern);
499 printf("\ndistance to pattern is %d\n\n", n);
508 * board_to_pattern_distance(pside, osequence, pmplty, GameCnt)
510 * Determine the maximal difference of the number of moves from the pattern
511 * to the initial position and to the current position.
512 * Differences are weighted, i.e. the more closer a position is to a pattern
513 * the more valuable is a move towards the pattern.
514 * Patterns, which are at least "pmplty" halfmoves away, are not counted.
518 board_to_pattern_distance
519 (short pside, short osequence, short pmplty, short GameCnt)
521 short i, d, dist, diff, weighted_diff;
522 short maxdiff = 0, max_weighted_diff = 0;
525 for (i = 0; i < MAX_SEQUENCE; i++)
527 for (pattern = OpeningSequence[osequence].first_pattern[i];
528 pattern != END_OF_PATTERNS;
529 pattern = Pattern[pattern].next_pattern)
531 if ((d = Pattern[pattern].distance[pside]) >= 0)
535 dist = pattern_distance (pside, pattern);
539 * "dist" is the distance of the current board
540 * position to the pattern. "d - dist" is the
541 * difference between the current distance and the
542 * initial distance. Compute "diff" as the weighted
546 /* try to reach the nearest pattern */
547 weighted_diff = (diff = (d - dist)) * (pmplty - d);
549 if (weighted_diff > max_weighted_diff)
554 maxdiff = weighted_diff;
556 max_weighted_diff = weighted_diff;
560 * A reached pattern should not be considered in
561 * the future (if GameCnt >= 0)
564 if (dist == 0 && GameCnt >= 0)
565 Pattern[pattern].reachedGameCnt[pside] = GameCnt;
579 DisplayPattern (FILE *fd, short n)
581 small_short pboard[NO_SQUARES], pcolor[NO_SQUARES];
584 for (sq = 0; sq < NO_SQUARES; sq++)
586 pboard[sq] = no_piece;
587 pcolor[sq] = neutral;
590 for (i = n; pattern_data[i] != END_OF_FIELDS; i += 2)
592 struct PatternField field;
593 set_field(i, &field);
594 pboard[field.square] = field.piece;
595 pcolor[field.square] = field.side;
598 for (r = NO_ROWS - 1; r >= 0; r--)
600 for (c = 0; c < NO_COLS; c++)
608 fprintf(fd, "%c%c", is_promoted[i] ? '+' : ' ',
609 pcolor[sq] ? pxx[i] : qxx[i]);
622 VisitReachable (int pside, short osequence, int k, int n, int remove)
627 /* Adjust to sequence pattern n */
628 for (i = 0, pattern = OpeningSequence[osequence].first_pattern[k];
631 pattern = Pattern[pattern].next_pattern;
634 /* do not perform visited link twice */
635 if (Pattern[pattern].visited)
641 Pattern[pattern].visited = true;
644 /* Declare links unreachable */
645 for (j = Pattern[pattern].first_link;
646 pattern_data[j] != END_OF_LINKS; j++)
648 VisitReachable(pside, osequence, k, pattern_data[j], remove);
651 /* Declare unreachable */
652 if (remove && Pattern[pattern].distance[pside] >= 0)
654 Pattern[pattern].distance[pside] = IS_SUCCESSOR;
659 /* simplified matching for opening type names */
661 #define match_char(a, b) \
662 (a == b || (a == '*' && b != 'U') || (b == '*' && a != 'U'))
664 #define match_name(a, b, l) \
665 (l > 8 && match_char(a[0], b[0]) && match_char(a[7], b[7]) \
666 && match_char(a[9], b[9]))
670 locate_opening_sequence(short pside, char *s, short GameCnt)
672 short i, j, k, os, d;
674 short check_visited[MAX_SEQUENCE];
675 char name[MAX_NAME], name2[MAX_NAME];
678 * Look for opening pattern name in the list of opening patterns.
683 for (i = 1, os = 0; os < MAX_OPENING_SEQUENCE; os++)
685 /* locate matching opening type name */
686 NameOfOpeningValue(OpeningSequence[os].opening_type, name);
688 if (match_name(s, name, l))
690 /* locate successor matching names */
691 for (k = os + 1; k < MAX_OPENING_SEQUENCE; k++)
693 NameOfOpeningValue(OpeningSequence[k].opening_type, name2);
695 if (match_name(s, name2, l))
697 OpeningSequence[os].first_pattern[i++]
698 = OpeningSequence[k].first_pattern[0];
706 if (os >= MAX_OPENING_SEQUENCE)
708 return END_OF_SEQUENCES;
712 for (; i < MAX_SEQUENCE;
713 OpeningSequence[os].first_pattern[i++] = END_OF_PATTERNS);
717 * Determine patterns which can be reached from the current
718 * board position. Only patterns which can be reached will be
719 * checked in the following search.
722 for (i = 0; i < MAX_SEQUENCE; i++)
724 check_visited[i] = false;
726 for (k = OpeningSequence[os].first_pattern[i];
727 k != END_OF_PATTERNS;
728 k = Pattern[k].next_pattern)
730 Pattern[k].visited = false;
734 for (i = 0; i < MAX_SEQUENCE; i++)
736 for (k = OpeningSequence[os].first_pattern[i];
737 k != END_OF_PATTERNS;
738 k = Pattern[k].next_pattern)
740 Pattern[k].distance[pside] = pattern_distance(pside, k);
742 /* Actually reached patterns need not to be observed. */
743 if (Pattern[k].distance[pside] == 0)
745 Pattern[k].distance[pside] = CANNOT_REACH;
746 check_visited[i] = Pattern[k].visited = true;
748 for (j = Pattern[k].first_link;
749 pattern_data[j] != END_OF_LINKS; j++)
751 VisitReachable(pside, os, i, pattern_data[j], false);
754 else if ((GameCnt >= 0)
755 && (GameCnt >= Pattern[k].reachedGameCnt[pside]))
757 Pattern[k].distance[pside] = IS_REACHED;
760 if (Pattern[k].reachedGameCnt[pside] >= GameCnt)
761 Pattern[k].reachedGameCnt[pside] = MAXMOVES;
766 * Remove reachable patterns from search, which are successors of
767 * reachable patterns. So, only the next pattern of a pattern sequence
771 for (i = 0; i < MAX_SEQUENCE; i++)
773 for (k = OpeningSequence[os].first_pattern[i];
774 k != END_OF_PATTERNS;
775 k = Pattern[k].next_pattern)
777 if (check_visited[i] && !Pattern[k].visited)
778 Pattern[k].distance[pside] = NOT_TO_REACH;
780 Pattern[k].visited = false;
784 for (i = 0; i < MAX_SEQUENCE; i++)
786 for (k = OpeningSequence[os].first_pattern[i];
787 k != END_OF_PATTERNS;
788 k = Pattern[k].next_pattern)
790 if ((d = Pattern[k].distance[pside]) >= 0)
792 for (j = Pattern[k].first_link;
793 pattern_data[j] != END_OF_LINKS; j++)
795 VisitReachable(pside, os, i, pattern_data[j], true);
802 * Look to see whether there is still a reachable pattern.
805 for (i = 0; i < MAX_SEQUENCE; i++)
807 for (k = OpeningSequence[os].first_pattern[i];
808 k != END_OF_PATTERNS;
809 k = Pattern[k].next_pattern)
811 if ((d = Pattern[k].distance[pside]) >= 0)
816 return END_OF_SEQUENCES;
823 update_advance_bonus (short pside, short os)
825 struct PatternField field;
828 for (j = 0; j < MAX_SEQUENCE; j++)
830 for (k = OpeningSequence[os].first_pattern[j];
831 k != END_OF_PATTERNS;
832 k = Pattern[k].next_pattern)
834 if ((d = Pattern[k].distance[pside]) >= 0)
836 for (i = Pattern[k].first_field;
837 pattern_data[i] != END_OF_FIELDS; i += 2)
839 set_field(i, &field);
840 if (field.side == black)
842 short square = (pside == black)
844 : NO_SQUARES - 1 - field.square;
846 (*Mpiece[field.piece])[pside][square]
847 += ADVNCM[field.piece];