Hi all,
On Fri, 28 Sep 2012 01:45:45 +0200
Shlomi Fish <shlomif_at_shlomifish.org> wrote:
> Hi Danny,
>
> On Thu, 27 Sep 2012 21:12:32 -0000
> "dannyjones183" <dannyjones183_at_yahoo.com> wrote:
>
> > My records indicate there are two intractable 8x4 deals in the first
> > 100,000,000 deals: #24,795,893 and #53,687,601. Does anyone have any
> > other results for these deals?
> >
>
> Running deal No 24,795,893 on both my depth_dbm_solver and the regular
> fc-solve (both with atomic moves and 4-freecells) seem to indicate
> that it is impossible. The depth_dbm_solver yields this output at the
> end:
>
> [QUOTE]
>
> Running threads for curr_depth=103
> instance_run_solver_thread start
> instance_run_solver_thread end
> instance_run_solver_thread start
> instance_run_solver_thread end
> instance_run_solver_thread start
> instance_run_solver_thread end
> instance_run_solver_thread start
> instance_run_solver_thread end
> Finished running threads for curr_depth=103
> Start mark-and-sweep cleanup for curr_depth=103
> Finish mark-and-sweep cleanup for curr_depth=103
> instance_run_all_threads end
> handle_and_destroy_instance_solution start
> Reached 65441019 ; States-in-collection: 65441019 ; Time:
> 1348787301.126059
> >>>Queue Stats: inserted=65441019 items_in_queue=0 extracted=65441019
> Could not solve successfully.
> handle_and_destroy_instance_solution end
>
> [/QUOTE]
>
> The regular fc-solve gives this:
>
> [QUOTE]
>
> I could not solve this game.
> Total number of states checked is 66639840.
> This scan generated 66639839 states.
>
> [/QUOTE]
>
> After it was invoked like:
>
> [COMMAND_LINE]
> ./fc-solve -to 01ABCDE -sp r:tf -p -t -sam -sel -o 24795893.out2
> 24795893.board [/COMMAND_LINE]
>
> One thing worrying is that the iterations count is different in both
> cases, which may be indicative of a bug. I'll have to investigate.
>
I investigated this by logging the intermediate states, and sorting them
(using the UNIX "sort -o [output] [input]" command) and then comparing them
(which was time-consuming as there were about 60-70 million states), and
discovered that the cause of the discrepancy was the fact that fc-solve
did the pruning explicitly (and emitted and counted the non-pruned positions)
, while the depth_dbm_fc_solver did them implicitly after performing every
move. So it was not a bug.
However, while I did that, I discovered a different bug with the DEBUG_OUT
#ifdef in dbm_fc_solver and the depth_dbm_fc_solver which I fixed.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Escape from GNU Autohell - http://www.shlomifish.org/open-source/anti/autohell/
<rindolf> If you repeat a scene 50k times, then the movie will have less
entropy and will compress better. ( irc://irc.freenode.org/#perlcafe )
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Sat Sep 29 2012 - 00:10:10 IST