diff options
| author | Sebastiano Tronto <sebastiano@tronto.net> | 2024-12-07 16:38:40 +0100 |
|---|---|---|
| committer | Sebastiano Tronto <sebastiano@tronto.net> | 2024-12-07 16:38:40 +0100 |
| commit | 9ac266c76f39620d8343e46ca41cb09d1534384c (patch) | |
| tree | 823bd419d99fe0f00e6b5b713237a73b4ec7ffca /src/solvers/h48/stats.h | |
| parent | ea25a7ccad625c4e664dfd114147971b8a2677f3 (diff) | |
| download | nissy-core-9ac266c76f39620d8343e46ca41cb09d1534384c.tar.gz nissy-core-9ac266c76f39620d8343e46ca41cb09d1534384c.zip | |
Merge the "solver-experiments" branch that I have been working on for
a few weeks. This include mainly three things:
1. Various tweaks for a total performance gain of around 30%.
2. Take into account symmetries and avoid repeated work. This
required a re-work of the splitting into tasks before the solve.
3. Add a second fallback table (eoesep). This gives huge performance
gains for particular scrambles (e.g. superflip).
After merging this commit, remove and re-generate all pruning tables.
Squashed commit of the following:
commit 60f0705d2d69050e6a30581a2810f686d6f69b80
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sat Dec 7 16:06:48 2024 +0100
Fix indentation
commit cc5d489a251812b6188c0ba264ac6cb2236f1afe
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sat Dec 7 15:56:19 2024 +0100
Updated documentation
commit a3f605dd628546e52564f82b139feb473b0725f3
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sat Dec 7 14:01:11 2024 +0100
use eoesep table as second fallback
commit c75e43c9116c64f97e92b0fe038be8a032925a72
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri Dec 6 16:13:23 2024 +0100
First commit for gendata_eoesep
commit fea7688ab8bdc5ae0c3480622e2510a3bcd39248
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Dec 3 17:31:00 2024 +0100
Add scramble to tool
commit 66866cb71dea4ca8278ecb9e90ff4295771feb42
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Dec 3 17:22:59 2024 +0100
Added tool to check multiple solutions
commit ef65611c772c3996bddca8d181da3538e0af1674
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Dec 3 17:16:20 2024 +0100
Write all solutions for symmetric positions
commit e3ded26db7d7d4ae7c0e2488151ed14f581f7b8e
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Nov 26 09:14:54 2024 +0100
Added symmetry filter (TODO: print excluded solutions)
commit 864c437a9751c58d58562650ca9eba4a9e6ad3eb
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon Nov 25 14:51:13 2024 +0100
Improved task split
commit b88926d36d7ab0c64c5fe3bb954fd15d41267fba
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri Nov 22 19:06:41 2024 +0100
Reworked tasks for multi-threading in view of symmetry filter
commit 26fa653f97df8cd601aecb80eaf89f0a00e9ba9f
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Thu Oct 31 15:37:43 2024 +0100
Added transform move
commit 19f655ef94d658eaa2fefb5cea3c167a3ec58db6
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Thu Oct 31 09:29:15 2024 +0100
Clarified doc
commit 3b0fe1e5ef8b628854e30f0f0067300e2763c954
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Thu Oct 31 08:36:58 2024 +0100
Handle solved cube correctly
commit 57705cbc4982e3abe97a36ed64871738d4f721c0
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Thu Oct 31 08:24:30 2024 +0100
Close file
commit fc7d462b58bcf3d3a3fbf26c1f3bd04c640a4898
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Oct 29 15:05:48 2024 +0100
Removed stats tool
commit 359bf7cb49ef405ee76ed662207d47cb2abcc5a9
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Oct 29 15:01:51 2024 +0100
Updated theory doc
commit 39c315af562bc4ce896f41004388a4c34d475d37
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Oct 29 14:51:40 2024 +0100
Remove unused constants
commit 57a5d24538aa59a4df9221dad2f99e9f0286bd9d
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue Oct 29 10:20:38 2024 +0100
Add tool to solve scrambles from file
commit 07e2918c216636891b1fa6adecc9756086a901e9
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon Oct 28 17:00:00 2024 +0100
Add make table to tool
commit f5e5266c654eb027a5a35c57cc618555246f5e5e
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon Oct 28 09:35:49 2024 +0100
Remove old solver, other small things
commit a1ec78025b7959dbb845213f7f4e6851ecebc204
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sun Oct 27 02:00:29 2024 +0200
Improvements
commit 8eea23dbe888d923e662e24ae969130e2c67b999
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sat Oct 26 12:24:19 2024 +0200
Makefile fix
commit 3fc3927beacc78971cefeb42da8d71fe6c015fc1
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri Oct 25 18:25:09 2024 +0200
More performance gains
commit 7b4efa1f9af9722de1ab9ccfc27899825a0d12c4
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri Oct 25 15:53:20 2024 +0200
Alternative solver implementation, small performance gain
Diffstat (limited to 'src/solvers/h48/stats.h')
| -rw-r--r-- | src/solvers/h48/stats.h | 100 |
1 files changed, 0 insertions, 100 deletions
diff --git a/src/solvers/h48/stats.h b/src/solvers/h48/stats.h deleted file mode 100644 index 2a7e887..0000000 --- a/src/solvers/h48/stats.h +++ /dev/null | |||
| @@ -1,100 +0,0 @@ | |||
| 1 | /* | ||
| 2 | The h48stats solver computes how many moves it takes to solve to | ||
| 3 | each of the 12 h48 coordinates, one for each value of h from 0 to 11. | ||
| 4 | The solutions array is filled with the length of the solutions. The | ||
| 5 | solutions array is therefore not a printable string. | ||
| 6 | */ | ||
| 7 | |||
| 8 | typedef struct { | ||
| 9 | cube_t cube; | ||
| 10 | int8_t nmoves; | ||
| 11 | int8_t depth; | ||
| 12 | uint8_t moves[MAXLEN]; | ||
| 13 | const uint32_t *cocsepdata; | ||
| 14 | const uint8_t *h48data; | ||
| 15 | char *s; | ||
| 16 | } dfsarg_solveh48stats_t; | ||
| 17 | |||
| 18 | STATIC int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *); | ||
| 19 | STATIC int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]); | ||
| 20 | |||
| 21 | STATIC int64_t | ||
| 22 | solve_h48stats_dfs(dfsarg_solveh48stats_t *arg) | ||
| 23 | { | ||
| 24 | const int64_t limit = 11; | ||
| 25 | |||
| 26 | int8_t bound, u; | ||
| 27 | uint8_t m; | ||
| 28 | uint32_t d; | ||
| 29 | int64_t coord, h; | ||
| 30 | dfsarg_solveh48stats_t nextarg; | ||
| 31 | |||
| 32 | /* Check cocsep lower bound (corners only) */ | ||
| 33 | bound = get_h48_cdata(arg->cube, arg->cocsepdata, &d); | ||
| 34 | if (bound + arg->nmoves > arg->depth) | ||
| 35 | return 0; | ||
| 36 | |||
| 37 | /* Check h48 lower bound for h=0 (esep, but no eo) */ | ||
| 38 | coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 0); | ||
| 39 | bound = get_h48_pval(arg->h48data, coord, 4); | ||
| 40 | if (bound + arg->nmoves > arg->depth) | ||
| 41 | return 0; | ||
| 42 | |||
| 43 | /* Update all other values, if solved */ | ||
| 44 | coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 11); | ||
| 45 | for (h = 0; h <= limit; h++) { | ||
| 46 | u = coord >> (11-h) == 0 && arg->s[h] == 99; | ||
| 47 | arg->s[h] = u * arg->nmoves + (1-u) * arg->s[h]; | ||
| 48 | } | ||
| 49 | |||
| 50 | if (arg->s[limit] != 99) | ||
| 51 | return 0; | ||
| 52 | |||
| 53 | nextarg = *arg; | ||
| 54 | nextarg.nmoves = arg->nmoves + 1; | ||
| 55 | for (m = 0; m < 18; m++) { | ||
| 56 | nextarg.moves[arg->nmoves] = m; | ||
| 57 | if (!allowednextmove(nextarg.moves, nextarg.nmoves)) { | ||
| 58 | /* If a move is not allowed, neither are its 180 | ||
| 59 | * and 270 degree variations */ | ||
| 60 | m += 2; | ||
| 61 | continue; | ||
| 62 | } | ||
| 63 | nextarg.cube = move(arg->cube, m); | ||
| 64 | solve_h48stats_dfs(&nextarg); | ||
| 65 | } | ||
| 66 | |||
| 67 | return 0; | ||
| 68 | } | ||
| 69 | |||
| 70 | STATIC int64_t | ||
| 71 | solve_h48stats( | ||
| 72 | cube_t cube, | ||
| 73 | int8_t maxmoves, | ||
| 74 | const void *data, | ||
| 75 | char solutions[static 12] | ||
| 76 | ) | ||
| 77 | { | ||
| 78 | int i; | ||
| 79 | dfsarg_solveh48stats_t arg; | ||
| 80 | |||
| 81 | arg = (dfsarg_solveh48stats_t) { | ||
| 82 | .cube = cube, | ||
| 83 | .cocsepdata = (uint32_t *)((char *)data + INFOSIZE), | ||
| 84 | .h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE, | ||
| 85 | .s = solutions | ||
| 86 | }; | ||
| 87 | |||
| 88 | for (i = 0; i < 12; i++) | ||
| 89 | solutions[i] = (char)99; | ||
| 90 | |||
| 91 | for (arg.depth = 0; | ||
| 92 | arg.depth <= maxmoves && solutions[11] == 99; | ||
| 93 | arg.depth++) | ||
| 94 | { | ||
| 95 | arg.nmoves = 0; | ||
| 96 | solve_h48stats_dfs(&arg); | ||
| 97 | } | ||
| 98 | |||
| 99 | return 0; | ||
| 100 | } | ||
