Determine optimal mastermind plays for different permutations of the rules.
This program determines how to optimally play a game of mastermind with n pegs in m colors, supplied by the user at the command line. It aims to do so without the aid of heuristics (a la Knuth), just because it is fun. We may add a mode which uses heuristics at some point in the future, however.
The current draft recursively expands trees based on sets of possible guesses and possible answers. Subsequent guesses partition remaining answers into bins keyed by reponse code. Expansion stops when all possible guesses are differentiated into singleton bins by a sequence of guesses. Expanded subtrees are compared and optimal trees (by depth) are kept. The best tree is printed.
The fun of this project is tuning the codebase, so below we discuss how we collect and analyze performance data and what measured changes we have made so far (all of which are tagged in git).
I originally generated "flamegraphs" [1] with Brendan Gregg’s toolchain [2]. Now I prefer to analyze perf data with hotspot [3].
Benchmark tests are defined using the #[bench] nightly feature. We build, run,
and analyze performance using the followng commands:
cargo clean
cargo bench --no-run
perf record --call-graph dwarf target/release/deps/mastermind-xyz --bench (1)
hotspot perf.data-
We can pass the name of a specific bench after the
--benchargument as well.
Each tagged performance improvement is described below by a table of performance benchmarks. "Test m^n" stands for a benchmark to exhaustively identify the optimal mastermind tree of base m and length n (i.e. n pegs from any of m colors, of which there are m^n.)
Performance gains are expressed as approximate percentage reduction in runtime. For example, a change of 95% means a 95% reduction in runtime, i.e. the new algorithm only takes 5% as long to complete as the old algorithm.
When there are only one or two remaining answers, prefer to guess only possible answers. This is optimal (the best worst-case scenario is two turns regardless of whether or not we guess an answer) and avoids the pathological case in which we try each of k guesses to determine the same outcome.
Test m^n |
Performance |
Change |
2^2 |
12,933 ns/iter (+/- 916) |
49% |
2^3 |
64,545 ns/iter (+/- 3,135) |
79% |
2^4 |
799,883 ns/iter (+/- 148,205) |
88% |
3^2 |
68,336 ns/iter (+/- 1,908) |
83% |
3^3 |
1,432,072 ns/iter (+/- 182,251) |
96% |
3^4 |
71,018,895 ns/iter (+/- 39,357,840) |
N/A |
4^2 |
352,357 ns/iter (+/- 13,255) |
87% |
4^3 |
32,575,069 ns/iter (+/- 18,852,419) |
N/A |
5^2 |
2,278,674 ns/iter (+/- 424,985) |
83% |
Eagerly abort evaluation of a tree if any subtree (generated by any answers-by-response group) is ranked such that the tree cannot beat the rank of the most-optimal tree found so far. This eliminates a substantial amount of waste work for larger problem sets.
Test m^n |
Performance |
Change |
2^2 |
25,386 ns/iter (+/- 938) |
21% |
2^3 |
306,947 ns/iter (+/- 27,659) |
95% |
2^4 |
6,426,608 ns/iter (+/- 2,405,029) |
N/A |
3^2 |
402,708 ns/iter (+/- 69,932) |
98% |
3^3 |
32,683,944 ns/iter (+/- 5,904,345) |
N/A |
4^2 |
2,678,412 ns/iter (+/- 242,848) |
N/A |
5^2 |
13,092,134 ns/iter (+/- 4,523,319) |
N/A |
Do not evaluate a RefTree if the guess code from which it is generated produces an answers-by-response mapping that is isomorphic to one already evaluated. This eliminates a great deal of memory management, esp. for larger problem sets, by pruning candidates across all levels of evaluation.
Test m^n |
Performance |
Change |
2^2 |
32,075 ns/iter (+/- 2,274) |
37% |
2^3 |
6,251,130 ns/iter (+/- 197,441) |
94% |
3^2 |
19,498,657 ns/iter (+/- 738,756) |
N/A |
Eliminate unecessary data cloning by sharing immutable references to Code instances.
Test m^n |
Performance |
Change |
2^2 |
51,308 ns/iter (+/- 5,124) |
26% |
2^3 |
104,537,830 ns/iter (+/- 1,638,485) |
N/A |