Here's what new on the Freecell Solver trunk as of r3265 since the previous
update:
*
http://svn.berlios.de/svnroot/repos/fc-solve/trunk
(Previous update is here -
http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1069 )
What's new:
-----------
1. Forward ported the Google Dense Hash positions' and columns' backends. This
was done in order to save space space, but I ended up finding more efficient
ways to save space later in the development (see below). Still it may prove of
utility later on.
1.1: added a choice between Google's dense_hash and sparse_hash.
2. In the benchmark script replaced "> dump002" with "|tee dump002" to allow
viewing the progress of the solver again. This is a small change but makes me
very happy.
3. There are some improvements to the profile-guided optimisation script and
process to make then more usable. New benchmarks showed that they now improved
performance.
4. Forward ported COMPACT_STATES.
5. Add two more atomic scans that yield especially short solutions on average
- scan No. 30 and Scan No. 31 to the scans database. I didn't construct meta-
scans out of them yet.
6. Add the --ms / -M flags ot 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).
7. Reworked the summarize-fc-solve script.
8. Replaced the ShareThis button on the site with AddToAny. Die Google
Analytics dependency! Die!
9. Add the implementation of the RCS-like states storage:
http://fc-solve.berlios.de/to-do.html#rcs_state_storage
{{{
It keeps only the states infos in the collection and makes sure that the
state keys are calculated from them and kept in a cache.
}}}
This conserves a lot of RAM.
10. Some other memory (and sometimes speed) optimisations:
* Made without-card-flipping the default.
* Add a flag to get rid of visited_iter.
* Add FCS_WITHOUT_DEPTH_FIELD to get rid of depth if fcs_state_extra_info_t.
* Convert num_active_children to an unsigned short.
* Now recycling the hard thread allocator between instance recyclings to
prevent excessive mallocs and frees.
* 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.
* Converted the allocation of the BrFS queue items to alloc.{c,h} . This
wastes less memory.
* 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.
(see note below)
* Reduced the size of num_moves in move_stack_t.
* Add support for the internal compact moves to the Tatzer script.
11. 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. Currently it crashes on the HPC computer with 64 GB that we ran
it on but after reaching 400 million iterations. There were several other
memory improvements afterwards, but I don't think they will make such a
difference, and we probably need a machine with more RAM.
12. Some new benchmarks were added. I can now solve the MS 32,000 on my old
P4-2.4GHz machine in 74.6558539867401 seconds ( over 428 deals per second).
-------------------------
Now a reflection on the optional removal of the fc_locs and stack_locs. I
recall them being the highlight of Freecell Solver 0.6 , which used them to
preserve the original indices of the columns and freecells in the state,
without rearranging them in the solution. Now that I looked at it, it seemed
unnecessary as the solution could be traced using the move stack and the
CANONIZE move. So the #ifdef to remove it made an improvement.
I initially thought of converting an 8-stack stack_locs to 8 3-bit fields (or
3 bytes) instead of the 8 bytes fields that we have now. Then I thought the 8-
factorial permutation will take less place. And then I realised we might not
need them at all.
The code has become a bit convulted due to all the changes with many #ifdef's.
Looking at all the work and improvements, I've been tempted in making the next
version Freecell Solver 4.0.0 , but I think it will be only 3.4.0 to be less
presumptious. Still, all of these are huge steps forward for Freeell Solver.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
My Aphorisms - http://www.shlomifish.org/humour.html
<rindolf> She's a hot chick. But she smokes.
<go|dfish> She can smoke as long as she's smokin'.
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Sat Oct 09 2010 - 15:23:18 IST