-
Notifications
You must be signed in to change notification settings - Fork 0
/
TODO
143 lines (131 loc) · 7.19 KB
/
TODO
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
Release Criteria for Version 1.1 (Apr 2012)
---------------------------------------------
Scope:
This release includes executables and user documentation. It does not
include the book.
Functionality:
Enable codemaker (mmserve), codebreaker (mmbreak), and debugger (mmdebug).
These tools should link statically to the Mastermind library.
Add user documentation for each of these utilities.
Add a few less-important heuristics for testing purpose.
Able to output strategy in Knuth, Irving, Enhanced, or XML format.
Able to read strategy in Irving, Knuth, or Enhanced format.
Able to diff two strategies read from files.
Add a replay strategy.
Add more commands to the debugger and add documentation for it.
Fix various bugs and hacks in the source code to prepare for future
releases.
Optimization:
Add various minor optimizations to improve speed.
Investigate the fact that -po yields a very close optimal strategy as
no -po. This means there can be large room of improvement.
Portability:
The cmake build system should work correctly on both Windows and Linux.
Distribution:
The source code is distributed under MIT Licence in .zip format.
Under Windows, pre-built binaries shoudld be provided for 32-bit and 64-bit.
Plan for Version 1.2 (May 2012):
Add -md switch to control the maximum depth constraint.
Find optimal strategy for MinDepth objective.
Find optimal strategy for MinWorst objective.
Improve lower bound estimate in the first few levels of the game.
Improve lower bound estimate when there are only a dozen remaining possibilites.
OpenMP support for optimal strategies.
Able to read strategy in Irving, Knuth, Enhanced, or XML format.
Plan for Version 1.3 (Jun 2012):
Complete the book.
Add support for rule variants (static, dynamic, head-to-head, etc.)
Plan for Version 2.0:
Qt or Java GUI. (mmstratx)
High Priority
---------------
If the client program does not control omp(), the library will by default use
4 threads. This is not desirable and we should add an initialization function
to be called by the client.
Find an icon for the project.
Implement -md switch for optimal strategy.
Move certain static variables into a CPP file to simplify the code.
Implement Irving notation reading and auto-complete
Simplify the Irving notation to adopt Knuth's notation for less-obvious guess.
Move the functionality of ObviousStrategy to a free-standing function.
Add a free-standing function to automatically fill a strategy-tree.
In simple_tree, check for the level of inserted node, and implement logic if
the node being inserted is not the last one of its level.
Add call counter to check how often is the first guess tried not the best guess
in an optimal strategy search level. A good lower bound estimate should
cause the first guess to be an optimal guess.
In recursive optimal search, the minus sign doesn't work except for MinSteps
objective.
Medium Priority
-----------------
Does it make sense to 'bootstrap' a good tree before depth-first-search for
an optimal tree from a given state?
Separate mastermind library and front-end utilities. Ensure binary compat.
It is probably better to change types to unsigned where possible, because
this tends to reduce redundant MOVSX instructions.
In optimal code breaker, when we rank the candidate guesses, we needn't compute
a full cost estimate; instead, we could just compute 'steps', and visit the
candidates by that score. This should reduce cost computation time, and
hopefully doesn't impact the visiting order too negatively.
Fix the optimization routine to respect -md switch
Try minimize the number of secrets revealed in a worst number of steps
Improve optimal strategy subject to maximum number of steps
Improve lower bound estimate
Improve simd_t related code (use slice more consistently)
MinimizeWorstCase heuristic needs more comparison when the first compare equal
Investigate why multi-threading doesn't benefit any more... maybe we should
move multithreading to another part? Like for heuristic strategies, to the
partition part? For optimal strategies, i don't know
Simplify fill_obvious_strategy_tree to only add a simple guess instead of
expanding the whole optimal tree redundantly.
Low Priority
--------------
Add a simple GUI for displaying/comparing strategies
Add a dynamic_tree implementation with the same interface as simple_tree.
This helps to find a common interface for the client code. Then we can
compare the performance by using either tree as underlying storage.
Try optimize color equivalence and constraint equivalence code (which combined
account for 20% of runtime)
Try to understand why changing the data type of StrategyTree::TDepth from
int or size_t to char or short degrades performance by 5-7%? This is
really weird. If this is so, are there other places that we might actually
improve the performance by using a native type? [e.g. frequency counting]
Improve 32-bit performance
Finished
----------
[done] Add test script to test command line switches.
[done] Add -po switch to enforce the "possibility only" constraint.
[done] Classify switch documentation according to type of strategy.
[done] Add -nc switch to specify "no correction" for heuristic strategies.
[done] Fix MSVC level 4 warnings and gcc pedantic warnings.
[done] Change Engine& to Engine* to prepare for future virtual interface.
[done] Write manual page in wiki markup and use a script to convert it.
[done] Import wiki as a subfolder and consolidate documentation into it.
[done] Improved Knuth's strategy to multi-level comparison.
[done] Added specialized comparison routine when one of the codewords being
compared contains no repeated colors. This is disabled by default.
[done] Apply constraint equivalence filter only once for each candidate guess.
[done] Add call counter to record the number of input and output of each
equivalence filters.
[done] Add -prof command switch to enable call counter profiling.
[done] Make the code compatible with the latest Intel C++ compiler.
[done] Optimized ColorEquivalenceFilter when there is only one excluded color.
[done] Investigate why GCC is slow; seems to be failing to automatically inline
a template function not explicitly marked as inline.
[done] Consolidates various constraints by the StrategyConstraint class
[done] Corrected Engine::compare() to enable return value optimization under VC.
[done] Output strategy tree in Irving notation
[done] Apply OpenMP at a higher level for heuristic strategies.
[done] Check vector::resize implementation
[done] Improve Feedback class implementation and documentation
[done] Reduce the size of FeedbackFrequencyTable to MaxOutcomes
[done] Refactor comparison routine to reduce code duplication
[done] Move benchmark tests to Benchmark.hpp
[done] Move HRTimer to hr_timer
[done] Move other utility routines under the util directory
[done] Write doxygen documentation for utility routines
[done] Write book to describe the data structure, algorith, etc.
Abandoned
-----------
[done] Check tree data structure to get a name for our strategy tree layout
[done] Optimize compare_tiny using 64-bit integer