4 * ----------------------------------------------------------------------
5 * Copyright (c) 1993, 1994, 1995 Matthias Mutz
6 * Copyright (c) 1999 Michael Vanier and the Free Software Foundation
7 * Copyright (c) 2008, 2013, 2014 Yann Dirson and the Free Software Foundation
9 * GNU SHOGI is based on GNU CHESS
11 * Copyright (c) 1988, 1989, 1990 John Stanback
12 * Copyright (c) 1992 Free Software Foundation
14 * This file is part of GNU SHOGI.
16 * GNU Shogi is free software; you can redistribute it and/or modify it
17 * under the terms of the GNU General Public License as published by the
18 * Free Software Foundation; either version 3 of the License,
19 * or (at your option) any later version.
21 * GNU Shogi is distributed in the hope that it will be useful, but WITHOUT
22 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
23 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
26 * You should have received a copy of the GNU General Public License along
27 * with GNU Shogi; see the file COPYING. If not, see
28 * <http://www.gnu.org/licenses/>.
29 * ----------------------------------------------------------------------
36 /* "pat2inc" generates constants and pattern_data */
37 #include "pattern.inc"
39 struct Pattern_rec Pattern
[MAX_PATTERN
];
40 struct OpeningSequence_rec OpeningSequence
[MAX_OPENING_SEQUENCE
];
42 small_short pattern_data
[MAX_PATTERN_DATA
];
46 NameOfOpeningValue (short i
, char *name
)
50 strcpy(name
, "CASTLE_?_?");
54 strcpy(name
, "ATTACK_?_?");
99 GetOpeningPatterns (short *max_opening_sequence
)
108 OpeningSequence
[os
].opening_type
= pattern_data
[pindex
++];
109 OpeningSequence
[os
].first_pattern
[0] = p
;
111 for (i
= 1; i
< MAX_SEQUENCE
; i
++)
112 OpeningSequence
[os
].first_pattern
[i
] = END_OF_PATTERNS
;
116 Pattern
[p
].reachedGameCnt
[black
] = MAXMOVES
;
117 Pattern
[p
].reachedGameCnt
[white
] = MAXMOVES
;
118 Pattern
[p
].first_link
= pindex
;
120 while (pattern_data
[pindex
] != END_OF_LINKS
)
124 Pattern
[p
].first_field
= pindex
;
126 while (pattern_data
[pindex
] != END_OF_FIELDS
)
130 if (pattern_data
[pindex
] != END_OF_PATTERNS
)
131 Pattern
[p
].next_pattern
= p
+ 1;
133 Pattern
[p
].next_pattern
= END_OF_PATTERNS
;
137 while (pattern_data
[pindex
] != END_OF_PATTERNS
);
142 while (pattern_data
[pindex
] != END_OF_SEQUENCES
);
144 *max_opening_sequence
= os
;
150 ShowOpeningPatterns (short max_opening_sequence
)
154 for (os
= 0; os
< max_opening_sequence
; os
++)
157 NameOfOpeningValue(OpeningSequence
[os
].opening_type
, name
);
158 printf("Opening Type: %s\n", name
);
160 for (p
= OpeningSequence
[os
].first_pattern
[0], n
= 0;
161 p
!= END_OF_PATTERNS
;
162 p
= Pattern
[p
].next_pattern
, n
++)
164 printf("Pattern %d (%d) with links ", p
, n
);
166 for (i
= Pattern
[p
].first_link
;
167 pattern_data
[i
] != END_OF_LINKS
;
170 printf("%d ", pattern_data
[i
]);
174 DisplayPattern(stdout
, Pattern
[p
].first_field
);
182 set_field (short i
, struct PatternField
*field
)
184 field
->piece
= pattern_data
[i
];
185 field
->square
= pattern_data
[i
+1];
187 if (field
->square
< 0)
189 field
->square
= -(field
->square
);
201 * piece_to_pattern_distance (side, piece, pside, pattern)
203 * Determine the minimum number of moves from the current position to a
204 * specific pattern for a specific piece. Consider the "side" piece of the
205 * pattern. The pattern should match for "pside".
209 piece_to_pattern_distance(short side
, short piece
,
210 short pside
, short pattern
)
212 short nP
, P
[4], nB
, B
[4]; /* at most 4 pieces of same kind */
213 short i
, j
, r
, dd
, occupied
, mindd
, c
[4], d
[4];
214 /* a "side" patternfield must match a "c1" piece on board: */
215 short c1
= side
^ pside
;
218 * If pside == white, a black piece in the pattern should match a white
219 * piece on board, and vice versa. Furthermore, if pside == white,
220 * reversed pattern should match board.
223 /* special pawn handling */
227 mindd
= occupied
= 0;
229 for (i
= Pattern
[pattern
].first_field
;
230 pattern_data
[i
] != END_OF_FIELDS
;
233 struct PatternField field
;
234 set_field(i
, &field
);
236 if ((field
.side
== side
) && (field
.piece
== pawn
))
238 short t
= field
.square
;
239 short pcol
= column(t
);
242 if (PawnCnt
[c1
][(side
== c1
) ? pcol
: (8 - pcol
)])
244 /* there is a pawn on the column */
245 for (j
= 0; j
<= PieceCnt
[c1
]; j
++)
247 short sq
= (short)PieceList
[c1
][j
];
249 if (board
[sq
] == pawn
)
252 sq
= NO_SQUARES
- 1 - sq
;
254 if (column(sq
) == pcol
)
256 dd
= piece_distance (side
, pawn
, sq
, t
);
258 printf("update %d pawn "
259 "from %d to %d is %d\n",
269 /* there is no pawn on the column; drop possible? */
270 if (Captured
[c1
][pawn
])
274 printf("update %d pawn drop to %d is %d\n",
282 /* Increment distance if pattern field is occupied */
292 psq
= (NO_SQUARES
- 1 - t
);
296 if ((color
[psq
] == pc
) && (board
[psq
] != pawn
))
299 printf("square %d is occupied\n", psq
);
313 return mindd
+ occupied
;
317 * Determine list of "side" "piece"s in pattern.
320 for (occupied
= nP
= 0, i
= Pattern
[pattern
].first_field
;
321 pattern_data
[i
] != END_OF_FIELDS
;
324 struct PatternField field
;
325 set_field(i
, &field
);
327 if ((field
.side
== side
) && (field
.piece
== piece
))
330 P
[nP
] = field
.square
;
332 printf("pattern %d piece %d on square %d\n", side
, piece
, P
[nP
]);
336 /* Increment distance if pattern field is occupied */
344 psq
= NO_SQUARES
- 1 - field
.square
;
348 if ((color
[psq
] == pc
) && (board
[psq
] != field
.piece
))
351 printf("square %d is occupied\n", psq
);
362 printf("finding in pattern %d pieces %d of side %d\n", nP
, piece
, side
);
366 * Determine list of "side ^ pside" "piece"s captured or on board.
369 for (nB
= 0; nB
< Captured
[c1
][piece
]; nB
++)
370 B
[nB
] = NO_SQUARES
+ piece
;
372 for (i
= 0; i
<= PieceCnt
[c1
]; i
++)
374 short sq
= PieceList
[c1
][i
];
376 if (board
[sq
] == piece
)
378 B
[nB
] = (pside
== black
) ? sq
: (NO_SQUARES
- 1 - sq
);
380 printf("%d piece %d on square %d\n", side
, piece
, B
[nB
]);
387 printf("found on board %d pieces %d of side %d\n", nB
, piece
, side
);
395 /* Determine best assignment from board piece to pattern piece */
399 mindd
= CANNOT_REACH
;
401 while ((r
>= 0) && (mindd
!= 0))
410 for (i
= 0; i
< r
; i
++)
418 d
[r
] = piece_distance (side
, piece
, B
[c
[r
]], P
[r
]);
420 printf("update d[%d] from %d to %d is %d\n",
421 r
, B
[c
[r
]], P
[r
], d
[r
]);
431 for (dd
= i
= 0; i
< nP
; i
++)
434 if ((dd
< mindd
) || (mindd
< 0))
438 printf("update min %d\n", mindd
);
456 return (mindd
+ occupied
);
463 * pattern_distance (pside, pattern)
465 * Determine the minimum number of moves for the pieces from
466 * the current position to reach a pattern.
467 * The result is CANNOT_REACH, if there is no possible sequence
473 pattern_distance (short pside
, short pattern
)
475 short side
, piece
, d
, n
;
478 printf("\nchecking pattern %d for pside=%d\n\n", pattern
, pside
);
481 for (n
= side
= 0; side
<= 1 && n
>= 0; side
++)
483 for (piece
= pawn
; piece
<= king
; piece
++)
485 d
= piece_to_pattern_distance (side
, piece
, pside
, pattern
);
500 printf("\ndistance to pattern is %d\n\n", n
);
509 * board_to_pattern_distance(pside, osequence, pmplty, GameCnt)
511 * Determine the maximal difference of the number of moves from the pattern
512 * to the initial position and to the current position.
513 * Differences are weighted, i.e. the more closer a position is to a pattern
514 * the more valuable is a move towards the pattern.
515 * Patterns, which are at least "pmplty" halfmoves away, are not counted.
519 board_to_pattern_distance
520 (short pside
, short osequence
, short pmplty
, short GameCnt
)
522 short i
, d
, dist
, diff
, weighted_diff
;
523 short maxdiff
= 0, max_weighted_diff
= 0;
526 for (i
= 0; i
< MAX_SEQUENCE
; i
++)
528 for (pattern
= OpeningSequence
[osequence
].first_pattern
[i
];
529 pattern
!= END_OF_PATTERNS
;
530 pattern
= Pattern
[pattern
].next_pattern
)
532 if ((d
= Pattern
[pattern
].distance
[pside
]) >= 0)
536 dist
= pattern_distance (pside
, pattern
);
540 * "dist" is the distance of the current board
541 * position to the pattern. "d - dist" is the
542 * difference between the current distance and the
543 * initial distance. Compute "diff" as the weighted
547 /* try to reach the nearest pattern */
548 weighted_diff
= (diff
= (d
- dist
)) * (pmplty
- d
);
550 if (weighted_diff
> max_weighted_diff
)
555 maxdiff
= weighted_diff
;
557 max_weighted_diff
= weighted_diff
;
561 * A reached pattern should not be considered in
562 * the future (if GameCnt >= 0)
565 if (dist
== 0 && GameCnt
>= 0)
566 Pattern
[pattern
].reachedGameCnt
[pside
] = GameCnt
;
580 DisplayPattern (FILE *fd
, short n
)
582 small_short pboard
[NO_SQUARES
], pcolor
[NO_SQUARES
];
585 for (sq
= 0; sq
< NO_SQUARES
; sq
++)
587 pboard
[sq
] = no_piece
;
588 pcolor
[sq
] = neutral
;
591 for (i
= n
; pattern_data
[i
] != END_OF_FIELDS
; i
+= 2)
593 struct PatternField field
;
594 set_field(i
, &field
);
595 pboard
[field
.square
] = field
.piece
;
596 pcolor
[field
.square
] = field
.side
;
599 for (r
= NO_ROWS
- 1; r
>= 0; r
--)
601 for (c
= 0; c
< NO_COLS
; c
++)
609 fprintf(fd
, "%c%c", is_promoted
[i
] ? '+' : ' ',
610 pcolor
[sq
] ? pxx
[i
] : qxx
[i
]);
623 VisitReachable (int pside
, short osequence
, int k
, int n
, int remove
)
628 /* Adjust to sequence pattern n */
629 for (i
= 0, pattern
= OpeningSequence
[osequence
].first_pattern
[k
];
632 pattern
= Pattern
[pattern
].next_pattern
;
635 /* do not perform visited link twice */
636 if (Pattern
[pattern
].visited
)
642 Pattern
[pattern
].visited
= true;
645 /* Declare links unreachable */
646 for (j
= Pattern
[pattern
].first_link
;
647 pattern_data
[j
] != END_OF_LINKS
; j
++)
649 VisitReachable(pside
, osequence
, k
, pattern_data
[j
], remove
);
652 /* Declare unreachable */
653 if (remove
&& Pattern
[pattern
].distance
[pside
] >= 0)
655 Pattern
[pattern
].distance
[pside
] = IS_SUCCESSOR
;
660 /* simplified matching for opening type names */
662 #define match_char(a, b) \
663 (a == b || (a == '*' && b != 'U') || (b == '*' && a != 'U'))
665 #define match_name(a, b, l) \
666 (l > 8 && match_char(a[0], b[0]) && match_char(a[7], b[7]) \
667 && match_char(a[9], b[9]))
671 locate_opening_sequence(short pside
, char *s
, short GameCnt
)
673 short i
, j
, k
, os
, d
;
675 short check_visited
[MAX_SEQUENCE
];
676 char name
[MAX_NAME
], name2
[MAX_NAME
];
679 * Look for opening pattern name in the list of opening patterns.
684 for (i
= 1, os
= 0; os
< MAX_OPENING_SEQUENCE
; os
++)
686 /* locate matching opening type name */
687 NameOfOpeningValue(OpeningSequence
[os
].opening_type
, name
);
689 if (match_name(s
, name
, l
))
691 /* locate successor matching names */
692 for (k
= os
+ 1; k
< MAX_OPENING_SEQUENCE
; k
++)
694 NameOfOpeningValue(OpeningSequence
[k
].opening_type
, name2
);
696 if (match_name(s
, name2
, l
))
698 OpeningSequence
[os
].first_pattern
[i
++]
699 = OpeningSequence
[k
].first_pattern
[0];
707 if (os
>= MAX_OPENING_SEQUENCE
)
709 return END_OF_SEQUENCES
;
713 for (; i
< MAX_SEQUENCE
;
714 OpeningSequence
[os
].first_pattern
[i
++] = END_OF_PATTERNS
);
718 * Determine patterns which can be reached from the current
719 * board position. Only patterns which can be reached will be
720 * checked in the following search.
723 for (i
= 0; i
< MAX_SEQUENCE
; i
++)
725 check_visited
[i
] = false;
727 for (k
= OpeningSequence
[os
].first_pattern
[i
];
728 k
!= END_OF_PATTERNS
;
729 k
= Pattern
[k
].next_pattern
)
731 Pattern
[k
].visited
= false;
735 for (i
= 0; i
< MAX_SEQUENCE
; i
++)
737 for (k
= OpeningSequence
[os
].first_pattern
[i
];
738 k
!= END_OF_PATTERNS
;
739 k
= Pattern
[k
].next_pattern
)
741 Pattern
[k
].distance
[pside
] = pattern_distance(pside
, k
);
743 /* Actually reached patterns need not to be observed. */
744 if (Pattern
[k
].distance
[pside
] == 0)
746 Pattern
[k
].distance
[pside
] = CANNOT_REACH
;
747 check_visited
[i
] = Pattern
[k
].visited
= true;
749 for (j
= Pattern
[k
].first_link
;
750 pattern_data
[j
] != END_OF_LINKS
; j
++)
752 VisitReachable(pside
, os
, i
, pattern_data
[j
], false);
755 else if ((GameCnt
>= 0)
756 && (GameCnt
>= Pattern
[k
].reachedGameCnt
[pside
]))
758 Pattern
[k
].distance
[pside
] = IS_REACHED
;
761 if (Pattern
[k
].reachedGameCnt
[pside
] >= GameCnt
)
762 Pattern
[k
].reachedGameCnt
[pside
] = MAXMOVES
;
767 * Remove reachable patterns from search, which are successors of
768 * reachable patterns. So, only the next pattern of a pattern sequence
772 for (i
= 0; i
< MAX_SEQUENCE
; i
++)
774 for (k
= OpeningSequence
[os
].first_pattern
[i
];
775 k
!= END_OF_PATTERNS
;
776 k
= Pattern
[k
].next_pattern
)
778 if (check_visited
[i
] && !Pattern
[k
].visited
)
779 Pattern
[k
].distance
[pside
] = NOT_TO_REACH
;
781 Pattern
[k
].visited
= false;
785 for (i
= 0; i
< MAX_SEQUENCE
; i
++)
787 for (k
= OpeningSequence
[os
].first_pattern
[i
];
788 k
!= END_OF_PATTERNS
;
789 k
= Pattern
[k
].next_pattern
)
791 if ((d
= Pattern
[k
].distance
[pside
]) >= 0)
793 for (j
= Pattern
[k
].first_link
;
794 pattern_data
[j
] != END_OF_LINKS
; j
++)
796 VisitReachable(pside
, os
, i
, pattern_data
[j
], true);
803 * Look to see whether there is still a reachable pattern.
806 for (i
= 0; i
< MAX_SEQUENCE
; i
++)
808 for (k
= OpeningSequence
[os
].first_pattern
[i
];
809 k
!= END_OF_PATTERNS
;
810 k
= Pattern
[k
].next_pattern
)
812 if ((d
= Pattern
[k
].distance
[pside
]) >= 0)
817 return END_OF_SEQUENCES
;
824 update_advance_bonus (short pside
, short os
)
826 struct PatternField field
;
829 for (j
= 0; j
< MAX_SEQUENCE
; j
++)
831 for (k
= OpeningSequence
[os
].first_pattern
[j
];
832 k
!= END_OF_PATTERNS
;
833 k
= Pattern
[k
].next_pattern
)
835 if ((d
= Pattern
[k
].distance
[pside
]) >= 0)
837 for (i
= Pattern
[k
].first_field
;
838 pattern_data
[i
] != END_OF_FIELDS
; i
+= 2)
840 set_field(i
, &field
);
841 if (field
.side
== black
)
843 short square
= (pside
== black
)
845 : NO_SQUARES
- 1 - field
.square
;
847 (*Mpiece
[field
.piece
])[pside
][square
]
848 += ADVNCM
[field
.piece
];