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
|
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="en">
<head>
<meta charset="UTF-8"/>
<!--[if IE]><meta http-equiv="X-UA-Compatible" content="IE=edge"/><![endif]-->
<meta name="viewport" content="width=device-width, initial-scale=1.0"/>
<meta name="generator" content="Asciidoctor 1.5.7.1"/>
<meta name="author" content="Shlomi Fish"/>
<title>Freecell Solver’s To-do list</title>
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Open+Sans:300,300italic,400,400italic,600,600italic%7CNoto+Serif:400,400italic,700,700italic%7CDroid+Sans+Mono:400,700"/>
<link rel="stylesheet" href="./asciidoctor.css"/>
</head>
<body class="article">
<div id="header">
<h1>Freecell Solver’s To-do list</h1>
<div class="details">
<span id="author" class="author">Shlomi Fish</span><br/>
<span id="email" class="email"><a href="mailto:shlomif@cpan.org">shlomif@cpan.org</a></span><br/>
</div>
</div>
<div id="content">
<div class="sect1">
<h2 id="pressing">Pressing</h2>
<div class="sectionbody">
</div>
</div>
<div class="sect1">
<h2 id="non_pressing">Non-pressing</h2>
<div class="sectionbody">
<div class="ulist">
<ul>
<li>
<p>Write a better initial board/initial layout validation code for the online
solver (at least initially]):</p>
<div class="ulist">
<ul>
<li>
<p>Exact number of playstacks. (requires introspection).</p>
</li>
<li>
<p>Number of Freecells not exceeded. (requires introspection).</p>
</li>
<li>
<p>missing/extra cards.</p>
</li>
<li>
<p>whitespace gaps.</p>
</li>
<li>
<p>invalid characters.</p>
</li>
<li>
<p>misformatting of the format.</p>
</li>
</ul>
</div>
</li>
<li>
<p>Find how well the solver performs with different permutations of the
order of columns/freecells.</p>
<div class="ulist">
<ul>
<li>
<p>See if it’s possible to combine several scans on such different
permutations.</p>
</li>
</ul>
</div>
</li>
<li>
<p>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.</p>
</li>
<li>
<p>Write the split-dbm-solver which stores the results on the disk for every
non-reversible-moves offset, and fully-connected-components.</p>
</li>
<li>
<p>Refer to <code>expand-solitaire-multi-card-moves</code> from the fc-solve process.</p>
</li>
<li>
<p>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.</p>
<div class="ulist">
<ul>
<li>
<p>Create a GUI version.</p>
</li>
</ul>
</div>
</li>
<li>
<p>If <code>-opt</code> 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.</p>
<div class="ulist">
<ul>
<li>
<p>Not sure about it.</p>
</li>
</ul>
</div>
</li>
<li>
<p>Implement more of Kevin Atkinson’s Common Lisp solver’s atomic move types,
and try to construct good heuristics out of them.</p>
</li>
<li>
<p>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.</p>
</li>
<li>
<p>PySolFC Deal No. 48007594292403677907 :</p>
</li>
</ul>
</div>
<div class="listingblock">
<div class="content">
<pre>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</pre>
</div>
</div>
<div class="listingblock">
<div class="content">
<pre>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</pre>
</div>
</div>
<div class="paragraph">
<p>However this scan generates takes too much time for most boards (over 100K
iterations).</p>
</div>
<div class="ulist">
<ul>
<li>
<p>PySolFC deal No. 03620802041832966472:</p>
</li>
</ul>
</div>
<div class="listingblock">
<div class="content">
<pre>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</pre>
</div>
</div>
<div class="ulist">
<ul>
<li>
<p>I solved it at length 87.</p>
<div class="ulist">
<ul>
<li>
<p>PySolFC deal No. 54369539487824719321:</p>
</li>
</ul>
</div>
</li>
</ul>
</div>
<div class="listingblock">
<div class="content">
<pre>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</pre>
</div>
</div>
<div class="ulist">
<ul>
<li>
<p>Shlomi Fish solved it in under 110 moves.</p>
<div class="ulist">
<ul>
<li>
<p>PySolFC deal 96166640969002647853:</p>
</li>
</ul>
</div>
</li>
</ul>
</div>
<div class="listingblock">
<div class="content">
<pre>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</pre>
</div>
</div>
<div class="ulist">
<ul>
<li>
<p>Shlomi Fish solved it in 77 moves.</p>
<div class="ulist">
<ul>
<li>
<p>PySolFC deal 26892246862786948900:</p>
</li>
</ul>
</div>
</li>
</ul>
</div>
<div class="listingblock">
<div class="content">
<pre>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</pre>
</div>
</div>
<div class="ulist">
<ul>
<li>
<p>Shlomi Fish solved it in 92 moves.</p>
<div class="ulist">
<ul>
<li>
<p>Add the new Freecell Solver-compatible game variants of PySolFC.</p>
</li>
<li>
<p>Convert magic rank constants such as 1 or 13 to FCS_MAX_RANK and
FCS_RANK_ACE/etc.</p>
</li>
<li>
<p>Investigate:</p>
</li>
</ul>
</div>
</li>
</ul>
</div>
<div class="listingblock">
<div class="content">
<pre>$ 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</pre>
</div>
</div>
<div class="ulist">
<ul>
<li>
<p>Consider adding the <code>restrict</code> keyword:</p>
<div class="ulist">
<ul>
<li>
<p><a href="http://stackoverflow.com/questions/776283/what-does-the-restrict-keyword-mean-in-c" class="bare">http://stackoverflow.com/questions/776283/what-does-the-restrict-keyword-mean-in-c</a></p>
</li>
<li>
<p><a href="https://duckduckgo.com/?q=restrict+keyword+c&ia=web" class="bare">https://duckduckgo.com/?q=restrict+keyword+c&ia=web</a></p>
</li>
</ul>
</div>
</li>
</ul>
</div>
</div>
</div>
<div class="sect1">
<h2 id="long_term">Long-term</h2>
<div class="sectionbody">
<div class="ulist">
<ul>
<li>
<p>Integrate the patsolve’s prioritization and mixed BFS/DFS scan.</p>
</li>
<li>
<p>Update the architecture document.</p>
</li>
<li>
<p>Make a super-strict parsable-output without all the quirks of
-p -t (see Games-Solitaire-Verify for why).</p>
<div class="ulist">
<ul>
<li>
<p>Perhaps see: <a href="https://groups.yahoo.com/neo/groups/fc-solve-discuss/conversations/topics/1264" class="bare">https://groups.yahoo.com/neo/groups/fc-solve-discuss/conversations/topics/1264</a> .</p>
</li>
</ul>
</div>
</li>
<li>
<p>Write a multi-threaded version.</p>
</li>
<li>
<p>Add a switch to ask the user if he wants to continue and enter a bigger
iterations limit.</p>
</li>
<li>
<p>Check for unmalloced data and if so gracefully exit.</p>
</li>
<li>
<p>Experiment with a delta-based state storage.</p>
<div class="ulist">
<ul>
<li>
<p>see delta_states_debondt.c - port it to the main libfreecell-solver.</p>
</li>
<li>
<p>see: <a href="http://fc-solve.shlomifish.org/to-do.html#orig_calc_states" class="bare">http://fc-solve.shlomifish.org/to-do.html#orig_calc_states</a> .</p>
</li>
</ul>
</div>
</li>
<li>
<p>Adapt the scans based on the parameters of the initial board.</p>
<div class="ulist">
<ul>
<li>
<p>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:</p>
<div class="olist arabic">
<ol class="arabic">
<li>
<p>Calculate the initial parameters on startup.</p>
</li>
<li>
<p>See what would be a good meta-scan based on them.</p>
</li>
<li>
<p>Use it.</p>
</li>
</ol>
</div>
</li>
</ul>
</div>
</li>
<li>
<p>Unit-test <code>fc_solve_compare_lru_cache_keys</code> in <code>scans.c</code>.</p>
</li>
<li>
<p>Interactive mode? Continue a scan that reached its limit.</p>
</li>
<li>
<p>Adapt <code>-dto2</code> to other parameters aside from depth, such as
total-number-of-cards-in-the-foundations or maximal foundation value.</p>
</li>
<li>
<p>Set up a <code>-dto2</code> like scheme for <code>--method a-star</code> where we change the tests
order based on the depth/etc.</p>
</li>
<li>
<p>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).</p>
</li>
</ul>
</div>
</div>
</div>
<div class="sect1">
<h2 id="to_be_considered">To be considered</h2>
<div class="sectionbody">
<div class="ulist">
<ul>
<li>
<p>Make the code <a href="https://sourceforge.net/projects/splint/">splint</a>-clean.</p>
</li>
<li>
<p>Write a multi-process client/server program.</p>
</li>
</ul>
</div>
</div>
</div>
</div>
<div id="footer">
<div id="footer-text">
Last updated 2018-09-05 14:19:07 IDT
</div>
</div>
</body>
</html>
|
