1 // This file is part of Freecell Solver. It is subject to the license terms in
2 // the COPYING.txt file found in the top-level directory of this distribution
3 // and at http://fc-solve.shlomifish.org/docs/distro/COPYING.html . No part of
4 // Freecell Solver, including this file, may be copied, modified, propagated,
5 // or distributed except according to the terms contained in the COPYING file.
6 //
7 // Copyright (c) 2000 Shlomi Fish
8 // scans_impl.h - code implementing the various scans as inline functions.
9 #pragma once
10
11 #ifdef __cplusplus
12 extern "C" {
13 #endif
14
15 #include <assert.h>
16
17 #include "scans.h"
18
19 #ifdef FCS_SINGLE_HARD_THREAD
20 #define check_if_limits_exceeded__num() \
21 ((*instance_num_checked_states_ptr) >= max_num_states)
22 #else
23 #define check_if_limits_exceeded__num() \
24 ((*hard_thread_num_checked_states_ptr) >= max_num_states)
25 #endif
26
27 #ifdef FCS_DISABLE_NUM_STORED_STATES
28 #define check_if_limits_exceeded__num_states()
29 #else
30 #define check_if_limits_exceeded__num_states() \
31 || (instance->i__stats.num_states_in_collection >= \
32 effective_max_num_states_in_collection)
33 #endif
34
35 // This macro checks if we need to terminate from running this soft
36 // thread and return to the soft thread manager with an
37 // FCS_STATE_SUSPEND_PROCESS
38 #define check_if_limits_exceeded() \
39 (check_if_limits_exceeded__num() check_if_limits_exceeded__num_states())
40
41 #define BEFS_MAX_DEPTH 20000
42
43 #ifdef FCS_FREECELL_ONLY
44 #define is_filled_by_any_card() true
45 #else
46 #define is_filled_by_any_card() \
47 (INSTANCE_EMPTY_STACKS_FILL == FCS_ES_FILLED_BY_ANY_CARD)
48 #endif
fc_solve_initialize_befs_rater(fcs_soft_thread * const soft_thread,fcs_state_weighting * const weighting)49 static inline void fc_solve_initialize_befs_rater(
50 fcs_soft_thread *const soft_thread, fcs_state_weighting *const weighting)
51 {
52 const fc_solve_weighting_float *const befs_weights =
53 weighting->befs_weights.weights;
54 // Normalize the BeFS Weights, so the sum of all of them would be 1.
55 fc_solve_weighting_float sum = 0;
56 for (int i = 0; i < FCS_NUM_BEFS_WEIGHTS; i++)
57 {
58 sum += befs_weights[i];
59 }
60 if (sum < 1e-6)
61 {
62 sum = 1;
63 }
64 const_AUTO(factor, INT_MAX / sum);
65 #define W(idx) (befs_weights[idx] * factor)
66 fcs_hard_thread *const hard_thread = soft_thread->hard_thread;
67 fcs_instance *const instance = HT_INSTANCE(hard_thread);
68 HARD__SET_GAME_PARAMS();
69
70 #ifndef FCS_FREECELL_ONLY
71 const bool unlimited_sequence_move_var = INSTANCE_UNLIMITED_SEQUENCE_MOVE;
72 #define unlimited_sequence_move unlimited_sequence_move_var
73 #else
74 #define unlimited_sequence_move false
75 #endif
76
77 const fc_solve_weighting_float num_cards_out_factor =
78 W(FCS_BEFS_WEIGHT_CARDS_OUT) / (LOCAL_DECKS_NUM * 52);
79
80 fc_solve_weighting_float out_sum = 0.0;
81 const_PTR(
82 num_cards_out_lookup_table, weighting->num_cards_out_lookup_table);
83 for (int i = 0; i <= 13; i++, out_sum += num_cards_out_factor)
84 {
85 num_cards_out_lookup_table[i] = out_sum;
86 }
87
88 weighting->max_sequence_move_factor =
89 W(FCS_BEFS_WEIGHT_MAX_SEQUENCE_MOVE) /
90 (is_filled_by_any_card()
91 ? (unlimited_sequence_move
92 ? (LOCAL_FREECELLS_NUM + INSTANCE_STACKS_NUM)
93 : ((LOCAL_FREECELLS_NUM + 1)
94 << (INSTANCE_STACKS_NUM)))
95 : (unlimited_sequence_move ? LOCAL_FREECELLS_NUM : 1));
96
97 weighting->cards_under_sequences_factor =
98 W(FCS_BEFS_WEIGHT_CARDS_UNDER_SEQUENCES) /
99 instance->initial_cards_under_sequences_value;
100
101 weighting->seqs_over_renegade_cards_factor =
102 W(FCS_BEFS_WEIGHT_SEQS_OVER_RENEGADE_CARDS) /
103 FCS_SEQS_OVER_RENEGADE_POWER(LOCAL_DECKS_NUM * (13 * 4));
104
105 weighting->depth_factor = W(FCS_BEFS_WEIGHT_DEPTH) / BEFS_MAX_DEPTH;
106
107 weighting->num_cards_not_on_parents_factor =
108 W(FCS_BEFS_WEIGHT_NUM_CARDS_NOT_ON_PARENTS) / (LOCAL_DECKS_NUM * 52);
109
110 weighting->should_go_over_stacks =
111 ((bool)weighting->max_sequence_move_factor ||
112 (bool)weighting->cards_under_sequences_factor ||
113 (bool)weighting->seqs_over_renegade_cards_factor);
114 }
115 #undef unlimited_sequence_move
116 #undef W
117
118 typedef int fcs_depth;
119
calc_depth(fcs_collectible_state * ptr_state GCC_UNUSED)120 static inline fcs_depth calc_depth(fcs_collectible_state *ptr_state GCC_UNUSED)
121 {
122 #ifdef FCS_WITH_DEPTH_FIELD
123 return (FCS_S_DEPTH(ptr_state));
124 #else
125 #ifdef FCS_HARD_CODE_STATE_DEPTH_FIELD
126 return 0;
127 #else
128 register fcs_depth ret = 0;
129 while ((ptr_state = FCS_S_PARENT(ptr_state)) != NULL)
130 {
131 ++ret;
132 }
133 return ret;
134 #endif
135 #endif
136 }
137
138 #ifdef DEBUG
fcs_trace(const char * const format,...)139 static inline __attribute__((format(printf, 1, 2))) void fcs_trace(
140 const char *const format, ...)
141 {
142 va_list my_va_list;
143 va_start(my_va_list, format);
144
145 if (getenv("FCS_TRACE"))
146 {
147 vfprintf(stdout, format, my_va_list);
148 fflush(stdout);
149 }
150 va_end(my_va_list);
151 }
152 #endif
153
count_num_vacant_freecells(const fcs_game_limit freecells_num GCC_UNUSED,const fcs_state * const state_ptr GCC_UNUSED)154 static inline fcs_game_limit count_num_vacant_freecells(
155 const fcs_game_limit freecells_num GCC_UNUSED,
156 const fcs_state *const state_ptr GCC_UNUSED)
157 {
158 #if MAX_NUM_FREECELLS > 0
159 fcs_game_limit num_vacant_freecells = 0;
160 for (int i = 0; i < freecells_num; i++)
161 {
162 if (fcs_freecell_is_empty(*state_ptr, i))
163 {
164 num_vacant_freecells++;
165 }
166 }
167
168 return num_vacant_freecells;
169 #else
170 return 0;
171 #endif
172 }
173
befs_rate_state(const fcs_soft_thread * const soft_thread,const fcs_state_weighting * const weighting,const fcs_state * const state,const int negated_depth)174 static inline pq_rating befs_rate_state(
175 const fcs_soft_thread *const soft_thread,
176 const fcs_state_weighting *const weighting, const fcs_state *const state,
177 const int negated_depth)
178 {
179 const_AUTO(instance, fcs_st_instance(soft_thread));
180 FCS_ON_NOT_FC_ONLY(const int sequences_are_built_by =
181 GET_INSTANCE_SEQUENCES_ARE_BUILT_BY(instance));
182 HARD__SET_GAME_PARAMS();
183
184 #ifndef FCS_FREECELL_ONLY
185 const bool unlimited_sequence_move_var = INSTANCE_UNLIMITED_SEQUENCE_MOVE;
186 #define unlimited_sequence_move unlimited_sequence_move_var
187 #else
188 #define unlimited_sequence_move false
189 #endif
190
191 fcs_seq_cards_power_type cards_under_sequences = 0;
192 fcs_seq_cards_power_type seqs_over_renegade_cards = 0;
193
194 // #ifdef FCS_HARD_CODE_STATE_DEPTH_FIELD
195 #if 0
196 fc_solve_weighting_float sum = 0;
197 #else
198 fc_solve_weighting_float sum =
199 (max(0, negated_depth) * weighting->depth_factor);
200 #endif
201 const_PTR(
202 num_cards_out_lookup_table, weighting->num_cards_out_lookup_table);
203 if ((bool)num_cards_out_lookup_table[1])
204 {
205 const int num_foundations = (LOCAL_DECKS_NUM << 2);
206 for (int found_idx = 0; found_idx < num_foundations; ++found_idx)
207 {
208 sum += num_cards_out_lookup_table[(
209 int)(fcs_foundation_value((*state), found_idx))];
210 }
211 }
212
213 fcs_game_limit num_vacant_stacks = 0;
214 if (weighting->should_go_over_stacks)
215 {
216 for (int a = 0; a < LOCAL_STACKS_NUM; ++a)
217 {
218 const_AUTO(col, fcs_state_get_col(*state, a));
219 const int cards_num = fcs_col_len(col);
220
221 if (cards_num <= 1)
222 {
223 if (cards_num == 0)
224 {
225 ++num_vacant_stacks;
226 }
227 continue;
228 }
229
230 const int c = update_col_cards_under_sequences(
231 #ifndef FCS_FREECELL_ONLY
232 sequences_are_built_by,
233 #endif
234 col, cards_num - 1);
235
236 cards_under_sequences += FCS_SEQS_OVER_RENEGADE_POWER(c);
237 if (c > 0)
238 {
239 seqs_over_renegade_cards +=
240 ((unlimited_sequence_move)
241 ? 1
242 : FCS_SEQS_OVER_RENEGADE_POWER(cards_num - c));
243 }
244 }
245
246 const fcs_game_limit num_vacant_freecells =
247 count_num_vacant_freecells(LOCAL_FREECELLS_NUM, state);
248 #define CALC_VACANCY_VAL() \
249 (is_filled_by_any_card() \
250 ? (unlimited_sequence_move \
251 ? (num_vacant_freecells + num_vacant_stacks) \
252 : ((num_vacant_freecells + 1) << num_vacant_stacks)) \
253 : (unlimited_sequence_move ? (num_vacant_freecells) : 0))
254 sum += ((CALC_VACANCY_VAL() * weighting->max_sequence_move_factor) +
255 ((instance->initial_cards_under_sequences_value -
256 cards_under_sequences) *
257 weighting->cards_under_sequences_factor) +
258 (seqs_over_renegade_cards *
259 weighting->seqs_over_renegade_cards_factor));
260 }
261
262 const fc_solve_weighting_float num_cards_not_on_parents_weight =
263 weighting->num_cards_not_on_parents_factor;
264 if ((bool)num_cards_not_on_parents_weight)
265 {
266 int num_cards_not_on_parents = (LOCAL_DECKS_NUM * 52);
267 for (int stack_idx = 0; stack_idx < LOCAL_STACKS_NUM; stack_idx++)
268 {
269 const_AUTO(col, fcs_state_get_col(*state, stack_idx));
270 const uint_fast16_t col_len = fcs_col_len(col);
271 for (uint_fast16_t h = 1; h < col_len; h++)
272 {
273 if (!fcs_is_parent_card(
274 fcs_col_get_card(col, h - 1), fcs_col_get_card(col, h)))
275 {
276 num_cards_not_on_parents--;
277 }
278 }
279 }
280 sum += num_cards_not_on_parents * num_cards_not_on_parents_weight;
281 }
282
283 #ifdef DEBUG
284 fcs_trace(
285 "BestFS(rate_state) - %s ; rating=%.40f .\n", "Before return", 0.1);
286 #endif
287 return ((int)sum);
288 #undef CALC_VACANCY_VAL
289 }
290
291 #ifdef FCS_RCS_STATES
292
293 #define FCS_SCANS_the_state (state_key)
294 #define VERIFY_DERIVED_STATE() \
295 { \
296 }
297 #define FCS_ASSIGN_STATE_KEY() \
298 (state_key = (*(fc_solve_lookup_state_key_from_val(instance, PTR_STATE))))
299 #define PTR_STATE (pass.val)
300 #define DECLARE_STATE() \
301 fcs_state state_key; \
302 fcs_kv_state pass = {.key = &(state_key)}
303
304 #else
305
306 #define FCS_SCANS_the_state (PTR_STATE->s)
307 #define VERIFY_DERIVED_STATE() verify_state_sanity(&(single_derived_state->s))
308 #define FCS_ASSIGN_STATE_KEY() \
309 (pass = (typeof(pass)){ \
310 .key = &FCS_SCANS_the_state, .val = &(PTR_STATE->info)})
311 #define PTR_STATE (ptr_state_raw)
312 #define DECLARE_STATE() \
313 fcs_collectible_state *ptr_state_raw; \
314 fcs_kv_state pass
315 #endif
316
317 #define ASSIGN_ptr_state(my_value) \
318 if ((PTR_STATE = my_value)) \
319 { \
320 FCS_ASSIGN_STATE_KEY(); \
321 }
322
323 #if defined(FCS_WITH_DEPTH_FIELD) && \
324 !defined(FCS_HARD_CODE_CALC_REAL_DEPTH_AS_FALSE)
325 // The calculate_real_depth() inline function traces the path of the state
326 // up to the original state, and thus calculates its real depth.
327 //
328 // It then assigns the newly updated depth throughout the path.
calculate_real_depth(const bool calc_real_depth,fcs_collectible_state * const ptr_state_orig)329 static inline void calculate_real_depth(
330 const bool calc_real_depth, fcs_collectible_state *const ptr_state_orig)
331 {
332 if (calc_real_depth)
333 {
334 int_fast32_t this_real_depth = -1;
335 fcs_collectible_state *temp_state = ptr_state_orig;
336 // Count the number of states until the original state.
337 while (temp_state != NULL)
338 {
339 temp_state = FCS_S_PARENT(temp_state);
340 ++this_real_depth;
341 }
342 temp_state = ptr_state_orig;
343 // Assign the new depth throughout the path
344 while (FCS_S_DEPTH(temp_state) != this_real_depth)
345 {
346 FCS_S_DEPTH(temp_state) = (int)this_real_depth;
347 --this_real_depth;
348 temp_state = FCS_S_PARENT(temp_state);
349 }
350 }
351 }
352 #else
353 #define calculate_real_depth(calc_real_depth, ptr_state_orig)
354 #endif
355
356 // The mark_as_dead_end() inline function marks a state as a dead end, and
357 // afterwards propagates this information to its parent and ancestor states.
mark_as_dead_end__proto(fcs_collectible_state * const ptr_state_input)358 static inline void mark_as_dead_end__proto(
359 fcs_collectible_state *const ptr_state_input)
360 {
361 fcs_collectible_state *temp_state = (ptr_state_input);
362 // Mark as a dead end
363 FCS_S_VISITED(temp_state) |= FCS_VISITED_DEAD_END;
364 temp_state = FCS_S_PARENT(temp_state);
365 if (temp_state != NULL)
366 {
367 // Decrease the refcount of the state
368 --(FCS_S_NUM_ACTIVE_CHILDREN(temp_state));
369 while ((FCS_S_NUM_ACTIVE_CHILDREN(temp_state) == 0) &&
370 (FCS_S_VISITED(temp_state) & FCS_VISITED_ALL_TESTS_DONE))
371 {
372 // Mark as dead end
373 FCS_S_VISITED(temp_state) |= FCS_VISITED_DEAD_END;
374 // Go to its parent state
375 temp_state = FCS_S_PARENT(temp_state);
376 if (!temp_state)
377 {
378 break;
379 }
380 // Decrease the refcount
381 (FCS_S_NUM_ACTIVE_CHILDREN(temp_state))--;
382 }
383 }
384 }
385
386 #ifdef FCS_HARD_CODE_SCANS_SYNERGY_AS_TRUE
387 #define MARK_AS_DEAD_END(state) \
388 { \
389 mark_as_dead_end__proto(state); \
390 }
391 #else
392 #define MARK_AS_DEAD_END(state) \
393 { \
394 if (scans_synergy) \
395 { \
396 mark_as_dead_end__proto(state); \
397 } \
398 }
399 #endif
400
401 #ifdef FCS_SINGLE_HARD_THREAD
402 #define BUMP_NUM_CHECKED_STATES__HT()
403 #else
404 #define BUMP_NUM_CHECKED_STATES__HT() (*hard_thread_num_checked_states_ptr)++;
405 #endif
406
407 #define BUMP_NUM_CHECKED_STATES() \
408 { \
409 (*instance_num_checked_states_ptr)++; \
410 BUMP_NUM_CHECKED_STATES__HT() \
411 }
412
count_num_vacant_stacks(const fcs_game_limit stacks_num,const fcs_state * const state_ptr)413 static inline fcs_game_limit count_num_vacant_stacks(
414 const fcs_game_limit stacks_num, const fcs_state *const state_ptr)
415 {
416 fcs_game_limit num_vacant_stacks = 0;
417
418 for (int i = 0; i < stacks_num; i++)
419 {
420 if (fcs_state_col_is_empty(*state_ptr, i))
421 {
422 ++num_vacant_stacks;
423 }
424 }
425
426 return num_vacant_stacks;
427 }
428
fcs__should_state_be_pruned__state(const fcs_collectible_state * const ptr_state)429 static inline bool fcs__should_state_be_pruned__state(
430 const fcs_collectible_state *const ptr_state)
431 {
432 return (!(FCS_S_VISITED(ptr_state) & FCS_VISITED_GENERATED_BY_PRUNING));
433 }
434
435 #ifdef FCS_ENABLE_PRUNE__R_TF__UNCOND
436 #define fcs__should_state_be_pruned(enable_pruning, ptr_state) \
437 fcs__should_state_be_pruned__state(ptr_state)
438 #else
fcs__should_state_be_pruned(const bool enable_pruning,const fcs_collectible_state * const ptr_state)439 static inline bool fcs__should_state_be_pruned(
440 const bool enable_pruning, const fcs_collectible_state *const ptr_state)
441 {
442 return (enable_pruning && fcs__should_state_be_pruned__state(ptr_state));
443 }
444 #endif
445
446 #ifdef FCS_SINGLE_HARD_THREAD
447 #define CALC_HARD_THREAD_MAX_NUM_CHECKED_STATES__HELPER() \
448 (instance->effective_max_num_checked_states)
449 #else
450 #define CALC_HARD_THREAD_MAX_NUM_CHECKED_STATES__HELPER() \
451 (HT_FIELD(hard_thread, ht__num_checked_states) + \
452 (instance->effective_max_num_checked_states - \
453 (instance->i__stats.num_checked_states)))
454 #endif
calc_ht_max_num_states(const fcs_instance * const instance GCC_UNUSED,const fcs_hard_thread * const hard_thread)455 static inline fcs_iters_int calc_ht_max_num_states(
456 const fcs_instance *const instance GCC_UNUSED,
457 const fcs_hard_thread *const hard_thread)
458 {
459 const_AUTO(a, HT_FIELD(hard_thread, ht__max_num_checked_states));
460 #ifdef FCS_WITHOUT_MAX_NUM_STATES
461 return a;
462 #else
463 const_AUTO(b, CALC_HARD_THREAD_MAX_NUM_CHECKED_STATES__HELPER());
464 return min(a, b);
465 #endif
466 }
467
468 #undef state
469 #undef ptr_state_key
470 #undef unlimited_sequence_move
471
472 #ifdef __cplusplus
473 }
474 #endif
475