102 Dalmatians: Puppies to the Rescue
Decompilation Source Reference | GitLab repository
Loading...
Searching...
No Matches
search.c
Go to the documentation of this file.
1/* Recovered game implementation; original addresses identify provenance. */
11#include <math.h>
12#include <stdarg.h>
13#include <string.h>
14
15// Original pcdogs.exe: 0x411f70
16// Builds the player's move list and returns whether the mandatory-capture rule selected a capture-only list. Optional-capture mode can retain both captures and simple moves, and output capacity is not checked.
17BOOL Checkers_BuildMoveList(struct Checkers_Board *board_state, enum Checkers_Player player, struct Checkers_MoveList *move_list)
18{
19 struct Checkers_MoveSequence *move_cursor = move_list->records;
20 BOOL capture_only = 0;
21
22 for (int32_t row_index = 0; row_index < CHECKERS_BOARD_SIDE; ++row_index)
23 {
24 int32_t source_row = player == CHECKERS_PLAYER_1 ? CHECKERS_LAST_COORDINATE - row_index : row_index;
25
26 for (int32_t source_col = (source_row - 1) & 1; source_col < CHECKERS_BOARD_SIDE; source_col += 2)
27 {
28 uint8_t source_piece = board_state->playable_by_col[source_col][source_row >> 1];
29
30 if (player != (source_piece & CHECKERS_PLAYER_MASK))
31 continue;
32
33 if (capture_only)
34 Checkers_AppendCaptureMoveSequences(board_state, source_col, source_row, &move_cursor);
35 else if (Checkers_CheckCapturePossible(board_state, source_piece, source_col, source_row))
36 {
38 {
39 capture_only = 1;
40 move_cursor = move_list->records;
41 }
42
43 Checkers_AppendCaptureMoveSequences(board_state, source_col, source_row, &move_cursor);
44 }
45
46 if (capture_only)
47 continue;
48
49 int32_t column_step = source_col < 4 ? -2 : 2;
50 int32_t row_step = source_row < 4 ? -2 : 2;
51 int32_t first_col = source_col - column_step / 2;
52 int32_t first_row = source_row - row_step / 2;
53
54 for (int32_t column_choice = 0; column_choice < 2; ++column_choice)
55 {
56 int32_t to_col = first_col + column_choice * column_step;
57
58 for (int32_t row_choice = 0; row_choice < 2; ++row_choice)
59 {
60 int32_t to_row = first_row + row_choice * row_step;
61
62 if (Checkers_ValidateSimpleMove(board_state, source_col, source_row, to_col, to_row) == CHECKERS_MOVE_SIMPLE)
63 {
64 *move_cursor++ = (struct Checkers_MoveSequence){
65 .fromCol = source_col,
66 .fromRow = source_row,
67 .packedToCols = to_col,
68 .packedToRows = to_row};
69 }
70 }
71 }
72 }
73 }
74
75 move_list->count = move_cursor - move_list->records;
76
77 return capture_only;
78}
79
80// Original pcdogs.exe: 0x4124e0
81// Appends valid captures from a board cell and recursively expands captures that can continue. The caller supplies sufficient output storage.
82void Checkers_AppendCaptureMoveSequences(struct Checkers_Board *board, int32_t from_col, int32_t from_row, struct Checkers_MoveSequence **move_cursor_in_out)
83{
84 for (int32_t to_col = from_col - 2; to_col <= from_col + 2; to_col += 4)
85 {
86 for (int32_t to_row = from_row - 2; to_row <= from_row + 2; to_row += 4)
87 {
88 if (Checkers_ValidateMove(board, from_col, from_row, to_col, to_row) != CHECKERS_MOVE_CAPTURE)
89 continue;
90
91 (*move_cursor_in_out)->fromCol = from_col;
92 (*move_cursor_in_out)->fromRow = from_row;
93 (*move_cursor_in_out)->packedToCols = to_col;
94 (*move_cursor_in_out)->packedToRows = to_row;
95
96 struct Checkers_Board candidate_board;
97
98 memcpy(&candidate_board, board, 0x20);
99
100 if (Checkers_ExecuteMove(&candidate_board, from_col, from_row, to_col, to_row) == CHECKERS_EXEC_CAPTURE_CAN_CONTINUE)
101 Checkers_ExpandCaptureSequences(&candidate_board, move_cursor_in_out, 0);
102 else
103 ++*move_cursor_in_out;
104 }
105 }
106}
107
108// Original pcdogs.exe: 0x412820
109// Recursively extends packed capture sequences, retaining intermediate prefixes when the configured rule allows them. Coordinate shifts retain the native five-bit mask and output capacity is not checked.
110void Checkers_ExpandCaptureSequences(struct Checkers_Board *board, struct Checkers_MoveSequence **move_cursor_in_out, uint32_t pack_shift)
111{
113 {
114 struct Checkers_MoveSequence *prefix_sequence = *move_cursor_in_out;
115
116 prefix_sequence[1].fromCol = prefix_sequence->fromCol;
117 prefix_sequence[1].fromRow = prefix_sequence->fromRow;
118 prefix_sequence[1].packedToCols = prefix_sequence->packedToCols;
119 prefix_sequence[1].packedToRows = prefix_sequence->packedToRows;
120 *move_cursor_in_out = &(*move_cursor_in_out)[1];
121 }
122
123 struct Checkers_MoveSequence *current_sequence = *move_cursor_in_out;
124 int32_t from_col = current_sequence->fromCol;
125 int32_t from_row = current_sequence->fromRow;
126 uint32_t packed_to_cols = current_sequence->packedToCols;
127 uint32_t packed_to_rows = current_sequence->packedToRows;
128 uint32_t jump_source_col = packed_to_cols >> ((uint8_t)pack_shift & 0x1f);
129 uint32_t jump_source_row = packed_to_rows >> ((uint8_t)pack_shift & 0x1f);
130 uint32_t next_pack_shift = pack_shift + 3;
131
132 for (int32_t column_delta = -2; column_delta <= 2; column_delta += 4)
133 {
134 int32_t to_col = column_delta + jump_source_col;
135 int32_t to_row = jump_source_row - 2;
136
137 for (int32_t row_choice = 0; row_choice < 2; ++row_choice, to_row += 4)
138 {
139 if ((to_row | to_col) & ~(uint32_t)CHECKERS_COORDINATE_MASK)
140 continue;
141
142 if (!Checkers_ValidateMove(board, jump_source_col, jump_source_row, to_col, to_row))
143 continue;
144
145 struct Checkers_Board candidate_board;
146
147 memcpy(&candidate_board, board, 0x20);
148
149 enum Checkers_MoveExecutionResult execution_result = Checkers_ExecuteMove(&candidate_board,
150 jump_source_col, jump_source_row, to_col, to_row);
151
152 (*move_cursor_in_out)->packedToCols =
153 (to_col << (next_pack_shift & 0x1f)) + packed_to_cols;
154 (*move_cursor_in_out)->packedToRows =
155 (to_row << (next_pack_shift & 0x1f)) + packed_to_rows;
156
157 if (execution_result == CHECKERS_EXEC_CAPTURE_CAN_CONTINUE)
158 Checkers_ExpandCaptureSequences(&candidate_board, move_cursor_in_out, next_pack_shift);
159 else
160 {
161 ++*move_cursor_in_out;
162 (*move_cursor_in_out)->fromCol = from_col;
163 (*move_cursor_in_out)->fromRow = from_row;
164 }
165 }
166 }
167}
168
169// C body of Checkers_SearchBestMove. Its x86 entry supplies the original stack workspace.
170// Searches checkers moves with alpha-beta pruning and optionally returns the selected move. Periodic rendering and the think deadline can leave through the saved jump context.
171int32_t Checkers_SearchWithMoveList(struct Checkers_Board *board, int32_t depth, struct Checkers_MoveSequence *out_best_move,
172 enum Checkers_Player player, int32_t alpha, int32_t beta, struct Checkers_MoveList *moves, int32_t *selected_index)
173{
174 int32_t visited_node_count = g_checkersAINodeCounter + 1;
175
176 g_checkersAINodeCounter = visited_node_count;
177
178 if (!((uint8_t)visited_node_count & CHECKERS_RENDER_NODE_MASK))
179 {
182
184
186 {
187 int32_t think_deadline = g_checkersAIThinkTimeout;
188
190
191 if (!think_deadline)
192 {
193 int32_t difficulty_setting = g_worldBonusStateArray[4];
194
195 if (difficulty_setting == CHECKERS_DIFFICULTY_EASY)
197 else if (difficulty_setting == CHECKERS_DIFFICULTY_NORMAL)
199 else if (difficulty_setting == CHECKERS_DIFFICULTY_HARD)
201 }
202 else if ((uint32_t)g_frameCounter > (uint32_t)think_deadline && (g_checkersAIMove_fromCol || g_checkersAIMove_fromRow) && (g_checkersAIMove_toCol || g_checkersAIMove_toRow))
203 {
205 /* no return */
206 }
207 }
208 }
209
210 if (!depth)
211 return Checkers_EvaluateBoardScore(board);
212
213 Checkers_BuildMoveList(board, player, moves);
214 bool maximizing = (uint32_t)player == (uint32_t)g_worldBonusStateArray[5];
215 int32_t best_score = maximizing ? -0x3fffffff : 0x3fffffff;
216
217 for (int32_t i = --moves->count; i >= 0; i = --moves->count)
218 {
219 struct Checkers_Board candidate = *board;
220 Checkers_ExecuteMoveSequence(&candidate, &moves->records[i]);
221 int32_t score = Checkers_SearchBestMove(&candidate, depth - 1, NULL,
222 player ^ CHECKERS_PLAYER_MASK, alpha, beta);
223
224 maximizing = (uint32_t)player == (uint32_t)g_worldBonusStateArray[5];
225 if (maximizing && score >= best_score)
226 {
227 *selected_index = i;
228 best_score = score;
229 if (score > alpha)
230 {
231 if (score >= beta)
232 break;
233 alpha = score;
234 }
235 }
236 else if (!maximizing && score <= best_score)
237 {
238 best_score = score;
239 if (score < beta)
240 {
241 if (score <= alpha)
242 break;
243 beta = score;
244 }
245 }
246 }
247
248 if (out_best_move)
249 *out_best_move = moves->records[*selected_index];
250 return best_score;
251}
252
253// Original pcdogs.exe: 0x412c00
254// Scores piece value and position, adds difficulty-dependent randomness and selects the score's sign from the configured player perspective.
256{
257 int32_t score = 0;
258 for (int32_t col = 0; col < CHECKERS_BOARD_SIDE; ++col)
259 {
260 for (int32_t row = (col ^ 1) & 1; row < CHECKERS_BOARD_SIDE; row += 2)
261 {
262 enum Checkers_Piece piece = board->playable_by_col[col][row >> 1];
263 if (piece == CHECKERS_PIECE_EMPTY)
264 continue;
265
266 if (piece == CHECKERS_PIECE_PLAYER1_MAN)
267 score -= CHECKERS_MAN_VALUE + row * row;
268 else if (piece == CHECKERS_PIECE_PLAYER2_MAN)
269 {
270 int32_t advance = CHECKERS_LAST_COORDINATE - row;
271 score += CHECKERS_MAN_VALUE + advance * advance;
272 }
273 else
274 {
275 int32_t value = CHECKERS_KING_VALUE;
276 if (col == 0 || col == CHECKERS_LAST_COORDINATE)
277 value -= CHECKERS_EDGE_PENALTY;
278 if (row == 0 || row == CHECKERS_LAST_COORDINATE)
279 value -= CHECKERS_EDGE_PENALTY;
280 score += piece == CHECKERS_PIECE_PLAYER1_KING ? -value : value;
281 }
282 }
283 }
284
285 int32_t jitter = 0;
286 switch (g_worldBonusStateArray[4])
287 {
291 }
292 if (jitter)
293 score += (int32_t)Math_GenerateRandom(2 * jitter + 1) - jitter;
294 return g_worldBonusStateArray[5] == CHECKERS_PLAYER_2 ? score : -score;
295}
#define CHECKERS_COORDINATE_MASK
Definition constants.h:11
#define CHECKERS_BOARD_SIDE
Definition constants.h:12
#define CHECKERS_NORMAL_SCORE_JITTER
Definition constants.h:30
@ CHECKERS_DIFFICULTY_HARD
Definition constants.h:24
@ CHECKERS_DIFFICULTY_EASY
Definition constants.h:22
@ CHECKERS_DIFFICULTY_NORMAL
Definition constants.h:23
#define CHECKERS_PLAYER_MASK
Definition constants.h:10
#define CHECKERS_EASY_SCORE_JITTER
Definition constants.h:29
#define CHECKERS_HARD_SCORE_JITTER
Definition constants.h:31
#define CHECKERS_MAN_VALUE
Definition constants.h:15
#define CHECKERS_RENDER_NODE_MASK
Definition constants.h:18
#define CHECKERS_EDGE_PENALTY
Definition constants.h:17
#define CHECKERS_KING_VALUE
Definition constants.h:16
#define CHECKERS_LAST_COORDINATE
Definition constants.h:13
Checkers_Piece
Definition enums.h:85
@ CHECKERS_PIECE_PLAYER1_MAN
Definition enums.h:91
@ CHECKERS_PIECE_PLAYER1_KING
Definition enums.h:97
@ CHECKERS_PIECE_PLAYER2_MAN
Definition enums.h:94
@ CHECKERS_PIECE_EMPTY
Definition enums.h:88
@ CHECKERS_MOVE_CAPTURE
Definition enums.h:75
@ CHECKERS_MOVE_SIMPLE
Definition enums.h:78
Checkers_Player
Definition enums.h:107
@ CHECKERS_PLAYER_2
Definition enums.h:113
@ CHECKERS_PLAYER_1
Definition enums.h:110
Checkers_MoveExecutionResult
Definition enums.h:50
@ CHECKERS_EXEC_CAPTURE_CAN_CONTINUE
Definition enums.h:56
@ CHECKERS_STATE_IDLE
Definition enums.h:10
@ CHECKERS_STATE_AI_RENDER_TICK
Definition enums.h:28
enum Checkers_MoveValidation Checkers_ValidateSimpleMove(struct Checkers_Board *board, int32_t from_col, int32_t from_row, int32_t to_col, int32_t to_row)
Definition board.c:27
BOOL Checkers_CheckCapturePossible(struct Checkers_Board *board, uint32_t piece, int32_t col, int32_t row)
Definition board.c:53
enum Checkers_MoveExecutionResult Checkers_ExecuteMoveSequence(struct Checkers_Board *board, struct Checkers_MoveSequence const *move_sequence)
Definition board.c:150
enum Checkers_MoveValidation Checkers_ValidateMove(struct Checkers_Board *board, int32_t from_col, int32_t from_row, int32_t to_col, int32_t to_row)
Definition board.c:91
int32_t Checkers_SearchBestMove(struct Checkers_Board *board, int32_t depth, struct Checkers_MoveSequence *out_best_move, enum Checkers_Player player, int32_t alpha, int32_t beta)
enum Checkers_MoveExecutionResult Checkers_ExecuteMove(struct Checkers_Board *board, int32_t from_col, int32_t from_row, int32_t to_col, int32_t to_row)
Definition board.c:118
BOOL Checkers_ProcessInputAndRender(void)
#define g_checkersAINodeCounter
Definition globals.h:54
#define g_checkersAIThinkTimeout
Definition globals.h:77
#define g_checkersJumpBuffer
Definition globals.h:74
#define g_checkersAIMove_fromRow
Definition globals.h:65
#define g_checkersAIMove_toRow
Definition globals.h:71
#define g_checkersAIMove_fromCol
Definition globals.h:62
#define g_checkersMinigameState
Definition globals.h:80
#define g_checkersAIMove_toCol
Definition globals.h:68
uint32_t Math_GenerateRandom(uint32_t range)
void _longjmp(struct CRT_JumpBuffer3 *jump_buffer, int32_t value)
void Checkers_ExpandCaptureSequences(struct Checkers_Board *board, struct Checkers_MoveSequence **move_cursor_in_out, uint32_t pack_shift)
Definition search.c:110
void Checkers_AppendCaptureMoveSequences(struct Checkers_Board *board, int32_t from_col, int32_t from_row, struct Checkers_MoveSequence **move_cursor_in_out)
Definition search.c:82
BOOL Checkers_BuildMoveList(struct Checkers_Board *board_state, enum Checkers_Player player, struct Checkers_MoveList *move_list)
Definition search.c:17
int32_t Checkers_EvaluateBoardScore(struct Checkers_Board *board)
Definition search.c:255
int32_t Checkers_SearchWithMoveList(struct Checkers_Board *board, int32_t depth, struct Checkers_MoveSequence *out_best_move, enum Checkers_Player player, int32_t alpha, int32_t beta, struct Checkers_MoveList *moves, int32_t *selected_index)
Definition search.c:171
enum Checkers_Piece playable_by_col[0x8][0x4]
Definition types.h:11
int32_t count
Definition types.h:34
struct Checkers_MoveSequence records[0x3c]
Definition types.h:35
uint32_t packedToRows
Definition types.h:24
uint32_t packedToCols
Definition types.h:23
#define g_frameCounter
Definition values.h:501
#define g_worldBonusStateArray
Definition values.h:828