4 * ----------------------------------------------------------------------
6 * Copyright (c) 2012 Free Software Foundation
8 * GNU SHOGI is based on GNU CHESS
10 * This file is part of GNU SHOGI.
12 * GNU Shogi is free software; you can redistribute it and/or modify it
13 * under the terms of the GNU General Public License as published by the
14 * Free Software Foundation; either version 3 of the License,
15 * or (at your option) any later version.
17 * GNU Shogi is distributed in the hope that it will be useful, but WITHOUT
18 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
19 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
22 * You should have received a copy of the GNU General Public License along
23 * with GNU Shogi; see the file COPYING. If not, see
24 * <http://www.gnu.org/licenses/>.
25 * ----------------------------------------------------------------------
32 /* constants and pattern_data are generated by "pat2inc" */
33 #include "pattern.inc"
35 struct Pattern_rec Pattern[MAX_PATTERN];
36 struct OpeningSequence_rec OpeningSequence[MAX_OPENING_SEQUENCE];
38 small_short pattern_data[MAX_PATTERN_DATA];
42 ValueOfOpeningName (char *name)
45 i = (name[0] == 'C') ? 0 : 100;
90 NameOfOpeningValue (short i, char *name)
94 strcpy(name, "CASTLE_?_?");
98 strcpy(name, "ATTACK_?_?");
143 GetOpeningPatterns (short *max_opening_sequence)
152 OpeningSequence[os].opening_type = pattern_data[pindex++];
153 OpeningSequence[os].first_pattern[0] = p;
155 for (i = 1; i < MAX_SEQUENCE; i++)
156 OpeningSequence[os].first_pattern[i] = END_OF_PATTERNS;
160 Pattern[p].reachedGameCnt[black] = MAXMOVES;
161 Pattern[p].reachedGameCnt[white] = MAXMOVES;
162 Pattern[p].first_link = pindex;
164 while (pattern_data[pindex] != END_OF_LINKS)
168 Pattern[p].first_field = pindex;
170 while (pattern_data[pindex] != END_OF_FIELDS)
174 if (pattern_data[pindex] != END_OF_PATTERNS)
175 Pattern[p].next_pattern = p + 1;
177 Pattern[p].next_pattern = END_OF_PATTERNS;
181 while (pattern_data[pindex] != END_OF_PATTERNS);
186 while (pattern_data[pindex] != END_OF_SEQUENCES);
188 *max_opening_sequence = os;
194 ShowOpeningPatterns (short max_opening_sequence)
199 for (os = 0; os < max_opening_sequence; os++)
202 NameOfOpeningValue(OpeningSequence[os].opening_type, name);
203 printf("Opening Type: %s\n", name);
205 for (p = OpeningSequence[os].first_pattern[0], n = 0;
206 p != END_OF_PATTERNS;
207 p = Pattern[p].next_pattern, n++)
209 printf("Pattern %d (%d) with links ", p, n);
211 for (i = Pattern[p].first_link;
212 pattern_data[i] != END_OF_LINKS;
215 printf("%d ", pattern_data[i]);
219 DisplayPattern(stdout, Pattern[p].first_field);
227 set_field (short i, struct PatternField *field)
229 field->piece = pattern_data[i];
230 field->square = pattern_data[i+1];
232 if (field->square < 0)
234 field->square = -(field->square);
246 * piece_to_pattern_distance (side, piece, pside, pattern)
248 * Determine the minimum number of moves from the current position to a
249 * specific pattern for a specific piece. Consider the "side" piece of the
250 * pattern. The pattern should match for "pside".
254 piece_to_pattern_distance(short side, short piece,
255 short pside, short pattern)
257 short nP, P[4], nB, B[4]; /* at most 4 pieces of same kind */
258 short i, j, r, dd, occupied, mindd, c[4], d[4];
259 /* a "side" patternfield must match a "c1" piece on board: */
260 short c1 = side ^ pside;
263 * If pside == white, a black piece in the pattern should match a white
264 * piece on board, and vice versa. Furthermore, if pside == white,
265 * reversed pattern should match board.
268 /* special pawn handling */
272 mindd = occupied = 0;
274 for (i = Pattern[pattern].first_field;
275 pattern_data[i] != END_OF_FIELDS;
278 struct PatternField field;
279 set_field(i, &field);
281 if ((field.side == side) && (field.piece == pawn))
283 short t = field.square;
284 short pcol = column(t);
287 if (PawnCnt[c1][(side == c1) ? pcol : (8 - pcol)])
289 /* there is a pawn on the column */
290 for (j = 0; j <= PieceCnt[c1]; j++)
292 short sq = (short)PieceList[c1][j];
294 if (board[sq] == pawn)
297 sq = NO_SQUARES - 1 - sq;
299 if (column(sq) == pcol)
301 dd = piece_distance (side, pawn, sq, t);
303 printf("update %d pawn "
304 "from %d to %d is %d\n",
314 /* there is no pawn on the column; drop possible? */
315 if (Captured[c1][pawn])
319 printf("update %d pawn drop to %d is %d\n",
327 /* Increment distance if pattern field is occupied */
337 psq = (NO_SQUARES - 1 - t);
341 if ((color[psq] == pc) && (board[psq] != pawn))
344 printf("square %d is occupied\n", psq);
358 return mindd + occupied;
362 * Determine list of "side" "piece"s in pattern.
365 for (occupied = nP = 0, i = Pattern[pattern].first_field;
366 pattern_data[i] != END_OF_FIELDS;
369 struct PatternField field;
370 set_field(i, &field);
372 if ((field.side == side) && (field.piece == piece))
375 P[nP] = field.square;
377 printf("pattern %d piece %d on square %d\n", side, piece, P[nP]);
381 /* Increment distance if pattern field is occupied */
389 psq = NO_SQUARES - 1 - field.square;
393 if ((color[psq] == pc) && (board[psq] != field.piece))
396 printf("square %d is occupied\n", psq);
407 printf("finding in pattern %d pieces %d of side %d\n", nP, piece, side);
411 * Determine list of "side ^ pside" "piece"s captured or on board.
414 for (nB = 0; nB < Captured[c1][piece]; nB++)
415 B[nB] = NO_SQUARES + piece;
417 for (i = 0; i <= PieceCnt[c1]; i++)
419 short sq = PieceList[c1][i];
421 if (board[sq] == piece)
423 B[nB] = (pside == black) ? sq : (NO_SQUARES - 1 - sq);
425 printf("%d piece %d on square %d\n", side, piece, B[nB]);
432 printf("found on board %d pieces %d of side %d\n", nB, piece, side);
440 /* Determine best assignment from board piece to pattern piece */
444 mindd = CANNOT_REACH;
446 while ((r >= 0) && (mindd != 0))
455 for (i = 0; i < r; i++)
463 d[r] = piece_distance (side, piece, B[c[r]], P[r]);
465 printf("update d[%d] from %d to %d is %d\n",
466 r, B[c[r]], P[r], d[r]);
476 for (dd = i = 0; i < nP; i++)
479 if ((dd < mindd) || (mindd < 0))
483 printf("update min %d\n", mindd);
501 return (mindd + occupied);
508 * pattern_distance (pside, pattern)
510 * Determine the minimum number of moves for the pieces from
511 * the current position to reach a pattern.
512 * The result is CANNOT_REACH, if there is no possible sequence
518 pattern_distance (short pside, short pattern)
520 short side, piece, d, n;
523 printf("\nchecking pattern %d for pside=%d\n\n", pattern, pside);
526 for (n = side = 0; side <= 1 && n >= 0; side++)
528 for (piece = pawn; piece <= king; piece++)
530 d = piece_to_pattern_distance (side, piece, pside, pattern);
545 printf("\ndistance to pattern is %d\n\n", n);
554 * board_to_pattern_distance(pside, osequence, pmplty, GameCnt)
556 * Determine the maximal difference of the number of moves from the pattern
557 * to the initial position and to the current position.
558 * Differences are weighted, i.e. the more closer a position is to a pattern
559 * the more valuable is a move towards the pattern.
560 * Patterns, which are at least "pmplty" halfmoves away, are not counted.
564 board_to_pattern_distance
565 (short pside, short osequence, short pmplty, short GameCnt)
567 short i, d, dist, diff, weighted_diff;
568 short maxdiff = 0, max_weighted_diff = 0;
571 for (i = 0; i < MAX_SEQUENCE; i++)
573 for (pattern = OpeningSequence[osequence].first_pattern[i];
574 pattern != END_OF_PATTERNS;
575 pattern = Pattern[pattern].next_pattern)
577 if ((d = Pattern[pattern].distance[pside]) >= 0)
581 dist = pattern_distance (pside, pattern);
585 * "dist" is the distance of the current board
586 * position to the pattern. "d - dist" is the
587 * difference between the current distance and the
588 * initial distance. Compute "diff" as the weighted
592 /* try to reach the nearest pattern */
593 weighted_diff = (diff = (d - dist)) * (pmplty - d);
595 if (weighted_diff > max_weighted_diff)
600 maxdiff = weighted_diff;
602 max_weighted_diff = weighted_diff;
606 * A reached pattern should not be considered in
607 * the future (if GameCnt >= 0)
610 if (dist == 0 && GameCnt >= 0)
611 Pattern[pattern].reachedGameCnt[pside] = GameCnt;
625 DisplayPattern (FILE *fd, short n)
627 small_short pboard[NO_SQUARES], pcolor[NO_SQUARES];
630 for (sq = 0; sq < NO_SQUARES; sq++)
632 pboard[sq] = no_piece;
633 pcolor[sq] = neutral;
636 for (i = n; pattern_data[i] != END_OF_FIELDS; i += 2)
638 struct PatternField field;
639 set_field(i, &field);
640 pboard[field.square] = field.piece;
641 pcolor[field.square] = field.side;
644 for (r = NO_ROWS - 1; r >= 0; r--)
646 for (c = 0; c < NO_COLS; c++)
654 fprintf(fd, "%c%c", is_promoted[i] ? '+' : ' ',
655 pcolor[sq] ? pxx[i] : qxx[i]);
668 VisitReachable (int pside, short osequence, int k, int n, int remove)
673 /* Adjust to sequence pattern n */
674 for (i = 0, pattern = OpeningSequence[osequence].first_pattern[k];
677 pattern = Pattern[pattern].next_pattern;
680 /* do not perform visited link twice */
681 if (Pattern[pattern].visited)
687 Pattern[pattern].visited = true;
690 /* Declare links unreachable */
691 for (j = Pattern[pattern].first_link;
692 pattern_data[j] != END_OF_LINKS; j++)
694 VisitReachable(pside, osequence, k, pattern_data[j], remove);
697 /* Declare unreachable */
698 if (remove && Pattern[pattern].distance[pside] >= 0)
700 Pattern[pattern].distance[pside] = IS_SUCCESSOR;
705 /* simplified matching for opening type names */
707 #define match_char(a, b) \
708 (a == b || (a == '*' && b != 'U') || (b == '*' && a != 'U'))
710 #define match_name(a, b, l) \
711 (l > 8 && match_char(a[0], b[0]) && match_char(a[7], b[7]) \
712 && match_char(a[9], b[9]))
716 locate_opening_sequence(short pside, char *s, short GameCnt)
718 short i, j, k, os, d;
720 short check_visited[MAX_SEQUENCE];
721 char name[MAX_NAME], name2[MAX_NAME];
724 * Look for opening pattern name in the list of opening patterns.
729 for (i = 1, os = 0; os < MAX_OPENING_SEQUENCE; os++)
731 /* locate matching opening type name */
732 NameOfOpeningValue(OpeningSequence[os].opening_type, name);
734 if (match_name(s, name, l))
736 /* locate successor matching names */
737 for (k = os + 1; k < MAX_OPENING_SEQUENCE; k++)
739 NameOfOpeningValue(OpeningSequence[k].opening_type, name2);
741 if (match_name(s, name2, l))
743 OpeningSequence[os].first_pattern[i++]
744 = OpeningSequence[k].first_pattern[0];
752 if (os >= MAX_OPENING_SEQUENCE)
754 return END_OF_SEQUENCES;
758 for (; i < MAX_SEQUENCE;
759 OpeningSequence[os].first_pattern[i++] = END_OF_PATTERNS);
763 * Determine patterns which can be reached from the current
764 * board position. Only patterns which can be reached will be
765 * checked in the following search.
768 for (i = 0; i < MAX_SEQUENCE; i++)
770 check_visited[i] = false;
772 for (k = OpeningSequence[os].first_pattern[i];
773 k != END_OF_PATTERNS;
774 k = Pattern[k].next_pattern)
776 Pattern[k].visited = false;
780 for (i = 0; i < MAX_SEQUENCE; i++)
782 for (k = OpeningSequence[os].first_pattern[i];
783 k != END_OF_PATTERNS;
784 k = Pattern[k].next_pattern)
786 Pattern[k].distance[pside] = pattern_distance(pside, k);
788 /* Actually reached patterns need not to be observed. */
789 if (Pattern[k].distance[pside] == 0)
791 Pattern[k].distance[pside] = CANNOT_REACH;
792 check_visited[i] = Pattern[k].visited = true;
794 for (j = Pattern[k].first_link;
795 pattern_data[j] != END_OF_LINKS; j++)
797 VisitReachable(pside, os, i, pattern_data[j], false);
800 else if ((GameCnt >= 0)
801 && (GameCnt >= Pattern[k].reachedGameCnt[pside]))
803 Pattern[k].distance[pside] = IS_REACHED;
806 if (Pattern[k].reachedGameCnt[pside] >= GameCnt)
807 Pattern[k].reachedGameCnt[pside] = MAXMOVES;
812 * Remove reachable patterns from search, which are successors of
813 * reachable patterns. So, only the next pattern of a pattern sequence
817 for (i = 0; i < MAX_SEQUENCE; i++)
819 for (k = OpeningSequence[os].first_pattern[i];
820 k != END_OF_PATTERNS;
821 k = Pattern[k].next_pattern)
823 if (check_visited[i] && !Pattern[k].visited)
824 Pattern[k].distance[pside] = NOT_TO_REACH;
826 Pattern[k].visited = false;
830 for (i = 0; i < MAX_SEQUENCE; i++)
832 for (k = OpeningSequence[os].first_pattern[i];
833 k != END_OF_PATTERNS;
834 k = Pattern[k].next_pattern)
836 if ((d = Pattern[k].distance[pside]) >= 0)
838 for (j = Pattern[k].first_link;
839 pattern_data[j] != END_OF_LINKS; j++)
841 VisitReachable(pside, os, i, pattern_data[j], true);
848 * Look to see whether there is still a reachable pattern.
851 for (i = 0; i < MAX_SEQUENCE; i++)
853 for (k = OpeningSequence[os].first_pattern[i];
854 k != END_OF_PATTERNS;
855 k = Pattern[k].next_pattern)
857 if ((d = Pattern[k].distance[pside]) >= 0)
862 return END_OF_SEQUENCES;
869 update_advance_bonus (short pside, short os)
871 struct PatternField field;
874 for (j = 0; j < MAX_SEQUENCE; j++)
876 for (k = OpeningSequence[os].first_pattern[j];
877 k != END_OF_PATTERNS;
878 k = Pattern[k].next_pattern)
880 if ((d = Pattern[k].distance[pside]) >= 0)
882 for (i = Pattern[k].first_field;
883 pattern_data[i] != END_OF_FIELDS; i += 2)
885 set_field(i, &field);
886 if (field.side == black)
888 short square = (pside == black)
890 : NO_SQUARES - 1 - field.square;
892 (*Mpiece[field.piece])[pside][square]
893 += ADVNCM[field.piece];