Make UpdateClocks and input-polling dspwrappers-based too.
[gnushogi.git] / gnushogi / pattern.c
1 /*
2  * FILE: pattern.c
3  *
4  * ----------------------------------------------------------------------
5  * Copyright (c) 1993, 1994, 1995 Matthias Mutz
6  * Copyright (c) 1999 Michael Vanier and the Free Software Foundation
7  *
8  * GNU SHOGI is based on GNU CHESS
9  *
10  * Copyright (c) 1988, 1989, 1990 John Stanback
11  * Copyright (c) 1992 Free Software Foundation
12  *
13  * This file is part of GNU SHOGI.
14  *
15  * GNU Shogi is free software; you can redistribute it and/or modify it
16  * under the terms of the GNU General Public License as published by the
17  * Free Software Foundation; either version 3 of the License,
18  * or (at your option) any later version.
19  *
20  * GNU Shogi is distributed in the hope that it will be useful, but WITHOUT
21  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
22  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
23  * for more details.
24  *
25  * You should have received a copy of the GNU General Public License along
26  * with GNU Shogi; see the file COPYING. If not, see
27  * <http://www.gnu.org/licenses/>.
28  * ----------------------------------------------------------------------
29  *
30  */
31
32 #include "gnushogi.h"
33 #include "pattern.h"
34
35 /* constants and pattern_data are generated by "pat2inc" */
36 #include "pattern.inc"
37
38 struct Pattern_rec Pattern[MAX_PATTERN];
39 struct OpeningSequence_rec OpeningSequence[MAX_OPENING_SEQUENCE];
40
41 small_short pattern_data[MAX_PATTERN_DATA];
42
43
44 short
45 ValueOfOpeningName (char *name)
46 {
47     short i;
48     i = (name[0] == 'C') ? 0 : 100;
49
50     switch (name[7])
51     {
52     case 'S':
53         i += 10;
54         break;
55
56     case 'R':
57         i += 20;
58         break;
59
60     case 'U':
61         i += 30;
62         break;
63
64     default:
65         i += 40;
66         break;
67     }
68
69     switch (name[9])
70     {
71     case 'S':
72         i += 1;
73         break;
74
75     case 'R':
76         i += 2;
77         break;
78
79     case 'U':
80         i += 3;
81         break;
82
83     default:
84         i += 4;
85         break;
86     }
87
88     return i;
89 }
90
91
92 static void
93 NameOfOpeningValue (short i, char *name)
94 {
95     if (i < 100)
96     {
97         strcpy(name, "CASTLE_?_?");
98     }
99     else
100     {
101         strcpy(name, "ATTACK_?_?");
102         i -= 100;
103     }
104
105     switch (i / 10)
106     {
107     case 1:
108         name[7] = 'S';
109         break;
110
111     case 2:
112         name[7] = 'R';
113         break;
114
115     case 3:
116         name[7] = 'U';
117         break;
118
119     default:
120         name[7] = '*';
121         break;
122     }
123
124     switch (i % 10)
125     {
126     case 1:
127         name[9] = 'S';
128         break;
129
130     case 2:
131         name[9] = 'R';
132         break;
133
134     case 3:
135         name[9] = 'U';
136         break;
137
138     default:
139         name[9] = '*';
140         break;
141     }
142 }
143
144
145 void
146 GetOpeningPatterns (short *max_opening_sequence)
147 {
148     short pindex = 0;
149     short os = 0;
150     short p = 0;
151     short i;
152
153     do
154     {
155         OpeningSequence[os].opening_type = pattern_data[pindex++];
156         OpeningSequence[os].first_pattern[0] = p;
157
158         for (i = 1; i < MAX_SEQUENCE; i++)
159             OpeningSequence[os].first_pattern[i] = END_OF_PATTERNS;
160
161         do
162         {
163             Pattern[p].reachedGameCnt[black] = MAXMOVES;
164             Pattern[p].reachedGameCnt[white] = MAXMOVES;
165             Pattern[p].first_link = pindex;
166
167             while (pattern_data[pindex] != END_OF_LINKS)
168                 pindex++;
169             pindex++;
170
171             Pattern[p].first_field = pindex;
172
173             while (pattern_data[pindex] != END_OF_FIELDS)
174                 pindex += 2;
175             pindex++;
176
177             if (pattern_data[pindex] != END_OF_PATTERNS)
178                 Pattern[p].next_pattern = p + 1;
179             else
180                 Pattern[p].next_pattern = END_OF_PATTERNS;
181
182             p++;
183         }
184         while (pattern_data[pindex] != END_OF_PATTERNS);
185
186         pindex++;
187         os++;
188     }
189     while (pattern_data[pindex] != END_OF_SEQUENCES);
190
191     *max_opening_sequence = os;
192 }
193
194
195
196 void
197 ShowOpeningPatterns (short max_opening_sequence)
198
199 {
200     short os, p, n, i;
201
202     for (os = 0; os < max_opening_sequence; os++)
203     {
204         char name[16];
205         NameOfOpeningValue(OpeningSequence[os].opening_type, name);
206         printf("Opening Type: %s\n", name);
207
208         for (p = OpeningSequence[os].first_pattern[0], n = 0;
209              p != END_OF_PATTERNS;
210              p = Pattern[p].next_pattern, n++)
211         {
212             printf("Pattern %d (%d) with links ", p, n);
213
214             for (i = Pattern[p].first_link;
215                  pattern_data[i] != END_OF_LINKS;
216                  i++)
217             {
218                 printf("%d ", pattern_data[i]);
219             }
220
221             printf("\n");
222             DisplayPattern(stdout, Pattern[p].first_field);
223         }
224     }
225 }
226
227
228
229 void
230 set_field (short i, struct PatternField *field)
231 {
232     field->piece  = pattern_data[i];
233     field->square = pattern_data[i+1];
234
235     if (field->square < 0)
236     {
237         field->square = -(field->square);
238         field->side   = white;
239     }
240     else
241     {
242         field->side  = black;
243     }
244 }
245
246
247
248 /*
249  * piece_to_pattern_distance (side, piece, pside, pattern)
250  *
251  * Determine the minimum number of moves from the current position to a
252  * specific pattern for a specific piece.  Consider the "side" piece of the
253  * pattern.  The pattern should match for "pside".
254  */
255
256 short
257 piece_to_pattern_distance(short side, short piece,
258                           short pside, short pattern)
259 {
260     short nP, P[4], nB, B[4]; /* at most 4 pieces of same kind */
261     short i, j, r, dd, occupied, mindd, c[4], d[4];
262     /* a "side" patternfield must match a "c1" piece on board: */
263     short c1 = side ^ pside;
264
265     /*
266      * If pside == white, a black piece in the pattern should match a white
267      * piece on board, and vice versa. Furthermore, if pside == white,
268      * reversed pattern should match board.
269      */
270
271     /* special pawn handling */
272
273     if (piece == pawn)
274     {
275         mindd = occupied = 0;
276
277         for (i = Pattern[pattern].first_field;
278              pattern_data[i] != END_OF_FIELDS;
279              i += 2)
280         {
281             struct PatternField field;
282             set_field(i, &field);
283
284             if ((field.side == side) && (field.piece == pawn))
285             {
286                 short t = field.square;
287                 short pcol = column(t);
288                 dd = CANNOT_REACH;
289
290                 if (PawnCnt[c1][(side == c1) ? pcol : (8 - pcol)])
291                 {
292                     /* there is a pawn on the column */
293                     for (j = 0; j <= PieceCnt[c1]; j++)
294                     {
295                         short sq = (short)PieceList[c1][j];
296
297                         if (board[sq] == pawn)
298                         {
299                             if (pside == white)
300                                 sq = NO_SQUARES - 1 - sq;
301
302                             if (column(sq) == pcol)
303                             {
304                                 dd = piece_distance (side, pawn, sq, t);
305 #ifdef TEST_PATTERN
306                                 printf("update %d pawn "
307                                        "from %d to %d is %d\n",
308                                        side, sq, t, dd);
309 #endif
310                                 break;
311                             }
312                         }
313                     }
314                 }
315                 else
316                 {
317                     /* there is no pawn on the column; drop possible? */
318                     if (Captured[c1][pawn])
319                     {
320                         dd = 1;
321 #ifdef TEST_PATTERN
322                         printf("update %d pawn drop to %d is %d\n",
323                                side, t, dd);
324 #endif
325                     }
326                 }
327
328                 if (dd >= 0)
329                 {
330                     /* Increment distance if pattern field is occupied */
331                     short psq, pc;
332
333                     if (pside == black)
334                     {
335                         psq = t;
336                         pc = field.side;
337                     }
338                     else
339                     {
340                         psq = (NO_SQUARES - 1 - t);
341                         pc = ~field.side;
342                     }
343
344                     if ((color[psq] == pc) && (board[psq] != pawn))
345                     {
346 #ifdef TEST_PATTERN
347                         printf("square %d is occupied\n", psq);
348 #endif
349                         ++occupied;
350                     }
351
352                     mindd += dd;
353                 }
354                 else
355                 {
356                     return CANNOT_REACH;
357                 }
358             }
359         }
360
361         return mindd + occupied;
362     }
363
364     /*
365      * Determine list of "side" "piece"s in pattern.
366      */
367
368     for (occupied = nP = 0, i = Pattern[pattern].first_field;
369          pattern_data[i] != END_OF_FIELDS;
370          i += 2)
371     {
372         struct PatternField field;
373         set_field(i, &field);
374
375         if ((field.side == side) && (field.piece == piece))
376         {
377             short psq, pc;
378             P[nP] = field.square;
379 #ifdef TEST_PATTERN
380             printf("pattern %d piece %d on square %d\n", side, piece, P[nP]);
381 #endif
382             nP++;
383
384             /* Increment distance if pattern field is occupied */
385             if (pside == black)
386             {
387                 psq = field.square;
388                 pc = field.side;
389             }
390             else
391             {
392                 psq = NO_SQUARES - 1 - field.square;
393                 pc  = field.side ^ 1;
394             }
395
396             if ((color[psq] == pc) && (board[psq] != field.piece))
397             {
398 #ifdef TEST_PATTERN
399                 printf("square %d is occupied\n", psq);
400 #endif
401                 ++occupied;
402             }
403         }
404     }
405
406     if (nP == 0)
407         return 0;
408
409 #ifdef TEST_PATTERN
410     printf("finding in pattern %d pieces %d of side %d\n", nP, piece, side);
411 #endif
412
413     /*
414      * Determine list of "side ^ pside" "piece"s captured or on board.
415      */
416
417     for (nB = 0; nB < Captured[c1][piece]; nB++)
418         B[nB] = NO_SQUARES + piece;
419
420     for (i = 0; i <= PieceCnt[c1]; i++)
421     {
422         short sq = PieceList[c1][i];
423
424         if (board[sq] == piece)
425         {
426             B[nB] = (pside == black) ? sq : (NO_SQUARES - 1 - sq);
427 #ifdef TEST_PATTERN
428             printf("%d piece %d on square %d\n", side, piece, B[nB]);
429 #endif
430             nB++;
431         }
432     }
433
434 #ifdef TEST_PATTERN
435     printf("found on board %d pieces %d of side %d\n", nB, piece, side);
436 #endif
437
438     if (nP > nB)
439     {
440         return CANNOT_REACH;
441     }
442
443     /* Determine best assignment from board piece to pattern piece */
444
445     r = 0;
446     c[0] = -1;
447     mindd = CANNOT_REACH;
448
449     while ((r >= 0) && (mindd != 0))
450     {
451
452         if (++c[r] == nB)
453         {
454             r--;
455         }
456         else
457         {
458             for (i = 0; i < r; i++)
459             {
460                 if (c[i] == c[r])
461                     break;
462             }
463
464             if (i == r)
465             {
466                 d[r] =  piece_distance (side, piece, B[c[r]], P[r]);
467 #ifdef TEST_PATTERN
468                 printf("update d[%d] from  %d to %d is %d\n",
469                        r, B[c[r]], P[r], d[r]);
470 #endif
471                 if (d[r] < 0)
472                 {
473                     /* r--; */
474                 }
475                 else
476                 {
477                     if (++r == nP)
478                     {
479                         for (dd = i = 0; i < nP; i++)
480                             dd += d[i];
481
482                         if ((dd < mindd) || (mindd < 0))
483                         {
484                             mindd = dd;
485 #ifdef TEST_PATTERN
486                             printf("update min %d\n", mindd);
487 #endif
488                         }
489
490                         r--;
491                     }
492                     else
493                     {
494                         c[r] = -1;
495                     }
496                 }
497             }
498         }
499     }
500
501     if (mindd < 0)
502         return CANNOT_REACH;
503     else
504         return (mindd + occupied);
505
506 }
507
508
509
510 /*
511  * pattern_distance (pside, pattern)
512  *
513  * Determine the minimum number of moves for the pieces from
514  * the current position to reach a pattern.
515  * The result is CANNOT_REACH, if there is no possible sequence
516  * of moves.
517  *
518  */
519
520 short
521 pattern_distance (short pside, short pattern)
522 {
523     short side, piece, d, n;
524
525 #ifdef TEST_PATTERN
526     printf("\nchecking pattern %d for pside=%d\n\n", pattern, pside);
527 #endif
528
529     for (n = side = 0; side <= 1 && n >= 0; side++)
530     {
531         for (piece = pawn; piece <= king; piece++)
532         {
533             d = piece_to_pattern_distance (side, piece, pside, pattern);
534
535             if (d < 0)
536             {
537                 n = CANNOT_REACH;
538                 break;
539             }
540             else
541             {
542                 n += d;
543             }
544         }
545     }
546
547 #ifdef TEST_PATTERN
548     printf("\ndistance to pattern is %d\n\n", n);
549 #endif
550
551     return n;
552 }
553
554
555
556 /*
557  * board_to_pattern_distance(pside, osequence, pmplty, GameCnt)
558  *
559  * Determine the maximal difference of the number of moves from the pattern
560  * to the initial position and to the current position.
561  * Differences are weighted, i.e. the more closer a position is to a pattern
562  * the more valuable is a move towards the pattern.
563  * Patterns, which are at least "pmplty" halfmoves away, are not counted.
564  */
565
566 short
567 board_to_pattern_distance
568 (short pside, short osequence, short pmplty, short GameCnt)
569 {
570     short i, d, dist, diff, weighted_diff;
571     short maxdiff = 0, max_weighted_diff = 0;
572     short pattern;
573
574     for (i = 0; i < MAX_SEQUENCE; i++)
575     {
576         for (pattern = OpeningSequence[osequence].first_pattern[i];
577              pattern != END_OF_PATTERNS;
578              pattern = Pattern[pattern].next_pattern)
579         {
580             if ((d = Pattern[pattern].distance[pside]) >= 0)
581             {
582                 if (pmplty > d)
583                 {
584                     dist = pattern_distance (pside, pattern);
585                     if (dist >= 0)
586                     {
587                         /*
588                          * "dist" is the distance of the current board
589                          * position to the pattern.  "d - dist" is the
590                          * difference between the current distance and the
591                          * initial distance. Compute "diff" as the weighted
592                          * difference.
593                          */
594
595                         /* try to reach the nearest pattern */
596                         weighted_diff = (diff = (d - dist)) * (pmplty - d);
597
598                         if (weighted_diff > max_weighted_diff)
599                         {
600 #ifdef COUNT_DIFF
601                             maxdiff = diff;
602 #else
603                             maxdiff = weighted_diff;
604 #endif
605                             max_weighted_diff = weighted_diff;
606                         }
607
608                         /*
609                          * A reached pattern should not be considered in
610                          * the future (if GameCnt >= 0)
611                          */
612
613                         if (dist == 0 && GameCnt >= 0)
614                             Pattern[pattern].reachedGameCnt[pside] = GameCnt;
615                     }
616                 }
617             }
618         }
619     }
620
621     return maxdiff;
622 }
623
624
625
626
627 void
628 DisplayPattern (FILE *fd, short n)
629 {
630     small_short pboard[NO_SQUARES], pcolor[NO_SQUARES];
631     short sq, i,  r, c;
632
633     for (sq = 0; sq < NO_SQUARES; sq++)
634     {
635         pboard[sq] = no_piece;
636         pcolor[sq] = neutral;
637     }
638
639     for (i = n; pattern_data[i] != END_OF_FIELDS; i += 2)
640     {
641         struct PatternField field;
642         set_field(i, &field);
643         pboard[field.square] = field.piece;
644         pcolor[field.square] = field.side;
645     }
646
647     for (r = NO_ROWS - 1; r >= 0; r--)
648     {
649         for (c = 0; c < NO_COLS; c++)
650         {
651             sq = r*NO_COLS + c;
652             i = pboard[sq];
653
654             if (i == no_piece)
655                 fprintf(fd, " -");
656             else
657                 fprintf(fd, "%c%c", is_promoted[i] ? '+' : ' ',
658                         pcolor[sq] ? pxx[i] : qxx[i]);
659         }
660
661         fprintf(fd, "\n");
662     }
663
664     fprintf(fd, "\n");
665 }
666
667
668
669
670 static void
671 VisitReachable (int pside, short osequence, int k, int n, int remove)
672 {
673     short i, j;
674     short pattern;
675
676     /* Adjust to sequence pattern n */
677     for (i = 0, pattern = OpeningSequence[osequence].first_pattern[k];
678          i < n; i++)
679     {
680         pattern = Pattern[pattern].next_pattern;
681     }
682
683     /* do not perform visited link twice */
684     if (Pattern[pattern].visited)
685     {
686         return;
687     }
688     else
689     {
690         Pattern[pattern].visited = true;
691     }
692
693     /* Declare links unreachable */
694     for (j = Pattern[pattern].first_link;
695          pattern_data[j] != END_OF_LINKS; j++)
696     {
697         VisitReachable(pside, osequence, k, pattern_data[j], remove);
698     }
699
700     /* Declare unreachable */
701     if (remove && Pattern[pattern].distance[pside] >= 0)
702     {
703         Pattern[pattern].distance[pside] = IS_SUCCESSOR;
704     }
705 }
706
707
708 /* simplified matching for opening type names */
709
710 #define match_char(a, b) \
711 (a == b || (a == '*' && b != 'U') || (b == '*' && a != 'U'))
712
713 #define match_name(a, b, l) \
714 (l > 8 && match_char(a[0], b[0]) && match_char(a[7], b[7]) \
715 && match_char(a[9], b[9]))
716
717
718 short
719 locate_opening_sequence(short pside, char *s, short GameCnt)
720 {
721     short i, j, k, os, d;
722     short l = strlen(s);
723     short check_visited[MAX_SEQUENCE];
724     char name[MAX_NAME], name2[MAX_NAME];
725
726     /*
727      * Look for opening pattern name in the list of opening patterns.
728      */
729
730     name[0] = '\0';
731
732     for (i = 1, os = 0; os < MAX_OPENING_SEQUENCE; os++)
733     {
734         /* locate matching opening type name */
735         NameOfOpeningValue(OpeningSequence[os].opening_type, name);
736
737         if (match_name(s, name, l))
738         {
739             /* locate successor matching names */
740             for (k = os + 1; k < MAX_OPENING_SEQUENCE; k++)
741             {
742                 NameOfOpeningValue(OpeningSequence[k].opening_type, name2);
743
744                 if (match_name(s, name2, l))
745                 {
746                     OpeningSequence[os].first_pattern[i++]
747                         = OpeningSequence[k].first_pattern[0];
748                 }
749             }
750
751             break;
752         }
753     }
754
755     if (os >= MAX_OPENING_SEQUENCE)
756     {
757         return END_OF_SEQUENCES;
758     }
759     else
760     {
761         for (; i < MAX_SEQUENCE;
762              OpeningSequence[os].first_pattern[i++] = END_OF_PATTERNS);
763     }
764
765     /*
766      * Determine patterns which can be reached from the current
767      * board position. Only patterns which can be reached will be
768      * checked in the following search.
769      */
770
771     for (i = 0; i < MAX_SEQUENCE; i++)
772     {
773         check_visited[i] = false;
774
775         for (k = OpeningSequence[os].first_pattern[i];
776              k != END_OF_PATTERNS;
777              k = Pattern[k].next_pattern)
778         {
779             Pattern[k].visited = false;
780         }
781     }
782
783     for (i = 0; i < MAX_SEQUENCE; i++)
784     {
785         for (k = OpeningSequence[os].first_pattern[i];
786              k != END_OF_PATTERNS;
787              k = Pattern[k].next_pattern)
788         {
789             Pattern[k].distance[pside] = pattern_distance(pside, k);
790
791             /* Actually reached patterns need not to be observed. */
792             if (Pattern[k].distance[pside] == 0)
793             {
794                 Pattern[k].distance[pside] = CANNOT_REACH;
795                 check_visited[i] = Pattern[k].visited = true;
796
797                 for (j = Pattern[k].first_link;
798                      pattern_data[j] != END_OF_LINKS; j++)
799                 {
800                     VisitReachable(pside, os, i, pattern_data[j], false);
801                 }
802             }
803             else if ((GameCnt >= 0)
804                      && (GameCnt >= Pattern[k].reachedGameCnt[pside]))
805             {
806                 Pattern[k].distance[pside] = IS_REACHED;
807             }
808
809             if (Pattern[k].reachedGameCnt[pside] >= GameCnt)
810                 Pattern[k].reachedGameCnt[pside] = MAXMOVES;
811         }
812     }
813
814     /*
815      * Remove reachable patterns from search, which are successors of
816      * reachable patterns. So, only the next pattern of a pattern sequence
817      * is observed.
818      */
819
820     for (i = 0; i < MAX_SEQUENCE; i++)
821     {
822         for (k = OpeningSequence[os].first_pattern[i];
823              k != END_OF_PATTERNS;
824              k = Pattern[k].next_pattern)
825         {
826             if (check_visited[i] && !Pattern[k].visited)
827                 Pattern[k].distance[pside] = NOT_TO_REACH;
828             else
829                 Pattern[k].visited = false;
830         }
831     }
832
833     for (i = 0; i < MAX_SEQUENCE; i++)
834     {
835         for (k = OpeningSequence[os].first_pattern[i];
836              k != END_OF_PATTERNS;
837              k = Pattern[k].next_pattern)
838         {
839             if ((d = Pattern[k].distance[pside]) >= 0)
840             {
841                 for (j = Pattern[k].first_link;
842                      pattern_data[j] != END_OF_LINKS; j++)
843                 {
844                     VisitReachable(pside, os, i, pattern_data[j], true);
845                 }
846             }
847         }
848     }
849
850     /*
851      * Look to see whether there is still a reachable pattern.
852      */
853
854     for (i = 0; i < MAX_SEQUENCE; i++)
855     {
856         for (k = OpeningSequence[os].first_pattern[i];
857              k != END_OF_PATTERNS;
858              k = Pattern[k].next_pattern)
859         {
860             if ((d = Pattern[k].distance[pside]) >= 0)
861                 return os;
862         }
863     }
864
865     return END_OF_SEQUENCES;
866 }
867
868
869
870
871 void
872 update_advance_bonus (short pside, short os)
873 {
874     struct PatternField field;
875     short i, j, k, d;
876
877     for (j = 0; j < MAX_SEQUENCE; j++)
878     {
879         for (k = OpeningSequence[os].first_pattern[j];
880              k != END_OF_PATTERNS;
881              k = Pattern[k].next_pattern)
882         {
883             if ((d = Pattern[k].distance[pside]) >= 0)
884             {
885                 for (i = Pattern[k].first_field;
886                      pattern_data[i] != END_OF_FIELDS; i += 2)
887                 {
888                     set_field(i, &field);
889                     if (field.side == black)
890                     {
891                         short square = (pside == black)
892                             ? field.square
893                             : NO_SQUARES - 1 - field.square;
894
895                         (*Mpiece[field.piece])[pside][square]
896                             += ADVNCM[field.piece];
897                     }
898                 }
899             }
900         }
901     }
902 }