« back to all changes in this revision
Viewing changes to scans.c
- browse files at revision 8
- compare with another revision
- download diff
- download tarball
- view history from revision 8
- Committer: Package Import Robot
- Author(s): Gergely Risko
- Date: 2012-06-22 10:08:05 UTC
- mfrom: (1.1.6)
- Revision ID: package-import@ubuntu.com-20120622100805-evoda1ccdr8vt5xr
Tags: 3.12.0-1
New upstream version. (closes: #675262)
- files added:
- .pc
- .pc/debian-changes
- .pc/debian-changes/Presets
- .pc/debian-changes/Presets/presets
- .pc/debian-changes/board_gen
- debian/patches
- libavl
- scripts/parallel-solve-setup-here
- t/dbm
- t/t/data/presets
- t/t/data/range-verifier
- t/t/data/range-verifier/bakers-game-11-to-20
- t/t/data/range-verifier/bakers-game-solutions-dir
- t/t/lib/Games/ABC_Path
- files removed:
- .2_freecells_2nd_time_using_atomic_moves.bash.swp
- files modified:
- AUTHORS
added
removed
scans.c
53
53
#include "likely.h"
54
54
#include "bool.h"
55
55
56
#if 0
57
#define DEBUG 1
58
#endif
59
56
60
#define SOFT_DFS_DEPTH_GROW_BY 16
57
61
void fc_solve_increase_dfs_max_depth(
58
62
fc_solve_soft_thread_t * soft_thread
89
93
#define FCS_IS_STATE_DEAD_END(ptr_state) \
90
94
(FCS_S_VISITED(ptr_state) & FCS_VISITED_DEAD_END)
91
95
96
#if ((FCS_STATE_STORAGE == FCS_STATE_STORAGE_INTERNAL_HASH) || (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GOOGLE_DENSE_HASH))
92
97
static fcs_bool_t free_states_should_delete(void * key, void * context)
93
98
{
94
fc_solve_instance_t * instance = (fc_solve_instance_t *)context;
95
fcs_collectible_state_t * ptr_state = (fcs_collectible_state_t *)key;
99
fc_solve_instance_t * const instance = (fc_solve_instance_t * const)context;
100
fcs_collectible_state_t * const ptr_state = (fcs_collectible_state_t * const)key;
96
101
97
102
if (FCS_IS_STATE_DEAD_END(ptr_state))
98
103
{
108
113
return FALSE;
109
114
}
110
115
}
116
#endif
117
118
static GCC_INLINE void free_states_handle_soft_dfs_soft_thread(
119
fc_solve_soft_thread_t * soft_thread
120
)
121
{
122
fcs_soft_dfs_stack_item_t * soft_dfs_info =
123
soft_thread->method_specific.soft_dfs.soft_dfs_info;
124
fcs_soft_dfs_stack_item_t * const end_soft_dfs_info =
125
soft_dfs_info + soft_thread->method_specific.soft_dfs.depth;
126
127
for(;soft_dfs_info < end_soft_dfs_info; soft_dfs_info++)
128
{
129
int * rand_index_ptr, * dest_rand_index_ptr, * end_rand_index_ptr;
130
fcs_derived_states_list_item_t * const states =
131
soft_dfs_info->derived_states_list.states;
132
/*
133
* We start from current_state_index instead of current_state_index+1
134
* because that is the next state to be checked - it is referenced
135
* by current_state_index++ instead of ++current_state_index .
136
* */
137
dest_rand_index_ptr = rand_index_ptr =
138
soft_dfs_info->derived_states_random_indexes
139
+ soft_dfs_info->current_state_index
140
;
141
end_rand_index_ptr =
142
soft_dfs_info->derived_states_random_indexes
143
+ soft_dfs_info->derived_states_list.num_states
144
;
145
146
for( ; rand_index_ptr < end_rand_index_ptr ; rand_index_ptr++ )
147
{
148
if (! FCS_IS_STATE_DEAD_END(states[*(rand_index_ptr)].state_ptr))
149
{
150
*(dest_rand_index_ptr++) = *(rand_index_ptr);
151
}
152
}
153
soft_dfs_info->derived_states_list.num_states =
154
dest_rand_index_ptr - soft_dfs_info->derived_states_random_indexes;
155
}
156
157
return;
158
}
159
160
#ifdef DEBUG
161
162
static void verify_state_sanity(
163
fcs_state_t * ptr_state
164
)
165
{
166
int i;
167
168
for (i=0; i < 8 ; i++)
169
{
170
int l = fcs_col_len(fcs_state_get_col(*(ptr_state), i));
171
assert ((l >= 0) && (l <= 7+12));
172
}
173
174
return;
175
}
176
177
#ifdef DEBUG_VERIFY_SOFT_DFS_STACK
178
static void verify_soft_dfs_stack(
179
fc_solve_soft_thread_t * soft_thread
180
)
181
{
182
int depth = 0, i, num_states;
183
for (depth = 0 ; depth < soft_thread->method_specific.soft_dfs.depth ; depth++)
184
{
185
fcs_soft_dfs_stack_item_t * soft_dfs_info;
186
int * rand_indexes;
187
188
soft_dfs_info = &(soft_thread->method_specific.soft_dfs.soft_dfs_info[depth]);
189
rand_indexes = soft_dfs_info->derived_states_random_indexes;
190
191
num_states = soft_dfs_info->derived_states_list.num_states;
192
193
for ( i=soft_dfs_info->current_state_index ; i < num_states ; i++)
194
{
195
verify_state_sanity(soft_dfs_info->derived_states_list.states[rand_indexes[i]].state_ptr);
196
}
197
}
198
199
return;
200
}
201
#define VERIFY_SOFT_DFS_STACK(soft_thread) verify_soft_dfs_stack(soft_thread)
202
#else
203
#define VERIFY_SOFT_DFS_STACK(soft_thread)
204
#endif
205
206
#endif
111
207
112
208
static void free_states(fc_solve_instance_t * instance)
113
209
{
210
#ifdef DEBUG
211
printf("%s\n", "FREE_STATES HIT");
212
#endif
213
#if (! ((FCS_STATE_STORAGE == FCS_STATE_STORAGE_INTERNAL_HASH) || (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GOOGLE_DENSE_HASH)))
214
return;
215
#else
216
{
217
HT_LOOP_DECLARE_VARS();
218
114
219
/* First of all, let's make sure the soft_threads will no longer
115
220
* traverse to the freed states that are currently dead end.
116
221
* */
117
222
118
HT_LOOP_DECLARE_VARS();
119
223
120
224
HT_LOOP_START()
121
225
{
129
233
case FCS_METHOD_HARD_DFS:
130
234
case FCS_METHOD_RANDOM_DFS:
131
235
{
132
fcs_soft_dfs_stack_item_t * soft_dfs_info,
133
* end_soft_dfs_info;
134
135
soft_dfs_info = soft_thread->method_specific.soft_dfs.soft_dfs_info;
136
137
end_soft_dfs_info = soft_dfs_info + soft_thread->method_specific.soft_dfs.depth;
138
139
for(;soft_dfs_info < end_soft_dfs_info; soft_dfs_info++)
140
{
141
int derived_state_idx_idx;
142
143
derived_state_idx_idx = soft_dfs_info->current_state_index+1;
144
145
for(;
146
derived_state_idx_idx <
147
soft_dfs_info->derived_states_list.num_states
148
;
149
derived_state_idx_idx++
150
)
151
{
152
if (FCS_IS_STATE_DEAD_END(soft_dfs_info->derived_states_list.states[soft_dfs_info->derived_states_random_indexes[derived_state_idx_idx]].state_ptr))
153
{
154
memmove(
155
soft_dfs_info->derived_states_random_indexes + derived_state_idx_idx+1,
156
soft_dfs_info->derived_states_random_indexes + derived_state_idx_idx,
157
(--(soft_dfs_info->derived_states_list.num_states) - derived_state_idx_idx)
158
);
159
}
160
}
161
}
236
free_states_handle_soft_dfs_soft_thread(soft_thread);
162
237
}
163
238
break;
164
239
215
290
((void *)instance)
216
291
);
217
292
#endif
293
}
294
#endif
218
295
}
219
296
220
/*
221
fc_solve_soft_dfs_do_solve is the event loop of the
222
Random-DFS scan. DFS which is recursive in nature is handled here
223
without procedural recursion
224
by using some dedicated stacks for the traversal.
225
*/
297
#define STATE_TO_PASS() (&(pass))
298
#define NEW_STATE_TO_PASS() (&(new_pass))
299
226
300
#ifdef FCS_RCS_STATES
301
302
#define INITIALIZE_STATE() pass.key = &(state_key)
227
303
#define the_state (state_key)
304
#define VERIFY_DERIVED_STATE() {}
305
#define FCS_ASSIGN_STATE_KEY() (state_key = (*(fc_solve_lookup_state_key_from_val(instance, PTR_STATE))))
306
#define PTR_STATE (pass.val)
307
#define DECLARE_STATE() fcs_state_t state_key; fcs_kv_state_t pass
308
#define DECLARE_NEW_STATE() fcs_kv_state_t new_pass
309
#define ptr_new_state (new_pass.val)
310
228
311
#else
229
#define the_state (ptr_state->s)
312
313
#define INITIALIZE_STATE() {}
314
#define the_state (PTR_STATE->s)
315
#define VERIFY_DERIVED_STATE() verify_state_sanity(&(single_derived_state->s))
316
#define FCS_ASSIGN_STATE_KEY() { pass.key = &(the_state); pass.val = &(PTR_STATE->info); }
317
#define PTR_STATE (ptr_state_raw)
318
#define DECLARE_STATE() fcs_collectible_state_t * ptr_state_raw; fcs_kv_state_t pass
319
#define DECLARE_NEW_STATE() fcs_collectible_state_t * ptr_new_state; fcs_kv_state_t new_pass
230
320
#endif
231
321
322
#define ASSIGN_ptr_state(my_value) { if ((PTR_STATE = my_value)) { FCS_ASSIGN_STATE_KEY(); } }
323
232
324
#ifdef DEBUG
233
325
#define TRACE0(message) \
234
326
{ \
235
327
if (getenv("FCS_TRACE")) \
236
328
{ \
237
printf("%s. Depth=%d ; the_soft_Depth=%d ; Iters=%d ; test_index=%d ; current_state_index=%d ; num_states=%d\n", \
329
printf("%s. Depth=%d ; the_soft_Depth=%ld ; Iters=%d ; test_index=%d ; current_state_index=%d ; num_states=%d\n", \
238
330
message, \
239
soft_thread->method_specific.soft_dfs.depth, (the_soft_dfs_info-soft_thread->method_specific.soft_dfs.soft_dfs_info), \
331
soft_thread->method_specific.soft_dfs.depth, \
332
(long int)(the_soft_dfs_info-soft_thread->method_specific.soft_dfs.soft_dfs_info), \
240
333
instance->num_times, the_soft_dfs_info->test_index, \
241
334
the_soft_dfs_info->current_state_index, \
242
335
(derived_states_list ? derived_states_list->num_states : -1) \
244
337
fflush(stdout); \
245
338
} \
246
339
}
340
341
#define VERIFY_STATE_SANITY() verify_state_sanity(&the_state)
342
343
#define VERIFY_PTR_STATE_TRACE0(string) \
344
{ \
345
TRACE0(string); \
346
VERIFY_STATE_SANITY(); \
347
VERIFY_SOFT_DFS_STACK(soft_thread); \
348
}
349
350
351
#define VERIFY_PTR_STATE_AND_DERIVED_TRACE0(string) \
352
{ \
353
TRACE0(string); \
354
VERIFY_STATE_SANITY(); \
355
VERIFY_DERIVED_STATE(); \
356
VERIFY_SOFT_DFS_STACK(soft_thread); \
357
}
358
247
359
#else
360
248
361
#define TRACE0(no_use) {}
362
#define VERIFY_PTR_STATE_TRACE0(no_use) {}
363
#define VERIFY_PTR_STATE_AND_DERIVED_TRACE0(no_use) {}
364
249
365
#endif
250
366
367
#ifndef FCS_WITHOUT_DEPTH_FIELD
251
368
/*
252
* This macro traces the path of the state up to the original state,
253
* and thus calculates its real depth.
369
* The calculate_real_depth() inline function traces the path of the state up
370
* to the original state, and thus calculates its real depth.
254
371
*
255
372
* It then assigns the newly updated depth throughout the path.
256
373
*
257
374
* */
258
375
259
#define calculate_real_depth(ptr_state_orig) \
260
{ \
261
if (calc_real_depth) \
262
{ \
263
int this_real_depth = 0; \
264
fcs_collectible_state_t * temp_state = ptr_state_orig; \
265
/* Count the number of states until the original state. */ \
266
while(temp_state != NULL) \
267
{ \
268
temp_state = FCS_S_PARENT(temp_state); \
269
this_real_depth++; \
270
} \
271
this_real_depth--; \
272
temp_state = (ptr_state_orig); \
273
/* Assign the new depth throughout the path */ \
274
while (FCS_S_DEPTH(temp_state) != this_real_depth) \
275
{ \
276
FCS_S_DEPTH(temp_state) = this_real_depth; \
277
this_real_depth--; \
278
temp_state = FCS_S_PARENT(temp_state); \
279
} \
280
} \
376
static GCC_INLINE void calculate_real_depth(fcs_bool_t calc_real_depth, fcs_collectible_state_t * ptr_state_orig)
377
{
378
if (calc_real_depth)
379
{
380
int this_real_depth = 0;
381
fcs_collectible_state_t * temp_state = ptr_state_orig;
382
/* Count the number of states until the original state. */
383
while(temp_state != NULL)
384
{
385
temp_state = FCS_S_PARENT(temp_state);
386
this_real_depth++;
387
}
388
this_real_depth--;
389
temp_state = (ptr_state_orig);
390
/* Assign the new depth throughout the path */
391
while (FCS_S_DEPTH(temp_state) != this_real_depth)
392
{
393
FCS_S_DEPTH(temp_state) = this_real_depth;
394
this_real_depth--;
395
temp_state = FCS_S_PARENT(temp_state);
396
}
397
}
398
399
return;
281
400
}
401
#else
402
#define calculate_real_depth(calc_real_depth, ptr_state_orig) {}
403
#endif
282
404
283
405
/*
284
* This macro marks a state as a dead end, and afterwards propogates
285
* this information to its parent and ancestor states.
406
* The mark_as_dead_end() inline function marks a state as a dead end, and
407
* afterwards propogates this information to its parent and ancestor states.
408
*
286
409
* */
287
410
288
#define mark_as_dead_end(ptr_state_input) \
289
{ \
290
if (scans_synergy) \
291
{ \
292
fcs_collectible_state_t * temp_state = (ptr_state_input); \
293
/* Mark as a dead end */ \
294
FCS_S_VISITED(temp_state)|= FCS_VISITED_DEAD_END; \
295
temp_state = FCS_S_PARENT(temp_state); \
296
if (temp_state != NULL) \
297
{ \
298
/* Decrease the refcount of the state */ \
299
(FCS_S_NUM_ACTIVE_CHILDREN(temp_state))--; \
300
while((FCS_S_NUM_ACTIVE_CHILDREN(temp_state) == 0) && (FCS_S_VISITED(temp_state) & FCS_VISITED_ALL_TESTS_DONE)) \
301
{ \
302
/* Mark as dead end */ \
303
FCS_S_VISITED(temp_state) |= FCS_VISITED_DEAD_END; \
304
/* Go to its parent state */ \
305
temp_state = FCS_S_PARENT(temp_state); \
306
if (temp_state == NULL) \
307
{ \
308
break; \
309
} \
310
/* Decrease the refcount */ \
311
(FCS_S_NUM_ACTIVE_CHILDREN(temp_state))--; \
312
} \
313
} \
314
} \
411
static GCC_INLINE void mark_as_dead_end(fcs_bool_t scans_synergy, fcs_collectible_state_t * ptr_state_input)
412
{
413
if (scans_synergy)
414
{
415
fcs_collectible_state_t * temp_state = (ptr_state_input);
416
/* Mark as a dead end */
417
FCS_S_VISITED(temp_state)|= FCS_VISITED_DEAD_END;
418
temp_state = FCS_S_PARENT(temp_state);
419
if (temp_state != NULL)
420
{
421
/* Decrease the refcount of the state */
422
(FCS_S_NUM_ACTIVE_CHILDREN(temp_state))--;
423
while((FCS_S_NUM_ACTIVE_CHILDREN(temp_state) == 0) && (FCS_S_VISITED(temp_state) & FCS_VISITED_ALL_TESTS_DONE))
424
{
425
/* Mark as dead end */
426
FCS_S_VISITED(temp_state) |= FCS_VISITED_DEAD_END;
427
/* Go to its parent state */
428
temp_state = FCS_S_PARENT(temp_state);
429
if (temp_state == NULL)
430
{
431
break;
432
}
433
/* Decrease the refcount */
434
(FCS_S_NUM_ACTIVE_CHILDREN(temp_state))--;
435
}
436
}
437
}
438
439
return;
315
440
}
316
441
317
442
#define BUMP_NUM_TIMES() \
318
443
{ \
319
instance->num_times++; \
320
hard_thread->num_times++; \
444
(*instance_num_times_ptr)++; \
445
(*hard_thread_num_times_ptr)++; \
321
446
}
322
447
323
448
#define SHOULD_STATE_BE_PRUNED(enable_pruning, ptr_state) \
336
461
fcs_collectible_state_t * state_val;
337
462
} cache_parents_stack_item_t;
338
463
464
/* TODO : Unit-test this function as it had had a bug beforehand
465
* because fcs_lru_side_t had been an unsigned long.
466
* */
467
typedef const char * fcs_lru_side_t;
468
469
extern int fc_solve_compare_lru_cache_keys(
470
const void * void_a, const void * void_b, void * context
471
)
472
{
473
#define GET_PARAM(p) ((fcs_lru_side_t)(((const fcs_cache_key_info_t *)(p))->val_ptr))
474
fcs_lru_side_t a, b;
475
476
a = GET_PARAM(void_a);
477
b = GET_PARAM(void_b);
478
479
return ((a > b) ? 1 : (a < b) ? (-1) : 0);
480
#undef GET_PARAM
481
}
482
339
483
#define NEXT_CACHE_STATE(s) ((s)->lower_pri)
340
484
fcs_state_t * fc_solve_lookup_state_key_from_val(
341
485
fc_solve_instance_t * instance,
342
486
fcs_collectible_state_t * orig_ptr_state_val
343
487
)
344
488
{
489
#if (FCS_RCS_CACHE_STORAGE == FCS_RCS_CACHE_STORAGE_JUDY)
345
490
PWord_t PValue;
491
#endif
346
492
fcs_lru_cache_t * cache;
347
493
cache_parents_stack_item_t * parents_stack;
348
494
int parents_stack_len, parents_stack_max_len;
366
512
367
513
while (1)
368
514
{
515
#if (FCS_RCS_CACHE_STORAGE == FCS_RCS_CACHE_STORAGE_JUDY)
369
516
JLI (
370
517
PValue,
371
518
cache->states_values_to_keys_map,
372
519
((Word_t)parents_stack[parents_stack_len-1].state_val)
373
520
);
374
375
521
if (*PValue)
376
522
{
377
523
parents_stack[parents_stack_len-1].new_cache_state
395
541
sizeof(*new_cache_state)
396
542
);
397
543
}
544
}
545
#else
546
{
547
fcs_cache_key_info_t * existing_cache_state;
548
549
if (cache->recycle_bin)
550
{
551
new_cache_state = cache->recycle_bin;
552
cache->recycle_bin = NEXT_CACHE_STATE(new_cache_state);
553
}
554
else
555
{
556
new_cache_state
557
= fcs_compact_alloc_ptr(
558
&(cache->states_values_to_keys_allocator),
559
sizeof(*new_cache_state)
560
);
561
}
562
563
new_cache_state->val_ptr = parents_stack[parents_stack_len-1].state_val;
564
existing_cache_state = (fcs_cache_key_info_t *)fc_solve_kaz_tree_alloc_insert(
565
cache->kaz_tree,
566
new_cache_state
567
);
568
569
if (existing_cache_state)
570
{
571
NEXT_CACHE_STATE( new_cache_state ) = cache->recycle_bin;
572
cache->recycle_bin = new_cache_state;
573
574
parents_stack[parents_stack_len-1].new_cache_state
575
= new_cache_state = existing_cache_state;
576
break;
577
}
578
}
579
#endif
398
580
399
581
parents_stack[parents_stack_len-1].new_cache_state
400
582
= new_cache_state;
401
583
584
#if (FCS_RCS_CACHE_STORAGE == FCS_RCS_CACHE_STORAGE_JUDY)
402
585
*PValue = ((Word_t)new_cache_state);
403
586
404
587
new_cache_state->val_ptr
405
588
= parents_stack[parents_stack_len-1].state_val;
589
#endif
406
590
407
591
new_cache_state->lower_pri = new_cache_state->higher_pri = NULL;
408
592
427
611
);
428
612
}
429
613
}
430
}
431
614
}
432
615
433
616
for (parents_stack_len--; parents_stack_len > 0; parents_stack_len--)
434
617
{
618
fcs_kv_state_t pass, src_pass;
619
435
620
fcs_collectible_state_t temp_new_state_val;
436
621
fcs_internal_move_t * next_move, * moves_end;
437
622
440
625
fcs_collectible_state_t * stack_ptr_this_state_val =
441
626
parents_stack[parents_stack_len-1].state_val;
442
627
443
fcs_duplicate_state(
444
&(new_cache_state->key),
445
&(temp_new_state_val),
446
&(parents_stack[parents_stack_len].new_cache_state->key),
447
parents_stack[parents_stack_len].state_val
448
);
449
450
moves_end =
628
pass.key = &(new_cache_state->key);
629
pass.val = &(temp_new_state_val);
630
src_pass.key = &(parents_stack[parents_stack_len].new_cache_state->key);
631
src_pass.val = parents_stack[parents_stack_len].state_val;
632
633
fcs_duplicate_state( &pass, &src_pass);
634
635
moves_end =
451
636
(
452
637
(next_move = stack_ptr_this_state_val->moves_to_parent->moves)
453
+
638
+
454
639
stack_ptr_this_state_val->moves_to_parent->num_moves
455
640
);
456
641
642
457
643
for ( ;
458
644
next_move < moves_end
459
645
; next_move++)
460
646
{
647
461
648
fc_solve_apply_move(
462
&(new_cache_state->key),
463
&(temp_new_state_val),
464
#ifdef FCS_WITHOUT_LOCS_FIELDS
649
&pass,
465
650
NULL,
466
#endif
467
651
(*next_move),
468
652
LOCAL_FREECELLS_NUM,
469
653
LOCAL_STACKS_NUM,
473
657
/* The state->parent_state moves stack has an implicit canonize
474
658
* suffix move. */
475
659
fc_solve_canonize_state(
476
#ifdef FCS_RCS_STATES
477
&(new_cache_state->key),
478
#endif
479
&(temp_new_state_val),
660
&(pass),
480
661
LOCAL_FREECELLS_NUM,
481
662
LOCAL_STACKS_NUM
482
663
);
498
679
new_cache_state->higher_pri->lower_pri =
499
680
new_cache_state->lower_pri;
500
681
}
682
501
683
if (new_cache_state->lower_pri)
502
684
{
503
685
new_cache_state->lower_pri->higher_pri =
504
686
new_cache_state->higher_pri;
505
687
}
688
/* Bug fix: make sure that ->lowest_pri is always valid. */
689
else if (new_cache_state->higher_pri)
690
{
691
cache->lowest_pri = new_cache_state->higher_pri;
692
}
693
506
694
/* Now promote it to be the highest. */
507
695
cache->highest_pri->higher_pri = new_cache_state;
508
696
new_cache_state->lower_pri = cache->highest_pri;
511
699
}
512
700
}
513
701
514
#ifdef DEBUG
515
{
516
fcs_state_t * state = &(((fcs_cache_key_info_t * )(*PValue))->key);
517
518
int s=0;
519
for (s=0;s<INSTANCE_STACKS_NUM; s++)
520
{
521
fcs_cards_column_t col = fcs_state_get_col(*state, s);
522
int col_len = fcs_col_len(col);
523
int c;
524
for (c = col_len ; c < MAX_NUM_CARDS_IN_A_STACK ; c++)
525
{
526
assert (fcs_col_get_card(col, c) == 0);
527
}
528
}
529
}
530
#endif
531
532
702
free(parents_stack);
533
703
534
704
if (cache->count_elements_in_cache > cache->max_num_elements_in_cache)
538
708
539
709
while (count > limit)
540
710
{
711
#if (FCS_RCS_CACHE_STORAGE == FCS_RCS_CACHE_STORAGE_JUDY)
541
712
int Rc_int;
713
#endif
542
714
fcs_cache_key_info_t * lowest_pri = cache->lowest_pri;
543
715
716
#if (FCS_RCS_CACHE_STORAGE == FCS_RCS_CACHE_STORAGE_JUDY)
544
717
JLD(
545
718
Rc_int,
546
719
cache->states_values_to_keys_map,
547
720
(Word_t)(lowest_pri->val_ptr)
548
721
);
722
#else
723
fc_solve_kaz_tree_delete_free(
724
cache->kaz_tree,
725
fc_solve_kaz_tree_lookup(
726
cache->kaz_tree, lowest_pri
727
)
728
);
729
#endif
549
730
550
731
cache->lowest_pri = lowest_pri->higher_pri;
551
732
cache->lowest_pri->lower_pri = NULL;
567
748
568
749
#endif
569
750
570
#define ASSIGN_STATE_KEY() (state_key = (*(fc_solve_lookup_state_key_from_val(instance, ptr_state))))
571
751
752
static GCC_INLINE fcs_game_limit_t count_num_vacant_freecells(
753
fcs_game_limit_t freecells_num,
754
fcs_state_t * state_ptr
755
)
756
{
757
fcs_game_limit_t num_vacant_freecells = 0;
758
int i;
759
760
for(i=0;i<freecells_num;i++)
761
{
762
if (fcs_freecell_card_num(*state_ptr, i) == 0)
763
{
764
num_vacant_freecells++;
765
}
766
}
767
768
return num_vacant_freecells;
769
}
770
771
static GCC_INLINE fcs_game_limit_t count_num_vacant_stacks(
772
fcs_game_limit_t stacks_num,
773
fcs_state_t * state_ptr
774
)
775
{
776
fcs_game_limit_t num_vacant_stacks = 0;
777
int i;
778
779
for ( i=0 ; i < stacks_num ; i++ )
780
{
781
if (fcs_col_len(fcs_state_get_col(*state_ptr, i)) == 0)
782
{
783
num_vacant_stacks++;
784
}
785
}
786
787
return num_vacant_stacks;
788
}
789
790
791
/*
792
* fc_solve_soft_dfs_do_solve() is the event loop of the
793
* Random-DFS scan. DFS which is recursive in nature is handled here
794
* without procedural recursion by using some dedicated stacks for
795
* the traversal.
796
*/
572
797
int fc_solve_soft_dfs_do_solve(
573
fc_solve_soft_thread_t * soft_thread
798
fc_solve_soft_thread_t * const soft_thread
574
799
)
575
800
{
576
fc_solve_hard_thread_t * hard_thread = soft_thread->hard_thread;
577
fc_solve_instance_t * instance = hard_thread->instance;
578
579
#ifdef FCS_RCS_STATES
580
fcs_state_t state_key;
581
#endif
582
fcs_collectible_state_t * ptr_state;
801
fc_solve_hard_thread_t * const hard_thread = soft_thread->hard_thread;
802
fc_solve_instance_t * const instance = hard_thread->instance;
803
804
DECLARE_STATE();
805
583
806
fcs_soft_dfs_stack_item_t * the_soft_dfs_info;
584
807
#if ((!defined(HARD_CODED_NUM_FREECELLS)) || (!defined(HARD_CODED_NUM_STACKS)))
585
808
DECLARE_GAME_PARAMS();
600
823
fcs_bool_t local_to_randomize = FALSE;
601
824
int * depth_ptr;
602
825
fcs_bool_t enable_pruning;
826
int * instance_num_times_ptr, * hard_thread_num_times_ptr;
827
int hard_thread_max_num_times;
828
fcs_instance_debug_iter_output_func_t debug_iter_output_func;
829
fcs_instance_debug_iter_output_context_t debug_iter_output_context;
603
830
604
831
#if ((!defined(HARD_CODED_NUM_FREECELLS)) || (!defined(HARD_CODED_NUM_STACKS)))
605
832
SET_GAME_PARAMS();
606
833
#endif
607
834
835
#define DEPTH() (*depth_ptr)
836
depth_ptr = &(soft_thread->method_specific.soft_dfs.depth);
608
837
609
the_soft_dfs_info = &(soft_thread->method_specific.soft_dfs.soft_dfs_info[soft_thread->method_specific.soft_dfs.depth]);
838
the_soft_dfs_info = &(soft_thread->method_specific.soft_dfs.soft_dfs_info[DEPTH()]);
610
839
611
840
dfs_max_depth = soft_thread->method_specific.soft_dfs.dfs_max_depth;
612
841
enable_pruning = soft_thread->enable_pruning;
613
842
614
ptr_state = the_soft_dfs_info->state;
843
ASSIGN_ptr_state (the_soft_dfs_info->state);
615
844
derived_states_list = &(the_soft_dfs_info->derived_states_list);
616
845
617
#ifdef FCS_RCS_STATES
618
ASSIGN_STATE_KEY();
619
#endif
620
621
846
rand_gen = &(soft_thread->method_specific.soft_dfs.rand_gen);
622
847
623
#ifndef FCS_WITHOUT_DEPTH_FIELD
624
calculate_real_depth(
625
ptr_state
626
);
627
#endif
848
calculate_real_depth(calc_real_depth, PTR_STATE);
628
849
629
850
by_depth_units = soft_thread->method_specific.soft_dfs.tests_by_depth_array.by_depth_units;
630
851
640
861
the_tests_list_ptr = &(curr_by_depth_unit->tests); \
641
862
}
642
863
643
depth_ptr = &(soft_thread->method_specific.soft_dfs.depth);
644
645
#define DEPTH() (*depth_ptr)
864
865
instance_num_times_ptr = &(instance->num_times);
866
hard_thread_num_times_ptr = &(hard_thread->num_times);
867
868
#define CALC_HARD_THREAD_MAX_NUM_TIMES() \
869
hard_thread_max_num_times = hard_thread->max_num_times; \
870
\
871
{ \
872
int lim = hard_thread->num_times \
873
+ (instance->effective_max_num_times - *(instance_num_times_ptr)) \
874
; \
875
\
876
hard_thread_max_num_times = min(hard_thread_max_num_times, lim); \
877
}
878
879
CALC_HARD_THREAD_MAX_NUM_TIMES();
880
881
debug_iter_output_func = instance->debug_iter_output_func;
882
debug_iter_output_context = instance->debug_iter_output_context;
883
884
INITIALIZE_STATE();
646
885
647
886
{
648
887
for (
695
934
696
935
if (is_a_complete_scan)
697
936
{
698
FCS_S_VISITED(ptr_state) |= FCS_VISITED_ALL_TESTS_DONE;
699
mark_as_dead_end(
700
ptr_state
701
);
937
FCS_S_VISITED(PTR_STATE) |= FCS_VISITED_ALL_TESTS_DONE;
938
mark_as_dead_end (scans_synergy, PTR_STATE);
702
939
}
703
940
704
941
free(the_soft_dfs_info->positions_by_rank);
711
948
the_soft_dfs_info--;
712
949
derived_states_list = &(the_soft_dfs_info->derived_states_list);
713
950
714
ptr_state = the_soft_dfs_info->state;
951
ASSIGN_ptr_state(the_soft_dfs_info->state);
715
952
716
#ifdef FCS_RCS_STATES
717
ASSIGN_STATE_KEY();
718
#endif
953
VERIFY_PTR_STATE_TRACE0("Verify Foo");
719
954
720
955
soft_thread->num_vacant_freecells = the_soft_dfs_info->num_vacant_freecells;
721
956
soft_thread->num_vacant_stacks = the_soft_dfs_info->num_vacant_stacks;
740
975
)
741
976
{
742
977
fcs_game_limit_t num_vacant_stacks, num_vacant_freecells;
743
int i;
744
978
745
979
TRACE0("In iter_handler");
746
980
747
if (instance->debug_iter_output_func)
981
if (debug_iter_output_func)
748
982
{
749
983
#ifdef DEBUG
750
984
printf("ST Name: %s\n", soft_thread->name);
751
985
#endif
752
instance->debug_iter_output_func(
753
(void*)instance->debug_iter_output_context,
754
instance->num_times,
755
soft_thread->method_specific.soft_dfs.depth,
986
debug_iter_output_func(
987
debug_iter_output_context,
988
*(instance_num_times_ptr),
989
DEPTH(),
756
990
(void*)instance,
757
#ifdef FCS_RCS_STATES
758
&(state_key),
759
#endif
760
ptr_state,
991
STATE_TO_PASS(),
761
992
#ifdef FCS_WITHOUT_VISITED_ITER
762
993
0
763
994
#else
764
((soft_thread->method_specific.soft_dfs.depth == 0) ?
995
((DEPTH() == 0) ?
765
996
0 :
766
FCS_S_VISITED_ITER(soft_thread->method_specific.soft_dfs.soft_dfs_info[soft_thread->method_specific.soft_dfs.depth-1].state)
997
FCS_S_VISITED_ITER(soft_thread->method_specific.soft_dfs.soft_dfs_info[DEPTH()-1].state)
767
998
)
768
999
#endif
769
1000
);
770
1001
}
771
1002
772
/* Count the free-cells */
773
num_vacant_freecells = 0;
774
for(i=0;i<LOCAL_FREECELLS_NUM;i++)
775
{
776
if (fcs_freecell_card_num(the_state, i) == 0)
777
{
778
num_vacant_freecells++;
779
}
780
}
781
782
/* Count the number of unoccupied stacks */
783
784
num_vacant_stacks = 0;
785
for(i=0;i<LOCAL_STACKS_NUM;i++)
786
{
787
if (fcs_col_len(fcs_state_get_col(the_state, i)) == 0)
788
{
789
num_vacant_stacks++;
790
}
791
}
1003
num_vacant_freecells =
1004
count_num_vacant_freecells(LOCAL_FREECELLS_NUM, &the_state);
1005
1006
num_vacant_stacks =
1007
count_num_vacant_stacks(LOCAL_STACKS_NUM, &the_state);
792
1008
793
1009
/* Check if we have reached the empty state */
794
1010
if (unlikely((num_vacant_stacks == LOCAL_STACKS_NUM) &&
795
1011
(num_vacant_freecells == LOCAL_FREECELLS_NUM)))
796
1012
{
797
instance->final_state = ptr_state;
1013
instance->final_state = PTR_STATE;
798
1014
799
1015
BUMP_NUM_TIMES();
800
1016
814
1030
num_vacant_stacks;
815
1031
816
1032
/* Perform the pruning. */
817
if (SHOULD_STATE_BE_PRUNED(enable_pruning, ptr_state))
1033
if (SHOULD_STATE_BE_PRUNED(enable_pruning, PTR_STATE))
818
1034
{
819
1035
fcs_collectible_state_t * derived;
820
#ifdef FCS_RCS_STATES
821
fcs_state_t derived_key;
822
#endif
823
1036
824
1037
if (fc_solve_sfs_raymond_prune(
825
1038
soft_thread,
826
#ifdef FCS_RCS_STATES
827
&(state_key),
828
#endif
829
ptr_state,
830
#ifdef FCS_RCS_STATES
831
&derived_key,
832
#endif
1039
STATE_TO_PASS(),
833
1040
&derived
834
1041
) == PRUNE_RET_FOLLOW_STATE
835
1042
)
864
1071
local_to_randomize = THE_TESTS_LIST.lists[
865
1072
the_soft_dfs_info->tests_list_index
866
1073
].to_randomize;
1074
867
1075
do
868
1076
{
1077
VERIFY_PTR_STATE_TRACE0("Verify Bar");
869
1078
870
1079
THE_TESTS_LIST.lists[
871
1080
the_soft_dfs_info->tests_list_index
872
1081
].tests[the_soft_dfs_info->test_index]
873
1082
(
874
1083
soft_thread,
875
#ifdef FCS_RCS_STATES
876
&(state_key),
877
#endif
878
ptr_state,
1084
STATE_TO_PASS(),
879
1085
derived_states_list
880
1086
);
881
1087
1088
VERIFY_PTR_STATE_TRACE0("Verify Glanko");
1089
882
1090
/* Move the counter to the next test */
883
1091
if ((++the_soft_dfs_info->test_index) ==
884
1092
THE_TESTS_LIST.lists[
912
1120
}
913
1121
rand_array = the_soft_dfs_info->derived_states_random_indexes;
914
1122
1123
VERIFY_PTR_STATE_TRACE0("Verify Panter");
1124
915
1125
for(a=0, ra_ptr = rand_array; a < num_states ; a++)
916
1126
{
917
1127
*(ra_ptr++) = a;
942
1152
}
943
1153
}
944
1154
1155
VERIFY_PTR_STATE_TRACE0("Verify Rondora");
1156
945
1157
/* We just performed a test, so the index of the first state that
946
1158
ought to be checked in this depth is 0.
947
1159
*/
955
1167
int * rand_array = the_soft_dfs_info->derived_states_random_indexes;
956
1168
fcs_collectible_state_t * single_derived_state;
957
1169
1170
VERIFY_PTR_STATE_TRACE0("Verify Klondike");
1171
958
1172
while (the_soft_dfs_info->current_state_index <
959
1173
num_states)
960
1174
{
964
1178
]
965
1179
].state_ptr;
966
1180
1181
VERIFY_PTR_STATE_AND_DERIVED_TRACE0("Verify Seahaven");
1182
967
1183
if (
968
1184
(! (FCS_S_VISITED(single_derived_state) &
969
1185
FCS_VISITED_DEAD_END)
976
1192
{
977
1193
BUMP_NUM_TIMES();
978
1194
1195
VERIFY_PTR_STATE_AND_DERIVED_TRACE0("Verify Gypsy");
1196
979
1197
set_scan_visited(
980
1198
single_derived_state,
981
1199
soft_thread_id
985
1203
FCS_S_VISITED_ITER(single_derived_state) = instance->num_times;
986
1204
#endif
987
1205
1206
VERIFY_PTR_STATE_AND_DERIVED_TRACE0("Verify Golf");
1207
988
1208
/*
989
1209
I'm using current_state_indexes[depth]-1 because we already
990
1210
increased it by one, so now it refers to the next state.
996
1216
}
997
1217
the_soft_dfs_info++;
998
1218
999
the_soft_dfs_info->state =
1000
ptr_state =
1001
single_derived_state;
1002
1003
#ifdef FCS_RCS_STATES
1004
ASSIGN_STATE_KEY();
1005
#endif
1006
1219
ASSIGN_ptr_state(single_derived_state);
1220
the_soft_dfs_info->state = PTR_STATE;
1221
1222
VERIFY_PTR_STATE_AND_DERIVED_TRACE0("Verify Zap");
1007
1223
1008
1224
the_soft_dfs_info->tests_list_index = 0;
1009
1225
the_soft_dfs_info->test_index = 0;
1012
1228
derived_states_list = &(the_soft_dfs_info->derived_states_list);
1013
1229
derived_states_list->num_states = 0;
1014
1230
1015
#ifndef FCS_WITHOUT_DEPTH_FIELD
1016
calculate_real_depth(
1017
ptr_state
1018
);
1019
#endif
1231
calculate_real_depth(calc_real_depth, PTR_STATE);
1020
1232
1021
1233
if (check_num_states_in_collection(instance))
1022
1234
{
1235
VERIFY_PTR_STATE_TRACE0("Verify Bakers_Game");
1236
1023
1237
free_states(instance);
1238
1239
VERIFY_PTR_STATE_TRACE0("Verify Penguin");
1024
1240
}
1025
1241
1026
1242
if (check_if_limits_exceeded())
1088
1304
1089
1305
static GCC_INLINE void initialize_befs_rater(
1090
1306
fc_solve_soft_thread_t * soft_thread,
1091
#ifdef FCS_RCS_STATES
1092
fcs_state_t * ptr_state_key,
1093
#define STATE() (*ptr_state_key)
1094
#else
1095
#define STATE() (ptr_state->s)
1096
#endif
1097
fcs_collectible_state_t * ptr_state
1098
)
1307
fcs_kv_state_t * raw_pass_raw
1308
)
1099
1309
{
1310
1311
#define pass (*raw_pass_raw)
1312
#define ptr_state_key (raw_pass_raw->key)
1313
1100
1314
#ifndef HARD_CODED_NUM_STACKS
1101
1315
fc_solve_hard_thread_t * hard_thread = soft_thread->hard_thread;
1102
1316
fc_solve_instance_t * instance = hard_thread->instance;
1108
1322
cards_under_sequences = 0;
1109
1323
for(a=0;a<INSTANCE_STACKS_NUM;a++)
1110
1324
{
1111
update_col_cards_under_sequences(soft_thread, fcs_state_get_col(STATE(), a), &cards_under_sequences);
1325
update_col_cards_under_sequences(soft_thread, fcs_state_get_col(*ptr_state_key, a), &cards_under_sequences);
1112
1326
}
1113
1327
soft_thread->method_specific.befs.meth.befs.initial_cards_under_sequences_value = cards_under_sequences;
1114
1328
}
1115
#undef STATE
1116
1329
1117
1330
#undef TRACE0
1118
1331
1139
1352
1140
1353
static GCC_INLINE pq_rating_t befs_rate_state(
1141
1354
fc_solve_soft_thread_t * soft_thread,
1142
#ifdef FCS_RCS_STATES
1143
fcs_state_t * ptr_state_key,
1144
#endif
1145
fcs_collectible_state_t * ptr_state
1355
fcs_kv_state_t * raw_pass_raw
1146
1356
)
1147
1357
{
1148
#ifdef FCS_RCS_STATES
1149
#define state_key (*ptr_state_key)
1150
#endif
1151
1358
#ifndef FCS_FREECELL_ONLY
1152
1359
fc_solve_hard_thread_t * hard_thread = soft_thread->hard_thread;
1153
1360
fc_solve_instance_t * instance = hard_thread->instance;
1154
1361
#endif
1362
fcs_state_t * state = raw_pass_raw->key;
1155
1363
1156
1364
double ret=0;
1157
1365
int a, c, cards_num, num_cards_in_founds;
1180
1388
seqs_over_renegade_cards = 0;
1181
1389
for(a=0;a<LOCAL_STACKS_NUM;a++)
1182
1390
{
1183
col = fcs_state_get_col(the_state, a);
1391
col = fcs_state_get_col(*state, a);
1184
1392
cards_num = fcs_col_len(col);
1185
1393
1186
1394
if (cards_num == 0)
1215
1423
num_cards_in_founds = 0;
1216
1424
for(a=0;a<(LOCAL_DECKS_NUM<<2);a++)
1217
1425
{
1218
num_cards_in_founds += fcs_foundation_value((the_state), a);
1426
num_cards_in_founds += fcs_foundation_value((*state), a);
1219
1427
}
1220
1428
1221
1429
ret += ((double)num_cards_in_founds/(LOCAL_DECKS_NUM*52)) * befs_weights[FCS_BEFS_WEIGHT_CARDS_OUT];
1223
1431
num_vacant_freecells = 0;
1224
1432
for(a=0;a<LOCAL_FREECELLS_NUM;a++)
1225
1433
{
1226
if (fcs_freecell_card_num((the_state),a) == 0)
1434
if (fcs_freecell_card_num((*state),a) == 0)
1227
1435
{
1228
1436
num_vacant_freecells++;
1229
1437
}
1262
1470
#ifdef FCS_WITHOUT_DEPTH_FIELD
1263
1471
ret += befs_weights[FCS_BEFS_WEIGHT_DEPTH];
1264
1472
#else
1265
if (FCS_S_DEPTH(ptr_state) <= 20000)
1266
1473
{
1267
ret += ((20000 - FCS_S_DEPTH(ptr_state))/20000.0) * befs_weights[FCS_BEFS_WEIGHT_DEPTH];
1474
int depth = raw_pass_raw->val->depth;
1475
if (depth <= 20000)
1476
{
1477
ret += ((20000 - depth)/20000.0) * befs_weights[FCS_BEFS_WEIGHT_DEPTH];
1478
}
1268
1479
}
1269
1480
#endif
1270
1481
1272
1483
1273
1484
return (int)(ret*INT_MAX);
1274
1485
}
1275
#ifdef FCS_RCS_STATES
1276
#undef state_key
1277
#endif
1278
1486
#undef pass
1487
#undef ptr_state_key
1279
1488
1280
1489
#ifdef FCS_FREECELL_ONLY
1281
1490
#undef unlimited_sequence_move
1282
1491
#endif
1283
1492
1284
/*
1285
fc_solve_befs_or_bfs_do_solve() is the main event
1286
loop of the BeFS And BFS scans. It is quite simple as all it does is
1287
extract elements out of the queue or priority queue and run all the test
1288
of them.
1289
1290
It goes on in this fashion until the final state was reached or
1291
there are no more states in the queue.
1292
*/
1293
1493
1294
1494
#undef TRACE0
1295
1495
1325
1525
sizeof(fcs_states_linked_list_item_t) \
1326
1526
));
1327
1527
1328
static void GCC_INLINE fc_solve_initialize_bfs_queue(fc_solve_soft_thread_t * soft_thread)
1528
static GCC_INLINE void fc_solve_initialize_bfs_queue(fc_solve_soft_thread_t * soft_thread)
1329
1529
{
1330
1530
fc_solve_hard_thread_t * hard_thread = soft_thread->hard_thread;
1331
1531
1377
1577
)
1378
1578
{
1379
1579
fc_solve_instance_t * instance = soft_thread->hard_thread->instance;
1380
fcs_collectible_state_t * ptr_orig_state;
1381
#ifdef FCS_RCS_STATES
1382
ptr_orig_state = &(instance->state_copy_ptr->info);
1383
#else
1384
ptr_orig_state = instance->state_copy_ptr;
1385
#endif
1580
fcs_kv_state_t pass;
1581
1582
pass.key = &(instance->state_copy_ptr->s);
1583
pass.val = &(instance->state_copy_ptr->info);
1386
1584
1387
1585
if (soft_thread->method == FCS_METHOD_A_STAR)
1388
1586
{
1396
1594
1397
1595
initialize_befs_rater(
1398
1596
soft_thread,
1399
#ifdef FCS_RCS_STATES
1400
&(instance->state_copy_ptr->s),
1401
#endif
1402
ptr_orig_state
1597
STATE_TO_PASS()
1403
1598
);
1404
1599
}
1405
1600
else
1431
1626
soft_thread->method_specific.befs.tests_list_end = next_test;
1432
1627
}
1433
1628
1434
soft_thread->first_state_to_check = ptr_orig_state;
1629
soft_thread->first_state_to_check =
1630
FCS_STATE_keyval_pair_to_collectible(instance->state_copy_ptr);
1435
1631
1436
1632
return;
1437
1633
}
1438
1634
1439
#define DEBUG
1440
1635
#ifdef DEBUG
1441
1636
#if 0
1442
1637
static void dump_pqueue (
1491
1686
return ret;
1492
1687
}
1493
1688
#endif
1689
1690
/*
1691
* fc_solve_befs_or_bfs_do_solve() is the main event
1692
* loop of the BeFS And BFS scans. It is quite simple as all it does is
1693
* extract elements out of the queue or priority queue and run all the test
1694
* of them.
1695
*
1696
* It goes on in this fashion until the final state was reached or
1697
* there are no more states in the queue.
1698
*/
1494
1699
int fc_solve_befs_or_bfs_do_solve(
1495
1700
fc_solve_soft_thread_t * soft_thread
1496
1701
)
1498
1703
fc_solve_hard_thread_t * hard_thread = soft_thread->hard_thread;
1499
1704
fc_solve_instance_t * instance = hard_thread->instance;
1500
1705
1501
fcs_collectible_state_t * ptr_state, * ptr_new_state;
1502
#ifdef FCS_RCS_STATES
1503
fcs_state_t state_key;
1504
#endif
1706
DECLARE_NEW_STATE();
1707
DECLARE_STATE();
1708
1505
1709
fcs_game_limit_t num_vacant_stacks, num_vacant_freecells;
1506
1710
fcs_states_linked_list_item_t * save_item;
1507
int a;
1508
1711
fcs_derived_states_list_t derived;
1509
1712
int derived_index;
1510
1713
fcs_bool_t enable_pruning;
1531
1734
1532
1735
int error_code;
1533
1736
1737
int * instance_num_times_ptr, * hard_thread_num_times_ptr;
1738
1739
int hard_thread_max_num_times;
1740
1741
1742
fcs_instance_debug_iter_output_func_t debug_iter_output_func;
1743
fcs_instance_debug_iter_output_context_t debug_iter_output_context;
1744
1534
1745
derived.num_states = 0;
1535
1746
derived.states = NULL;
1536
1747
1537
1748
tests_list = soft_thread->method_specific.befs.tests_list;
1538
1749
tests_list_end = soft_thread->method_specific.befs.tests_list_end;
1539
1750
1540
ptr_state = soft_thread->first_state_to_check;
1751
ASSIGN_ptr_state(soft_thread->first_state_to_check);
1541
1752
enable_pruning = soft_thread->enable_pruning;
1542
1753
1543
1754
method = soft_thread->method;
1755
instance_num_times_ptr = &(instance->num_times);
1756
hard_thread_num_times_ptr = &(hard_thread->num_times);
1757
1758
INITIALIZE_STATE();
1544
1759
1545
1760
if (method == FCS_METHOD_A_STAR)
1546
1761
{
1556
1771
SET_GAME_PARAMS();
1557
1772
#endif
1558
1773
1774
CALC_HARD_THREAD_MAX_NUM_TIMES();
1775
1776
debug_iter_output_func = instance->debug_iter_output_func;
1777
debug_iter_output_context = instance->debug_iter_output_context;
1778
1559
1779
/* Continue as long as there are states in the queue or
1560
1780
priority queue. */
1561
while ( ptr_state != NULL)
1781
while ( PTR_STATE != NULL)
1562
1782
{
1563
1783
TRACE0("Start of loop");
1564
1784
1565
#ifdef FCS_RCS_STATES
1566
ASSIGN_STATE_KEY();
1567
#endif
1568
1569
1785
#ifdef DEBUG
1570
1786
dump_pqueue(soft_thread, "loop_start", scan_specific.pqueue);
1571
1787
#endif
1579
1795
* Therefore, we prune before checking for the visited flags.
1580
1796
* */
1581
1797
TRACE0("Pruning");
1582
if (SHOULD_STATE_BE_PRUNED(enable_pruning, ptr_state))
1798
if (SHOULD_STATE_BE_PRUNED(enable_pruning, PTR_STATE))
1583
1799
{
1584
fcs_collectible_state_t * derived;
1585
#ifdef FCS_RCS_STATES
1586
fcs_state_t derived_key;
1587
#endif
1800
fcs_collectible_state_t * after_pruning_state;
1588
1801
1589
1802
if (fc_solve_sfs_raymond_prune(
1590
1803
soft_thread,
1591
#ifdef FCS_RCS_STATES
1592
(&state_key),
1593
#endif
1594
ptr_state,
1595
#ifdef FCS_RCS_STATES
1596
&derived_key,
1597
#endif
1598
&derived
1804
STATE_TO_PASS(),
1805
&after_pruning_state
1599
1806
) == PRUNE_RET_FOLLOW_STATE
1600
1807
)
1601
1808
{
1602
ptr_state = derived;
1603
1604
#ifdef FCS_RCS_STATES
1605
ASSIGN_STATE_KEY();
1606
#endif
1607
1809
ASSIGN_ptr_state(after_pruning_state);
1608
1810
}
1609
1811
}
1610
1812
1611
1813
{
1612
register int temp_visited = FCS_S_VISITED(ptr_state);
1814
register int temp_visited = FCS_S_VISITED(PTR_STATE);
1613
1815
1614
1816
/*
1615
1817
* If this is an optimization scan and the state being checked is
1629
1831
(
1630
1832
(temp_visited & FCS_VISITED_DEAD_END)
1631
1833
||
1632
(is_scan_visited(ptr_state, soft_thread_id))
1834
(is_scan_visited(PTR_STATE, soft_thread_id))
1633
1835
)
1634
1836
)
1635
1837
{
1639
1841
1640
1842
TRACE0("Counting cells");
1641
1843
1642
/* Count the free-cells */
1643
num_vacant_freecells = 0;
1644
for(a=0;a<LOCAL_FREECELLS_NUM;a++)
1645
{
1646
if (fcs_freecell_card_num(the_state, a) == 0)
1647
{
1648
num_vacant_freecells++;
1649
}
1650
}
1651
1652
/* Count the number of unoccupied stacks */
1653
1654
num_vacant_stacks = 0;
1655
for(a=0;a<LOCAL_STACKS_NUM;a++)
1656
{
1657
if (fcs_col_len(fcs_state_get_col(the_state, a)) == 0)
1658
{
1659
num_vacant_stacks++;
1660
}
1661
}
1662
1844
num_vacant_freecells =
1845
count_num_vacant_freecells(LOCAL_FREECELLS_NUM, &the_state);
1846
1847
num_vacant_stacks =
1848
count_num_vacant_stacks(LOCAL_STACKS_NUM, &the_state);
1663
1849
1664
1850
if (check_if_limits_exceeded())
1665
1851
{
1666
soft_thread->first_state_to_check = ptr_state;
1852
soft_thread->first_state_to_check = PTR_STATE;
1667
1853
1668
1854
TRACE0("myreturn - FCS_STATE_SUSPEND_PROCESS");
1669
1855
error_code = FCS_STATE_SUSPEND_PROCESS;
1671
1857
}
1672
1858
1673
1859
TRACE0("debug_iter_output");
1674
if (instance->debug_iter_output_func)
1860
if (debug_iter_output_func)
1675
1861
{
1676
1862
#ifdef DEBUG
1677
1863
printf("ST Name: %s\n", soft_thread->name);
1678
1864
#endif
1679
instance->debug_iter_output_func(
1680
(void*)instance->debug_iter_output_context,
1681
instance->num_times,
1865
debug_iter_output_func(
1866
debug_iter_output_context,
1867
*(instance_num_times_ptr),
1682
1868
#ifdef FCS_WITHOUT_DEPTH_FIELD
1683
calc_depth(ptr_state),
1869
calc_depth(PTR_STATE),
1684
1870
#else
1685
FCS_S_DEPTH(ptr_state),
1871
FCS_S_DEPTH(PTR_STATE),
1686
1872
#endif
1687
1873
(void*)instance,
1688
#ifdef FCS_RCS_STATES
1689
(&state_key),
1690
#endif
1691
ptr_state,
1874
STATE_TO_PASS(),
1692
1875
#ifdef FCS_WITHOUT_VISITED_ITER
1693
1876
0
1694
1877
#else
1695
((FCS_S_PARENT(ptr_state) == NULL) ?
1878
((FCS_S_PARENT(PTR_STATE) == NULL) ?
1696
1879
0 :
1697
FCS_S_VISITED_ITER(FCS_S_PARENT(ptr_state))
1880
FCS_S_VISITED_ITER(FCS_S_PARENT(PTR_STATE))
1698
1881
)
1699
1882
#endif
1700
1883
);
1703
1886
1704
1887
if ((num_vacant_stacks == LOCAL_STACKS_NUM) && (num_vacant_freecells == LOCAL_FREECELLS_NUM))
1705
1888
{
1706
instance->final_state = ptr_state;
1889
instance->final_state = PTR_STATE;
1707
1890
1708
1891
BUMP_NUM_TIMES();
1709
1892
1711
1894
goto my_return_label;
1712
1895
}
1713
1896
1714
#ifndef FCS_WITHOUT_DEPTH_FIELD
1715
calculate_real_depth(
1716
ptr_state
1717
);
1718
#endif
1897
calculate_real_depth (calc_real_depth, PTR_STATE);
1719
1898
1720
1899
soft_thread->num_vacant_freecells = num_vacant_freecells;
1721
1900
soft_thread->num_vacant_stacks = num_vacant_stacks;
1740
1919
{
1741
1920
(*next_test)(
1742
1921
soft_thread,
1743
#ifdef FCS_RCS_STATES
1744
&(state_key),
1745
#endif
1746
ptr_state,
1922
STATE_TO_PASS(),
1747
1923
&derived
1748
1924
);
1749
1925
}
1750
1926
1751
1927
if (is_a_complete_scan)
1752
1928
{
1753
FCS_S_VISITED(ptr_state) |= FCS_VISITED_ALL_TESTS_DONE;
1929
FCS_S_VISITED(PTR_STATE) |= FCS_VISITED_ALL_TESTS_DONE;
1754
1930
}
1755
1931
1756
1932
/* Increase the number of iterations by one .
1763
1939
1764
1940
for(derived_index = 0 ; derived_index < derived.num_states ; derived_index++)
1765
1941
{
1942
#ifdef FCS_RCS_STATES
1943
new_pass.key =
1944
fc_solve_lookup_state_key_from_val(instance,
1945
new_pass.val = derived.states[derived_index].state_ptr
1946
);
1947
#else
1766
1948
ptr_new_state = derived.states[derived_index].state_ptr;
1949
new_pass.key = &(ptr_new_state->s);
1950
new_pass.val = &(ptr_new_state->info);
1951
#endif
1767
1952
1768
1953
if (method == FCS_METHOD_A_STAR)
1769
1954
{
1770
1955
fc_solve_PQueuePush(
1771
1956
pqueue,
1772
1957
ptr_new_state,
1773
befs_rate_state(
1774
soft_thread,
1775
#ifdef FCS_RCS_STATES
1776
fc_solve_lookup_state_key_from_val(instance, ptr_new_state),
1777
#endif
1778
ptr_new_state
1779
)
1958
befs_rate_state( soft_thread, NEW_STATE_TO_PASS())
1780
1959
);
1781
1960
}
1782
1961
else
1804
1983
1805
1984
if (method == FCS_METHOD_OPTIMIZE)
1806
1985
{
1807
FCS_S_VISITED(ptr_state) |= FCS_VISITED_IN_OPTIMIZED_PATH;
1986
FCS_S_VISITED(PTR_STATE) |= FCS_VISITED_IN_OPTIMIZED_PATH;
1808
1987
}
1809
1988
else
1810
1989
{
1811
1990
set_scan_visited(
1812
ptr_state,
1991
PTR_STATE,
1813
1992
soft_thread_id
1814
1993
);
1815
1994
1817
1996
{
1818
1997
if (is_a_complete_scan)
1819
1998
{
1820
mark_as_dead_end(
1821
ptr_state
1822
);
1999
mark_as_dead_end(scans_synergy, PTR_STATE);
1823
2000
}
1824
2001
}
1825
2002
}
1826
2003
1827
2004
#ifndef FCS_WITHOUT_VISITED_ITER
1828
FCS_S_VISITED_ITER(ptr_state) = instance->num_times-1;
2005
FCS_S_VISITED_ITER(PTR_STATE) = *(instance_num_times_ptr)-1;
1829
2006
#endif
1830
2007
1831
2008
label_next_state:
1835
2012
*/
1836
2013
if (method == FCS_METHOD_A_STAR)
1837
2014
{
1838
2015
fcs_collectible_state_t * new_ptr_state;
1839
2016
#ifdef DEBUG
1840
2017
dump_pqueue(soft_thread, "before_pop", scan_specific.pqueue);
1841
2018
#endif
1842
2019
/* It is an BeFS scan */
1843
2020
fc_solve_PQueuePop(
1844
2021
pqueue,
1845
&ptr_state
2022
&(new_ptr_state)
1846
2023
);
2024
2025
ASSIGN_ptr_state(new_ptr_state);
1847
2026
}
1848
2027
else
1849
2028
{
1850
2029
save_item = queue->next;
1851
2030
if (save_item != queue_last_item)
1852
2031
{
1853
ptr_state = save_item->s;
2032
ASSIGN_ptr_state(save_item->s);
1854
2033
queue->next = save_item->next;
1855
2034
save_item->next = my_brfs_recycle_bin;
1856
2035
my_brfs_recycle_bin = save_item;
1857
2036
}
1858
2037
else
1859
2038
{
1860
ptr_state = NULL;
2039
ASSIGN_ptr_state(NULL);
1861
2040
}
1862
2041
}
1863
2042
}
1888
2067
#undef myreturn
1889
2068
1890
2069
/*
1891
* Calculate, cache and return the positions_by_rank meta-data
2070
* fc_solve_get_the_positions_by_rank_data() :
2071
*
2072
* calculate, cache and return the positions_by_rank meta-data
1892
2073
* about the currently-evaluated state.
2074
*
1893
2075
*/
1894
2076
extern char * fc_solve_get_the_positions_by_rank_data(
1895
fc_solve_soft_thread_t * soft_thread,
1896
#ifdef FCS_RCS_STATES
1897
fcs_state_t * ptr_state_key,
1898
#endif
1899
fcs_collectible_state_t * ptr_state
1900
)
2077
fc_solve_soft_thread_t * soft_thread,
2078
fcs_kv_state_t * ptr_state_raw
2079
)
1901
2080
{
1902
#ifdef FCS_RCS_STATES
2081
#define ptr_state_key (ptr_state_raw->key)
1903
2082
#define state_key (*ptr_state_key)
1904
#endif
2083
#undef the_state
2084
#define the_state state_key
1905
2085
1906
2086
char * * positions_by_rank_location;
2087
2088
#ifdef DEBUG
2089
if (getenv("FCS_TRACE"))
2090
{
2091
printf("%s\n", "Verify Quux");
2092
fflush(stdout);
2093
}
2094
VERIFY_STATE_SANITY();
2095
#endif
2096
1907
2097
switch(soft_thread->method)
1908
2098
{
1909
2099
case FCS_METHOD_SOFT_DFS:
2035
2225
2036
2226
return *positions_by_rank_location;
2037
2227
}
2038
#ifdef FCS_RCS_STATES
2039
2228
#undef state_key
2040
#endif
2229
#undef ptr_state_key
2041
2230
2042
2231
/*
2043
2232
* These functions are used by the move functions in freecell.c and
2044
2233
* simpsim.c.
2045
2234
* */
2046
2235
int fc_solve_sfs_check_state_begin(
2047
fc_solve_hard_thread_t * hard_thread,
2048
#ifdef FCS_RCS_STATES
2049
fcs_state_t * out_new_state_key,
2050
#endif
2051
fcs_collectible_state_t * * out_ptr_new_state,
2052
#ifdef FCS_RCS_STATES
2053
fcs_state_t * ptr_state_key,
2054
#endif
2055
fcs_collectible_state_t * ptr_state,
2056
fcs_move_stack_t * moves
2236
fc_solve_hard_thread_t * const hard_thread,
2237
fcs_kv_state_t * const out_new_state_out,
2238
fcs_kv_state_t * const raw_ptr_state_raw,
2239
fcs_move_stack_t * const moves
2057
2240
)
2058
2241
{
2059
fcs_collectible_state_t * ptr_new_state;
2060
fc_solve_instance_t * instance;
2061
2062
instance = hard_thread->instance;
2242
#define ptr_state (raw_ptr_state_raw->val)
2243
fcs_collectible_state_t * raw_ptr_new_state;
2244
fc_solve_instance_t * const instance = hard_thread->instance;
2063
2245
2064
2246
if ((hard_thread->allocated_from_list =
2065
2247
(instance->list_of_vacant_states != NULL)))
2066
2248
{
2067
ptr_new_state = instance->list_of_vacant_states;
2249
raw_ptr_new_state = instance->list_of_vacant_states;
2068
2250
instance->list_of_vacant_states = FCS_S_NEXT(instance->list_of_vacant_states);
2069
2251
}
2070
2252
else
2071
2253
{
2072
ptr_new_state =
2254
raw_ptr_new_state =
2073
2255
fcs_state_ia_alloc_into_var(
2074
2256
&(hard_thread->allocator)
2075
2257
);
2076
2258
}
2077
2259
2078
fcs_duplicate_state(
2079
#ifdef FCS_RCS_STATES
2080
out_new_state_key,
2081
#endif
2082
ptr_new_state,
2083
#ifdef FCS_RCS_STATES
2084
ptr_state_key,
2085
#endif
2086
ptr_state
2260
FCS_STATE_collectible_to_kv(out_new_state_out, raw_ptr_new_state);
2261
fcs_duplicate_kv_state(
2262
out_new_state_out,
2263
raw_ptr_state_raw
2087
2264
);
2265
#ifdef FCS_RCS_STATES
2266
#define INFO_STATE_PTR(kv_ptr) ((kv_ptr)->val)
2267
#else
2268
/* TODO : That's very hacky - get rid of it. */
2269
#define INFO_STATE_PTR(kv_ptr) ((fcs_state_keyval_pair_t *)((kv_ptr)->key))
2270
#endif
2088
2271
/* Some BeFS and BFS parameters that need to be initialized in
2089
2272
* the derived state.
2090
2273
* */
2091
FCS_S_PARENT(ptr_new_state) = ptr_state;
2092
FCS_S_MOVES_TO_PARENT(ptr_new_state) = moves;
2274
FCS_S_PARENT(raw_ptr_new_state) = INFO_STATE_PTR(raw_ptr_state_raw);
2275
FCS_S_MOVES_TO_PARENT(raw_ptr_new_state) = moves;
2093
2276
/* Make sure depth is consistent with the game graph.
2094
2277
* I.e: the depth of every newly discovered state is derived from
2095
2278
* the state from which it was discovered. */
2096
2279
#ifndef FCS_WITHOUT_DEPTH_FIELD
2097
(FCS_S_DEPTH(ptr_new_state))++;
2280
(FCS_S_DEPTH(raw_ptr_new_state))++;
2098
2281
#endif
2099
2282
/* Mark this state as a state that was not yet visited */
2100
FCS_S_VISITED(ptr_new_state) = 0;
2283
FCS_S_VISITED(raw_ptr_new_state) = 0;
2101
2284
/* It's a newly created state which does not have children yet. */
2102
FCS_S_NUM_ACTIVE_CHILDREN(ptr_new_state) = 0;
2103
memset(&(FCS_S_SCAN_VISITED(ptr_new_state)), '\0',
2104
sizeof(FCS_S_SCAN_VISITED(ptr_new_state))
2285
FCS_S_NUM_ACTIVE_CHILDREN(raw_ptr_new_state) = 0;
2286
memset(&(FCS_S_SCAN_VISITED(raw_ptr_new_state)), '\0',
2287
sizeof(FCS_S_SCAN_VISITED(raw_ptr_new_state))
2105
2288
);
2106
2289
fcs_move_stack_reset(moves);
2107
2290
2108
*out_ptr_new_state = ptr_new_state;
2109
2110
2291
return 0;
2111
2292
}
2293
#undef ptr_state
2112
2294
2113
2295
extern void fc_solve_sfs_check_state_end(
2114
fc_solve_soft_thread_t * soft_thread,
2115
#ifdef FCS_RCS_STATES
2116
fcs_state_t * ptr_state_key,
2117
#endif
2118
fcs_collectible_state_t * ptr_state,
2119
#ifdef FCS_RCS_STATES
2120
fcs_state_t * ptr_new_state_key,
2121
#endif
2122
fcs_collectible_state_t * ptr_new_state,
2123
int state_context_value,
2124
fcs_move_stack_t * moves,
2125
fcs_derived_states_list_t * derived_states_list
2296
fc_solve_soft_thread_t * const soft_thread,
2297
fcs_kv_state_t * const raw_ptr_state_raw,
2298
fcs_kv_state_t * const raw_ptr_new_state_raw,
2299
const int state_context_value,
2300
fcs_move_stack_t * const moves,
2301
fcs_derived_states_list_t * const derived_states_list
2126
2302
)
2127
2303
{
2128
fcs_internal_move_t temp_move;
2129
fc_solve_hard_thread_t * hard_thread;
2130
fc_solve_instance_t * instance;
2131
fcs_runtime_flags_t calc_real_depth;
2132
fcs_runtime_flags_t scans_synergy;
2133
fcs_collectible_state_t * existing_state;
2134
2135
#ifdef FCS_RCS_STATES
2136
fcs_state_t * existing_state_key;
2304
fc_solve_hard_thread_t * const hard_thread = soft_thread->hard_thread;
2305
fc_solve_instance_t * const instance = hard_thread->instance;
2306
#ifndef FCS_WITHOUT_DEPTH_FIELD
2307
const fcs_runtime_flags_t calc_real_depth
2308
= STRUCT_QUERY_FLAG(instance, FCS_RUNTIME_CALC_REAL_DEPTH);
2309
const fcs_runtime_flags_t scans_synergy
2310
= STRUCT_QUERY_FLAG(instance, FCS_RUNTIME_SCANS_SYNERGY);
2137
2311
#endif
2138
2139
temp_move = fc_solve_empty_move;
2140
2141
hard_thread = soft_thread->hard_thread;
2142
instance = hard_thread->instance;
2143
2144
calc_real_depth = STRUCT_QUERY_FLAG(instance, FCS_RUNTIME_CALC_REAL_DEPTH);
2145
scans_synergy = STRUCT_QUERY_FLAG(instance, FCS_RUNTIME_SCANS_SYNERGY);
2312
fcs_kv_state_t existing_state;
2313
2314
#define ptr_new_state_foo (raw_ptr_new_state_raw->val)
2315
#define ptr_state (raw_ptr_state_raw->val)
2146
2316
2147
2317
if (! fc_solve_check_and_add_state(
2148
2318
hard_thread,
2149
#ifdef FCS_RCS_STATES
2150
ptr_new_state_key,
2151
#endif
2152
ptr_new_state,
2153
#ifdef FCS_RCS_STATES
2154
&existing_state_key,
2155
#endif
2319
raw_ptr_new_state_raw,
2156
2320
&existing_state
2157
2321
))
2158
2322
{
2323
#define existing_state_val (existing_state.val)
2159
2324
if (hard_thread->allocated_from_list)
2160
2325
{
2161
FCS_S_NEXT(ptr_new_state) = instance->list_of_vacant_states;
2162
instance->list_of_vacant_states = ptr_new_state;
2326
ptr_new_state_foo->parent = instance->list_of_vacant_states;
2327
instance->list_of_vacant_states = INFO_STATE_PTR(raw_ptr_new_state_raw);
2163
2328
}
2164
2329
else
2165
2330
{
2166
2331
fcs_compact_alloc_release(&(hard_thread->allocator));
2167
2332
}
2333
2168
2334
#ifndef FCS_WITHOUT_DEPTH_FIELD
2169
calculate_real_depth(existing_state);
2335
calculate_real_depth (calc_real_depth, FCS_STATE_kv_to_collectible(&existing_state));
2336
2170
2337
/* Re-parent the existing state to this one.
2171
2338
*
2172
2339
* What it means is that if the depth of the state if it
2174
2341
* already have, then re-assign its parent to this state.
2175
2342
* */
2176
2343
if (STRUCT_QUERY_FLAG(instance, FCS_RUNTIME_TO_REPARENT_STATES_REAL) &&
2177
(FCS_S_DEPTH(existing_state) > FCS_S_DEPTH(ptr_state)+1))
2344
(existing_state_val->depth > ptr_state->depth+1))
2178
2345
{
2179
2346
/* Make a copy of "moves" because "moves" will be destroyed */
2180
FCS_S_MOVES_TO_PARENT(existing_state) =
2347
existing_state_val->moves_to_parent =
2181
2348
fc_solve_move_stack_compact_allocate(
2182
2349
hard_thread, moves
2183
2350
);
2184
if (!(FCS_S_VISITED(existing_state) & FCS_VISITED_DEAD_END))
2351
if (!(existing_state_val->visited & FCS_VISITED_DEAD_END))
2185
2352
{
2186
if ((--(FCS_S_NUM_ACTIVE_CHILDREN(FCS_S_PARENT(existing_state)))) == 0)
2353
if ((--(FCS_S_NUM_ACTIVE_CHILDREN(existing_state_val->parent))) == 0)
2187
2354
{
2188
mark_as_dead_end(
2189
FCS_S_PARENT(existing_state)
2190
);
2355
mark_as_dead_end(scans_synergy, existing_state_val->parent);
2191
2356
}
2192
FCS_S_NUM_ACTIVE_CHILDREN(ptr_state)++;
2357
ptr_state->num_active_children++;
2193
2358
}
2194
FCS_S_PARENT(existing_state) = ptr_state;
2195
FCS_S_DEPTH(existing_state) = FCS_S_DEPTH(ptr_state) + 1;
2359
existing_state_val->parent = INFO_STATE_PTR(raw_ptr_state_raw);
2360
existing_state_val->depth = ptr_state->depth + 1;
2196
2361
}
2362
2197
2363
#endif
2364
2198
2365
fc_solve_derived_states_list_add_state(
2199
2366
derived_states_list,
2200
existing_state,
2367
FCS_STATE_kv_to_collectible(&existing_state),
2201
2368
state_context_value
2202
2369
);
2370
2203
2371
}
2204
2372
else
2205
2373
{
2206
2374
fc_solve_derived_states_list_add_state(
2207
2375
derived_states_list,
2208
ptr_new_state,
2376
INFO_STATE_PTR(raw_ptr_new_state_raw),
2209
2377
state_context_value
2210
2378
);
2211
2379
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1