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_h48.h | 62 ++++++++++++++++++++++++++++++++----------- 1 file changed, 46 insertions(+), 16 deletions(-) (limited to 'src/solvers/h48/gendata_h48.h') diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h index 55c4f34..ae0b732 100644 --- a/src/solvers/h48/gendata_h48.h +++ b/src/solvers/h48/gendata_h48.h @@ -61,13 +61,13 @@ gendata_h48short(gendata_h48short_arg_t *arg) return arg->map->n; } -/* Generic function that dispatches to the data generators */ STATIC int64_t gendata_h48(gendata_h48_arg_t *arg) { - uint64_t size, cocsepsize, h48size, fallbacksize; + uint64_t size, cocsepsize, h48size, fallbacksize, fallback2size, of; + long long r; void *cocsepdata_offset; - tableinfo_t cocsepinfo, h48info; + tableinfo_t cocsepinfo, h48info, fallbackinfo; gendata_h48_arg_t arg_h0k4; if (arg == NULL) { @@ -78,7 +78,8 @@ gendata_h48(gendata_h48_arg_t *arg) cocsepsize = COCSEP_FULLSIZE; h48size = INFOSIZE + H48_TABLESIZE(arg->h, arg->k); fallbacksize = arg->k == 2 ? INFOSIZE + H48_TABLESIZE(0, 4) : 0; - size = cocsepsize + h48size + fallbacksize; + fallback2size = EOESEP_FULLSIZE; + size = cocsepsize + h48size + fallbacksize + fallback2size; if (arg->buf == NULL) return size; /* Dry-run */ @@ -110,18 +111,22 @@ gendata_h48(gendata_h48_arg_t *arg) return NISSY_ERROR_INVALID_SOLVER; } - if (readtableinfo(arg->buf_size, arg->buf, &cocsepinfo) != NISSY_OK) { + r = readtableinfo(arg->buf_size, arg->buf, &cocsepinfo); + if (r != NISSY_OK) { LOG("gendata_h48: could not read info for cocsep table\n"); return NISSY_ERROR_UNKNOWN; } cocsepinfo.next = cocsepsize; - if (writetableinfo(&cocsepinfo, arg->buf_size, arg->buf) != NISSY_OK) { + r = writetableinfo(&cocsepinfo, arg->buf_size, arg->buf); + if (r != NISSY_OK) { LOG("gendata_h48: could not write info for cocsep table" " with updated 'next' value\n"); return NISSY_ERROR_UNKNOWN; } + /* Add h0k4 fallback table */ + if (arg->k == 2) { arg_h0k4 = *arg; arg_h0k4.h = 0; @@ -134,16 +139,42 @@ gendata_h48(gendata_h48_arg_t *arg) gendata_h48h0k4(&arg_h0k4); - if (readtableinfo_n(arg->buf_size, arg->buf, 2, &h48info) - != NISSY_OK) { - LOG("gendata_h48: could not read info for h48 table\n"); + } + + /* Add eoesep fallback table */ + + gendata_eoesep((char *)arg->buf + (size - fallback2size), 20); + + /* Update tableinfo with correct next values */ + + r = readtableinfo_n(arg->buf_size, arg->buf, 2, &h48info); + if (r != NISSY_OK) { + LOG("gendata_h48: could not read info for h48 table\n"); + return NISSY_ERROR_UNKNOWN; + } + h48info.next = h48size; + r = writetableinfo(&h48info, + arg->buf_size - cocsepsize, (char *)arg->buf + cocsepsize); + if (r != NISSY_OK) { + LOG("gendata_h48: could not write info for h48 table\n"); + return NISSY_ERROR_UNKNOWN; + } + + if (arg->k == 2) { + r = readtableinfo_n(arg->buf_size, arg->buf, 3, &fallbackinfo); + if (r != NISSY_OK) { + LOG("gendata_h48: could not read info for h48 " + "fallback table\n"); return NISSY_ERROR_UNKNOWN; } - h48info.next = h48size; - if (writetableinfo(&h48info, arg->buf_size - cocsepsize, - (char *)arg->buf + cocsepsize) != NISSY_OK) { - LOG("gendata_h48: could not write info for h48 table\n"); + of = cocsepsize + h48size; + fallbackinfo.next = fallbacksize; + r = writetableinfo(&fallbackinfo, + arg->buf_size - of, (char *)arg->buf + of); + if (r != NISSY_OK) { + LOG("gendata_h48: could not write info for h48 " + "fallback table\n"); return NISSY_ERROR_UNKNOWN; } } @@ -302,9 +333,8 @@ gendata_h48k2(gendata_h48_arg_t *arg) * * The following values for the base have been hand-picked. I first * performed some statistics on the frequency of these values, but - * they turned out to be unreliable. I have not figured out why yet. - * In the end I resorted to generating the same table with multiple - * base value and see what was best. + * they turned out to be unreliable. In the end I generated the same + * table with multiple base value and see what was best. * * A curious case is h3, which has this distribution for base 8: * [0] = 6686828 -- cgit v1.3