4 * ----------------------------------------------------------------------
5 * Copyright (c) 1993, 1994, 1995 Matthias Mutz
6 * Copyright (c) 1999 Michael Vanier and the Free Software Foundation
8 * GNU SHOGI is based on GNU CHESS
10 * Copyright (c) 1988, 1989, 1990 John Stanback
11 * Copyright (c) 1992 Free Software Foundation
13 * This file is part of GNU SHOGI.
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 1, or (at your option) any
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
25 * You should have received a copy of the GNU General Public License along
26 * with GNU Shogi; see the file COPYING. If not, write to the Free
27 * Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
28 * ----------------------------------------------------------------------
35 /* constants and pattern_data are generated by "pat2inc" */
36 #include "pattern.inc"
38 struct Pattern_rec Pattern
[MAX_PATTERN
];
39 struct OpeningSequence_rec OpeningSequence
[MAX_OPENING_SEQUENCE
];
41 small_short pattern_data
[MAX_PATTERN_DATA
];
45 ValueOfOpeningName (char *name
)
48 i
= (name
[0] == 'C') ? 0 : 100;
93 NameOfOpeningValue (short i
, char *name
)
97 strcpy(name
, "CASTLE_?_?");
101 strcpy(name
, "ATTACK_?_?");
146 GetOpeningPatterns (short *max_opening_sequence
)
155 OpeningSequence
[os
].opening_type
= pattern_data
[pindex
++];
156 OpeningSequence
[os
].first_pattern
[0] = p
;
158 for (i
= 1; i
< MAX_SEQUENCE
; i
++)
159 OpeningSequence
[os
].first_pattern
[i
] = END_OF_PATTERNS
;
163 Pattern
[p
].reachedGameCnt
[black
] = MAXMOVES
;
164 Pattern
[p
].reachedGameCnt
[white
] = MAXMOVES
;
165 Pattern
[p
].first_link
= pindex
;
167 while (pattern_data
[pindex
] != END_OF_LINKS
)
171 Pattern
[p
].first_field
= pindex
;
173 while (pattern_data
[pindex
] != END_OF_FIELDS
)
177 if (pattern_data
[pindex
] != END_OF_PATTERNS
)
178 Pattern
[p
].next_pattern
= p
+ 1;
180 Pattern
[p
].next_pattern
= END_OF_PATTERNS
;
184 while (pattern_data
[pindex
] != END_OF_PATTERNS
);
189 while (pattern_data
[pindex
] != END_OF_SEQUENCES
);
191 *max_opening_sequence
= os
;
197 ShowOpeningPatterns (short max_opening_sequence
)
202 for (os
= 0; os
< max_opening_sequence
; os
++)
205 NameOfOpeningValue(OpeningSequence
[os
].opening_type
, name
);
206 printf("Opening Type: %s\n", name
);
208 for (p
= OpeningSequence
[os
].first_pattern
[0], n
= 0;
209 p
!= END_OF_PATTERNS
;
210 p
= Pattern
[p
].next_pattern
, n
++)
212 printf("Pattern %d (%d) with links ", p
, n
);
214 for (i
= Pattern
[p
].first_link
;
215 pattern_data
[i
] != END_OF_LINKS
;
218 printf("%d ", pattern_data
[i
]);
222 DisplayPattern(stdout
, Pattern
[p
].first_field
);
230 set_field (short i
, struct PatternField
*field
)
232 field
->piece
= pattern_data
[i
];
233 field
->square
= pattern_data
[i
+1];
235 if (field
->square
< 0)
237 field
->square
= -(field
->square
);
249 * piece_to_pattern_distance (side, piece, pside, pattern)
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".
257 piece_to_pattern_distance(short side
, short piece
,
258 short pside
, short pattern
)
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
;
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.
271 /* special pawn handling */
275 mindd
= occupied
= 0;
277 for (i
= Pattern
[pattern
].first_field
;
278 pattern_data
[i
] != END_OF_FIELDS
;
281 struct PatternField field
;
282 set_field(i
, &field
);
284 if ((field
.side
== side
) && (field
.piece
== pawn
))
286 short t
= field
.square
;
287 short pcol
= column(t
);
290 if (PawnCnt
[c1
][(side
== c1
) ? pcol
: (8 - pcol
)])
292 /* there is a pawn on the column */
293 for (j
= 0; j
<= PieceCnt
[c1
]; j
++)
295 short sq
= (short)PieceList
[c1
][j
];
297 if (board
[sq
] == pawn
)
300 sq
= NO_SQUARES
- 1 - sq
;
302 if (column(sq
) == pcol
)
304 dd
= piece_distance (side
, pawn
, sq
, t
);
306 printf("update %d pawn "
307 "from %d to %d is %d\n",
317 /* there is no pawn on the column; drop possible? */
318 if (Captured
[c1
][pawn
])
322 printf("update %d pawn drop to %d is %d\n",
330 /* Increment distance if pattern field is occupied */
340 psq
= (NO_SQUARES
- 1 - t
);
344 if ((color
[psq
] == pc
) && (board
[psq
] != pawn
))
347 printf("square %d is occupied\n", psq
);
361 return mindd
+ occupied
;
365 * Determine list of "side" "piece"s in pattern.
368 for (occupied
= nP
= 0, i
= Pattern
[pattern
].first_field
;
369 pattern_data
[i
] != END_OF_FIELDS
;
372 struct PatternField field
;
373 set_field(i
, &field
);
375 if ((field
.side
== side
) && (field
.piece
== piece
))
378 P
[nP
] = field
.square
;
380 printf("pattern %d piece %d on square %d\n", side
, piece
, P
[nP
]);
384 /* Increment distance if pattern field is occupied */
392 psq
= NO_SQUARES
- 1 - field
.square
;
396 if ((color
[psq
] == pc
) && (board
[psq
] != field
.piece
))
399 printf("square %d is occupied\n", psq
);
410 printf("finding in pattern %d pieces %d of side %d\n", nP
, piece
, side
);
414 * Determine list of "side ^ pside" "piece"s captured or on board.
417 for (nB
= 0; nB
< Captured
[c1
][piece
]; nB
++)
418 B
[nB
] = NO_SQUARES
+ piece
;
420 for (i
= 0; i
<= PieceCnt
[c1
]; i
++)
422 short sq
= PieceList
[c1
][i
];
424 if (board
[sq
] == piece
)
426 B
[nB
] = (pside
== black
) ? sq
: (NO_SQUARES
- 1 - sq
);
428 printf("%d piece %d on square %d\n", side
, piece
, B
[nB
]);
435 printf("found on board %d pieces %d of side %d\n", nB
, piece
, side
);
443 /* Determine best assignment from board piece to pattern piece */
447 mindd
= CANNOT_REACH
;
449 while ((r
>= 0) && (mindd
!= 0))
458 for (i
= 0; i
< r
; i
++)
466 d
[r
] = piece_distance (side
, piece
, B
[c
[r
]], P
[r
]);
468 printf("update d[%d] from %d to %d is %d\n",
469 r
, B
[c
[r
]], P
[r
], d
[r
]);
479 for (dd
= i
= 0; i
< nP
; i
++)
482 if ((dd
< mindd
) || (mindd
< 0))
486 printf("update min %d\n", mindd
);
504 return (mindd
+ occupied
);
511 * pattern_distance (pside, pattern)
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
521 pattern_distance (short pside
, short pattern
)
523 short side
, piece
, d
, n
;
526 printf("\nchecking pattern %d for pside=%d\n\n", pattern
, pside
);
529 for (n
= side
= 0; side
<= 1 && n
>= 0; side
++)
531 for (piece
= pawn
; piece
<= king
; piece
++)
533 d
= piece_to_pattern_distance (side
, piece
, pside
, pattern
);
548 printf("\ndistance to pattern is %d\n\n", n
);
557 * board_to_pattern_distance(pside, osequence, pmplty, GameCnt)
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.
567 board_to_pattern_distance
568 (short pside
, short osequence
, short pmplty
, short GameCnt
)
570 short i
, d
, dist
, diff
, weighted_diff
;
571 short maxdiff
= 0, max_weighted_diff
= 0;
574 for (i
= 0; i
< MAX_SEQUENCE
; i
++)
576 for (pattern
= OpeningSequence
[osequence
].first_pattern
[i
];
577 pattern
!= END_OF_PATTERNS
;
578 pattern
= Pattern
[pattern
].next_pattern
)
580 if ((d
= Pattern
[pattern
].distance
[pside
]) >= 0)
584 dist
= pattern_distance (pside
, pattern
);
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
595 /* try to reach the nearest pattern */
596 weighted_diff
= (diff
= (d
- dist
)) * (pmplty
- d
);
598 if (weighted_diff
> max_weighted_diff
)
603 maxdiff
= weighted_diff
;
605 max_weighted_diff
= weighted_diff
;
609 * A reached pattern should not be considered in
610 * the future (if GameCnt >= 0)
613 if (dist
== 0 && GameCnt
>= 0)
614 Pattern
[pattern
].reachedGameCnt
[pside
] = GameCnt
;
628 DisplayPattern (FILE *fd
, short n
)
630 small_short pboard
[NO_SQUARES
], pcolor
[NO_SQUARES
];
633 for (sq
= 0; sq
< NO_SQUARES
; sq
++)
635 pboard
[sq
] = no_piece
;
636 pcolor
[sq
] = neutral
;
639 for (i
= n
; pattern_data
[i
] != END_OF_FIELDS
; i
+= 2)
641 struct PatternField field
;
642 set_field(i
, &field
);
643 pboard
[field
.square
] = field
.piece
;
644 pcolor
[field
.square
] = field
.side
;
647 for (r
= NO_ROWS
- 1; r
>= 0; r
--)
649 for (c
= 0; c
< NO_COLS
; c
++)
657 fprintf(fd
, "%c%c", is_promoted
[i
] ? '+' : ' ',
658 pcolor
[sq
] ? pxx
[i
] : qxx
[i
]);
671 VisitReachable (int pside
, short osequence
, int k
, int n
, int remove
)
676 /* Adjust to sequence pattern n */
677 for (i
= 0, pattern
= OpeningSequence
[osequence
].first_pattern
[k
];
680 pattern
= Pattern
[pattern
].next_pattern
;
683 /* do not perform visited link twice */
684 if (Pattern
[pattern
].visited
)
690 Pattern
[pattern
].visited
= true;
693 /* Declare links unreachable */
694 for (j
= Pattern
[pattern
].first_link
;
695 pattern_data
[j
] != END_OF_LINKS
; j
++)
697 VisitReachable(pside
, osequence
, k
, pattern_data
[j
], remove
);
700 /* Declare unreachable */
701 if (remove
&& Pattern
[pattern
].distance
[pside
] >= 0)
703 Pattern
[pattern
].distance
[pside
] = IS_SUCCESSOR
;
708 /* simplified matching for opening type names */
710 #define match_char(a, b) \
711 (a == b || (a == '*' && b != 'U') || (b == '*' && a != 'U'))
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]))
719 locate_opening_sequence(short pside
, char *s
, short GameCnt
)
721 short i
, j
, k
, os
, d
;
723 short check_visited
[MAX_SEQUENCE
];
724 char name
[MAX_NAME
], name2
[MAX_NAME
];
727 * Look for opening pattern name in the list of opening patterns.
732 for (i
= 1, os
= 0; os
< MAX_OPENING_SEQUENCE
; os
++)
734 /* locate matching opening type name */
735 NameOfOpeningValue(OpeningSequence
[os
].opening_type
, name
);
737 if (match_name(s
, name
, l
))
739 /* locate successor matching names */
740 for (k
= os
+ 1; k
< MAX_OPENING_SEQUENCE
; k
++)
742 NameOfOpeningValue(OpeningSequence
[k
].opening_type
, name2
);
744 if (match_name(s
, name2
, l
))
746 OpeningSequence
[os
].first_pattern
[i
++]
747 = OpeningSequence
[k
].first_pattern
[0];
755 if (os
>= MAX_OPENING_SEQUENCE
)
757 return END_OF_SEQUENCES
;
761 for (; i
< MAX_SEQUENCE
;
762 OpeningSequence
[os
].first_pattern
[i
++] = END_OF_PATTERNS
);
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.
771 for (i
= 0; i
< MAX_SEQUENCE
; i
++)
773 check_visited
[i
] = false;
775 for (k
= OpeningSequence
[os
].first_pattern
[i
];
776 k
!= END_OF_PATTERNS
;
777 k
= Pattern
[k
].next_pattern
)
779 Pattern
[k
].visited
= false;
783 for (i
= 0; i
< MAX_SEQUENCE
; i
++)
785 for (k
= OpeningSequence
[os
].first_pattern
[i
];
786 k
!= END_OF_PATTERNS
;
787 k
= Pattern
[k
].next_pattern
)
789 Pattern
[k
].distance
[pside
] = pattern_distance(pside
, k
);
791 /* Actually reached patterns need not to be observed. */
792 if (Pattern
[k
].distance
[pside
] == 0)
794 Pattern
[k
].distance
[pside
] = CANNOT_REACH
;
795 check_visited
[i
] = Pattern
[k
].visited
= true;
797 for (j
= Pattern
[k
].first_link
;
798 pattern_data
[j
] != END_OF_LINKS
; j
++)
800 VisitReachable(pside
, os
, i
, pattern_data
[j
], false);
803 else if ((GameCnt
>= 0)
804 && (GameCnt
>= Pattern
[k
].reachedGameCnt
[pside
]))
806 Pattern
[k
].distance
[pside
] = IS_REACHED
;
809 if (Pattern
[k
].reachedGameCnt
[pside
] >= GameCnt
)
810 Pattern
[k
].reachedGameCnt
[pside
] = MAXMOVES
;
815 * Remove reachable patterns from search, which are successors of
816 * reachable patterns. So, only the next pattern of a pattern sequence
820 for (i
= 0; i
< MAX_SEQUENCE
; i
++)
822 for (k
= OpeningSequence
[os
].first_pattern
[i
];
823 k
!= END_OF_PATTERNS
;
824 k
= Pattern
[k
].next_pattern
)
826 if (check_visited
[i
] && !Pattern
[k
].visited
)
827 Pattern
[k
].distance
[pside
] = NOT_TO_REACH
;
829 Pattern
[k
].visited
= false;
833 for (i
= 0; i
< MAX_SEQUENCE
; i
++)
835 for (k
= OpeningSequence
[os
].first_pattern
[i
];
836 k
!= END_OF_PATTERNS
;
837 k
= Pattern
[k
].next_pattern
)
839 if ((d
= Pattern
[k
].distance
[pside
]) >= 0)
841 for (j
= Pattern
[k
].first_link
;
842 pattern_data
[j
] != END_OF_LINKS
; j
++)
844 VisitReachable(pside
, os
, i
, pattern_data
[j
], true);
851 * Look to see whether there is still a reachable pattern.
854 for (i
= 0; i
< MAX_SEQUENCE
; i
++)
856 for (k
= OpeningSequence
[os
].first_pattern
[i
];
857 k
!= END_OF_PATTERNS
;
858 k
= Pattern
[k
].next_pattern
)
860 if ((d
= Pattern
[k
].distance
[pside
]) >= 0)
865 return END_OF_SEQUENCES
;
872 update_advance_bonus (short pside
, short os
)
874 struct PatternField field
;
877 for (j
= 0; j
< MAX_SEQUENCE
; j
++)
879 for (k
= OpeningSequence
[os
].first_pattern
[j
];
880 k
!= END_OF_PATTERNS
;
881 k
= Pattern
[k
].next_pattern
)
883 if ((d
= Pattern
[k
].distance
[pside
]) >= 0)
885 for (i
= Pattern
[k
].first_field
;
886 pattern_data
[i
] != END_OF_FIELDS
; i
+= 2)
888 set_field(i
, &field
);
889 if (field
.side
== black
)
891 short square
= (pside
== black
)
893 : NO_SQUARES
- 1 - field
.square
;
895 (*Mpiece
[field
.piece
])[pside
][square
]
896 += ADVNCM
[field
.piece
];