SokoSolve Update: 2020-12

Covid-lockdown #2 has given me the time and motivation to get SokoSolve into a stable place; enough to write-up the project and possibility make a explanitory video.

Some serious bugs: fixes 😅

  • Incorrect Fwd <-> Rev node chains
  • Incorrect Rev root/starting positions
  • Rev chains may be found that leave the player on the wrong side, is not in a valid ending position and should be correctly discarded

Improvements & Optimisations:

  • local-locking Binary Search Tree (based on hash)
  • Much improved hash function. From ~50% hash (over 1min), to ~30%, then to 1%!
  • Strategy Pattern for Topology (Pool:Eval, Queue:UnEval; Pool:Eval+UnEval)

Next Steps:

Comparitive Testing: Same Machine, different OS/Framework

  • bramble 'AMD Ryzen Threadripper 2950X 16-Core Processor'
    • OS:Unix5.4.0.59 dotnet:3.1.10 Threads:32 x64 RELEASE
      9,047,563 nodes at 50,099/s in 3 min
    • OS:WIN6.2.9200.0 dotnet:3.1.10 Threads:32 x64 RELEASE
      10,966,852 nodes at 60,564/s in 3 min, 1 sec
    • OS:Unix5.4.0.59 dotnet:5.0.1 Threads:32 x64 RELEASE
      9,581,726 nodes at 53,151/s in 3 min
    • OS:WIN10.0.19042.0 dotnet:5.0.1 Threads:32 x64 RELEASE
      11,328,789 nodes at 62,569/s in 3 min, 1 sec
  • WILLOW 'Intel(R) Core(TM) i7-3930K CPU @ 3.20GHz'
    • OS:WIN10.0.19042.0 dotnet:5.0.1 Threads:12 x64 RELEASE
      11,727,506 nodes at 64,679/s in 3 min, 1 sec
    • OS:WIN10.0.19042.0 dotnet:5.0.1 Threads:12 x64 RELEASE
      12,349,921 nodes at 68,080/s in 3 min, 1 sec

After the better hash function:

Computer: GUYZEN 'AMD Ryzen Threadripper 2950X 16-Core Processor' OS:WIN6.2.9200.0 dotnet:3.1.11 Threads:32 x64 RELEASE
 Version: '[DIRTY] 9f29c79 MAJOR BUG: Alt Tree not used in multi solver -- Fixed, rev:465' at 2021-01-13 14:13:26Z, v3.4.1
| Solver | Pool      | Puzzle | State    | Solutions | Statistics                                    |
|--------|-----------|--------|----------|-----------|------------------------------------------------|
| fr!    | bb:bst:lt | SQ1~P5 | Continue |           |  29,122,591 nodes at 160,785/s in 3 min, 1 sec |

Computer: GUYZEN 'AMD Ryzen Threadripper 2950X 16-Core Processor' OS:WIN10.0.19042.0 dotnet:5.0.2 Threads:32 x64 RELEASE
| Solver | Pool      | Puzzle | State    | Solutions | Statistics                              |
|--------|-----------|--------|----------|-----------|-----------------------------------------|
| fr!    | bb:bst:lt | SQ1~P5 | Continue |           |  29,778,162 nodes at 164,595/s in 3 min |

Q: Why is a 6 core faster than a 16 core cpu?

All tests passing, but I have some suspicions

Seems all solutions are found im under 6sec, and NO solution greater than 500K nodes -- 1mil .. 80mil nodes (7sec .. 30min) no solutions; that is very suspicious!

https://github.com/guylangston/SokoSolve/issues/2

Computer: WILLOW 'Intel(R) Core(TM) i7-3930K CPU @ 3.20GHz' OS:WIN10.0.19042.0 dotnet:5.0.1 Threads:12 x64 RELEASE
 Version: '[DIRTY] acdefcb Fixed null, rev:360' at 2020-12-10 16:17:56Z, v3.4.0
    Args: SQ1 --solver fr! --pool lock:bst:lt --min 30
  Report: C:\repo\SokoSolve\src\SokoSolve.Console\results\benchmark--2020-12-10T10-44-31.txt
| Solver | Pool        | Puzzle  | State    | Solutions | Statistics                                      |
|--------|-------------|---------|----------|-----------|-------------------------------------------------|
| fr!    | lock:bst:lt | SQ1~P1  | Solution | 2         |       1,434 nodes at   1,373/s in 1.0 sec       |
| fr!    | lock:bst:lt | SQ1~P3  | Solution | 2         |         624 nodes at     611/s in 1.0 sec       |
| fr!    | lock:bst:lt | SQ1~P17 | Solution | 10        |      21,931 nodes at  21,701/s in 1.0 sec       |
| fr!    | lock:bst:lt | SQ1~P27 | Solution | 2         |       2,647 nodes at   2,602/s in 1.0 sec       |
| fr!    | lock:bst:lt | SQ1~P21 | Solution | 7         |      52,012 nodes at  51,261/s in 1.0 sec       |
| fr!    | lock:bst:lt | SQ1~P13 | Solution | 2         |     346,066 nodes at  68,087/s in 5 sec         |
| fr!    | lock:bst:lt | SQ1~P29 | Solution | 4         |     232,582 nodes at  76,052/s in 3 sec         |
| fr!    | lock:bst:lt | SQ1~P15 | Solution | 4         |      12,200 nodes at  11,973/s in 1.0 sec       |
| fr!    | lock:bst:lt | SQ1~P41 | TimeOut  |           |  84,144,365 nodes at  46,743/s in 30 min        |
| fr!    | lock:bst:lt | SQ1~P43 | TimeOut  |           |  63,171,399 nodes at  35,075/s in 30 min, 1 sec |
| fr!    | lock:bst:lt | SQ1~P97 | TimeOut  |           |  65,874,387 nodes at  36,569/s in 30 min, 1 sec |
| fr!    | lock:bst:lt | SQ1~P39 | Solution | 3         |     535,305 nodes at  87,331/s in 6 sec         |
| fr!    | lock:bst:lt | SQ1~P7  | TimeOut  |           |  66,768,437 nodes at  37,055/s in 30 min, 1 sec |
| fr!    | lock:bst:lt | SQ1~P37 | TimeOut  |           |  80,509,972 nodes at  44,694/s in 30 min, 1 sec |
| fr!    | lock:bst:lt | SQ1~P25 | TimeOut  |           |  61,594,840 nodes at  34,193/s in 30 min, 1 sec |
| fr!    | lock:bst:lt | SQ1~P5  | TimeOut  |           |  67,556,406 nodes at  37,497/s in 30 min, 1 sec |
| fr!    | lock:bst:lt | SQ1~P19 | TimeOut  |           |  62,915,521 nodes at  34,920/s in 30 min, 1 sec |
| fr!    | lock:bst:lt | SQ1~P31 | TimeOut  |           |  60,322,430 nodes at  33,489/s in 30 min, 1 sec |
| fr!    | lock:bst:lt | SQ1~P51 | TimeOut  |           |  66,744,860 nodes at  37,047/s in 30 min, 1 sec |
| fr!    | lock:bst:lt | SQ1~P53 | TimeOut  |           |  70,927,680 nodes at  39,380/s in 30 min, 1 sec |

Next Steps

  • False Solution Counts in statistic (Warnings)
  • Console Reports to include solutions path
  • Track vs known solution