From 9ac266c76f39620d8343e46ca41cb09d1534384c Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sat, 7 Dec 2024 16:38:40 +0100 Subject: 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 Date: Sat Dec 7 16:06:48 2024 +0100 Fix indentation commit cc5d489a251812b6188c0ba264ac6cb2236f1afe Author: Sebastiano Tronto Date: Sat Dec 7 15:56:19 2024 +0100 Updated documentation commit a3f605dd628546e52564f82b139feb473b0725f3 Author: Sebastiano Tronto Date: Sat Dec 7 14:01:11 2024 +0100 use eoesep table as second fallback commit c75e43c9116c64f97e92b0fe038be8a032925a72 Author: Sebastiano Tronto Date: Fri Dec 6 16:13:23 2024 +0100 First commit for gendata_eoesep commit fea7688ab8bdc5ae0c3480622e2510a3bcd39248 Author: Sebastiano Tronto Date: Tue Dec 3 17:31:00 2024 +0100 Add scramble to tool commit 66866cb71dea4ca8278ecb9e90ff4295771feb42 Author: Sebastiano Tronto Date: Tue Dec 3 17:22:59 2024 +0100 Added tool to check multiple solutions commit ef65611c772c3996bddca8d181da3538e0af1674 Author: Sebastiano Tronto Date: Tue Dec 3 17:16:20 2024 +0100 Write all solutions for symmetric positions commit e3ded26db7d7d4ae7c0e2488151ed14f581f7b8e Author: Sebastiano Tronto Date: Tue Nov 26 09:14:54 2024 +0100 Added symmetry filter (TODO: print excluded solutions) commit 864c437a9751c58d58562650ca9eba4a9e6ad3eb Author: Sebastiano Tronto Date: Mon Nov 25 14:51:13 2024 +0100 Improved task split commit b88926d36d7ab0c64c5fe3bb954fd15d41267fba Author: Sebastiano Tronto Date: Fri Nov 22 19:06:41 2024 +0100 Reworked tasks for multi-threading in view of symmetry filter commit 26fa653f97df8cd601aecb80eaf89f0a00e9ba9f Author: Sebastiano Tronto Date: Thu Oct 31 15:37:43 2024 +0100 Added transform move commit 19f655ef94d658eaa2fefb5cea3c167a3ec58db6 Author: Sebastiano Tronto Date: Thu Oct 31 09:29:15 2024 +0100 Clarified doc commit 3b0fe1e5ef8b628854e30f0f0067300e2763c954 Author: Sebastiano Tronto Date: Thu Oct 31 08:36:58 2024 +0100 Handle solved cube correctly commit 57705cbc4982e3abe97a36ed64871738d4f721c0 Author: Sebastiano Tronto Date: Thu Oct 31 08:24:30 2024 +0100 Close file commit fc7d462b58bcf3d3a3fbf26c1f3bd04c640a4898 Author: Sebastiano Tronto Date: Tue Oct 29 15:05:48 2024 +0100 Removed stats tool commit 359bf7cb49ef405ee76ed662207d47cb2abcc5a9 Author: Sebastiano Tronto Date: Tue Oct 29 15:01:51 2024 +0100 Updated theory doc commit 39c315af562bc4ce896f41004388a4c34d475d37 Author: Sebastiano Tronto Date: Tue Oct 29 14:51:40 2024 +0100 Remove unused constants commit 57a5d24538aa59a4df9221dad2f99e9f0286bd9d Author: Sebastiano Tronto Date: Tue Oct 29 10:20:38 2024 +0100 Add tool to solve scrambles from file commit 07e2918c216636891b1fa6adecc9756086a901e9 Author: Sebastiano Tronto Date: Mon Oct 28 17:00:00 2024 +0100 Add make table to tool commit f5e5266c654eb027a5a35c57cc618555246f5e5e Author: Sebastiano Tronto Date: Mon Oct 28 09:35:49 2024 +0100 Remove old solver, other small things commit a1ec78025b7959dbb845213f7f4e6851ecebc204 Author: Sebastiano Tronto Date: Sun Oct 27 02:00:29 2024 +0200 Improvements commit 8eea23dbe888d923e662e24ae969130e2c67b999 Author: Sebastiano Tronto Date: Sat Oct 26 12:24:19 2024 +0200 Makefile fix commit 3fc3927beacc78971cefeb42da8d71fe6c015fc1 Author: Sebastiano Tronto Date: Fri Oct 25 18:25:09 2024 +0200 More performance gains commit 7b4efa1f9af9722de1ab9ccfc27899825a0d12c4 Author: Sebastiano Tronto Date: Fri Oct 25 15:53:20 2024 +0200 Alternative solver implementation, small performance gain --- src/solvers/h48/gendata_eoesep.h | 274 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 274 insertions(+) create mode 100644 src/solvers/h48/gendata_eoesep.h (limited to 'src/solvers/h48/gendata_eoesep.h') diff --git a/src/solvers/h48/gendata_eoesep.h b/src/solvers/h48/gendata_eoesep.h new file mode 100644 index 0000000..d3b73ea --- /dev/null +++ b/src/solvers/h48/gendata_eoesep.h @@ -0,0 +1,274 @@ +STATIC int64_t coord_eoesep_sym(cube_t, const uint32_t [static ESEP_MAX]); +STATIC size_t gendata_esep_classes( + uint32_t [static ESEP_MAX], uint16_t [static ESEP_CLASSES]); +STATIC size_t gendata_eoesep(char [static EOESEP_FULLSIZE], uint8_t); +STATIC uint32_t gendata_eoesep_bfs(uint8_t, uint8_t [static EOESEP_BUF], + uint32_t [static ESEP_MAX], uint16_t [static ESEP_CLASSES]); +STATIC uint32_t gendata_eoesep_fromnew(uint8_t, uint8_t [static EOESEP_BUF], + uint32_t [static ESEP_MAX], uint16_t [static ESEP_CLASSES]); +STATIC uint32_t gendata_eoesep_fromdone(uint8_t, uint8_t [static EOESEP_BUF], + uint32_t [static ESEP_MAX], uint16_t [static ESEP_CLASSES]); +STATIC uint32_t gendata_eoesep_marksim(int64_t, uint8_t, + uint8_t [static EOESEP_BUF], uint32_t [static ESEP_MAX]); +STATIC bool gendata_eoesep_next(cube_t, uint8_t, + uint8_t [static EOESEP_BUF], uint32_t [static ESEP_MAX]); +STATIC uint8_t get_eoesep_pval(const uint8_t *, int64_t); +STATIC uint8_t get_eoesep_pval_cube(const void *, cube_t); +STATIC void set_eoesep_pval(uint8_t *, int64_t, uint8_t); + +STATIC int64_t +coord_eoesep_sym(cube_t c, const uint32_t esep_classes[static ESEP_MAX]) +{ + uint8_t ttrep; + uint32_t edata, class; + int64_t esep, eo; + + esep = coord_esep(c); + edata = esep_classes[esep]; + class = ECLASS(edata); + ttrep = TTREP(edata); + eo = coord_eo(transform(c, ttrep)); + + return (class << UINT32_C(11)) + eo; +} + +STATIC size_t +gendata_esep_classes( + uint32_t esep_classes[static ESEP_MAX], + uint16_t rep[static ESEP_CLASSES] +) +{ + bool visited[ESEP_MAX]; + uint8_t t; + uint32_t class, cl, ti; + int64_t i, j; + cube_t c; + + memset(visited, 0, ESEP_MAX * sizeof(bool)); + class = 0; + for (i = 0; i < ESEP_MAX; i++) { + if (visited[i]) + continue; + c = invcoord_esep(i); + for (t = 0; t < 48; t++) { + j = coord_esep(transform(c, t)); + cl = class << UINT32_C(16); + ti = inverse_trans(t) << UINT32_C(8); + esep_classes[j] = cl | ti; + visited[j] = true; + } + rep[class] = i; + class++; + } + + return class; +} + +STATIC size_t +gendata_eoesep(char buf[static EOESEP_FULLSIZE], uint8_t maxdepth) +{ + uint8_t *buf8, d; + uint16_t rep[ESEP_CLASSES]; + uint32_t *esep_classes, done, level; + int64_t coord; + tableinfo_t info; + + if (buf == NULL) + goto gendata_eoesep_return_size; + + LOG("Computing eoesep data\n"); + memset(buf, 0xFF, EOESEP_FULLSIZE); + esep_classes = (uint32_t *)(buf + INFOSIZE); + buf8 = (uint8_t *)(buf + INFOSIZE + 4*ESEP_MAX); + gendata_esep_classes(esep_classes, rep); + + info = (tableinfo_t) { + .solver = "eoesep data for h48", + .type = TABLETYPE_SPECIAL, + .infosize = INFOSIZE, + .fullsize = EOESEP_FULLSIZE, + .hash = 0, + .entries = EOESEP_TABLESIZE, + .classes = ESEP_CLASSES, + .bits = 4, + .base = 0, + .maxvalue = 11, + .next = 0 + }; + + coord = 0; /* Assumed coordinate of solved cube */ + set_eoesep_pval(buf8, coord, 0); + done = 1; + info.distribution[0] = 1; + for (d = 1; d <= maxdepth && done < EOESEP_TABLESIZE; d++) { + level = gendata_eoesep_bfs(d, buf8, esep_classes, rep); + done += level; + info.distribution[d] = level; + } + + writetableinfo(&info, EOESEP_FULLSIZE, buf); + + LOG("eoesep data computed\n"); + +gendata_eoesep_return_size: + return EOESEP_FULLSIZE; +} + +STATIC uint32_t +gendata_eoesep_bfs( + uint8_t d, + uint8_t buf8[EOESEP_BUF], + uint32_t esep_classes[static ESEP_MAX], + uint16_t rep[static ESEP_CLASSES] +) +{ + if (d < 9) + return gendata_eoesep_fromdone(d, buf8, esep_classes, rep); + else + return gendata_eoesep_fromnew(d, buf8, esep_classes, rep); +} + +STATIC uint32_t +gendata_eoesep_fromdone( + uint8_t d, + uint8_t buf8[EOESEP_BUF], + uint32_t esep_classes[static ESEP_MAX], + uint16_t rep[static ESEP_CLASSES] +) +{ + uint8_t pval; + int64_t i, esep, eo, coord, done; + + done = 0; + for (i = 0; i < (int64_t)ESEP_CLASSES; i++) { + esep = rep[i]; + for (eo = 0; eo < POW_2_11; eo++) { + coord = (i << INT64_C(11)) + eo; + pval = get_eoesep_pval(buf8, coord); + if (pval != d-1) + continue; + + coord = (esep << INT64_C(11)) + eo; + done += gendata_eoesep_marksim( + coord, d, buf8, esep_classes); + } + } + + return done; +} + +STATIC uint32_t +gendata_eoesep_fromnew( + uint8_t d, + uint8_t buf8[EOESEP_BUF], + uint32_t esep_classes[static ESEP_MAX], + uint16_t rep[static ESEP_CLASSES] +) +{ + uint8_t pval; + int64_t i, esep, eo, coord, done; + cube_t c; + + done = 0; + for (i = 0; i < (int64_t)ESEP_CLASSES; i++) { + esep = rep[i]; + for (eo = 0; eo < POW_2_11; eo++) { + coord = (i << INT64_C(11)) + eo; + pval = get_eoesep_pval(buf8, coord); + if (pval != 15) + continue; + + c = invcoord_eoesep((esep << INT64_C(11)) + eo); + if (gendata_eoesep_next(c, d, buf8, esep_classes)) { + set_eoesep_pval(buf8, coord, d); + done++; + } + } + } + + return done; +} + +STATIC uint32_t +gendata_eoesep_marksim( + int64_t i, + uint8_t d, + uint8_t buf8[static EOESEP_BUF], + uint32_t esep_classes[static ESEP_MAX] +) +{ + uint8_t t, m, pval; + cube_t c, moved, transformed; + uint32_t done; + int64_t coord; + + done = 0; + c = invcoord_eoesep(i); + for (m = 0; m < 18; m++) { + moved = move(c, m); + for (t = 0; t < 48; t++) { + transformed = transform(moved, t); + coord = coord_eoesep_sym(transformed, esep_classes); + pval = get_eoesep_pval(buf8, coord); + if (pval > d) { + set_eoesep_pval(buf8, coord, d); + done++; + } + } + } + + return done; +} + +STATIC bool +gendata_eoesep_next( + cube_t c, + uint8_t d, + uint8_t buf8[static EOESEP_BUF], + uint32_t esep_classes[static ESEP_MAX] +) +{ + uint8_t m, t, pval; + int64_t coord; + cube_t moved, transformed; + + for (t = 0; t < 48; t++) { + transformed = transform(c, t); + for (m = 0; m < 18; m++) { + moved = move(transformed, m); + coord = coord_eoesep_sym(moved, esep_classes); + pval = get_eoesep_pval(buf8, coord); + if (pval == d-1) + return true; + } + } + + return false; +} + +STATIC uint8_t +get_eoesep_pval(const uint8_t *table, int64_t i) +{ + return (table[EOESEP_INDEX(i)] & EOESEP_MASK(i)) >> EOESEP_SHIFT(i); +} + +STATIC uint8_t +get_eoesep_pval_cube(const void *data, cube_t c) +{ + int64_t coord; + const uint8_t *table; + const uint32_t *esep_classes; + + esep_classes = (const uint32_t *)data; + table = (const uint8_t *)data + 4*ESEP_MAX; + coord = coord_eoesep_sym(c, esep_classes); + + return get_eoesep_pval(table, coord); +} + +STATIC void +set_eoesep_pval(uint8_t *table, int64_t i, uint8_t val) +{ + table[EOESEP_INDEX(i)] = (table[EOESEP_INDEX(i)] & (~EOESEP_MASK(i))) + | (val << EOESEP_SHIFT(i)); +} -- cgit v1.3