2 * pattern.c - C source for GNU SHOGI
4 * Copyright (c) 1993, 1994, 1995 Matthias Mutz
6 * GNU SHOGI is based on GNU CHESS
8 * Copyright (c) 1988,1989,1990 John Stanback
9 * Copyright (c) 1992 Free Software Foundation
11 * This file is part of GNU SHOGI.
13 * GNU Shogi is free software; you can redistribute it and/or modify
14 * it under the terms of the GNU General Public License as published by
15 * the Free Software Foundation.
17 * GNU Shogi is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU General Public License for more details.
22 * You should have received a copy of the GNU General Public License
23 * along with GNU Shogi; see the file COPYING. If not, write to
24 * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
30 #if defined DEBUG && !defined EXTPATTERNFILE
31 /* #define DEBUG_PATTERN */
32 /* #define TEST_PATTERN */
46 #define MAX_PATTERN_DATA 5000
48 small_short pattern_data[MAX_PATTERN_DATA];
50 #define MAX_OPENING_SEQUENCE 20
51 #define MAX_PATTERN 200
55 /* constants and pattern_data are generated by "pat2inc" */
57 #include "pattern.inc"
61 struct Pattern_rec Pattern[MAX_PATTERN];
62 struct OpeningSequence_rec OpeningSequence[MAX_OPENING_SEQUENCE];
66 #if defined DEBUG || defined DEBUG_EVAL
67 static small_ushort sequence_id;
72 short ValueOfOpeningName (char *name)
75 i = (name[0] == 'C') ? 0 : 100;
77 case 'S' : i += 10; break;
78 case 'R' : i += 20; break;
79 case 'U' : i += 30; break;
80 default : i += 40; break;
83 case 'S' : i += 1; break;
84 case 'R' : i += 2; break;
85 case 'U' : i += 3; break;
86 default : i += 4; break;
92 void NameOfOpeningValue (short i, char *name)
95 strcpy(name,"CASTLE_?_?");
97 strcpy(name,"ATTACK_?_?");
101 case 1 : name[7] = 'S'; break;
102 case 2 : name[7] = 'R'; break;
103 case 3 : name[7] = 'U'; break;
104 default : name[7] = '*'; break;
107 case 1 : name[9] = 'S'; break;
108 case 2 : name[9] = 'R'; break;
109 case 3 : name[9] = 'U'; break;
110 default : name[9] = '*'; break;
115 #ifdef EXTPATTERNFILE
117 char *patternfile = PATTERNFILE;
119 #define is_digit(c) ((c) >= '0' && (c) <= '9')
120 #define is_alfa(c) ((c) >= 'a' && (c) <= 'z' || (c) >= 'A' && (c) <= 'Z')
122 #define eos(s) (*s == '\0' || *s == '\n')
125 /* skip blanks and comments in brackets */
127 static void skipbb(char **s)
128 { while (**s == ' ' || **s == '|' || **s == '[') {
130 while (**s != ']') (*s)++;
135 /* skip unsigned numbers */
137 static void skipi(char **s)
139 while ( is_digit(**s) )
147 ScanPiece (char **s, small_short *side, small_short *piece, small_short *square)
149 short isp, isw, c, r;
151 /* determine promotion status */
156 /* determine side and piece */
157 for (c = 0; c < NO_PIECES; c++)
158 if ((isw = (**s == pxx[c])) || **s == qxx[c])
160 *piece = isp ? promoted[c] : unpromoted[c];
169 /* piece is captured */
171 *square = NO_SQUARES + *piece;
175 /* determine column */
176 for (c = 0; c < NO_COLS; c++)
185 for (r = 0; r < NO_ROWS; r++)
191 if (r >= NO_ROWS) return(1);
192 /* determine square */
193 *square = r*NO_COLS + c;
202 ScanPattern (char *s, short *pindex)
204 small_short side, piece, square;
205 skipbb(&s); /* skip blanks and comments */
206 while ( is_digit(*s) ) {
207 pattern_data[(*pindex)++] = atoi(s);
210 pattern_data[(*pindex)++] = END_OF_LINKS;
213 if ( ScanPiece(&s, &side, &piece, &square) ) {
216 pattern_data[(*pindex)++] = piece;
217 pattern_data[(*pindex)++] = (side ? -square : square);
220 pattern_data[(*pindex)++] = END_OF_FIELDS;
226 ReadOpeningSequences (short *pindex)
231 short max_pattern = 0;
232 short max_opening_sequence = 0;
234 if ( (fd = fopen (patternfile, "r")) == NULL )
235 fd = fopen ("gnushogi.pat", "r");
239 while ( fgets (s, 256, fd) != NULL )
242 /* comment, skip line */
243 } else if ( is_alfa(*s) ) {
244 if ( max_opening_sequence++ > 0 ) {
245 pattern_data[(*pindex)++] = END_OF_PATTERNS;
247 pattern_data[(*pindex)++] = ValueOfOpeningName(s);
249 if ( ScanPattern(s,pindex) ) {
250 ShowMessage("error in pattern sequence...");
257 pattern_data[(*pindex)++] = END_OF_PATTERNS;
258 pattern_data[(*pindex)++] = END_OF_SEQUENCES;
259 #if defined NONDSP || defined MSDOS
260 sprintf(s, "Pattern: %d bytes for %d sequences with %d patterns.\n",
261 *pindex, max_opening_sequence, max_pattern);
266 #if defined NONDSP || defined MSDOS
268 sprintf(s, "no pattern file '%s'",patternfile);
276 WriteOpeningSequences (short pindex)
280 short max_pattern = 0;
281 short max_opening_sequence = 0;
283 fd = fopen ("pattern.inc", "w");
284 fprintf(fd,"#define MAX_PATTERN_DATA %d\n\n",pindex);
285 fprintf(fd,"small_short pattern_data[MAX_PATTERN_DATA] =\n{\n");
287 fprintf(fd," %d,\n",pattern_data[n++]);
291 while ( pattern_data[n] != END_OF_LINKS ) {
292 fprintf(fd,"%d, ",pattern_data[n++]);
294 fprintf(fd,"%d, ",pattern_data[n++]);
297 fprintf(fd,"%d,",pattern_data[n++]);
298 } while ( pattern_data[n] != END_OF_FIELDS );
299 fprintf(fd,"%d,\n",pattern_data[n++]);
301 } while ( pattern_data[n] != END_OF_PATTERNS );
302 fprintf(fd," %d,\n",pattern_data[n++]);
303 max_opening_sequence++;
304 } while ( pattern_data[n] != END_OF_SEQUENCES );
305 fprintf(fd," %d\n};\n",pattern_data[n++]);
309 fprintf(fd,"\n#define MAX_OPENING_SEQUENCE %d\n",max_opening_sequence);
310 fprintf(fd,"\n#define MAX_PATTERN %d\n",max_pattern);
320 GetOpeningPatterns (short *max_opening_sequence)
329 OpeningSequence[os].opening_type = pattern_data[pindex++];
330 OpeningSequence[os].first_pattern[0] = p;
331 for ( i=1; i<MAX_SEQUENCE; i++ )
332 OpeningSequence[os].first_pattern[i] = END_OF_PATTERNS;
334 Pattern[p].reachedGameCnt[black] = MAXMOVES;
335 Pattern[p].reachedGameCnt[white] = MAXMOVES;
336 Pattern[p].first_link = pindex;
337 while ( pattern_data[pindex] != END_OF_LINKS ) pindex++;
339 Pattern[p].first_field = pindex;
340 while ( pattern_data[pindex] != END_OF_FIELDS ) pindex += 2;
342 if ( pattern_data[pindex] != END_OF_PATTERNS )
343 Pattern[p].next_pattern = p+1;
345 Pattern[p].next_pattern = END_OF_PATTERNS;
347 } while (pattern_data[pindex] != END_OF_PATTERNS );
350 } while ( pattern_data[pindex] != END_OF_SEQUENCES );
351 *max_opening_sequence = os;
357 ShowOpeningPatterns (short max_opening_sequence)
362 for ( os=0; os<max_opening_sequence; os++ ) {
364 NameOfOpeningValue(OpeningSequence[os].opening_type, name);
365 printf("Opening Type: %s\n",name);
366 for ( p=OpeningSequence[os].first_pattern[0],n=0; p != END_OF_PATTERNS; p=Pattern[p].next_pattern,n++ ) {
367 printf("Pattern %d (%d) with links ",p,n);
368 for ( i=Pattern[p].first_link; pattern_data[i]!=END_OF_LINKS; i++ ) {
369 printf("%d ",pattern_data[i]);
372 DisplayPattern(stdout,Pattern[p].first_field);
379 void set_field (short i, struct PatternField *field)
381 field->piece = pattern_data[i];
382 field->square = pattern_data[i+1];
383 if ( field->square < 0 ) {
384 field->square = -(field->square);
394 piece_to_pattern_distance
395 (short side, short piece, short pside, short pattern)
398 * Determine the minimum number of moves from the current position
399 * to a specific pattern for a specific piece.
400 * Consider the "side" piece of the pattern.
401 * The pattern should match for "pside".
404 short nP, P[4], nB, B[4]; /* at most 4 pieces of same kind */
405 short nC, i, j, r, dd, occupied, mindd, c[4], d[4];
406 short c1 = side ^ pside; /* a "side" patternfield must match a "c1" piece on board */
409 * If pside == white, a black piece in the pattern should match
410 * a white piece on board, and vice versa. Furthermore, if
411 * pside == white, reversed pattern should match board.
414 /* special pawn handling */
416 if ( piece == pawn ) {
417 mindd = occupied = 0;
418 for ( i = Pattern[pattern].first_field; pattern_data[i] != END_OF_FIELDS; i += 2 ) {
419 struct PatternField field;
420 set_field(i, &field);
421 if ( (field.side == side) && (field.piece == pawn) ) {
422 short t = field.square;
423 short pcol = column(t);
425 if ( PawnCnt[c1][(side == c1) ? pcol : (8 - pcol)] ) {
426 /* there is a pawn on the column */
427 for ( j = 0; j <= PieceCnt[c1]; j++) {
428 short sq = (short)PieceList[c1][j];
429 if ( board[sq] == pawn ) {
430 if ( pside == white ) sq = NO_SQUARES - 1 - sq;
431 if ( column(sq) == pcol ) {
432 dd = piece_distance (side, pawn, sq, t);
434 printf("update %d pawn from %d to %d is %d\n", side, sq, t, dd);
441 /* there is no pawn on the column; drop possible? */
442 if ( Captured[c1][pawn] ) {
445 printf("update %d pawn drop to %d is %d\n", side, t, dd);
450 /* Increment distance if pattern field is occupied */
452 if ( pside == black ) {
456 psq = (NO_SQUARES - 1 - t);
459 if ( (color[psq] == pc) && (board[psq] != pawn) ) {
461 printf("square %d is occupied\n", psq);
467 return (CANNOT_REACH);
471 return (mindd + occupied);
475 * Determine list of "side" "piece"s in pattern.
478 for ( occupied = nP = 0, i = Pattern[pattern].first_field; pattern_data[i] != END_OF_FIELDS; i+=2 ) {
479 struct PatternField field;
480 set_field(i, &field);
481 if ( (field.side == side) && (field.piece == piece) ) {
483 P[nP] = field.square;
485 printf("pattern %d piece %d on square %d\n",side,piece,P[nP]);
488 /* Increment distance if pattern field is occupied */
489 if ( pside == black ) {
493 psq = (NO_SQUARES - 1 - field.square);
496 if ( (color[psq] == pc) && (board[psq] != field.piece) ) {
498 printf("square %d is occupied\n", psq);
509 printf("finding in pattern %d pieces %d of side %d\n", nP, piece, side);
513 * Determine list of "side ^ pside" "piece"s captured or on board.
516 for ( nB = 0; nB < Captured[c1][piece]; nB++ )
517 B[nB] = NO_SQUARES + piece;
519 for ( i = 0; i <= PieceCnt[c1]; i++ ) {
520 short sq = PieceList[c1][i];
521 if ( board[sq] == piece ) {
522 B[nB] = (pside == black) ? sq : (NO_SQUARES - 1 - sq);
524 printf("%d piece %d on square %d\n",side,piece,B[nB]);
531 printf("found on board %d pieces %d of side %d\n", nB, piece, side);
535 return (CANNOT_REACH);
538 /* Determine best assignment from board piece to pattern piece */
540 r = 0; c[0] = -1; mindd = CANNOT_REACH;
542 while ( (r >= 0) && (mindd != 0) ) {
544 if ( ++c[r] == nB ) {
547 for ( i = 0; i < r; i++ )
551 d[r] = piece_distance (side, piece, B[c[r]], P[r]);
553 printf("update d[%d] from %d to %d is %d\n", r, B[c[r]], P[r], d[r]);
559 for (dd = i = 0; i < nP; i++)
561 if ( (dd < mindd) || (mindd < 0) ) {
564 printf("update min %d\n", mindd);
577 return (CANNOT_REACH);
579 return (mindd + occupied);
585 pattern_distance (short pside, short pattern)
588 * Determine the minimum number of moves for the pieces from
589 * the current position to reach a pattern.
590 * The result is CANNOT_REACH, if there is no possible sequence
595 short side, piece, d, n;
598 printf("\nchecking pattern %d for pside=%d\n\n",pattern,pside);
601 for ( n = side = 0; side <= 1 && n >= 0; side++ )
602 for ( piece = pawn; piece <= king; piece++ ) {
603 d = piece_to_pattern_distance (side, piece, pside, pattern);
605 n = CANNOT_REACH; break;
611 printf("\ndistance to pattern is %d\n\n",n);
620 board_to_pattern_distance
621 (short pside, short osequence, short pmplty, short GameCnt)
624 * Determine the maximal difference of the number of moves from the pattern
625 * to the initial position and to the current position.
626 * Differences are weighted, i.e. the more closer a position is to a pattern
627 * the more valuable is a move towards the pattern.
628 * Patterns, which are at least "pmplty" halfmoves away, are not counted.
632 short i, d, dist, diff, weighted_diff;
633 short maxdiff = 0, max_weighted_diff = 0;
639 NameOfOpeningValue(OpeningSequence[osequence].opening_type,name);
640 fprintf(debug_eval_file,"board to %s pattern distance pside=%s, pmplty=%d, GameCnt=%d\n",
641 name, ColorStr[pside], pmplty, GameCnt);
645 for ( i=0; i<MAX_SEQUENCE; i++ )
646 for ( pattern = OpeningSequence[osequence].first_pattern[i]; pattern != END_OF_PATTERNS; pattern = Pattern[pattern].next_pattern ) {
649 fprintf(debug_eval_file,"%spattern %d",
650 (i?"common ":""),pattern);
652 if ( (d = Pattern[pattern].distance[pside]) >= 0 ) {
655 fprintf(debug_eval_file," initially reachable in %d steps\n",d);
659 dist = pattern_distance (pside, pattern);
662 /* "dist" is the distance of the current board position to the pattern.
663 * "d - dist" is the difference between the current distance and the
664 * initial distance. Compute "diff" as the weighted difference.
668 fprintf(debug_eval_file," now reachable in %d steps\n",dist);
669 DisplayPattern(debug_eval_file,Pattern[pattern].first_field);
672 /* try to reach the nearest pattern */
673 weighted_diff = (diff = (d - dist)) * (pmplty - d);
674 if ( weighted_diff > max_weighted_diff ) {
678 maxdiff = weighted_diff;
680 max_weighted_diff = weighted_diff;
683 fprintf(debug_eval_file,"current maximum gain %d\n",maxdiff);
689 fprintf(debug_eval_file,"gain %d\n",diff);
692 /* A reached pattern should not be considered in the future (if GameCnt >= 0) */
693 if ( dist == 0 && GameCnt >= 0)
695 Pattern[pattern].reachedGameCnt[pside] = GameCnt;
698 fprintf(debug_eval_file,"pattern reached in move %d\n",GameCnt);
705 fprintf(debug_eval_file," now unreachable\n");
712 fprintf(debug_eval_file," beyond %d steps\n",pmplty);
719 fprintf(debug_eval_file,
720 (d == NOT_TO_REACH) ? " not to reach\n" :
721 (d == IS_REACHED) ? " is reached\n" :
722 (d == IS_SUCCESSOR) ? " is successor\n" : " cannot reach\n");
733 DisplayPattern (FILE *fd, short n)
736 small_short pboard[NO_SQUARES], pcolor[NO_SQUARES];
739 for (sq = 0; sq < NO_SQUARES; sq++)
741 pboard[sq] = no_piece;
742 pcolor[sq] = neutral;
745 for (i = n; pattern_data[i] != END_OF_FIELDS; i += 2)
747 struct PatternField field;
749 pboard[field.square] = field.piece;
750 pcolor[field.square] = field.side;
753 for (r = NO_ROWS-1; r >= 0; r--)
755 for (c = 0; c < NO_COLS; c++)
762 fprintf(fd,"%c%c",is_promoted[i]?'+':' ',pcolor[sq]?pxx[i]:qxx[i]);
776 VisitReachable (int pside, short osequence, int k, int n, int remove)
782 printf("visit reachable %d %d %s\n",k,n,remove?"remove":"");
785 /* Adjust to sequence pattern n */
786 for (i=0,pattern=OpeningSequence[osequence].first_pattern[k]; i<n; i++)
787 pattern = Pattern[pattern].next_pattern;
790 printf("pattern id = %d\n",pattern);
793 /* do not perform visited link twice */
794 if ( Pattern[pattern].visited ) {
796 printf("pattern %d %d visited\n",n,pattern);
800 Pattern[pattern].visited = true;
802 /* Declare links unreachable */
803 for (j=Pattern[pattern].first_link; pattern_data[j] != END_OF_LINKS; j++)
804 VisitReachable(pside,osequence,k,pattern_data[j],remove);
806 /* Declare unreachable */
807 if ( remove && Pattern[pattern].distance[pside] >= 0 ) {
808 Pattern[pattern].distance[pside] = IS_SUCCESSOR;
810 printf("removing %d\n",n);
817 /* simplified matching for opening type names */
819 #define match_char(a,b) (a == b || (a == '*' && b != 'U') || (b == '*' && a != 'U'))
820 #define match_name(a,b,l) (l>8 && match_char(a[0],b[0]) && match_char(a[7],b[7]) && match_char(a[9],b[9]))
823 short locate_opening_sequence(short pside, char *s, short GameCnt)
826 short i,j,k, os, removed, d;
831 short check_visited[MAX_SEQUENCE];
832 char name[MAX_NAME], name2[MAX_NAME];
835 * Look for opening pattern name in the list of opening patterns.
839 for ( i = 1,os = 0; os<MAX_OPENING_SEQUENCE; os++ )
841 /* locate matching opening type name */
842 NameOfOpeningValue(OpeningSequence[os].opening_type,name);
844 printf("try to match %s with %s\n",s,name);
846 if ( match_name(s,name,l) ) {
848 printf("%s matches pattern %d %s\n",s,os,name);
850 /* locate successor matching names */
851 for ( k=os+1; k<MAX_OPENING_SEQUENCE; k++ ) {
852 NameOfOpeningValue(OpeningSequence[k].opening_type,name2);
853 if ( match_name(s,name2,l) ) {
855 printf("%s matches pattern %d %s [%d]\n",s,k,name2,i);
857 OpeningSequence[os].first_pattern[i++] = OpeningSequence[k].first_pattern[0];
864 if ( os>=MAX_OPENING_SEQUENCE )
865 return(END_OF_SEQUENCES);
867 for ( ; i<MAX_SEQUENCE; OpeningSequence[os].first_pattern[i++] = END_OF_PATTERNS);
870 printf("%s uses opening line %s\n",ColorStr[pside],name);
874 * Determine patterns which can be reached from the current
875 * board position. Only patterns which can be reached will be
876 * checked in the following search.
879 for ( i=0; i<MAX_SEQUENCE; i++) {
880 check_visited[i] = false;
881 for ( k=OpeningSequence[os].first_pattern[i]; k!=END_OF_PATTERNS; k=Pattern[k].next_pattern )
882 Pattern[k].visited = false;
885 for ( i=0; i<MAX_SEQUENCE; i++)
886 for ( k=OpeningSequence[os].first_pattern[i]; k!=END_OF_PATTERNS; k=Pattern[k].next_pattern )
888 Pattern[k].distance[pside] = pattern_distance(pside,k);
889 /* Actually reached patterns need not to be observed. */
890 if ( Pattern[k].distance[pside] == 0 ) {
891 Pattern[k].distance[pside] = CANNOT_REACH;
893 printf("pattern id=%d removed because reached\n",k);
894 DisplayPattern(stdout,Pattern[k].first_field);
896 check_visited[i] = Pattern[k].visited = true;
897 for (j=Pattern[k].first_link; pattern_data[j]!=END_OF_LINKS; j++) {
899 printf("visit successors for link %d\n",pattern_data[j]);
901 VisitReachable(pside,os,i,pattern_data[j],false);
903 } else if ( GameCnt >= 0 && GameCnt >= Pattern[k].reachedGameCnt[pside] ) {
904 Pattern[k].distance[pside] = IS_REACHED;
906 printf("pattern %d removed because reached at GameCnt %d below current %d\n",
907 k,Pattern[k].reachedGameCnt[pside],GameCnt);
910 if ( Pattern[k].reachedGameCnt[pside] >= GameCnt )
911 Pattern[k].reachedGameCnt[pside] = MAXMOVES;
915 * Remove reachable patterns from search, which are successors of
916 * reachable patterns. So, only the next pattern of a pattern sequence
920 for ( i=0; i<MAX_SEQUENCE; i++)
921 for ( k=OpeningSequence[os].first_pattern[i]; k!=END_OF_PATTERNS; k=Pattern[k].next_pattern ) {
922 if ( check_visited[i] && !Pattern[k].visited ) {
923 Pattern[k].distance[pside] = NOT_TO_REACH;
925 printf("pattern id = %d removed because no successor of reached pattern\n",
929 Pattern[k].visited = false;
933 for ( i=0; i<MAX_SEQUENCE; i++)
934 for (k=OpeningSequence[os].first_pattern[i]; k!=END_OF_PATTERNS; k=Pattern[k].next_pattern) {
935 short d = Pattern[k].distance[pside];
936 assert(!Pattern[k].visited);
938 (d == NOT_TO_REACH) ? " not to reach" :
939 (d == IS_REACHED) ? " is reached" :
940 (d == IS_SUCCESSOR) ? " is successor" : " cannot reach");
944 for ( i=0; i<MAX_SEQUENCE; i++)
945 for (k=OpeningSequence[os].first_pattern[i]; k!=END_OF_PATTERNS; k=Pattern[k].next_pattern)
946 if ( (d = Pattern[k].distance[pside]) >= 0 ) {
947 for (j=Pattern[k].first_link; pattern_data[j]!=END_OF_LINKS; j++) {
949 printf("removing successors for link %d\n",pattern_data[j]);
951 VisitReachable(pside,os,i,pattern_data[j],true);
956 * Look, whether there is still a reachable pattern.
959 for ( i=0; i<MAX_SEQUENCE; i++ )
960 for ( k=OpeningSequence[os].first_pattern[i]; k!=END_OF_PATTERNS; k=Pattern[k].next_pattern )
961 if ( (d = Pattern[k].distance[pside]) >= 0 )
964 for ( i=n=m=0; i<MAX_SEQUENCE; i++ )
965 for (k=OpeningSequence[os].first_pattern[i]; k!=END_OF_PATTERNS; k=Pattern[k].next_pattern,n++)
966 if ( (d = Pattern[k].distance[pside]) >= 0 )
968 printf("%d reachable %s patterns out of %d patterns\n",
969 m,ColorStr[pside],n);
975 printf("all %s patterns out of %d patterns (%d reachable) removed\n",
976 ColorStr[pside],n,m);
979 return (END_OF_SEQUENCES);
983 void update_advance_bonus (short pside, short os)
985 struct PatternField field;
988 for ( j=0; j<MAX_SEQUENCE; j++ )
989 for ( k=OpeningSequence[os].first_pattern[j]; k!=END_OF_PATTERNS; k=Pattern[k].next_pattern )
990 if ( (d = Pattern[k].distance[pside]) >= 0 )
992 for ( i = Pattern[k].first_field; pattern_data[i]!=END_OF_FIELDS; i+=2 ) {
994 if ( field.side == black ) {
995 short square = (pside == black)
997 : NO_SQUARES - 1 - field.square;
998 (*Mpiece[field.piece])[pside][square] += ADVNCM[field.piece];