Source

fc-solve / fc-solve / source / NEWS.txt

Full commit
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
Freecell Solver's News File
===========================
Shlomi Fish <shlomif@cpan.org>
:Date: 2009-09-05
:Revision: $Id$

1. Add the +-l micro-finance-improved+ preset (or +-l mfi+ for short),
which somewhat improves the length of the solutions of the +micro-finance+
preset.

2. Add the +--flares-choice+ option, which determines how the winning flare
is chosen.

3. Add the +--flares-iters-factor+ option (or +-fif+ for short), which
specifies a factor to multiply the flares quotas.

Version 3.14.1: (01-Nov-2012)
-----------------------------

1. Fix the build on Windows with Dwimperl and its Mingw32 (+strndup()+
was missing).

Version 3.14.0: (31-Oct-2012)
-----------------------------

1. Got the tests to pass with +cmake -DFCS_WITHOUT_DEPTH_FIELD=1+ by making
the library behave the same as without it. This also affected the behaviour of
+./fc-solve -l mo+ with attempting to solve Baker’s Dozen deals.

2. On UNIX platforms, +fc-solve+ now exits gracefully with the message
“Iterations count exceeded.”, upon receiving a SIGABRT signal. Can be
triggered by executing +pkill -ABRT fc-solve+.

3. The game states’ input routines now accept regular columns that start with
a leading colon (":"). As a result, one can input the states as output from
the solver with the +-p+ and +-t+ flags directly there.

4. Added a 6th BeFS weight (see the +-asw+ flag) of the inverse of the number
of cards not above parents. Using
+./freecell-solver-range-parallel-solve 1 32000 1 -p -t -sam --method a-star -to 0123467589 -asw 1,0,0,0,0,1 -sp r:tf -mi 100000+
appears to be interesting.

5. Allow test groups inside the +-to+ and +-dto+ flags to be ordered using
the +=asw(…)+ function and its parameters, based on the BeFS (Best-first
search) weights calculation.

6. Added the +-l amateur-star+ (or +-l as+ for short) preset, based on the
+=asw(…)+ ordering that is the fastest preset yet.

7. Added the +-l micro-finance+ (or +-l mf+ for short) preset, based on the
6th BeFS weight.

8. Implement a Prune for games whose columns cannot be filled by any card
(such as Baker’s Dozen), where moving the last card on a column to a
different column is pointless. For more information, see
http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1121 .

9. In +dbm_fc_solver+ and +depth_dbm_fc_solver+, implement the “DeBondt”
encoding method for Freecell and Baker’s Dozen, which allows for an even more
compact representation of the encoded states.

10. The libfreecell-solver code is now 64-bit-enabled and many of the limits
were converted to allow for 64-bit systems.

11. Dropped support for Microsoft Visual C++ (+CL.EXE+) and other compilers
that don't support C99/gnu99.

12. Add +scripts/convert-dbm-fc-solver-solution-to-fc-solve-solution.pl+
to convert a solution output of the dbm_fc_solver to one compatible with
fc-solve.

Version 3.12.0: (12-Jun-2012)
-----------------------------

1. Add the +--show-exceeded-limits+ / +-sel+ flag that removes some ambiguity
in the output.

2. Fix invoking the solver with +--set-pruning r:tf+ in conjunction
with +-opt+.

3. Add the +-l three-eighty+ preset.

4. Many +dbm_solver.c+ improvements including the implementations of kaztree
and libavl2-derived backends, several major reductions of the memory
consumption, and many code cleanups and bug fixes.

5. Add support for building and testing the distribution in an out-of-tree
build (e.g:
+mkdir build ; cd build ; cmake -DFCS_WITH_SUITE=1 .. ; make ; make test+
).

6. A new experimental +fcc_solver.c+ which aims to reduce memory consumption
in exhaustive scans even further.

7. Removed many #ifdefs from the code by creating common abstractions.

8. Eliminate many GCC warnings with certain GCC compile flags.

Version 3.10.0: (15-Jan-2012)
-----------------------------

1. Convert the references to the web-site and repository away from berlios.de,
as it was announced it will become offline.

2. Bug fix: correct the handling of foundations with values 0 (e.g: +H-0+,
+S-0+ ).

3. Bug fix: made the +-mi+/+--max-iters+ flag global for all instances.
Previously, it affected only the last one.

4. Add an experimental +delta_states.c+ implementation and
+dbm_solver.c+ that uses it to drive a Freecell Solver scan with an on-disk
database (currently Google LevelDB and Berkeley DB are supported). So far
it seems that with a limited cache size, this does not scale too well.

5. Add the experimental +pruner-main.c+ (not installed by default).

6. Add support for generating "all_in_a_row" deals to
+make_pysol_freecll_board.py+ .

7. Many small optimizations and cleanups.

Version 3.8.0: (01-Jul-2011)
----------------------------

1. Fix the crashes when using +--trim-max-stored-states+.

2. Add a man page generated by AsciiDoc instead of the token man page
that was present previously.

3. The number of states in the collection is now preserved if the verdict
was unsolved.

4. Add a +--solutions-directory+ argument to +test_multi_parallel.c+ .

5. Fix the rpm spec - +%{version}+ instead of +%{PACKAGE_VERSION}+ .

6. Add +scripts/parallel-range-solver-total+ to solve a range of deals in
parallel by splitting them into chunks.

7. Add +-DFCS_BUILD_DOCS=+ to CMake to avoid building documentation.

8. Add a way to dump the valid outputs in
+t/t/lib/Games/Solitaire/FC_Solve/CheckResults.pm+ to files.

9. Add an environment flag to filter out the valgrind test when running
+make test+.

10. Many refactorings.

Version 3.6.0: (01-Feb-2011)
----------------------------

1. Now installing the +fcs_dllexport.h+ header file. It is needed for use
of libfreecell-solver in third-party programs, so previously including
+fcs_user.h+ did not work.

2. Add the +--tracemem+ compile-time option for tracing the amount of RAM
and time used by Freecell Solver as a function of the iterations count.

3. Bug fix for incrementally increasing the limits.

4. Add a modified version of kazlib's balanced binary search tree to the
distribution so one will be available built-in. It can be used for both
the states' storage and for the --rcs LRU cache.

5. Revamped the various range solvers, while extracting common functionality
into header files, functions and macros.

6. Some relatively minor optimisations and code cleanups.

Version 3.4.0: (05-Dec-2010)
----------------------------

1. Compiling without card flipping on by default now (finally it makes
the code a little faster instead of slower.)

2. Added the +--set-pruning+ / +-sp+ flag to turn on pruning. This sets the
Horne play prune of moving cards that can no longer be used to build other
cards upon to the foundations.

3. New preset +-l enlightened-ostrich+ / +-l eo+ based on it, which is
significantly faster than +-l foss-nessy+. Amadiro, who helped me with the
Black Hole Solitaire solver picked the name.

4. New preset +-l maliciously-obscure+ / +-l mo+ for short solutions.

5. There's now an option to set a different hard-coded freecells' num at
compile-time.

6. Add an experimental flag of "--trim-max-stored-states". Currently may
crash the solver. (See the +Known_Bugs.txt+ file).

7. Added support for -fwhole-program and static linking the Freecell Solver
executables. This yielded another speed boost.

8. Forward ported hte Google Dense Hash / Google Sparse Hash support for
the positions and columns.

9. Forward ported COMPACT_STATES.

10. Add the +--ms+ / +-M+ flags to +make_pysol_freecell_board.py+ to generate
MS Deals even for the higher numbers (> 32,000 which are not used for that in
PySol and PySol FC).

11. Add a compile-time option to use RCS-like states storage:
http://fc-solve.shlomifish.org/to-do.html#rcs_state_storage - this conserves
a lot of RAM.

12. Add a flag to get rid of visited_iter.

13. Add FCS_WITHOUT_DEPTH_FIELD to get rid of depth if fcs_state_extra_info_t.

14. Convert num_active_children to an unsigned short.

15. Forward ported the FCS_STATE_STORAGE_LIBAVL2_TREE to the new fc-solve and
the FCS_RCS_STATES. It seems to scale much better for FCS_RCS_STATES than
FCS_STATE_STORAGE_INTERNAL_HASH.

16. Converted the allocation of the BrFS queue items to alloc.{c,h} . This
wastes less memory.

17. Implement FCS_WITHOUT_LOCS_FIELDS . This removes the fc_locs / stack_locs
from the extra_info's to conserve more space. It also makes solving faster.

18. Reduced the size of num_moves in move_stack_t.

19. Add support for the internal compact moves to the Tatzer script.

20. Added /trunk/fc-solve/scripts/automatic-build-for-982-2fc-solving/Makefile
which automatically builds and runs fc-solve for solving the two-freecell MS
deal No. 982.

21. Updated the cmake configuration to use lib${LIB_SUFFIX} so it can be
built on some 64-bit systems.

22. Many small optimisations.

Version 3.2.0: (14-Jul-2010)
----------------------------

1. Add the +--depth-tests-order+ (or +-dto+ for short) flag that allows
varying the tests' order based on the depth. This allows for interesting
(and faster) searches.

2. Add the +the-iglu-cabal+ , +foss-nessy+ and +tea-for-two+ presets.
The latter is optimized for two freecell deals.

3. Fixed a bug where when specifying the +--max-iters+ flag it did not
yield an +FCS_STATE_SUSPEND_PROCESS+ return code.

4. Fix a crash when using a --prelude with a soft thread with a NULL name.

5. Add support for Google's Dense Hash for the states' storage and the stacks
storage. It does not perform as well as our own custom hash.

6. Internals: defined a boolean data type +fcs_bool_t+ with two constants
+TRUE+ and +FALSE+ , so it can be semantically different.

7. Some optimizations.

Version 3.0.0: (23-May-2010)
----------------------------

1. Implement the flares API (see +USAGE.txt+), which allows running several
alternative scans and then picking up the one with the shortest solution.

2. Add the +-l children-playing-ball+ and +-l sentient-pearls+ presets
that optimize on solution length (based on flares).

3. Add +scripts/tag-fc-solve-release.bash+ to tag using svn.

4. Updated the CMake version in the build-on-win32.pl scritp.

5. Add +scripts/stat-analysis-2.pl+ which is a faster version of the
script for statistical analysis of the solution length.

6. Refactored the +split_cmd_line.c+ module.

7. Renamed many "a_star" and "A*" occurences in the code to "BeFS", because
what was thought to be the A* scan was actually Best-First-Search.

8. Convert the soft-DFS tests' order to a list-of-lists-of-tests, and no
longer recalculating the tests_list on any recycling.

Version 2.42.0: (27-March-2010)
-------------------------------

1. Add the +-o+ / +--output+ flag to +fc-solve+ to output to a file.

2. Now installing the new executables ( freecell-solver-fc-pro-range-solve ,
freecell-solver-multi-thread-solve , freecell-solver-range-parallel-solve ,
etc.) by default.

3. Bug fix: added a missing break after a case in cmd_line.c.

4. Fixed the Makefile's "pdfs" target.

5. Converted many +char *+ data types in the interface to
+freecell_solver_string_t+, which can be +const char *+. The default is
+const char *+.

6. +pqueue.h+ was converted to the MIT/X11 license, with the permission of its
author. Freecell Solver is now fullly MIT/X11.

7. Fixed a Best-First-Search recycling memory leak that was reported by
valgrind.

8. Bug fix: now continuing a solution if a is_a_complete_scan thread terminates
with the scans synergy set to +dead-end-marks+. This was done to avoid states
reported as falsely unsolvable such as MS 254,076 with +-l by+.

9. Added a forking range solver - not installed by default. See:
http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1038 . Sometimes
it yields somewhat better performance.

10. Disabled tcmalloc in debug mode because it messes things up.

11. Various internals cleanups and optimizations.

Version 2.40.0: (27-Jan-2010)
-----------------------------

1. make_pysol_freecell_board.py now has support for "Black Hole" dealing. See:
http://www.shlomifish.org/open-source/projects/black-hole-solitaire-solver/ .

2. Added the "Scan:" header to indicate the current scan / soft-thread
when using the -s -i flags.

3. *Security*: Fixed a string overflow bug in +cmd_line.c+ with the +-asw+
weights. As a result of this problem, Freecell Solver can write several NUL
characters ('\0') to after the string specifying the command line argument.
+
Now unspecified +-asw+ are set to 0.

4. Fixed an off-by-1 iterations count report when a board was found to be
solvable.

5. iter_handler is now applied globally across all instances.

6. Add the +-l blue-yonder+ / +-l by+ preset that is extra fast at solving
the Microsoft 32,00 based on running the optimization algorithm:
+
http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1027 .

7. Added a compile-time option to reduce the size of the internal move token
structs. This may make memory consumption smaller, but definitely makes
Freecell Solver run slower, so it is off by default.

Version 2.38.0: (29-Dec-2009)
-----------------------------

1. Made sure that one can build Freecell Solver outside the source directory
without needing AsciiDoc. (That was a major build-sytem problem).

2. Add a missing newline at the end of one of the lines of the help.

3. Add the "-F"/"--pysolfc" flag to board_gen/make_pysol_freecell_board.py
for generating PySolFC deals.

Version 2.36.0: (27-Nov-2009)
-----------------------------

1. Converted the +README+ / +USAGE+ / +NEWS+ etc. files to
http://www.methods.co.nz/asciidoc/[AsciiDoc] . The sources are in .txt
and they are copied to their non-.txt files. The PDF build is still a bit
broken due to a strange CMake problem.

2. Simplified the test suite and benchmarking process. (Thanks to
http://pythack.com/[LECA Dimitri (Pythack)] for the inspiration).

3. Many documents were otherwise enhanced with examples and other enhancements.

4. Inlined the hash comparison and several other functions in the code.
This made the code a little faster.

5. Clarified the documentation for broken versions of CMake (cmake-2.6.2)
like the one that ships with some versions of Ubuntu.

6. Fixed the tests for a valgrind regression.

Version 2.34.0: (10-Jul-2009)
-----------------------------

1. Added generation and installation of a libfreecell-solver.pc pkg-config
file.

2. Added the preset "toons-for-twenty-somethings".
+
It is an atomic moves preset that can solve the MS 32K deals.

3. Re-implemented the missing --next-instance/-ni flag.

4. Added the "-l the-last-mohican"/"-l tlm" theme for Simple Simon
that can solve more boards.

5. Now can rpmbuild -tb a tar.bz2.

6. Added information on running the test suite to the "HACKING" file.

7. Added a Python ctypes example under examples/ .

8. Added support for Sun Studio to Makefile.gnu. the -fast flag yields worse
results than gcc.

9. Fixed some typos in the --help and the "USAGE" files.

10. Some internal changes:
    - The soft_thread structure now uses a union.
    - Added some tests to the command line-like argument splitting.
        - fixed a minor bug with it.


Version 2.32.1: (25-Jun-2009)
-----------------------------

1. Added a "#define BUILDING_DLL 1" so fcs_dllexport.h will work fine on
Microsoft Visual C++.

2. Normalised the DLLEXPORT modifiers.

3. Some fixes to the CMake build system:
    - CHECK_C_COMPILER_FLAG now uses a different variable for each flag,
    since the variable was cached.
    - tcmalloc is now truly optional.

4. Moved the declaration of the strncasecmp(a,b,c) macro for WIN32 systems
to before its first use.

5. All of this was done to fix many build/compilation problems.

Version 2.32.0: (24-Jun-2009)
-----------------------------

1. Added meaningful heading comments to the *.c and *.h files where they
were absent.

2. Many small memory/speed optimisations.

3. Removed a lot of unnecessary code and merged a lot of code. Used:
scripts/find-ids.rb for finding uncommonly occuring identifiers.

4. Converted many macros to inline functions.

5. Now calculating the bit-width of the 'int' data type in the CMake version.
There's a fallback logic for it in config.h.

6. Extracted empty_two_cols_from_new_state() in freecell.c.

7. Restored the max_depth functionality. Currently not working very well.

8. Now supporting inline on non-GCC compilers using CMake.

9. Made many functions that were used only once or twice inline.

10. Added the --iters-update-on option to the threaded range solver.

11. Fixed some CMake bugs (especially wrong compiler flags to check).

12. Optionally link with Google's tcmalloc, which yields better performance
(especially for the multi-threaded solver).

13. Added the support for DLLEXPORT to not export fc_solve_* from the DLL.
This reduces the size of the .so / .dll considerably.

    - Added -fvisibility=hidden to the build.

14. Got rid of using preset.c for FCS_FREECELL_ONLY.

Version 2.30.0: (07-Jun-2009)
-----------------------------

1. Added the presets "gooey-unknown-thing", "sand-stone" and "slick-rock"
to minimize the resultant solutions' length.

2. The Freecell Solver states storage and columns storage can now be
made to use any of the trees provided by libavl2
( http://www.stanford.edu/~blp/avl/ ) . The results seem to be somewhat
slower than libJudy and much slower than our own custom hash.

3. Fixed the auto-moves calculation in fc_pro_iface.c .
+
It was too pessimistic before, and had an off-by-one error. A card
can be automatically moved if all foundations of opposite color are -2
and the opposite foundation is -3.

4. Now one can exclude the Simple Simon-related move routines and logic from
the binaries during compilation. See "FCS_DISABLE_SIMPLE_SIMON" in the
CMake configuration.

5. Added scripts/measure-binaries-sizes.rb to measure the sizes of the binaries
in various configurations.

6. Merged Makefile.icc , Makefile.tendra , Makefile.tcc , Makefile.pcc
and Makefile.lcc into Makefile.gnu. Which compiler can be specified using
the Makefile.gnu COMPILER variable.

7. Added the threaded_range_solver "--worker-step $N" argument.
+
What is does is allow allocating uniform quotas to the different threads
to process. So far increasing the quotas from 1 to 16 does not seem to improve
the situation.

8. Fixed many warnings reported by the Intel C++ compiler (icc)

9. Re-organized the code - renamed many files, moved declarations and
definitions to different files, and did a lot of overhaul.

10. Got rid of FCS_DEBUG_MOVES - it was never used and became obnoxious.

11. Added scripts/verify-simple-simon-range.pl and
scripts/simple-simon-stats-analysis.pl .

12. Added a regression test for verifying the validity of a
Simple Simon solution.

13. Fixed Makefile.gnu to propagate CFLAGS to CREATE_SHARED.

14. Implemented FCS_WITHOUT_CARD_FLIPPING to exclude a lot of card flipping
code at build time. It is disabled by default because strangely it seems
to make the execution speed worse.

Version 2.28.1 (18-May-2009)
----------------------------

1. Added a fix to an off-by-one-error in alloc.h that caused a segfault
on x86-64. (Thanks to Ido Kanner).

Version 2.28.0 (17-May-2009)
----------------------------

1. Several cleanups, refactoring and optimizations - especially to the
freecell.c file.

2. Converted more move functions ot positions_by_rank.

3. Changed the hash function from Bob Jenkins's to perl 5's and inlined it.
These were substantial optimizations.

4. Unified many macros in state.h instead of having duplicate definitions
for every state type. Verified that the alternative state types (
COMPACT_STATES and DEBUG_STATES) build correctly.

5. Added the optional -Werror=implicit-function-declarations flag to the
compiler.

6. Added tests for some Simple Simon boards.

7. Created an fcs_cards_column_t type and converted the internals to use it.

8. Added the threaded range solver - freecell-solver-multi-thread-solve .
It performs better than the serial one on my machine.  It is built only if
pthreads (POSIX threads) is found.

9. Add the HACKING file with some information on benchmarking.

10. Renamed the configuration script to "Tatzer" so people who are used
to Autoconf's "./configure ; make ; make install" won't use it.

11. Got rid of all the max_num_$something in the dynamically-growing
arrays because num_$something is enough to tell where the limit is and grow it
if necessary. There's now a lot of bit-fiddling logic to grow the
dynamically-growing arrays when necessary.

12. Added support for adding the gcc -fomit-frame-pointer and -march=$CPU_ARCH
flags.

13. Added the following makefiles for alternative Linux compilers:
+
    - Makefile.icc
    - Makefile.tcc
    - Makefile.tendra
    - Makefile.lcc
    - Makefile.pcc
+
So far only Intel's icc and TenDRA produce working executables that
pass all the tests. The code had to be adapted to be compiled using TenDRA.

14. Added scripts/fcs-win32-create-package.pl that provides some guidance
in creating a package under Windows.

Version 2.26.0 (27-Apr-2009)
----------------------------

1. Now Freecell Solver can be compiled with gcc-2.95 (again). It was needed
to test it with this old gcc version.

2. Some fixes to CMakeLists.txt.

3. fcs_hash.c: now the secondary hash value calculation is optional
and should be enabled explicitly. Without it, Freecell Solver is faster:
    - http://tech.groups.yahoo.com/group/fc-solve-discuss/message/941

4. Surgically removed fcs_hash.c's "optimizing_for_cache" which made a small
speed improvement.
    - http://tech.groups.yahoo.com/group/fc-solve-discuss/message/942

5. Made t/Makefile generated by CMake, so the tests can be run from the
packages source distribution. (Previously t/Makefile was excluded, and
since it was not generated, was not available).

6. Eliminated BUILD_TYPE=release warnings.

7. Optimized fc_solve_sfs_move_freecell_cards_on_top_of_stacks() . This
involved a lot of refactoring and re-structuring of the internals. Now
Freecell Solver is significantly faster.
    - http://tech.groups.yahoo.com/group/fc-solve-discuss/message/943

8. Fixed the testing targets and the building of the rpm from the tar.gz
archive.

Version 2.24.0 (18-Apr-2009)
----------------------------

1. Many code cleanups and internal changes. Reduced the size of the library
considerably.

2. Added Makefile.llvm to build LLVM bitcodes from the Freecell Solver
sources. So far, they seem significantly slower than the native code compiled
using gcc-4.3.2.

3. Implemented "cmake -DCMAKE_BUILD_TYPE=profile" . Can be activated using
"./configure --profile"

4. Now build (but not installing) freecell-solver-fc-pro-range-solve , which
runs a range of MS-Freecell / Freecell Pro boards using the solver and outputs
the number of FCS moves, the number of FC-Pro moves, and the FC-Pro moves
in standard notation.

5. Fixed some bugs (crashes, leaks, etc.) when running -opt on a range
of boards (or recycling instances with -opt in general).

6. Some CMake / Build system cleanups and improvements. Among them, trimmed
the distribution from unnecessary files.

Version 2.22.0 (31-Mar-2009)
----------------------------

1. Various improvements to the CMake build process:
    - Updated freecell-solver-config
    - Fixed the building if build from a different directory.
        (e.g: mkdir build ; cd build ; cmake ..)
    - Now also building a static library by default. There's a cmake option
    to trigger it off.
    - Thanks to RISKO Gergely (the maintainer of the Freecell Solver Debian
    package) for a contributed patch.

2. Fixed the rpmbuild -tb process on Mandriva Linux Cooker (and
possibly other systems).

3. Removed some old, unnecessary and/or no-longer-working files.

4. Converted the package from the Public Domain to the MIT/X11 Licence
( http://en.wikipedia.org/wiki/MIT_License ). This change was done due to
the many problems with licensing source code under the public domain:

    - http://linuxmafia.com/faq/Licensing_and_Law/public-domain.html

Version 2.20.0 (26-Mar-2009)
----------------------------

1. Updated the "NEWS" file (this file) with all the previous versions up
to 0.4 (the first release after the first initial release).

2. Many fixes to the Win32 NSIS Package creation process of CMake/CPack .
The NSIS package is now built and installed properly.

3. Fixed a bug with the recycling logic of the optimization thread.
+
This influenced "freecell-solver-range-parallel-solve 1 2 1 -opt" among other
things. In the process, I refactored the code a bit after trying to follow
some false leads.

4. Fixed the --prefix flag in ./configure to be treated as a string instead
of a boolean.

5. Fixed the running of the executables under a specified PREFIX
( http://www.cmake.org/Wiki/CMake_RPATH_handling )

6. Minor changes to "README", "INSTALL" and "USAGE".

Version 2.18.0 (19-Mar-2009)
----------------------------

1. Added the FCS_FREECELL_ONLY compile-time flag to hard-code the settings
for Freecell and thus allow faster run-time. On a Pentium 4-2.4GHz machine
running Mandriva Linux Cooker, this allows to solve the Microsoft 32,000 in
194.56353 seconds ( 164 deals / second ) instead of
228.84 seconds for the generic version ( 140 deals / second ).

2. Fixed using libredblack ( http://libredblack.sourceforge.net/ ) for states
and stacks storage. (Compile-time options)

3. Added an option to use libJudy ( http://judy.sourceforge.net/ ) for states
and stacks storage. Yields better performance than libredblack, but worse
than the internal hash.

4. Added the -Wall by default for gcc in CMake.

5. Added the boards target to generate 24.board and 1941.board.

6. Updated the TODO file.

7. Added previous NEWS items for previous versions (in this file).

8. Now documenting the --version flag in USAGE.

9. Added an experimental ./configure convenience script (written in
Perl) to run CMake using some configuration options. NOTE: Please don't
use it to build packages.

10. Added "scripts/time-fcs.pl" to help time a
freecell-solver-range-parallel-solve dump.

11. Got rid of the hard_dfs() scan. It is still accepted as an argument, but
is now using the soft_dfs() routines instead.

12. Many internal refactorings, cleanups tweaks and fine-tunings.

13. Moved away change_ver.sh to scripts/old/change_ver.sh - it does not
seem to be used any longer.

Version 2.16.0 (15-Mar-2009)
----------------------------

1. Made sure the indexes of the iterations when the "-s -i" flags are specified
are consecutive. Previously, they were much more inconsistent.

2. (Internals) Split ptr_state_with_locations_t into ptr_state_t (the key)
and ptr_state_extra_info_t (the value). Not all code inside the #ifdef's
(like the libavl / libredblack code) was ported to use it instead.

Version 2.14.0 (25-Jan-2009)
----------------------------

1. Fixed the compilation with profiling information in Makefile.gnu (should be
of concern only to developers).

2. Optimized move_stack_cards_to_different_stacks, yielding a substantial
speed increase.

3. Converted the identifiers from starting with freecell_solver_ to
starting with fc_solve_ , which is shorter and saner.
+
freecell_solver_user_ is still used in the API in order to not break
compatibility.

4. Made sure the effect of the "--sequence-move unlimited" option is not
dependent on other options, so the sequence move will always be unlimited.
(Thanks to larrysan for reporting this bug).

5. Fixed run-tests.pl (and as a result also ctest -V and make test) to
run properly after a raw unpacking.

Version 2.12.0 ( 10-Dec-2008)
-----------------------------

1. A New Configuration and build system based on CMake
( http://www.cmake.org/ ) which results in faster configurations
and builds, and a much reduced archive size.

2. There's a new suite of automated tests. See the file README for details
how to run them.

3. There's a new --version flag that prints the version of the library.

4. A speed optimization to the command line processing based on a radix-tree.

5. Many bug-fixes since 2.8.0. (Released as 2.8.x).

Version 2.8.0 ( 28-Sep-2002 )
-----------------------------

1. Better documentation and help screens. See:
+
http://freshmeat.net/articles/time-to-rethink-your-help-flag

2. A preset system - see the "-l" flag in USAGE.

3. An option to read paramters from files. See "--read-from-file" in USAGE.

4. Finally, it is now possible to run one instance of the solver after the
other in case the other one has returned a negative verdict. This is useful
for example to run an atomic moves preset after a meta-moves one, as the
latter cannot guarantee an accurate false verdict.

Version 2.6.0 ( 12-Jul-2002 )
-----------------------------

1. Atomic moves and some atomic moves presets have been added. Solving
using atomic moves guarantees that there will be no false negatives, but
is slower than the Meta-moves-based presets. (At least for now). It also
yields less interesting solutions.

2. There is now a "--prelude" switch (see USAGE) that allows running a
static order of quotas at the beginning of the scan for the participating
soft threads. It makes constructing faster solving presets easier, especially
after utilising this code:
+
http://code.google.com/p/fc-solve/source/browse/#svn%2Ffc-solve%2Ftrunk%2Ffc-solve%2Fpresets
+
Also see the "--st-name" option.

3. The PySol "Fan" game preset was added to make_pysol_freecell_board.py and
to Freecell Solver itself. Note that the game is played with 18
columns/stacks , so Freecell Solver will usually need to be recompiled.

4. Several other command line options:
+
    - "--reparent-states"
    - "--calc-real-depth"
    - "--optimization-tests-order"
    - "--scans-synergy"
+
See the "USAGE" file for more information.

5. The internal code has undergone several speed boosts that made Freecell
Solver much faster. Now the INDIRECT_STACK_STATES is a bit faster than
COMPACT_STATES.

6. Updated the TODO list.

Version 2.4.0 ( 29-Mar-2002 )
-----------------------------

1. Now several scans are to operate on the same states' collection. This is
done using a mechanism called "soft threads", which is switched in user-land
and does not require system multi-threading. In the file "USAGE" see:
+
    - "-nst"  / "--next-soft-thread"
    - "-nht"  / "--next-hard-thread"
    - "-step" / "--soft-thread-step"

2. fcs_cl.h was included in the RPM .spec.

Version 2.2.0 ( 18-Feb-2002 )
-----------------------------

1. Freecell Solver's version is now kept in the file ver.txt

2. Added manual pages symbolic links for the following command-line board
generators:
+
    - make-gnome-freecell-board
    - make_pysol_freecell_board.py
    - make-aisleriot-freecell-board
    - pi-make-microsoft-freecell-board

3. Moved more declarations of functions to header files (ending with .h)

4. Added some compiler-optional inline annotations for functions.

5. The identifiers of the library are now all residing under freecell_solver_

6. New flag:
+
    - "--max-stored-states"

7. The package can now be built as an RPM for Red Hat Linux and compatible
systems by running rpmbuild -ta on the archive.

8. Several speed-ups.

Version 2.0.0 ( 19-Dec-2001 )
-----------------------------

1. Added some presets for the PySol games "Beleaguered Castle", "Citadel"
and "Streets and Alleys".

2. Re-factoring of the scans code to make it simpler.

3. Added many functions to the external API.

4. fc-solve now uses it, so it is fully loosely-coupled with the library
it is linked against.

5. Added a randomized DFS scan (with a user-defined seed).

6. Win32 Makefile can now generate a working DLL.

Version 1.10.0 ( 02-Oct-2001 )
------------------------------

Added support for solving deals of "Simple Simon" in addition to
all the freecell-like variants that it could solve before.

Version 1.8.0 ( 31-Aug-2001 )
-----------------------------

1. A new build and configuration process based on the GNU Autotools (Autoconf,
Automake and libtool). This allows portably build shared and static libraries
and stuff like that.

2. The GNOME AisleRiot board-generation program can generate the boards of
the more Solitaire variants which are supported by Freecell Solver.

Version 1.6.0 ( 11-Apr-2001 )
-----------------------------

1. Freecell Solver now has a solution optimization scan. Check it out
by adding the "-opt" flag.

2. Many comments were added to the code, and you are welcome to go over
it and see if you understand everything that goes on there. If you don't,
contact me and I'll add some more comments.

3. Several speed optimizations were done in the internal hash, so I think
it should run at least a little faster.

Version 1.4.0 ( 07-Feb-2001 )
-----------------------------

1. Many fixes for bugs and memory leaks.

2. A Soft-DFS scan - Depth-First Search that does not use procedural recursion
was introduced.

3. A New Best-first Search Scan (called A* in the code and documentation was
introduced).

4. A New Breadth-First-Search (BFS or BrFS) scan was introduced. It's not
very practical.

The choice between all those scans can be specified at run-time using
command-line arguments.

Version 1.2.0 ( 21-Dec-2000 )
-----------------------------

1. Several moves were improved or added, so it can solve more layouts.

2. A more robust command-line argument handling, so less segfaults can be
expected if it's improperly used.

Version 1.0.0 ( 19-Nov-2000 )
-----------------------------

1. Added support for solving more game types.

2. Can be compiled so it will be less memory intensive (INDIRECT_STACK_STATES).

3. There's an API for use by third-party developers. It supports
suspending a solution process and resuming it from its last position.

4. Several random bug-fixes.

Version 0.10.0 ( 09-Oct-2000 )
------------------------------

1. Support was added for several Solitaire variants besides Freecell, such as
Forecell, Seahaven Towers and Eight Off.

2. It now can emits the moves themselves, instead of just the intermediate
solutiosn.

3. Several bug-fixes.

Version 0.8.0 ( 28-Aug-2000 )
-----------------------------

1. Some bug-fixes.

2. Support for a variable number of freecells, columns, and cards per column.

3. Board generators for Microsoft Freecell, Freecell Pro and PySol.

4. An option to use the balanced binary tree implementations of libavl
( http://adtinfo.org/ ), glib ( http://en.wikipedia.org/wiki/GLib ), or
libredblack ( http://libredblack.sourceforge.net/ ). Using them makes
Freecell Solver about 33% faster.

5. Support for using "T" instead of "10" in board input/output.

6. Improved Documentation.

Version 0.6 ( 28-Jul-2000 )
---------------------------

1. An extra movement that allows Freecell Solver to solve some boards which
it could not solve previously.

2. The order of the stacks and freecells is preserved throughout the
solutions.

3. There is now in abilitiy to limit to a certain number of iterations (so
Freecell Solver will stop before it consumes too much memory)

4. Specify the order of the movements that will be tested. Usually, a test
order can be found that will solve a given board really quickly.

Version 0.4 ( 06-Jun-2000 )
---------------------------

1. Three major code optimizations. Freecell Solver now runs much faster.

2. Freecell Solver is now able to start solving from a non-initial board.