Source

fc-solve / fc-solve / source / TODO.txt

Freecell Solver's To-do list
============================
Shlomi Fish <shlomif@cpan.org>
:Date: 2009-08-14
:Revision: $Id$

Pressing
--------

Non-pressing
------------

* Implement a --flares-iters-factor option for multiplying the iters count
allocated to each flare by a constant factor (so one can say make them times
10, or times 100 or times 0.5, etc.).
    - Test more thoroughly.

* Convert the functions in lib.c to do
+fcs_user_t * user = (fcs_user_t *)api_instance;+ .

* Investigate the scan of:
+--method random-dfs -to '[01]=rand()[23456789]=rand()' -dto '13,[0123456]=asw(1)' -sp r:tf+.
* It seems to yield good results.
** It generates a relatively short and a fast solution for MS #6240 , for
which "-l micro-finance" generates the longest solution out of the Microsoft
32K

* 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.

* Investigate a way to have positions_by_rank also index according to the
suit, and to traverse only the possible parents or children based on the
suit.

* Investigate ways to perform more pointer arithematics and
(ptr < end_ptr) ; ptr++ . A lot of code is under-optimized this way.

* In the states handling, there's still some room for pointer arithmetics.

* Implement more of Kevin Atkinson's Common Lisp solver's atomic move types,
and try to contruct 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.

* Add a FCS_2FC_FREECELL_ONLY macro for quickly solving 2 freecell games.

* 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.

* Add the new Freecell Solver-compatible game variants of PySolFC.

Long-term
---------

* Code a generic tests grouping.

* 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).

* Write a multi-threaded version.

* Port to Java (?)

* 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 .

* Make the dbm_fc_solver not dependent on http://gmplib.org/ by implementing
our own big ints.

* 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.

To be considered
----------------

* Make the code https://sourceforge.net/projects/splint/[splint]-clean.

* Write a multi-process client/server program.

* Add a limit to stacks number (in the case of Indirect Stack States),
number of states that are stored anywhere, etc.
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.