4 * ----------------------------------------------------------------------
5 * Copyright (c) 1993, 1994, 1995 Matthias Mutz
6 * Copyright (c) 1999 Michael Vanier and the Free Software Foundation
7 * Copyright (c) 2008, 2013, 2014 Yann Dirson and the Free Software Foundation
9 * GNU SHOGI is based on GNU CHESS
11 * Copyright (c) 1988, 1989, 1990 John Stanback
12 * Copyright (c) 1992 Free Software Foundation
14 * This file is part of GNU SHOGI.
16 * GNU Shogi is free software; you can redistribute it and/or modify it
17 * under the terms of the GNU General Public License as published by the
18 * Free Software Foundation; either version 3 of the License,
19 * or (at your option) any later version.
21 * GNU Shogi is distributed in the hope that it will be useful, but WITHOUT
22 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
23 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
26 * You should have received a copy of the GNU General Public License along
27 * with GNU Shogi; see the file COPYING. If not, see
28 * <http://www.gnu.org/licenses/>.
29 * ----------------------------------------------------------------------
36 /* "pat2inc" generates constants and pattern_data */
37 #include "pattern.inc"
39 struct Pattern_rec Pattern[MAX_PATTERN];
40 struct OpeningSequence_rec OpeningSequence[MAX_OPENING_SEQUENCE];
42 small_short pattern_data[MAX_PATTERN_DATA];
46 NameOfOpeningValue (short i, char *name)
50 strcpy(name, "CASTLE_?_?");
54 strcpy(name, "ATTACK_?_?");
99 GetOpeningPatterns (short *max_opening_sequence)
108 OpeningSequence[os].opening_type = pattern_data[pindex++];
109 OpeningSequence[os].first_pattern[0] = p;
111 for (i = 1; i < MAX_SEQUENCE; i++)
112 OpeningSequence[os].first_pattern[i] = END_OF_PATTERNS;
116 Pattern[p].reachedGameCnt[black] = MAXMOVES;
117 Pattern[p].reachedGameCnt[white] = MAXMOVES;
118 Pattern[p].first_link = pindex;
120 while (pattern_data[pindex] != END_OF_LINKS)
124 Pattern[p].first_field = pindex;
126 while (pattern_data[pindex] != END_OF_FIELDS)
130 if (pattern_data[pindex] != END_OF_PATTERNS)
131 Pattern[p].next_pattern = p + 1;
133 Pattern[p].next_pattern = END_OF_PATTERNS;
137 while (pattern_data[pindex] != END_OF_PATTERNS);
142 while (pattern_data[pindex] != END_OF_SEQUENCES);
144 *max_opening_sequence = os;
150 ShowOpeningPatterns (short max_opening_sequence)
154 for (os = 0; os < max_opening_sequence; os++)
157 NameOfOpeningValue(OpeningSequence[os].opening_type, name);
158 printf("Opening Type: %s\n", name);
160 for (p = OpeningSequence[os].first_pattern[0], n = 0;
161 p != END_OF_PATTERNS;
162 p = Pattern[p].next_pattern, n++)
164 printf("Pattern %d (%d) with links ", p, n);
166 for (i = Pattern[p].first_link;
167 pattern_data[i] != END_OF_LINKS;
170 printf("%d ", pattern_data[i]);
174 DisplayPattern(stdout, Pattern[p].first_field);
182 set_field (short i, struct PatternField *field)
184 field->piece = pattern_data[i];
185 field->square = pattern_data[i+1];
187 if (field->square < 0)
189 field->square = -(field->square);
201 * piece_to_pattern_distance (side, piece, pside, pattern)
203 * Determine the minimum number of moves from the current position to a
204 * specific pattern for a specific piece. Consider the "side" piece of the
205 * pattern. The pattern should match for "pside".
209 piece_to_pattern_distance(short side, short piece,
210 short pside, short pattern)
212 short nP, P[4], nB, B[4]; /* at most 4 pieces of same kind */
213 short i, j, r, dd, occupied, mindd, c[4], d[4];
214 /* a "side" patternfield must match a "c1" piece on board: */
215 short c1 = side ^ pside;
218 * If pside == white, a black piece in the pattern should match a white
219 * piece on board, and vice versa. Furthermore, if pside == white,
220 * reversed pattern should match board.
223 /* special pawn handling */
227 mindd = occupied = 0;
229 for (i = Pattern[pattern].first_field;
230 pattern_data[i] != END_OF_FIELDS;
233 struct PatternField field;
234 set_field(i, &field);
236 if ((field.side == side) && (field.piece == pawn))
238 short t = field.square;
239 short pcol = column(t);
242 if (PawnCnt[c1][(side == c1) ? pcol : (8 - pcol)])
244 /* there is a pawn on the column */
245 for (j = 0; j <= PieceCnt[c1]; j++)
247 short sq = (short)PieceList[c1][j];
249 if (board[sq] == pawn)
252 sq = NO_SQUARES - 1 - sq;
254 if (column(sq) == pcol)
256 dd = piece_distance (side, pawn, sq, t);
258 printf("update %d pawn "
259 "from %d to %d is %d\n",
269 /* there is no pawn on the column; drop possible? */
270 if (Captured[c1][pawn])
274 printf("update %d pawn drop to %d is %d\n",
282 /* Increment distance if pattern field is occupied */
292 psq = (NO_SQUARES - 1 - t);
296 if ((color[psq] == pc) && (board[psq] != pawn))
299 printf("square %d is occupied\n", psq);
313 return mindd + occupied;
317 * Determine list of "side" "piece"s in pattern.
320 for (occupied = nP = 0, i = Pattern[pattern].first_field;
321 pattern_data[i] != END_OF_FIELDS;
324 struct PatternField field;
325 set_field(i, &field);
327 if ((field.side == side) && (field.piece == piece))
330 P[nP] = field.square;
332 printf("pattern %d piece %d on square %d\n", side, piece, P[nP]);
336 /* Increment distance if pattern field is occupied */
344 psq = NO_SQUARES - 1 - field.square;
348 if ((color[psq] == pc) && (board[psq] != field.piece))
351 printf("square %d is occupied\n", psq);
362 printf("finding in pattern %d pieces %d of side %d\n", nP, piece, side);
366 * Determine list of "side ^ pside" "piece"s captured or on board.
369 for (nB = 0; nB < Captured[c1][piece]; nB++)
370 B[nB] = NO_SQUARES + piece;
372 for (i = 0; i <= PieceCnt[c1]; i++)
374 short sq = PieceList[c1][i];
376 if (board[sq] == piece)
378 B[nB] = (pside == black) ? sq : (NO_SQUARES - 1 - sq);
380 printf("%d piece %d on square %d\n", side, piece, B[nB]);
387 printf("found on board %d pieces %d of side %d\n", nB, piece, side);
395 /* Determine best assignment from board piece to pattern piece */
399 mindd = CANNOT_REACH;
401 while ((r >= 0) && (mindd != 0))
410 for (i = 0; i < r; i++)
418 d[r] = piece_distance (side, piece, B[c[r]], P[r]);
420 printf("update d[%d] from %d to %d is %d\n",
421 r, B[c[r]], P[r], d[r]);
431 for (dd = i = 0; i < nP; i++)
434 if ((dd < mindd) || (mindd < 0))
438 printf("update min %d\n", mindd);
456 return (mindd + occupied);
463 * pattern_distance (pside, pattern)
465 * Determine the minimum number of moves for the pieces from
466 * the current position to reach a pattern.
467 * The result is CANNOT_REACH, if there is no possible sequence
473 pattern_distance (short pside, short pattern)
475 short side, piece, d, n;
478 printf("\nchecking pattern %d for pside=%d\n\n", pattern, pside);
481 for (n = side = 0; side <= 1 && n >= 0; side++)
483 for (piece = pawn; piece <= king; piece++)
485 d = piece_to_pattern_distance (side, piece, pside, pattern);
500 printf("\ndistance to pattern is %d\n\n", n);
509 * board_to_pattern_distance(pside, osequence, pmplty, GameCnt)
511 * Determine the maximal difference of the number of moves from the pattern
512 * to the initial position and to the current position.
513 * Differences are weighted, i.e. the more closer a position is to a pattern
514 * the more valuable is a move towards the pattern.
515 * Patterns, which are at least "pmplty" halfmoves away, are not counted.
519 board_to_pattern_distance
520 (short pside, short osequence, short pmplty, short GameCnt)
522 short i, d, dist, diff, weighted_diff;
523 short maxdiff = 0, max_weighted_diff = 0;
526 for (i = 0; i < MAX_SEQUENCE; i++)
528 for (pattern = OpeningSequence[osequence].first_pattern[i];
529 pattern != END_OF_PATTERNS;
530 pattern = Pattern[pattern].next_pattern)
532 if ((d = Pattern[pattern].distance[pside]) >= 0)
536 dist = pattern_distance (pside, pattern);
540 * "dist" is the distance of the current board
541 * position to the pattern. "d - dist" is the
542 * difference between the current distance and the
543 * initial distance. Compute "diff" as the weighted
547 /* try to reach the nearest pattern */
548 weighted_diff = (diff = (d - dist)) * (pmplty - d);
550 if (weighted_diff > max_weighted_diff)
555 maxdiff = weighted_diff;
557 max_weighted_diff = weighted_diff;
561 * A reached pattern should not be considered in
562 * the future (if GameCnt >= 0)
565 if (dist == 0 && GameCnt >= 0)
566 Pattern[pattern].reachedGameCnt[pside] = GameCnt;
580 DisplayPattern (FILE *fd, short n)
582 small_short pboard[NO_SQUARES], pcolor[NO_SQUARES];
585 for (sq = 0; sq < NO_SQUARES; sq++)
587 pboard[sq] = no_piece;
588 pcolor[sq] = neutral;
591 for (i = n; pattern_data[i] != END_OF_FIELDS; i += 2)
593 struct PatternField field;
594 set_field(i, &field);
595 pboard[field.square] = field.piece;
596 pcolor[field.square] = field.side;
599 for (r = NO_ROWS - 1; r >= 0; r--)
601 for (c = 0; c < NO_COLS; c++)
609 fprintf(fd, "%c%c", is_promoted[i] ? '+' : ' ',
610 pcolor[sq] ? pxx[i] : qxx[i]);
623 VisitReachable (int pside, short osequence, int k, int n, int remove)
628 /* Adjust to sequence pattern n */
629 for (i = 0, pattern = OpeningSequence[osequence].first_pattern[k];
632 pattern = Pattern[pattern].next_pattern;
635 /* do not perform visited link twice */
636 if (Pattern[pattern].visited)
642 Pattern[pattern].visited = true;
645 /* Declare links unreachable */
646 for (j = Pattern[pattern].first_link;
647 pattern_data[j] != END_OF_LINKS; j++)
649 VisitReachable(pside, osequence, k, pattern_data[j], remove);
652 /* Declare unreachable */
653 if (remove && Pattern[pattern].distance[pside] >= 0)
655 Pattern[pattern].distance[pside] = IS_SUCCESSOR;
660 /* simplified matching for opening type names */
662 #define match_char(a, b) \
663 (a == b || (a == '*' && b != 'U') || (b == '*' && a != 'U'))
665 #define match_name(a, b, l) \
666 (l > 8 && match_char(a[0], b[0]) && match_char(a[7], b[7]) \
667 && match_char(a[9], b[9]))
671 locate_opening_sequence(short pside, char *s, short GameCnt)
673 short i, j, k, os, d;
675 short check_visited[MAX_SEQUENCE];
676 char name[MAX_NAME], name2[MAX_NAME];
679 * Look for opening pattern name in the list of opening patterns.
684 for (i = 1, os = 0; os < MAX_OPENING_SEQUENCE; os++)
686 /* locate matching opening type name */
687 NameOfOpeningValue(OpeningSequence[os].opening_type, name);
689 if (match_name(s, name, l))
691 /* locate successor matching names */
692 for (k = os + 1; k < MAX_OPENING_SEQUENCE; k++)
694 NameOfOpeningValue(OpeningSequence[k].opening_type, name2);
696 if (match_name(s, name2, l))
698 OpeningSequence[os].first_pattern[i++]
699 = OpeningSequence[k].first_pattern[0];
707 if (os >= MAX_OPENING_SEQUENCE)
709 return END_OF_SEQUENCES;
713 for (; i < MAX_SEQUENCE;
714 OpeningSequence[os].first_pattern[i++] = END_OF_PATTERNS);
718 * Determine patterns which can be reached from the current
719 * board position. Only patterns which can be reached will be
720 * checked in the following search.
723 for (i = 0; i < MAX_SEQUENCE; i++)
725 check_visited[i] = false;
727 for (k = OpeningSequence[os].first_pattern[i];
728 k != END_OF_PATTERNS;
729 k = Pattern[k].next_pattern)
731 Pattern[k].visited = false;
735 for (i = 0; i < MAX_SEQUENCE; i++)
737 for (k = OpeningSequence[os].first_pattern[i];
738 k != END_OF_PATTERNS;
739 k = Pattern[k].next_pattern)
741 Pattern[k].distance[pside] = pattern_distance(pside, k);
743 /* Actually reached patterns need not to be observed. */
744 if (Pattern[k].distance[pside] == 0)
746 Pattern[k].distance[pside] = CANNOT_REACH;
747 check_visited[i] = Pattern[k].visited = true;
749 for (j = Pattern[k].first_link;
750 pattern_data[j] != END_OF_LINKS; j++)
752 VisitReachable(pside, os, i, pattern_data[j], false);
755 else if ((GameCnt >= 0)
756 && (GameCnt >= Pattern[k].reachedGameCnt[pside]))
758 Pattern[k].distance[pside] = IS_REACHED;
761 if (Pattern[k].reachedGameCnt[pside] >= GameCnt)
762 Pattern[k].reachedGameCnt[pside] = MAXMOVES;
767 * Remove reachable patterns from search, which are successors of
768 * reachable patterns. So, only the next pattern of a pattern sequence
772 for (i = 0; i < MAX_SEQUENCE; i++)
774 for (k = OpeningSequence[os].first_pattern[i];
775 k != END_OF_PATTERNS;
776 k = Pattern[k].next_pattern)
778 if (check_visited[i] && !Pattern[k].visited)
779 Pattern[k].distance[pside] = NOT_TO_REACH;
781 Pattern[k].visited = false;
785 for (i = 0; i < MAX_SEQUENCE; i++)
787 for (k = OpeningSequence[os].first_pattern[i];
788 k != END_OF_PATTERNS;
789 k = Pattern[k].next_pattern)
791 if ((d = Pattern[k].distance[pside]) >= 0)
793 for (j = Pattern[k].first_link;
794 pattern_data[j] != END_OF_LINKS; j++)
796 VisitReachable(pside, os, i, pattern_data[j], true);
803 * Look to see whether there is still a reachable pattern.
806 for (i = 0; i < MAX_SEQUENCE; i++)
808 for (k = OpeningSequence[os].first_pattern[i];
809 k != END_OF_PATTERNS;
810 k = Pattern[k].next_pattern)
812 if ((d = Pattern[k].distance[pside]) >= 0)
817 return END_OF_SEQUENCES;
824 update_advance_bonus (short pside, short os)
826 struct PatternField field;
829 for (j = 0; j < MAX_SEQUENCE; j++)
831 for (k = OpeningSequence[os].first_pattern[j];
832 k != END_OF_PATTERNS;
833 k = Pattern[k].next_pattern)
835 if ((d = Pattern[k].distance[pside]) >= 0)
837 for (i = Pattern[k].first_field;
838 pattern_data[i] != END_OF_FIELDS; i += 2)
840 set_field(i, &field);
841 if (field.side == black)
843 short square = (pside == black)
845 : NO_SQUARES - 1 - field.square;
847 (*Mpiece[field.piece])[pside][square]
848 += ADVNCM[field.piece];