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 */
38 # include "gnushogi-pattern.inc"
40 # include "gnuminishogi-pattern.inc"
43 struct Pattern_rec Pattern[MAX_PATTERN];
44 struct OpeningSequence_rec OpeningSequence[MAX_OPENING_SEQUENCE];
46 small_short pattern_data[MAX_PATTERN_DATA];
50 NameOfOpeningValue (short i, char *name)
54 strcpy(name, "CASTLE_?_?");
58 strcpy(name, "ATTACK_?_?");
103 GetOpeningPatterns (short *max_opening_sequence)
112 OpeningSequence[os].opening_type = pattern_data[pindex++];
113 OpeningSequence[os].first_pattern[0] = p;
115 for (i = 1; i < MAX_SEQUENCE; i++)
116 OpeningSequence[os].first_pattern[i] = END_OF_PATTERNS;
120 Pattern[p].reachedGameCnt[black] = MAXMOVES;
121 Pattern[p].reachedGameCnt[white] = MAXMOVES;
122 Pattern[p].first_link = pindex;
124 while (pattern_data[pindex] != END_OF_LINKS)
128 Pattern[p].first_field = pindex;
130 while (pattern_data[pindex] != END_OF_FIELDS)
134 if (pattern_data[pindex] != END_OF_PATTERNS)
135 Pattern[p].next_pattern = p + 1;
137 Pattern[p].next_pattern = END_OF_PATTERNS;
141 while (pattern_data[pindex] != END_OF_PATTERNS);
146 while (pattern_data[pindex] != END_OF_SEQUENCES);
148 *max_opening_sequence = os;
154 ShowOpeningPatterns (short max_opening_sequence)
158 for (os = 0; os < max_opening_sequence; os++)
161 NameOfOpeningValue(OpeningSequence[os].opening_type, name);
162 printf("Opening Type: %s\n", name);
164 for (p = OpeningSequence[os].first_pattern[0], n = 0;
165 p != END_OF_PATTERNS;
166 p = Pattern[p].next_pattern, n++)
168 printf("Pattern %d (%d) with links ", p, n);
170 for (i = Pattern[p].first_link;
171 pattern_data[i] != END_OF_LINKS;
174 printf("%d ", pattern_data[i]);
178 DisplayPattern(stdout, Pattern[p].first_field);
186 set_field (short i, struct PatternField *field)
188 field->piece = pattern_data[i];
189 field->square = pattern_data[i+1];
191 if (field->square < 0)
193 field->square = -(field->square);
205 * piece_to_pattern_distance (side, piece, pside, pattern)
207 * Determine the minimum number of moves from the current position to a
208 * specific pattern for a specific piece. Consider the "side" piece of the
209 * pattern. The pattern should match for "pside".
213 piece_to_pattern_distance(short side, short piece,
214 short pside, short pattern)
216 short nP, P[4], nB, B[4]; /* at most 4 pieces of same kind */
217 short i, j, r, dd, occupied, mindd, c[4], d[4];
218 /* a "side" patternfield must match a "c1" piece on board: */
219 short c1 = side ^ pside;
222 * If pside == white, a black piece in the pattern should match a white
223 * piece on board, and vice versa. Furthermore, if pside == white,
224 * reversed pattern should match board.
227 /* special pawn handling */
231 mindd = occupied = 0;
233 for (i = Pattern[pattern].first_field;
234 pattern_data[i] != END_OF_FIELDS;
237 struct PatternField field;
238 set_field(i, &field);
240 if ((field.side == side) && (field.piece == pawn))
242 short t = field.square;
243 short pcol = column(t);
246 if (PawnCnt[c1][(side == c1) ? pcol : (8 - pcol)])
248 /* there is a pawn on the column */
249 for (j = 0; j <= PieceCnt[c1]; j++)
251 short sq = (short)PieceList[c1][j];
253 if (board[sq] == pawn)
256 sq = NO_SQUARES - 1 - sq;
258 if (column(sq) == pcol)
260 dd = piece_distance (side, pawn, sq, t);
262 printf("update %d pawn "
263 "from %d to %d is %d\n",
273 /* there is no pawn on the column; drop possible? */
274 if (Captured[c1][pawn])
278 printf("update %d pawn drop to %d is %d\n",
286 /* Increment distance if pattern field is occupied */
296 psq = (NO_SQUARES - 1 - t);
300 if ((color[psq] == pc) && (board[psq] != pawn))
303 printf("square %d is occupied\n", psq);
317 return mindd + occupied;
321 * Determine list of "side" "piece"s in pattern.
324 for (occupied = nP = 0, i = Pattern[pattern].first_field;
325 pattern_data[i] != END_OF_FIELDS;
328 struct PatternField field;
329 set_field(i, &field);
331 if ((field.side == side) && (field.piece == piece))
334 P[nP] = field.square;
336 printf("pattern %d piece %d on square %d\n", side, piece, P[nP]);
340 /* Increment distance if pattern field is occupied */
348 psq = NO_SQUARES - 1 - field.square;
352 if ((color[psq] == pc) && (board[psq] != field.piece))
355 printf("square %d is occupied\n", psq);
366 printf("finding in pattern %d pieces %d of side %d\n", nP, piece, side);
370 * Determine list of "side ^ pside" "piece"s captured or on board.
373 for (nB = 0; nB < Captured[c1][piece]; nB++)
374 B[nB] = NO_SQUARES + piece;
376 for (i = 0; i <= PieceCnt[c1]; i++)
378 short sq = PieceList[c1][i];
380 if (board[sq] == piece)
382 B[nB] = (pside == black) ? sq : (NO_SQUARES - 1 - sq);
384 printf("%d piece %d on square %d\n", side, piece, B[nB]);
391 printf("found on board %d pieces %d of side %d\n", nB, piece, side);
399 /* Determine best assignment from board piece to pattern piece */
403 mindd = CANNOT_REACH;
405 while ((r >= 0) && (mindd != 0))
414 for (i = 0; i < r; i++)
422 d[r] = piece_distance (side, piece, B[c[r]], P[r]);
424 printf("update d[%d] from %d to %d is %d\n",
425 r, B[c[r]], P[r], d[r]);
435 for (dd = i = 0; i < nP; i++)
438 if ((dd < mindd) || (mindd < 0))
442 printf("update min %d\n", mindd);
460 return (mindd + occupied);
467 * pattern_distance (pside, pattern)
469 * Determine the minimum number of moves for the pieces from
470 * the current position to reach a pattern.
471 * The result is CANNOT_REACH, if there is no possible sequence
477 pattern_distance (short pside, short pattern)
479 short side, piece, d, n;
482 printf("\nchecking pattern %d for pside=%d\n\n", pattern, pside);
485 for (n = side = 0; side <= 1 && n >= 0; side++)
487 for (piece = pawn; piece <= king; piece++)
489 d = piece_to_pattern_distance (side, piece, pside, pattern);
504 printf("\ndistance to pattern is %d\n\n", n);
513 * board_to_pattern_distance(pside, osequence, pmplty, GameCnt)
515 * Determine the maximal difference of the number of moves from the pattern
516 * to the initial position and to the current position.
517 * Differences are weighted, i.e. the more closer a position is to a pattern
518 * the more valuable is a move towards the pattern.
519 * Patterns, which are at least "pmplty" halfmoves away, are not counted.
523 board_to_pattern_distance
524 (short pside, short osequence, short pmplty, short GameCnt)
526 short i, d, dist, diff, weighted_diff;
527 short maxdiff = 0, max_weighted_diff = 0;
530 for (i = 0; i < MAX_SEQUENCE; i++)
532 for (pattern = OpeningSequence[osequence].first_pattern[i];
533 pattern != END_OF_PATTERNS;
534 pattern = Pattern[pattern].next_pattern)
536 if ((d = Pattern[pattern].distance[pside]) >= 0)
540 dist = pattern_distance (pside, pattern);
544 * "dist" is the distance of the current board
545 * position to the pattern. "d - dist" is the
546 * difference between the current distance and the
547 * initial distance. Compute "diff" as the weighted
551 /* try to reach the nearest pattern */
552 weighted_diff = (diff = (d - dist)) * (pmplty - d);
554 if (weighted_diff > max_weighted_diff)
559 maxdiff = weighted_diff;
561 max_weighted_diff = weighted_diff;
565 * A reached pattern should not be considered in
566 * the future (if GameCnt >= 0)
569 if (dist == 0 && GameCnt >= 0)
570 Pattern[pattern].reachedGameCnt[pside] = GameCnt;
584 DisplayPattern (FILE *fd, short n)
586 small_short pboard[NO_SQUARES], pcolor[NO_SQUARES];
589 for (sq = 0; sq < NO_SQUARES; sq++)
591 pboard[sq] = no_piece;
592 pcolor[sq] = neutral;
595 for (i = n; pattern_data[i] != END_OF_FIELDS; i += 2)
597 struct PatternField field;
598 set_field(i, &field);
599 pboard[field.square] = field.piece;
600 pcolor[field.square] = field.side;
603 for (r = NO_ROWS - 1; r >= 0; r--)
605 for (c = 0; c < NO_COLS; c++)
613 fprintf(fd, "%c%c", is_promoted[i] ? '+' : ' ',
614 pcolor[sq] ? pxx[i] : qxx[i]);
627 VisitReachable (int pside, short osequence, int k, int n, int remove)
632 /* Adjust to sequence pattern n */
633 for (i = 0, pattern = OpeningSequence[osequence].first_pattern[k];
636 pattern = Pattern[pattern].next_pattern;
639 /* do not perform visited link twice */
640 if (Pattern[pattern].visited)
646 Pattern[pattern].visited = true;
649 /* Declare links unreachable */
650 for (j = Pattern[pattern].first_link;
651 pattern_data[j] != END_OF_LINKS; j++)
653 VisitReachable(pside, osequence, k, pattern_data[j], remove);
656 /* Declare unreachable */
657 if (remove && Pattern[pattern].distance[pside] >= 0)
659 Pattern[pattern].distance[pside] = IS_SUCCESSOR;
664 /* simplified matching for opening type names */
666 #define match_char(a, b) \
667 (a == b || (a == '*' && b != 'U') || (b == '*' && a != 'U'))
669 #define match_name(a, b, l) \
670 (l > 8 && match_char(a[0], b[0]) && match_char(a[7], b[7]) \
671 && match_char(a[9], b[9]))
675 locate_opening_sequence(short pside, char *s, short GameCnt)
677 short i, j, k, os, d;
679 short check_visited[MAX_SEQUENCE];
680 char name[MAX_NAME], name2[MAX_NAME];
683 * Look for opening pattern name in the list of opening patterns.
688 for (i = 1, os = 0; os < MAX_OPENING_SEQUENCE; os++)
690 /* locate matching opening type name */
691 NameOfOpeningValue(OpeningSequence[os].opening_type, name);
693 if (match_name(s, name, l))
695 /* locate successor matching names */
696 for (k = os + 1; k < MAX_OPENING_SEQUENCE; k++)
698 NameOfOpeningValue(OpeningSequence[k].opening_type, name2);
700 if (match_name(s, name2, l))
702 OpeningSequence[os].first_pattern[i++]
703 = OpeningSequence[k].first_pattern[0];
711 if (os >= MAX_OPENING_SEQUENCE)
713 return END_OF_SEQUENCES;
717 for (; i < MAX_SEQUENCE;
718 OpeningSequence[os].first_pattern[i++] = END_OF_PATTERNS);
722 * Determine patterns which can be reached from the current
723 * board position. Only patterns which can be reached will be
724 * checked in the following search.
727 for (i = 0; i < MAX_SEQUENCE; i++)
729 check_visited[i] = false;
731 for (k = OpeningSequence[os].first_pattern[i];
732 k != END_OF_PATTERNS;
733 k = Pattern[k].next_pattern)
735 Pattern[k].visited = false;
739 for (i = 0; i < MAX_SEQUENCE; i++)
741 for (k = OpeningSequence[os].first_pattern[i];
742 k != END_OF_PATTERNS;
743 k = Pattern[k].next_pattern)
745 Pattern[k].distance[pside] = pattern_distance(pside, k);
747 /* Actually reached patterns need not to be observed. */
748 if (Pattern[k].distance[pside] == 0)
750 Pattern[k].distance[pside] = CANNOT_REACH;
751 check_visited[i] = Pattern[k].visited = true;
753 for (j = Pattern[k].first_link;
754 pattern_data[j] != END_OF_LINKS; j++)
756 VisitReachable(pside, os, i, pattern_data[j], false);
759 else if ((GameCnt >= 0)
760 && (GameCnt >= Pattern[k].reachedGameCnt[pside]))
762 Pattern[k].distance[pside] = IS_REACHED;
765 if (Pattern[k].reachedGameCnt[pside] >= GameCnt)
766 Pattern[k].reachedGameCnt[pside] = MAXMOVES;
771 * Remove reachable patterns from search, which are successors of
772 * reachable patterns. So, only the next pattern of a pattern sequence
776 for (i = 0; i < MAX_SEQUENCE; i++)
778 for (k = OpeningSequence[os].first_pattern[i];
779 k != END_OF_PATTERNS;
780 k = Pattern[k].next_pattern)
782 if (check_visited[i] && !Pattern[k].visited)
783 Pattern[k].distance[pside] = NOT_TO_REACH;
785 Pattern[k].visited = false;
789 for (i = 0; i < MAX_SEQUENCE; i++)
791 for (k = OpeningSequence[os].first_pattern[i];
792 k != END_OF_PATTERNS;
793 k = Pattern[k].next_pattern)
795 if ((d = Pattern[k].distance[pside]) >= 0)
797 for (j = Pattern[k].first_link;
798 pattern_data[j] != END_OF_LINKS; j++)
800 VisitReachable(pside, os, i, pattern_data[j], true);
807 * Look to see whether there is still a reachable pattern.
810 for (i = 0; i < MAX_SEQUENCE; i++)
812 for (k = OpeningSequence[os].first_pattern[i];
813 k != END_OF_PATTERNS;
814 k = Pattern[k].next_pattern)
816 if ((d = Pattern[k].distance[pside]) >= 0)
821 return END_OF_SEQUENCES;
828 update_advance_bonus (short pside, short os)
830 struct PatternField field;
833 for (j = 0; j < MAX_SEQUENCE; j++)
835 for (k = OpeningSequence[os].first_pattern[j];
836 k != END_OF_PATTERNS;
837 k = Pattern[k].next_pattern)
839 if ((d = Pattern[k].distance[pside]) >= 0)
841 for (i = Pattern[k].first_field;
842 pattern_data[i] != END_OF_FIELDS; i += 2)
844 set_field(i, &field);
845 if (field.side == black)
847 short square = (pside == black)
849 : NO_SQUARES - 1 - field.square;
851 (*Mpiece[field.piece])[pside][square]
852 += ADVNCM[field.piece];