src/pattern.c

   1 /*
   2  * pattern.c - C source for GNU SHOGI
   3  *
   4  * Copyright (c) 1993, 1994, 1995 Matthias Mutz
   5  *
   6  * GNU SHOGI is based on GNU CHESS
   7  *
   8  * Copyright (c) 1988,1989,1990 John Stanback
   9  * Copyright (c) 1992 Free Software Foundation
  10  *
  11  * This file is part of GNU SHOGI.
  12  *
  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.
  16  *
  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.
  21  *
  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.
  25  */
  26
  27
  28 #include "gnushogi.h"
  29
  30 #if defined DEBUG && !defined EXTPATTERNFILE
  31 /* #define DEBUG_PATTERN */
  32 /* #define TEST_PATTERN */
  33 #endif
  34
  35
  36 #ifdef DEBUG_PATTERN
  37 #include <assert.h>
  38 #endif
  39
  40
  41 #include "pattern.h"
  42
  43
  44 #ifdef EXTPATTERNFILE
  45
  46 #define MAX_PATTERN_DATA 5000
  47
  48 small_short pattern_data[MAX_PATTERN_DATA];
  49
  50 #define MAX_OPENING_SEQUENCE 20
  51 #define MAX_PATTERN 200
  52
  53 #else
  54
  55 /* constants and pattern_data are generated by "pat2inc" */
  56
  57 #include "pattern.inc"
  58
  59 #endif
  60
  61 struct Pattern_rec Pattern[MAX_PATTERN];
  62 struct OpeningSequence_rec OpeningSequence[MAX_OPENING_SEQUENCE];
  63
  64
  65
  66 #if defined DEBUG || defined DEBUG_EVAL
  67 static small_ushort sequence_id;
  68 #endif
  69
  70
  71
  72 short ValueOfOpeningName (char *name)
  73 {
  74   short i;
  75   i = (name[0] == 'C') ? 0 : 100;
  76   switch ( name[7] ) {
  77     case 'S' : i += 10; break;
  78     case 'R' : i += 20; break;
  79     case 'U' : i += 30; break;
  80     default  : i += 40; break;
  81   }
  82   switch ( name[9] ) {
  83     case 'S' : i += 1; break;
  84     case 'R' : i += 2; break;
  85     case 'U' : i += 3; break;
  86     default  : i += 4; break;
  87   }
  88   return(i);
  89 }
  90
  91
  92 void NameOfOpeningValue (short i, char *name)
  93 {
  94   if ( i < 100 )
  95     strcpy(name,"CASTLE_?_?");
  96   else {
  97     strcpy(name,"ATTACK_?_?");
  98     i -= 100;
  99   }
 100   switch ( i / 10 ) {
 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;
 105   }
 106   switch ( i % 10 ) {
 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;
 111   }
 112 }
 113
 114
 115 #ifdef EXTPATTERNFILE
 116
 117 char *patternfile = PATTERNFILE;
 118
 119 #define is_digit(c) ((c) >= '0' && (c) <= '9')
 120 #define is_alfa(c) ((c) >= 'a' && (c) <= 'z' || (c) >= 'A' && (c) <= 'Z')
 121
 122 #define eos(s) (*s == '\0' || *s == '\n')
 123
 124
 125 /* skip blanks and comments in brackets */
 126
 127 static void skipbb(char **s)
 128  { while (**s == ' ' || **s == '|' || **s == '[') {
 129      if ( **s == '[' )
 130        while (**s != ']') (*s)++;
 131      (*s)++;
 132    } \
 133  }
 134
 135 /* skip unsigned numbers */
 136
 137 static void skipi(char **s)
 138  {
 139    while ( is_digit(**s) )
 140      (*s)++;
 141    skipbb(s);
 142  }
 143
 144
 145 static
 146 short
 147 ScanPiece (char **s, small_short *side, small_short *piece, small_short *square)
 148 {
 149   short isp, isw, c, r;
 150
 151   /* determine promotion status */
 152   if ( **s == '+' )
 153     isp = true, (*s)++;
 154   else
 155     isp = false;
 156   /* determine side and piece */
 157   for (c = 0; c < NO_PIECES; c++)
 158     if ((isw = (**s == pxx[c])) || **s == qxx[c])
 159       {
 160         *piece = isp ? promoted[c] : unpromoted[c];
 161         *side  = isw;
 162         (*s)++;
 163         break;
 164       }
 165   if (c == NO_PIECES)
 166     return(1);
 167   if ( **s == '*' )
 168     {
 169       /* piece is captured */
 170       (*s)++;
 171       *square = NO_SQUARES + *piece;
 172     }
 173   else
 174     {
 175       /* determine column */
 176       for (c = 0; c < NO_COLS; c++)
 177         if (**s == cxx[c])
 178           {
 179             (*s)++;
 180             break;
 181           }
 182       if (c >= NO_COLS)
 183         return(1);
 184       /* determine row */
 185       for (r = 0; r < NO_ROWS; r++)
 186         if (**s == rxx[r])
 187           {
 188             (*s)++;
 189             break;
 190           }
 191       if (r >= NO_ROWS) return(1);
 192       /* determine square */
 193       *square = r*NO_COLS + c;
 194     }
 195   skipbb(s);
 196   return(0);
 197 }
 198
 199
 200 static
 201 short
 202 ScanPattern (char *s, short *pindex)
 203 {
 204   small_short side, piece, square;
 205   skipbb(&s); /* skip blanks and comments */
 206   while ( is_digit(*s) ) {
 207     pattern_data[(*pindex)++] = atoi(s);
 208     skipi(&s);
 209   }
 210   pattern_data[(*pindex)++] = END_OF_LINKS;
 211   skipbb(&s);
 212   while ( !eos(s) ) {
 213       if ( ScanPiece(&s, &side, &piece, &square) ) {
 214         return(1);
 215       } else {
 216         pattern_data[(*pindex)++] = piece;
 217         pattern_data[(*pindex)++] = (side ? -square : square);
 218       }
 219   }
 220   pattern_data[(*pindex)++] = END_OF_FIELDS;
 221   return(0);
 222 }
 223
 224
 225 void
 226 ReadOpeningSequences (short *pindex)
 227
 228 {
 229     FILE *fd;
 230     char s[256];
 231     short max_pattern = 0;
 232     short max_opening_sequence = 0;
 233
 234     if ( (fd = fopen (patternfile, "r")) == NULL )
 235         fd = fopen ("gnushogi.pat", "r");
 236
 237     if ( fd != NULL ) {
 238         *pindex = 0;
 239         while ( fgets (s, 256, fd) != NULL )
 240           {
 241             if ( *s == '#' ) {
 242               /* comment, skip line */
 243             } else if ( is_alfa(*s) ) {
 244                 if ( max_opening_sequence++ > 0 ) {
 245                   pattern_data[(*pindex)++] = END_OF_PATTERNS;
 246                 }
 247                 pattern_data[(*pindex)++] = ValueOfOpeningName(s);
 248             } else {
 249                 if ( ScanPattern(s,pindex) ) {
 250                     ShowMessage("error in pattern sequence...");
 251                     exit(1);
 252                 } else {
 253                     max_pattern++;
 254                 }
 255             }
 256           }
 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);
 262         ShowMessage(s);
 263 #endif
 264         fclose(fd);
 265     }
 266 #if defined NONDSP || defined MSDOS
 267       else {
 268         sprintf(s, "no pattern file '%s'",patternfile);
 269         ShowMessage(s);
 270     }
 271 #endif
 272 }
 273
 274
 275 void
 276 WriteOpeningSequences (short pindex)
 277 {
 278   FILE *fd;
 279   short n = 0;
 280   short max_pattern = 0;
 281   short max_opening_sequence = 0;
 282
 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");
 286   do {
 287     fprintf(fd,"  %d,\n",pattern_data[n++]);
 288     do {
 289       fprintf(fd,"    ");
 290       /* write links */
 291       while ( pattern_data[n] != END_OF_LINKS ) {
 292         fprintf(fd,"%d, ",pattern_data[n++]);
 293       };
 294       fprintf(fd,"%d, ",pattern_data[n++]);
 295       /* write pattern */
 296       do {
 297         fprintf(fd,"%d,",pattern_data[n++]);
 298       } while ( pattern_data[n] != END_OF_FIELDS );
 299       fprintf(fd,"%d,\n",pattern_data[n++]);
 300       max_pattern++;
 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++]);
 306 #ifdef DEBUG_PATTERN
 307   assert(n == pindex);
 308 #endif
 309   fprintf(fd,"\n#define MAX_OPENING_SEQUENCE %d\n",max_opening_sequence);
 310   fprintf(fd,"\n#define MAX_PATTERN %d\n",max_pattern);
 311   fclose(fd);
 312 }
 313
 314
 315 #endif
 316
 317
 318
 319 void
 320 GetOpeningPatterns (short *max_opening_sequence)
 321
 322 {
 323   short pindex = 0;
 324   short os = 0;
 325   short p = 0;
 326   short i;
 327
 328   do {
 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;
 333     do {
 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++;
 338       pindex++;
 339       Pattern[p].first_field = pindex;
 340       while ( pattern_data[pindex] != END_OF_FIELDS ) pindex += 2;
 341       pindex++;
 342       if ( pattern_data[pindex] != END_OF_PATTERNS )
 343         Pattern[p].next_pattern = p+1;
 344       else
 345         Pattern[p].next_pattern = END_OF_PATTERNS;
 346       p++;
 347     } while (pattern_data[pindex] != END_OF_PATTERNS );
 348     pindex++;
 349     os++;
 350   } while ( pattern_data[pindex] != END_OF_SEQUENCES );
 351   *max_opening_sequence = os;
 352 }
 353
 354
 355
 356 void
 357 ShowOpeningPatterns (short max_opening_sequence)
 358
 359 {
 360   short os, p, n, i;
 361
 362   for ( os=0; os<max_opening_sequence; os++ ) {
 363     char name[16];
 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]);
 370       }
 371       printf("\n");
 372       DisplayPattern(stdout,Pattern[p].first_field);
 373     }
 374   }
 375
 376 }
 377
 378
 379 void set_field (short i, struct PatternField *field)
 380 {
 381       field->piece  = pattern_data[i];
 382       field->square = pattern_data[i+1];
 383       if ( field->square < 0 ) {
 384         field->square = -(field->square);
 385         field->side  = white;
 386       } else {
 387         field->side  = black;
 388       }
 389 }
 390
 391
 392
 393 short
 394 piece_to_pattern_distance
 395   (short side, short piece, short pside, short pattern)
 396
 397 /*
 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".
 402  */
 403 {
 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 */
 407
 408   /*
 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.
 412    */
 413
 414   /* special pawn handling */
 415
 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);
 424         dd = CANNOT_REACH;
 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);
 433 #ifdef TEST_PATTERN
 434                 printf("update %d pawn from %d to %d is %d\n", side, sq, t, dd);
 435 #endif
 436                 break;
 437               }
 438             }
 439           }
 440         } else {
 441           /* there is no pawn on the column; drop possible? */
 442           if ( Captured[c1][pawn] ) {
 443             dd = 1;
 444 #ifdef TEST_PATTERN
 445             printf("update %d pawn drop to %d is %d\n", side, t, dd);
 446 #endif
 447           }
 448         }
 449         if ( dd >= 0 ) {
 450           /* Increment distance if pattern field is occupied */
 451           short psq, pc;
 452           if ( pside == black ) {
 453             psq = t;
 454             pc = field.side;
 455           } else {
 456             psq = (NO_SQUARES - 1 - t);
 457             pc = ~field.side;
 458           }
 459           if ( (color[psq] == pc) && (board[psq] != pawn) ) {
 460 #ifdef TEST_PATTERN
 461             printf("square %d is occupied\n", psq);
 462 #endif
 463             ++occupied;
 464           }
 465           mindd += dd;
 466         } else {
 467           return (CANNOT_REACH);
 468         }
 469       }
 470     }
 471     return (mindd + occupied);
 472   }
 473
 474   /*
 475    * Determine list of "side" "piece"s in pattern.
 476    */
 477
 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) ) {
 482           short psq, pc;
 483           P[nP] = field.square;
 484 #ifdef TEST_PATTERN
 485           printf("pattern %d piece %d on square %d\n",side,piece,P[nP]);
 486 #endif
 487           nP++;
 488           /* Increment distance if pattern field is occupied */
 489           if ( pside == black ) {
 490             psq = field.square;
 491             pc = field.side;
 492           } else {
 493             psq = (NO_SQUARES - 1 - field.square);
 494             pc = field.side ^ 1;
 495           }
 496           if ( (color[psq] == pc) && (board[psq] != field.piece) ) {
 497 #ifdef TEST_PATTERN
 498             printf("square %d is occupied\n", psq);
 499 #endif
 500             ++occupied;
 501           }
 502         }
 503   }
 504
 505   if ( nP == 0 )
 506     return (0);
 507
 508 #ifdef TEST_PATTERN
 509   printf("finding in pattern %d pieces %d of side %d\n", nP, piece, side);
 510 #endif
 511
 512   /*
 513    * Determine list of "side ^ pside" "piece"s captured or on board.
 514    */
 515
 516   for ( nB = 0; nB < Captured[c1][piece]; nB++ )
 517     B[nB] = NO_SQUARES + piece;
 518
 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);
 523 #ifdef TEST_PATTERN
 524           printf("%d piece %d on square %d\n",side,piece,B[nB]);
 525 #endif
 526           nB++;
 527         }
 528   }
 529
 530 #ifdef TEST_PATTERN
 531   printf("found on board %d pieces %d of side %d\n", nB, piece, side);
 532 #endif
 533
 534   if ( nP > nB ) {
 535     return (CANNOT_REACH);
 536   }
 537
 538   /* Determine best assignment from board piece to pattern piece */
 539
 540   r = 0; c[0] = -1; mindd = CANNOT_REACH;
 541
 542   while ( (r >= 0) && (mindd != 0) ) {
 543
 544     if ( ++c[r] == nB ) {
 545         r--;
 546     } else {
 547         for ( i = 0; i < r; i++ )
 548           if ( c[i] == c[r] )
 549             break;
 550         if ( i == r ) {
 551           d[r] =  piece_distance (side, piece, B[c[r]], P[r]);
 552 #ifdef TEST_PATTERN
 553           printf("update d[%d] from  %d to %d is %d\n", r, B[c[r]], P[r], d[r]);
 554 #endif
 555           if ( d[r] < 0 ) {
 556             /* r--; */
 557           } else {
 558             if ( ++r == nP ) {
 559                 for (dd = i = 0; i < nP; i++)
 560                   dd += d[i];
 561                 if ( (dd < mindd) || (mindd < 0) ) {
 562                   mindd = dd;
 563 #ifdef TEST_PATTERN
 564                   printf("update min %d\n", mindd);
 565 #endif
 566                 }
 567                 r--;
 568             } else
 569                 c[r] = -1;
 570           }
 571         }
 572     }
 573
 574   }
 575
 576   if ( mindd < 0 )
 577     return (CANNOT_REACH);
 578   else
 579     return (mindd + occupied);
 580
 581 }
 582
 583
 584 short
 585 pattern_distance (short pside, short pattern)
 586
 587 /*
 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
 591  * of moves.
 592  */
 593
 594 {
 595    short side, piece, d, n;
 596
 597 #ifdef TEST_PATTERN
 598    printf("\nchecking pattern %d for pside=%d\n\n",pattern,pside);
 599 #endif
 600
 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);
 604         if ( d < 0 ) {
 605           n = CANNOT_REACH; break;
 606         } else
 607           n += d;
 608      }
 609
 610 #ifdef TEST_PATTERN
 611    printf("\ndistance to pattern is %d\n\n",n);
 612 #endif
 613
 614    return (n);
 615
 616 }
 617
 618
 619 short
 620 board_to_pattern_distance
 621   (short pside, short osequence, short pmplty, short GameCnt)
 622
 623 /*
 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.
 629  */
 630
 631 {
 632    short i, d, dist, diff, weighted_diff;
 633    short maxdiff = 0, max_weighted_diff = 0;
 634    short pattern;
 635
 636 #ifdef DEBUG_EVAL
 637    if ( debug_eval ) {
 638      char name[MAX_NAME];
 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);
 642    }
 643 #endif
 644
 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 ) {
 647 #ifdef DEBUG_EVAL
 648      if ( debug_eval )
 649        fprintf(debug_eval_file,"%spattern %d",
 650                         (i?"common ":""),pattern);
 651 #endif
 652      if ( (d = Pattern[pattern].distance[pside]) >= 0 ) {
 653 #ifdef DEBUG_EVAL
 654        if ( debug_eval )
 655            fprintf(debug_eval_file," initially reachable in %d steps\n",d);
 656 #endif
 657        if ( pmplty > d )
 658          {
 659            dist = pattern_distance (pside, pattern);
 660            if ( dist >= 0 )
 661              {
 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.
 665                 */
 666 #ifdef DEBUG_EVAL
 667                if ( debug_eval ) {
 668                   fprintf(debug_eval_file," now reachable in %d steps\n",dist);
 669                   DisplayPattern(debug_eval_file,Pattern[pattern].first_field);
 670                }
 671 #endif
 672                /* try to reach the nearest pattern */
 673                weighted_diff = (diff = (d - dist)) * (pmplty - d);
 674                if ( weighted_diff > max_weighted_diff ) {
 675 #ifdef COUNT_DIFF
 676                   maxdiff = diff;
 677 #else
 678                   maxdiff = weighted_diff;
 679 #endif
 680                   max_weighted_diff = weighted_diff;
 681 #ifdef DEBUG_EVAL
 682                   if ( debug_eval )
 683                      fprintf(debug_eval_file,"current maximum gain %d\n",maxdiff);
 684 #endif
 685                }
 686 #ifdef DEBUG_EVAL
 687                else {
 688                   if ( debug_eval )
 689                      fprintf(debug_eval_file,"gain %d\n",diff);
 690                }
 691 #endif
 692                /* A reached pattern should not be considered in the future (if GameCnt >= 0) */
 693                if ( dist == 0 && GameCnt >= 0)
 694                  {
 695                    Pattern[pattern].reachedGameCnt[pside] = GameCnt;
 696 #ifdef DEBUG_EVAL
 697                    if ( debug_eval )
 698                      fprintf(debug_eval_file,"pattern reached in move %d\n",GameCnt);
 699 #endif
 700                  }
 701              }
 702 #ifdef DEBUG_EVAL
 703            else
 704             if ( debug_eval )
 705               fprintf(debug_eval_file," now unreachable\n");
 706 #endif
 707          }
 708 #ifdef DEBUG_EVAL
 709        else
 710          {
 711            if ( debug_eval )
 712              fprintf(debug_eval_file," beyond %d steps\n",pmplty);
 713          }
 714 #endif
 715      }
 716 #ifdef DEBUG_EVAL
 717      else {
 718        if ( debug_eval )
 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");
 723      }
 724 #endif
 725    }
 726
 727    return (maxdiff);
 728
 729 }
 730
 731
 732 void
 733 DisplayPattern (FILE *fd, short n)
 734
 735 {
 736   small_short pboard[NO_SQUARES], pcolor[NO_SQUARES];
 737   short sq, i,  r, c;
 738
 739   for (sq = 0; sq < NO_SQUARES; sq++)
 740     {
 741       pboard[sq] = no_piece;
 742       pcolor[sq] = neutral;
 743     }
 744
 745   for (i = n; pattern_data[i] != END_OF_FIELDS; i += 2)
 746     {
 747       struct PatternField field;
 748       set_field(i,&field);
 749       pboard[field.square] = field.piece;
 750       pcolor[field.square] = field.side;
 751     }
 752
 753   for (r = NO_ROWS-1; r >= 0; r--)
 754     {
 755       for (c = 0; c < NO_COLS; c++)
 756         {
 757           sq = r*NO_COLS + c;
 758           i = pboard[sq];
 759           if ( i == no_piece )
 760             fprintf(fd," -");
 761           else
 762             fprintf(fd,"%c%c",is_promoted[i]?'+':' ',pcolor[sq]?pxx[i]:qxx[i]);
 763         }
 764       fprintf(fd,"\n");
 765     }
 766
 767   fprintf(fd,"\n");
 768
 769 }
 770
 771
 772
 773
 774 static
 775 void
 776 VisitReachable (int pside, short osequence, int k, int n, int remove)
 777 {
 778   short i,j;
 779   short pattern;
 780
 781 #ifdef DEBUG_PATTERN
 782   printf("visit reachable %d %d %s\n",k,n,remove?"remove":"");
 783 #endif
 784
 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;
 788
 789 #ifdef DEBUG_PATTERN
 790   printf("pattern id = %d\n",pattern);
 791 #endif
 792
 793   /* do not perform visited link twice */
 794   if ( Pattern[pattern].visited ) {
 795 #ifdef DEBUG_PATTERN
 796       printf("pattern %d %d visited\n",n,pattern);
 797 #endif
 798       return;
 799   } else
 800       Pattern[pattern].visited = true;
 801
 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);
 805
 806   /* Declare unreachable */
 807   if ( remove && Pattern[pattern].distance[pside] >= 0 )  {
 808     Pattern[pattern].distance[pside] = IS_SUCCESSOR;
 809 #ifdef DEBUG_PATTERN
 810     printf("removing %d\n",n);
 811 #endif
 812   }
 813
 814 }
 815
 816
 817 /* simplified matching for opening type names */
 818
 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]))
 821
 822
 823 short locate_opening_sequence(short pside, char *s, short GameCnt)
 824
 825 {
 826    short i,j,k, os, removed, d;
 827 #ifdef DEBUG_PATTERN
 828    short n = 0, m = 0;
 829 #endif
 830    short l = strlen(s);
 831    short check_visited[MAX_SEQUENCE];
 832    char name[MAX_NAME], name2[MAX_NAME];
 833
 834   /*
 835    * Look for opening pattern name in the list of opening patterns.
 836    */
 837
 838    name[0] = '\0';
 839    for ( i = 1,os = 0; os<MAX_OPENING_SEQUENCE; os++ )
 840      {
 841         /* locate matching opening type name */
 842         NameOfOpeningValue(OpeningSequence[os].opening_type,name);
 843 #ifdef notdef
 844         printf("try to match %s with %s\n",s,name);
 845 #endif
 846         if ( match_name(s,name,l) ) {
 847 #ifdef DEBUG_PATTERN
 848           printf("%s matches pattern %d %s\n",s,os,name);
 849 #endif
 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) ) {
 854 #ifdef DEBUG_PATTERN
 855               printf("%s matches pattern %d %s [%d]\n",s,k,name2,i);
 856 #endif
 857               OpeningSequence[os].first_pattern[i++] = OpeningSequence[k].first_pattern[0];
 858             }
 859           }
 860           break;
 861         }
 862      }
 863
 864    if ( os>=MAX_OPENING_SEQUENCE )
 865      return(END_OF_SEQUENCES);
 866    else
 867      for ( ; i<MAX_SEQUENCE; OpeningSequence[os].first_pattern[i++] = END_OF_PATTERNS);
 868
 869 #ifdef DEBUG_PATTERN
 870    printf("%s uses opening line %s\n",ColorStr[pside],name);
 871 #endif
 872
 873   /*
 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.
 877    */
 878
 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;
 883    }
 884
 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 )
 887      {
 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;
 892 #ifdef DEBUG_PATTERN
 893          printf("pattern id=%d removed because reached\n",k);
 894          DisplayPattern(stdout,Pattern[k].first_field);
 895 #endif
 896          check_visited[i] = Pattern[k].visited = true;
 897          for (j=Pattern[k].first_link; pattern_data[j]!=END_OF_LINKS; j++) {
 898 #ifdef DEBUG_PATTERN
 899            printf("visit successors for link %d\n",pattern_data[j]);
 900 #endif
 901            VisitReachable(pside,os,i,pattern_data[j],false);
 902          }
 903        } else if ( GameCnt >= 0 && GameCnt >= Pattern[k].reachedGameCnt[pside] ) {
 904          Pattern[k].distance[pside] = IS_REACHED;
 905 #ifdef DEBUG_PATTERN
 906          printf("pattern %d removed because reached at GameCnt %d below current %d\n",
 907                         k,Pattern[k].reachedGameCnt[pside],GameCnt);
 908 #endif
 909        }
 910        if ( Pattern[k].reachedGameCnt[pside] >= GameCnt )
 911          Pattern[k].reachedGameCnt[pside] = MAXMOVES;
 912      }
 913
 914   /*
 915    * Remove reachable patterns from search, which are successors of
 916    * reachable patterns. So, only the next pattern of a pattern sequence
 917    * is observed.
 918    */
 919
 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;
 924 #ifdef DEBUG_PATTERN
 925          printf("pattern id = %d removed because no successor of reached pattern\n",
 926                         k);
 927 #endif
 928        } else
 929          Pattern[k].visited = false;
 930     }
 931
 932 #ifdef DEBUG_PATTERN
 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);
 937         printf("%d %s\n",k,
 938                   (d == NOT_TO_REACH) ? " not to reach" :
 939                   (d == IS_REACHED) ? " is reached" :
 940                   (d == IS_SUCCESSOR) ? " is successor" : " cannot reach");
 941     }
 942 #endif
 943
 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++) {
 948 #ifdef DEBUG_PATTERN
 949          printf("removing successors for link %d\n",pattern_data[j]);
 950 #endif
 951          VisitReachable(pside,os,i,pattern_data[j],true);
 952        }
 953      }
 954
 955   /*
 956    * Look, whether there is still a reachable pattern.
 957    */
 958
 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 )
 962        {
 963 #ifdef DEBUG_PATTERN
 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 )
 967               m++;
 968          printf("%d reachable %s patterns out of %d patterns\n",
 969                         m,ColorStr[pside],n);
 970 #endif
 971          return(os);
 972        }
 973
 974 #ifdef DEBUG_PATTERN
 975    printf("all %s patterns out of %d patterns (%d reachable) removed\n",
 976                 ColorStr[pside],n,m);
 977 #endif
 978
 979    return (END_OF_SEQUENCES);
 980 }
 981
 982
 983 void update_advance_bonus (short pside, short os)
 984 {
 985    struct PatternField field;
 986    short i, j, k, d;
 987
 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 )
 991        {
 992           for ( i = Pattern[k].first_field; pattern_data[i]!=END_OF_FIELDS; i+=2 ) {
 993             set_field(i,&field);
 994             if ( field.side == black ) {
 995                 short square = (pside == black)
 996                                 ? field.square
 997                                 : NO_SQUARES - 1 - field.square;
 998                 (*Mpiece[field.piece])[pside][square] += ADVNCM[field.piece];
 999             }
1000           }
1001        }
1002 }