1 // This file is part of patsolve. It is subject to the license terms in
2 // the LICENSE file found in the top-level directory of this distribution
3 // and at https://github.com/shlomif/patsolve/blob/master/LICENSE . No
4 // part of patsolve, 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) 2002 Tom Holroyd
8 #pragma once
9 #include "freecell-solver/fcs_conf.h"
10
11 #include "game_type_params.h"
12 #include "freecell-solver/fcs_enums.h"
13 #include "tree.h"
14 #include "param.h"
15 #include <limits.h>
16 #include <stdbool.h>
17 #include "freecell-solver/fcs_dllexport.h"
18 #include "state.h"
19 #include "fnv.h"
20 #include "rinutils/alloc_wrap.h"
21 #include "instance.h"
22
23 #define FCS_PATS__COLOR 0x01 /* black if set */
24 #define FCS_PATS__SUIT 0x03 /* mask both suit bits */
25
26 #define FCS_PATS__KING 13
27
28 /* The following implements
29 (Same_suit ? (suit(a) == suit(b)) : (color(a) != color(b))) */
30 #ifdef FCS_FREECELL_ONLY
fcs_pats_is_suitable(const fcs_card a,const fcs_card b)31 static inline bool fcs_pats_is_suitable(const fcs_card a, const fcs_card b)
32 {
33 const fcs_card suit_mask = FCS_PATS__COLOR;
34 const fcs_card suit_val = FCS_PATS__COLOR;
35 return (((a ^ b) & suit_mask) == suit_val);
36 }
37 #else
fcs_pats_is_suitable(const fcs_card a,const fcs_card b,const fcs_card suit_mask,const fcs_card suit_val)38 static inline bool fcs_pats_is_suitable(const fcs_card a, const fcs_card b,
39 const fcs_card suit_mask, const fcs_card suit_val)
40 {
41 return (((a ^ b) & suit_mask) == suit_val);
42 }
43 #endif
44
fcs_pats_is_king_only(const bool not_king_only,const fcs_card card)45 static inline bool fcs_pats_is_king_only(
46 const bool not_king_only, const fcs_card card)
47 {
48 return (not_king_only || fcs_card_rank(card) == FCS_PATS__KING);
49 }
50
51 // Represent a move.
52
53 typedef struct
54 {
55 fcs_card card; /* the card we're moving */
56 unsigned char from, to, fromtype, totype;
57 fcs_card srccard; /* card we're uncovering */
58 fcs_card destcard; /* card we're moving to */
59 signed char pri; /* move priority (low priority == low value) */
60 } fcs_pats__move;
61
62 // Pile types
63 #define FCS_PATS__TYPE_FOUNDATION 1
64 #define FCS_PATS__TYPE_FREECELL 2
65 #define FCS_PATS__TYPE_WASTE 3
66
67 /* Position information. We store a compact representation of the position;
68 Temp cells are stored separately since they don't have to be compared.
69 We also store the move that led to this position from the parent, as well
70 as a pointers back to the parent, and the btree of all positions examined so
71 far. */
72 typedef struct fc_solve_pats__pos__struct
73 {
74 struct fc_solve_pats__pos__struct *queue; /* next position in the queue */
75 struct fc_solve_pats__pos__struct
76 *parent; /* point back up the move stack */
77 fcs_pats__tree *node; /* compact position rep.'s tree node */
78 fcs_pats__move move; /* move that got us here from the parent */
79 unsigned short cluster; /* the cluster this node is in */
80 short depth; /* number of moves so far */
81 unsigned char num_cards_in_freecells; /* number of cards in T */
82 unsigned char num_childs; /* number of child nodes left */
83 } fcs_pats_position;
84
85 // Temp storage for possible moves.
86 // > max # moves from any position
87 #define FCS_PATS__MAX_NUM_MOVES 64
88
89 typedef enum
90 {
91 FCS_PATS__INSERT_CODE_NEW,
92 FCS_PATS__INSERT_CODE_FOUND,
93 FCS_PATS__INSERT_CODE_FOUND_BETTER,
94 FCS_PATS__INSERT_CODE_ERR
95 } fcs_pats__insert_code;
96
97 typedef enum
98 {
99 FCS_PATS__FAIL = -1,
100 FCS_PATS__WIN = 0,
101 FCS_PATS__NOSOL = 1
102 } fc_solve_pats__status_code;
103
104 #ifdef FCS_PATSOLVE__WITH_FAIL_REASON
105 typedef enum
106 {
107 FCS_PATS__FAIL_CHECKED_STATES = 0,
108 } fc_solve_pats__status_fail_reason;
109 #endif
110
111 // Memory.
112 typedef struct fcs_pats__block_struct
113 {
114 unsigned char *block;
115 unsigned char *ptr;
116 size_t remaining;
117 struct fcs_pats__block_struct *next;
118 } fcs_pats__block;
119
120 #define FC_SOLVE__PATS__BLOCKSIZE (32 * 4096)
121
122 typedef struct fcs_pats__treelist_struct
123 {
124 fcs_pats__tree *tree;
125 int cluster;
126 struct fcs_pats__treelist_struct *next;
127 } fcs_pats__treelist;
128
129 #define FC_SOLVE_BUCKETLIST_NBUCKETS 4093 /* the largest 12 bit prime */
130 #define FC_SOLVE__MAX_NUM_PILES 4096 /* a 12 bit code */
131
132 typedef struct fcs_pats__bucket_list_struct
133 {
134 unsigned char *pile; /* 0 terminated copy of the pile */
135 uint32_t hash; /* the pile's hash code */
136 int pilenum; /* the unique id for this pile */
137 struct fcs_pats__bucket_list_struct *next;
138 } fcs_pats__bucket_list;
139
140 // Statistics.
141 #define FC_SOLVE_PATS__NUM_QUEUES 100
142
143 #ifdef PATSOLVE_STANDALONE
144 struct fc_solve_instance_struct
145 {
146 // game parameters
147 fcs_game_type_params game_params;
148 #ifndef FCS_FREECELL_ONLY
149 fcs_card game_variant_suit_mask;
150 fcs_card game_variant_desired_suit_value;
151 #endif
152 };
153
154 typedef struct fc_solve_instance_struct fcs_instance;
155 #endif
156
157 enum FC_SOLVE_PATS__MYDIR
158 {
159 FC_SOLVE_PATS__UP,
160 FC_SOLVE_PATS__DOWN
161 };
162
163 struct fc_solve__patsolve_thread_struct
164 {
165 fcs_instance *instance;
166 size_t remaining_memory;
167 size_t bytes_per_pile;
168 fcs_pats_position
169 *queue_head[FC_SOLVE_PATS__NUM_QUEUES]; /* separate queue for each
170 priority */
171 fcs_pats_position
172 *queue_tail[FC_SOLVE_PATS__NUM_QUEUES]; /* positions are added here */
173 int max_queue_idx;
174 #ifdef DEBUG
175 int num_positions_in_clusters[0x10000];
176 int num_positions_in_queue[FC_SOLVE_PATS__NUM_QUEUES];
177 #endif
178 fcs_pats_position *freed_positions; /* position freelist */
179
180 // Work arrays.
181 struct
182 {
183 fcs_state s;
184 DECLARE_IND_BUF_T(indirect_stacks_buffer)
185 /* used to keep the piles sorted */
186 int column_idxs[MAX_NUM_STACKS];
187 /* Every different pile has a hash and a unique id. */
188 uint32_t stack_hashes[MAX_NUM_STACKS];
189 int stack_ids[MAX_NUM_STACKS];
190 } current_pos;
191
192 /* Temp storage for possible moves. */
193 fcs_pats__move possible_moves[FCS_PATS__MAX_NUM_MOVES];
194
195 /* Statistics. */
196 unsigned long num_checked_states, max_num_checked_states;
197 unsigned long num_states_in_collection;
198 fcs_pats_xy_params pats_solve_params;
199 size_t position_size;
200
201 fcs_pats__bucket_list *buckets_list[FC_SOLVE_BUCKETLIST_NBUCKETS];
202 /* The next pile number to be assigned. */
203 int next_pile_idx;
204 /* reverse lookup for unpack to get the bucket
205 from the pile */
206 fcs_pats__bucket_list *bucket_from_pile_lookup[FC_SOLVE__MAX_NUM_PILES];
207 size_t bytes_per_tree_node;
208 bool dont_exit_on_sol; /* -E means don't exit */
209 int num_solutions; /* number of solutions found in -E mode */
210 /* -S means stack, not queue, the moves to be done. This is a boolean
211 * value.
212 * Default should be false.
213 * */
214 bool to_stack;
215 /* Switch between depth- and breadth-first. Default is "1".*/
216 int num_moves_to_cut_off;
217 /* win, lose, or fail */
218 fc_solve_pats__status_code status;
219 #ifdef FCS_PATSOLVE__WITH_FAIL_REASON
220 fc_solve_pats__status_fail_reason fail_reason;
221 #endif
222 #define FCS_PATS__TREE_LIST_NUM_BUCKETS 499 /* a prime */
223 fcs_pats__treelist *tree_list[FCS_PATS__TREE_LIST_NUM_BUCKETS];
224 fcs_pats__block *my_block;
225
226 ssize_t dequeue__minpos, dequeue__qpos;
227 fcs_pats__move *moves_to_win;
228 size_t num_moves_to_win;
229
230 #define FCS_PATS__SOLVE_LEVEL_GROW_BY 16
231 int curr_solve_depth, max_solve_depth;
232 struct
233 {
234 fcs_pats_position *parent;
235 int num_moves;
236 fcs_pats__move *moves_start, *moves_end, *move_ptr;
237 bool q;
238 fcs_pats_position *pos;
239 } * solve_stack;
240 fcs_pats_position *curr_solve_pos;
241 enum FC_SOLVE_PATS__MYDIR curr_solve_dir;
242 };
243
244 typedef struct fc_solve__patsolve_thread_struct fcs_pats_thread;
245
246 extern fcs_pats__insert_code fc_solve_pats__insert(
247 fcs_pats_thread *soft_thread, int *cluster, int d, fcs_pats__tree **node);
248 extern void fc_solve_pats__do_it(fcs_pats_thread *);
249 extern fcs_pats__move *fc_solve_pats__get_moves(
250 fcs_pats_thread *soft_thread, fcs_pats_position *, int *);
251 extern unsigned char *fc_solve_pats__new_from_block(
252 fcs_pats_thread *soft_thread, size_t);
253 extern void fc_solve_pats__sort_piles(fcs_pats_thread *soft_thread);
254
255 extern fcs_pats__block *fc_solve_pats__new_block(
256 fcs_pats_thread *const soft_thread);
257
fc_solve_pats__init_clusters(fcs_pats_thread * const soft_thread)258 static inline void fc_solve_pats__init_clusters(
259 fcs_pats_thread *const soft_thread)
260 {
261 memset(soft_thread->tree_list, 0, sizeof(soft_thread->tree_list));
262 soft_thread->my_block = fc_solve_pats__new_block(soft_thread);
263 }
264
265 /* In order to keep the fcs_pats__tree structure aligned, we need to add
266 up to 7 bytes on Alpha or 3 bytes on Intel -- but this is still
267 better than storing the fcs_pats__tree nodes and keys separately, as that
268 requires a pointer. On Intel for -f bytes_per_tree_node winds up being
269 a multiple of 8 currently anyway so it doesn't matter. */
fc_solve_pats__align(const size_t i)270 static inline size_t fc_solve_pats__align(const size_t i)
271 {
272 const typeof(i) ALIGN_BITS = 0x7;
273 return ((i & ALIGN_BITS) ? ((i | ALIGN_BITS) + 1) : i);
274 }
275
fc_solve_pats__init_buckets(fcs_pats_thread * const soft_thread)276 static inline void fc_solve_pats__init_buckets(
277 fcs_pats_thread *const soft_thread)
278 {
279 #if !defined(HARD_CODED_NUM_STACKS) || !defined(HARD_CODED_NUM_FREECELLS)
280 const fcs_instance *const instance = soft_thread->instance;
281 #endif
282 const int stacks_num = INSTANCE_STACKS_NUM;
283 const int freecells_num = INSTANCE_FREECELLS_NUM;
284
285 // Packed positions need 3 bytes for every 2 piles.
286 soft_thread->bytes_per_pile =
287 (size_t)(((stacks_num * 3) >> 1) + (stacks_num & 0x1));
288
289 memset(soft_thread->buckets_list, 0, sizeof(soft_thread->buckets_list));
290 soft_thread->next_pile_idx = 0;
291 soft_thread->bytes_per_tree_node = fc_solve_pats__align(
292 sizeof(fcs_pats__tree) + soft_thread->bytes_per_pile);
293 soft_thread->position_size =
294 fc_solve_pats__align(sizeof(fcs_pats_position) + (size_t)freecells_num);
295 }
296
297 // A function and some macros for allocating memory.
298 // Allocate some space and return a pointer to it. See fc_solve_pats__new()
fc_solve_pats__malloc(fcs_pats_thread * const soft_thread,const size_t s)299 static inline void *fc_solve_pats__malloc(
300 fcs_pats_thread *const soft_thread, const size_t s)
301 {
302 if (s > soft_thread->remaining_memory)
303 {
304 #if 0
305 fcs_pats_position *pos;
306
307 /* Try to get some space back from the freelist. A vain hope. */
308
309 while (soft_thread->freed_positions) {
310 pos = soft_thread->freed_positions->queue;
311 fc_solve_pats__free_array(soft_thread->freed_positions, unsigned char, sizeof(*pos) + LOCAL_FREECELLS_NUM);
312 soft_thread->freed_positions = pos;
313 }
314 if (s > soft_thread->remaining_memory) {
315 soft_thread->status = FCS_PATS__FAIL;
316 return NULL;
317 }
318 #else
319 soft_thread->status = FCS_PATS__FAIL;
320 return NULL;
321 #endif
322 }
323
324 void *const x = malloc(s);
325
326 if (x == NULL)
327 {
328 soft_thread->status = FCS_PATS__FAIL;
329 return NULL;
330 }
331
332 soft_thread->remaining_memory -= s;
333 return x;
334 }
335
336 #define fc_solve_pats__new(soft_thread, type) \
337 ((type *)fc_solve_pats__malloc(soft_thread, sizeof(type)))
338
fc_solve_pats__release(fcs_pats_thread * const soft_thread,void * const ptr,const size_t count_freed)339 static inline void fc_solve_pats__release(fcs_pats_thread *const soft_thread,
340 void *const ptr, const size_t count_freed)
341 {
342 free(ptr);
343 soft_thread->remaining_memory += count_freed;
344 }
345
346 #define fc_solve_pats__free_ptr(soft_thread, ptr, type) \
347 fc_solve_pats__release((soft_thread), (ptr), sizeof(type))
348
349 #define fc_solve_pats__new_array(soft_thread, type, size) \
350 ((type *)fc_solve_pats__malloc(soft_thread, (size) * sizeof(type)))
351 #define fc_solve_pats__free_array(soft_thread, ptr, type, size) \
352 fc_solve_pats__release((soft_thread), (ptr), ((size) * sizeof(type)))
353
fc_solve_pats__free_buckets(fcs_pats_thread * const soft_thread)354 static inline void fc_solve_pats__free_buckets(
355 fcs_pats_thread *const soft_thread)
356 {
357 for (int i = 0; i < FC_SOLVE_BUCKETLIST_NBUCKETS; i++)
358 {
359 var_AUTO(l, soft_thread->buckets_list[i]);
360 while (l)
361 {
362 var_AUTO(n, l->next);
363 fc_solve_pats__free_array(soft_thread, l->pile, unsigned char,
364 strlen((const char *)l->pile) + 1);
365 fc_solve_pats__free_ptr(soft_thread, l, fcs_pats__bucket_list);
366 l = n;
367 }
368 soft_thread->buckets_list[i] = NULL;
369 }
370 }
371
fc_solve_pats__free_blocks(fcs_pats_thread * const soft_thread)372 static inline void fc_solve_pats__free_blocks(
373 fcs_pats_thread *const soft_thread)
374 {
375 var_AUTO(b, soft_thread->my_block);
376 while (b)
377 {
378 const_AUTO(next, b->next);
379 fc_solve_pats__free_array(
380 soft_thread, b->block, unsigned char, FC_SOLVE__PATS__BLOCKSIZE);
381 fc_solve_pats__free_ptr(soft_thread, b, fcs_pats__block);
382 b = next;
383 }
384 soft_thread->my_block = NULL;
385 }
386
fc_solve_pats__free_clusters(fcs_pats_thread * const soft_thread)387 static inline void fc_solve_pats__free_clusters(
388 fcs_pats_thread *const soft_thread)
389 {
390 for (int i = 0; i < FCS_PATS__TREE_LIST_NUM_BUCKETS; i++)
391 {
392 var_AUTO(l, soft_thread->tree_list[i]);
393 while (l)
394 {
395 var_AUTO(n, l->next);
396 fc_solve_pats__free_ptr(soft_thread, l, fcs_pats__treelist);
397 l = n;
398 }
399 soft_thread->tree_list[i] = NULL;
400 }
401 }
402
fc_solve_pats__soft_thread_reset_helper(fcs_pats_thread * const soft_thread)403 static inline void fc_solve_pats__soft_thread_reset_helper(
404 fcs_pats_thread *const soft_thread)
405 {
406 soft_thread->freed_positions = NULL;
407 soft_thread->num_checked_states = 0;
408 soft_thread->num_states_in_collection = 0;
409 soft_thread->num_solutions = 0;
410
411 soft_thread->status = FCS_PATS__NOSOL;
412
413 soft_thread->dequeue__qpos = 0;
414 soft_thread->dequeue__minpos = 0;
415
416 soft_thread->curr_solve_depth = 0;
417 soft_thread->curr_solve_pos = NULL;
418 }
419
fc_solve_pats__recycle_soft_thread(fcs_pats_thread * const soft_thread)420 static inline void fc_solve_pats__recycle_soft_thread(
421 fcs_pats_thread *const soft_thread)
422 {
423 fc_solve_pats__free_buckets(soft_thread);
424 fc_solve_pats__free_clusters(soft_thread);
425 fc_solve_pats__free_blocks(soft_thread);
426
427 if (soft_thread->moves_to_win)
428 {
429 free(soft_thread->moves_to_win);
430 soft_thread->moves_to_win = NULL;
431 soft_thread->num_moves_to_win = 0;
432 }
433 fc_solve_pats__soft_thread_reset_helper(soft_thread);
434 }
435
fc_solve_pats__init_soft_thread(fcs_pats_thread * const soft_thread,fcs_instance * const instance)436 static inline void fc_solve_pats__init_soft_thread(
437 fcs_pats_thread *const soft_thread, fcs_instance *const instance)
438 {
439 soft_thread->instance = instance;
440 soft_thread->dont_exit_on_sol = false;
441 soft_thread->to_stack = false;
442 soft_thread->num_moves_to_cut_off = 1;
443 soft_thread->remaining_memory = (50 * 1000 * 1000);
444 soft_thread->freed_positions = NULL;
445 soft_thread->max_num_checked_states = ULONG_MAX;
446
447 soft_thread->moves_to_win = NULL;
448 soft_thread->num_moves_to_win = 0;
449
450 fc_solve_pats__soft_thread_reset_helper(soft_thread);
451
452 soft_thread->max_solve_depth = FCS_PATS__SOLVE_LEVEL_GROW_BY;
453 soft_thread->solve_stack = (typeof(soft_thread->solve_stack))SMALLOC(
454 soft_thread->solve_stack, (size_t)soft_thread->max_solve_depth);
455 }
456
fc_solve_pats__destroy_soft_thread(fcs_pats_thread * const soft_thread)457 static inline void fc_solve_pats__destroy_soft_thread(
458 fcs_pats_thread *const soft_thread)
459 {
460 free(soft_thread->solve_stack);
461 soft_thread->solve_stack = NULL;
462 soft_thread->max_solve_depth = 0;
463 soft_thread->curr_solve_depth = -1;
464 }
465
fc_solve_pats__hashpile(fcs_pats_thread * const soft_thread,const int w)466 static inline void fc_solve_pats__hashpile(
467 fcs_pats_thread *const soft_thread, const int w)
468 {
469 var_AUTO(col, fcs_state_get_col(soft_thread->current_pos.s, w));
470 fcs_col_get_card(col, (int)fcs_col_len(col)) = '\0';
471 soft_thread->current_pos.stack_hashes[w] =
472 fnv_hash_str((const unsigned char *)(col + 1));
473
474 // Invalidate this pile's id. We'll calculate it later.
475 soft_thread->current_pos.stack_ids[w] = -1;
476 }
477
478 extern fcs_pats_position *fc_solve_pats__new_position(
479 fcs_pats_thread *const soft_thread, fcs_pats_position *const parent,
480 const fcs_pats__move *const m);
481
482 extern void fc_solve_pats__queue_position(
483 fcs_pats_thread *const soft_thread, fcs_pats_position *const pos, int pri);
484
485 #if !defined(HARD_CODED_NUM_STACKS)
486 #define DECLARE_STACKS() const_SLOT(game_params, soft_thread->instance)
487 #else
488 #define DECLARE_STACKS()
489 #endif
490
fc_solve_pats__hash_layout(fcs_pats_thread * const soft_thread)491 static inline void fc_solve_pats__hash_layout(
492 fcs_pats_thread *const soft_thread)
493 {
494 DECLARE_STACKS();
495
496 for (int w = 0; w < LOCAL_STACKS_NUM; w++)
497 {
498 fc_solve_pats__hashpile(soft_thread, w);
499 }
500 }
501
fc_solve_pats__initialize_solving_process(fcs_pats_thread * const soft_thread)502 static inline void fc_solve_pats__initialize_solving_process(
503 fcs_pats_thread *const soft_thread)
504 {
505 // Init the queues.
506 for (int i = 0; i < FC_SOLVE_PATS__NUM_QUEUES; i++)
507 {
508 soft_thread->queue_head[i] = NULL;
509 }
510 soft_thread->max_queue_idx = 0;
511 #ifdef DEBUG
512 memset(soft_thread->num_positions_in_clusters, 0,
513 sizeof(soft_thread->num_positions_in_clusters));
514 memset(soft_thread->num_positions_in_queue, 0,
515 sizeof(soft_thread->num_positions_in_queue));
516 #endif
517
518 // Queue the initial position to get started.
519 fc_solve_pats__hash_layout(soft_thread);
520 fc_solve_pats__sort_piles(soft_thread);
521 fcs_pats__move m;
522 m.card = fc_solve_empty_card;
523 fcs_pats_position *const pos =
524 fc_solve_pats__new_position(soft_thread, NULL, &m);
525 if (pos == NULL)
526 {
527 return;
528 }
529 fc_solve_pats__queue_position(soft_thread, pos, 0);
530 }
531
fc_solve_pats__set_cut_off(fcs_pats_thread * const soft_thread)532 static inline void fc_solve_pats__set_cut_off(
533 fcs_pats_thread *const soft_thread)
534 {
535 soft_thread->num_moves_to_cut_off =
536 soft_thread->pats_solve_params.x[FC_SOLVE_PATS__NUM_X_PARAM - 1];
537 }
538
539 #if 0
540 #ifdef DEBUG
541
542 #include "msg.h"
543 static inline void fc_solve_pats__print_queue(fcs_pats_thread * soft_thread)
544 {
545 fc_solve_msg("max_queue_idx %d\n", soft_thread->max_queue_idx);
546 int n = 0;
547 for (int i = 0; i <= soft_thread->max_queue_idx; i++) {
548 if (soft_thread->num_positions_in_queue[i]) {
549 fc_solve_msg("num_positions_in_queue %2d %5d", i, soft_thread->num_positions_in_queue[i]);
550 if (n & 1) {
551 fc_solve_msg("\n");
552 } else {
553 fc_solve_msg("\t\t");
554 }
555 n++;
556 }
557 }
558 fc_solve_msg("\n");
559 }
560 #endif
561 #endif
562