Permalink
Switch branches/tags
v2_4_2@3681 v2_4_2@5 v2_4_2@3 v2_4_2 releases@3681 releases prepare-depth-dbm-fc-solve-for-amazon-aws--two-remaining-4fc-deals--take1--2016-12-26 prepare-depth-dbm-fc-solve-for-amazon-aws--take1--2016-11-04 latest-devel@3681 latest-devel@737 latest-devel@619 latest-devel@573 latest-devel gcc-4.5-slowdown-Before@3681 gcc-4.5-slowdown-Before@2947 gcc-4.5-slowdown-Before@2910 gcc-4.5-slowdown-Before@2909 gcc-4.5-slowdown-Before gcc-4.5-slowdown-After@3681 gcc-4.5-slowdown-After@2949 gcc-4.5-slowdown-After@2910 gcc-4.5-slowdown-After@2909 gcc-4.5-slowdown-After freecell-solver-4.20.0 freecell-solver-4.18.0 freecell-solver-4.16.0 freecell-solver-4.14.1 freecell-solver-4.14.0 freecell-solver-4.12.1 freecell-solver-4.12.0 freecell-solver-4.10.0 freecell-solver-4.8.0 freecell-solver-4.6.1 freecell-solver-4.6.0 freecell-solver-4.4.0 freecell-solver-4.2.0 freecell-solver-4.0.2 freecell-solver-4.0.1 freecell-solver-4.0.0 freecell-solver-3.27.0 freecell-solver-3.26.0 freecell-solver-3.24.0 freecell-solver-3.22.0 freecell-solver-3.21.5 freecell-solver-3.20.1 freecell-solver-3.20.0 freecell-solver-3.18.1 freecell-solver-3.18.0 freecell-solver-3.17.3-testsuite-and-rpmbuild-working-on-32-bit freecell-solver-3.16.0 freecell-solver-3.14.1 freecell-solver-3.14.0 freecell-solver-3.12.0 freecell-solver-3.11.0 depth_dbm_fc_solver_100M_4fc_intractables_for_Amadiro depth_dbm_fc_solver_100M_short_solutions_for_amadiro depth_dbm_fc_solver_100K_to_400k_run_with_500GB depth_dbm_fc_solver_100K_to_400k_run_with_500GB_with_fixed_avl_tree depth_dbm_fc_solver_100K_to_400k_run_with_500GB_take7 dbm_fcs_for_subanark.tar.gz dbm_fcs_for_amadiro-WITH_RAM_OPTIMISATIONS-try2.tar.gz dbm_fcs_for_amadiro-WITH_RAM_OPTIMISATIONS-try1.tar.gz dbm_fc_solver_32001_to_50000_tar.gz dbm_fc_solver_100K_to_400k.tar.gz dbm_fc_solver_100K_to_400k_run_with_500GB dbm_fc_solver_100K_to_400k_run_with_500GB_take4 dbm_fc_solver_100K_to_400k_run_with_127GB dbm_fc_solver_100K_to_400k-127GB-take2.tar.gz dbm_fc_solver_50K_to_100K_tar.gz before-remove-cmake-generated-files-in-dot-dir asciidoc.vim-USAGE-bug@3681 asciidoc.vim-USAGE-bug@2188 asciidoc.vim-USAGE-bug@2183 asciidoc.vim-USAGE-bug Task-FreecellSolver-Testing@3681 Task-FreecellSolver-Testing Task-FreecellSolver-Testing-MultiConfig-0.0.1 Task-FreecellSolver-Testing-0.0.11 Task-FreecellSolver-Testing-0.0.10 Task-FreecellSolver-Testing-0.0.9 Task-FreecellSolver-Testing-0.0.8 Task-FreecellSolver-Testing-0.0.7 Task-FreecellSolver-Testing-0.0.6 Task-FreecellSolver-Testing-0.0.5 Task-FreecellSolver-Testing-0.0.4 Task-FreecellSolver-Testing-0.0.3 MALLOC_CHECK_-problems@3681 MALLOC_CHECK_-problems@1946 MALLOC_CHECK_-problems LATEST_DEVEL@3681 LATEST_DEVEL@573 LATEST_DEVEL Initial_CVS@3681 Initial_CVS@41 Initial_CVS@3 Initial_CVS Games-Solitaire-Verify@3681 Games-Solitaire-Verify Games-Solitaire-Verify-0.1800 Games-Solitaire-Verify-0.1701
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
194 lines (143 sloc) 7.73 KB
Freecell Solver's To-do list
============================
Shlomi Fish <shlomif@cpan.org>
:Date: 2009-08-14
:Revision: $Id$
[id="pressing"]
Pressing
--------
[id="non_pressing"]
Non-pressing
------------
* Write a better initial board/initial layout validation code for the online
solver (at least initially]):
** Exact number of playstacks. (requires introspection).
** Number of Freecells not exceeded. (requires introspection).
** missing/extra cards.
** whitespace gaps.
** invalid characters.
** misformatting of the format.
* Find how well the solver performs with different permutations of the
order of columns/freecells.
** See if it's possible to combine several scans on such different
permutations.
* Write a "simulator" for new flare-based runs to see how they improve on
the existing runs. It will process the scans' command line based on their
end results and performance and will generate the new estimated performance.
* Write the split-dbm-solver which stores the results on the disk for every
non-reversible-moves offset, and fully-connected-components.
* Refer to +expand-solitaire-multi-card-moves+ from the fc-solve process.
* Create a displayer for fc-solve's solutions which will allow seeing where a
card was moved from (using a colored →) and where it was placed.
** Create a GUI version.
* If +-opt+ is specified for the flare, then make sure that if the flares
loop stop it when it's doing the optimization scan, then the optimization scan
goes on until it ends.
** Not sure about it.
* Implement more of Kevin Atkinson's Common Lisp solver's atomic move types,
and try to construct good heuristics out of them.
* Play with writing a memory-re-cycling Soft-DFS scan: if a sub-tree was
marked as a dead-end, then its states might be able to be placed on a linked
list of states that can be reused.
* PySolFC Deal No. 48007594292403677907 :
--------------------------------------------------------
shlomif:~$ make_pysol_freecell_board.py -t -F 48007594292403677907 | fc-solve -l cpb -sam | grep ^Move | wc -l
106
shlomif:~$ make_pysol_freecell_board.py -t -F 48007594292403677907 | fc-solve --method a-star -to 01234675 -asw 300,1500,0,2,50000 -sam | grep ^Move | wc -l
105
shlomif:~$ make_pysol_freecell_board.py -t -F 48007594292403677907 | fc-solve --method a-star -to 01234675 -asw 40,2,40,0,40 -sam | grep ^Move | wc -l
121
shlomif:~$ make_pysol_freecell_board.py -t -F 48007594292403677907 | fc-solve --method a-star -to 0123467589 -asw 300,1500,0,2,50000 -sam | grep ^Move | wc -l
100
shlomif:~$ make_pysol_freecell_board.py -t -F 48007594292403677907 | fc-solve --method a-star -to 0123467589 -asw 300,1500,0,2,40000 -sam | grep ^Move | wc -l
106
shlomif:~$ make_pysol_freecell_board.py -t -F 48007594292403677907 | fc-solve --method a-star -to 0123467589 -asw 300,1500,0,2,60000 -sam | grep ^Move | wc -l
91
--------------------------------------------------------
--------------------------------------------------------
shlomif:~$ make_pysol_freecell_board.py -F -t 91151234961275807905 | ~/apps/test/fcs/bin/fc-solve -p -t -sam --method a-star -to 0123467589 -asw 300,1000,0,2,90000 | grep ^Move | wc -l
84
--------------------------------------------------------
However this scan generates takes too much time for most boards (over 100K
iterations).
* PySolFC deal No. 03620802041832966472:
--------------------------------------------------------
shlomif[fcs]:$trunk/fc-solve/source$ make_pysol_freecell_board.py -t -F 03620802041832966472 | ./scripts/summarize-fc-solve -- --method a-star -to 0123467589 -asw 300,1500,99,2,65000
Verdict: Solved ; Iters: 156 ; Length: 87
--------------------------------------------------------
** I solved it at length 87.
* PySolFC deal No. 54369539487824719321:
--------------------------------------------------------
shlomif[fcs]:$trunk/fc-solve/source$ make_pysol_freecell_board.py -F -t 54369539487824719321 | ./scripts/summarize-fc-solve --method a-star -to 0123456789 -asw 3000,100,60,0,500
Verdict: Solved ; Iters: 1325 ; Length: 115
--------------------------------------------------------
** Shlomi Fish solved it in under 110 moves.
* PySolFC deal 96166640969002647853:
--------------------------------------------------------
shlomif[fcs]:$trunk/fc-solve/source$ make_pysol_freecell_board.py -F -t 96166640969002647853 | ./scripts/summarize-fc-solve --method a-star -to 0123467589 -asw 370,0,0,2,90000
Verdict: Solved ; Iters: 615 ; Length: 77
--------------------------------------------------------
** Shlomi Fish solved it in 77 moves.
* PySolFC deal 26892246862786948900:
--------------------------------------------------------
shlomif[fcs]:$trunk/fc-solve/source$ make_pysol_freecell_board.py -F -t 26892246862786948900 | perl scripts/summarize-fc-solve -l qsi --flares-choice fc_solve
Verdict: Solved ; Iters: 195331 ; Length: 98
shlomif[fcs]:$trunk/fc-solve/source$ make_pysol_freecell_board.py -F -t 26892246862786948900 | perl scripts/summarize-fc-solve --method a-star -asw '1,0,4,0,4' --flares-choice fc_solve
Verdict: Solved ; Iters: 111 ; Length: 92
--------------------------------------------------------
** Shlomi Fish solved it in 92 moves.
* Add the new Freecell Solver-compatible game variants of PySolFC.
* Convert magic rank constants such as 1 or 13 to FCS_MAX_RANK and
FCS_RANK_ACE/etc.
* Investigate:
--------------------------------------------------------
$ make_pysol_freecell_board.py -F -t 00682189035907813607 | perl ../scripts/summarize-fc-solve -l qsi
Verdict: Solved ; Iters: 157905 ; Length: 109
$ make_pysol_freecell_board.py -F -t 00682189035907813607 | perl ../scripts/summarize-fc-solve --method a-star -to '01234567' -asw 1 -opt
Verdict: Solved ; Iters: 433 ; Length: 89
--------------------------------------------------------
* Consider adding the +restrict+ keyword:
** http://stackoverflow.com/questions/776283/what-does-the-restrict-keyword-mean-in-c
** https://duckduckgo.com/?q=restrict+keyword+c&ia=web
[id="long_term"]
Long-term
---------
* Integrate the patsolve's prioritization and mixed BFS/DFS scan.
* Update the architecture document.
* Make a super-strict parsable-output without all the quirks of
-p -t (see Games-Solitaire-Verify for why).
** Perhaps see: http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1264 .
* Write a multi-threaded version.
* Add a switch to ask the user if he wants to continue and enter a bigger
iterations limit.
* Check for unmalloced data and if so gracefully exit.
* Experiment with a delta-based state storage.
- see delta_states_debondt.c - port it to the main libfreecell-solver.
- see: http://fc-solve.shlomifish.org/to-do.html#orig_calc_states .
* Adapt the scans based on the parameters of the initial board.
+
** Try to find a correlation between various parameters of the initial board
(such as those calculated in the A* scan or the number of steps required to
sort the cards in each column by rank), and the performance of various scans
and then:
+
1. Calculate the initial parameters on startup.
+
2. See what would be a good meta-scan based on them.
+
3. Use it.
* Unit-test +fc_solve_compare_lru_cache_keys+ in +scans.c+.
* Interactive mode? Continue a scan that reached its limit.
* Adapt +-dto2+ to other parameters aside from depth, such as
total-number-of-cards-in-the-foundations or maximal foundation value.
* Set up a +-dto2+ like scheme for +--method a-star+ where we change the tests
order based on the depth/etc.
* Work on HYBRID_STACKS_STATES where if the stacks are shorter than 8 cards,
then one can store them in the normally pointer bytes, by specifying whether
the stack is a pointer or a direct stack using the low bit. (An improvement
to INDIRECT_STACK_STATES).
[id="to_be_considered"]
To be considered
----------------
* Make the code https://sourceforge.net/projects/splint/[splint]-clean.
* Write a multi-process client/server program.