Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

twsearch cannot find optimal solution for some specific positions. #110

Open
coldsun0630 opened this issue Feb 3, 2025 · 2 comments
Open

Comments

@coldsun0630
Copy link

File 1. "FTO-test_puzzle.tws"

Name FTO-test_puzzle

Set CORN 6 2
Set EDGE 12 1
Set TRIA 12 1
Set TRIB 12 1

Solved
CORN
1 2 3 4 5 6
0 0 0 0 0 0
EDGE
1 2 3 4 5 6 7 8 9 10 11 12
TRIA
1 2 3 4 5 6 7 8 9 10 11 12
TRIB
1 2 3 4 5 6 7 8 9 10 11 12
End

Move R
CORN
1 3 5 4 2 6
0 0 1 0 1 0
EDGE
1 2 3 6 4 5 7 8 9 10 11 12
TRIA
1 7 8 4 5 6 12 10 9 3 11 2
TRIB
1 2 3 6 4 5 7 8 9 10 11 12
End

File 2. "FTO-test_pos.scr"

Scramble FTO-test_pos
CORN
1 3 5 4 2 6
0 0 1 0 1 0
EDGE
1 2 3 6 4 5 7 8 9 10 11 12
TRIA
1 7 8 4 5 6 12 10 9 3 11 2
TRIB
1 2 3 6 4 5 7 8 9 10 11 12
End

File 3. "FTO-test_scr.scr"

ScrambleAlg FTO-test_scr
   R
End

==========

Log 1. Solving a scramble algorithm "R"

DESKTOP% ./build/bin/twsearch -M 49152 -t 14 --mindepth 1 --maxdepth 3 --alloptimal "samples/main/FTO-test_puzzle.tws" "samples/main/FTO-test_scr.scr"
# This is twsearch v0.6.6-264-gff84160 (C) 2022 Tomas Rokicki.
# ./build/bin/twsearch -M 49152 -t 14 --mindepth 1 --maxdepth 3 --alloptimal samples/main/FTO-test_puzzle.tws samples/main/FTO-test_scr.scr
Created new moves R'
State size is about 1.58261 x 10^29 log2 96.9982
Requiring 152 bits 20 bytes per entry; 20 from identity.
Found 2 canonical move states.
Calculated canonical states in 0.00203609
For memsize 51539607552 bytesize 51539607552 subshift 2 memshift 26 shardshift 32
Trying to allocate 51539607616
Initializing memory in 0.00166297
Filling depth 0 val 0 saw 1 (1) in 0.000237942 rate 0.00420271
Filling depth 1 val 0 saw 2 (2) in 0.000139952 rate 0.0142906
Filling depth 2 val 0 saw 0 (0) in 0.000115156 rate 0
Filling depth 3 val 0 saw 0 (0) in 0.000110865 rate 0
Solving FTO-test_scr
 R'
Found 1 solution max depth 1 probes 4 nodes 3 in 2.81334e-05 rate 0.14218
Twsearch finished.

Log 2. Solving a position equivalent to "R"

DESKTOP% ./build/bin/twsearch -M 49152 -t 14 --mindepth 1 --maxdepth 3 --alloptimal "samples/main/FTO-test_puzzle.tws" "samples/main/FTO-test_pos.scr"
# This is twsearch v0.6.6-264-gff84160 (C) 2022 Tomas Rokicki.
# ./build/bin/twsearch -M 49152 -t 14 --mindepth 1 --maxdepth 3 --alloptimal samples/main/FTO-test_puzzle.tws samples/main/FTO-test_pos.scr
Created new moves R'
State size is about 1.58261 x 10^29 log2 96.9982
Requiring 152 bits 20 bytes per entry; 20 from identity.
Found 2 canonical move states.
Calculated canonical states in 0.000946999
For memsize 51539607552 bytesize 51539607552 subshift 2 memshift 26 shardshift 32
Trying to allocate 51539607616
Initializing memory in 0.000812054
Filling depth 0 val 0 saw 1 (1) in 0.000231028 rate 0.00432849
Filling depth 1 val 0 saw 2 (2) in 0.000151873 rate 0.0131689
Filling depth 2 val 0 saw 0 (0) in 0.000128984 rate 0
Filling depth 3 val 0 saw 0 (0) in 0.000118017 rate 0
Solving FTO-test_pos
No solution found in 0
Twsearch finished.

==========

This doesn't happen and outputs as expected, when the move (which both in .tws and .scr file) contains no orientations, like:

Move F
CORN
1 2 4 5 3 6
0 0 0 0 0 0
EDGE
1 10 3 4 5 2 7 8 9 6 11 12
TRIA
1 2 3 4 5 6 9 7 8 10 11 12
TRIB
1 10 11 3 5 2 7 8 9 6 4 12
End

==========

Just in case, here are the exact files I've used. (The 3 files above are zipped into "FTO-test.zip"):
https://mega.nz/file/hUsFTAxB#YZn29-wJJfVdOInztp7zTxjIGA06A4lWqtFUkTETE6U

@coldsun0630
Copy link
Author

I found this also happens for non-1-move positions. For example:

For this .scr, twsearch succeeds to find 2 solutions in total ("U d'", "d' U"):

Scramble FTO-Uv_pos
CORN
3 1 2 5 6 4
0 0 0 1 0 1
EDGE
4 5 6 7 8 9 1 2 3 11 12 10
TRIA
3 1 2 7 8 9 10 11 12 4 5 6
TRIB
4 5 6 7 8 9 1 2 3 11 12 10
End

But for this .scr, twsearch fails to find any ≤3 moves solution:

Scramble FTO-Rv_pos
CORN
4 3 5 6 2 1
1 0 1 0 1 1
EDGE
10 11 12 6 4 5 2 3 1 9 7 8
TRIA
9 7 8 5 6 4 12 10 11 3 1 2
TRIB
10 11 12 6 4 5 2 3 1 9 7 8
End

@coldsun0630 coldsun0630 changed the title twsearch cannot find 1 move solution when the move contains orientation definition. twsearch cannot find optimal solution when a Move contains orientation vectors. Feb 3, 2025
@coldsun0630 coldsun0630 changed the title twsearch cannot find optimal solution when a Move contains orientation vectors. twsearch cannot find optimal solution for some specific positions. Feb 3, 2025
@coldsun0630
Copy link
Author

I have to note that the Move d (in that custom def) also contains orientation vectors:

Move d
CORN
1 2 3 6 4 5
0 0 0 1 0 1
EDGE
1 8 9 4 2 3 7 5 6 12 10 11
TRIA
1 2 3 10 11 12 4 5 6 7 8 9
TRIB
1 2 9 4 5 3 7 8 6 12 10 11
End

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant