domino14 / macondo

A crossword board game AI, written in Go
https://domino14.github.io/macondo
GNU General Public License v3.0
48 stars 10 forks source link

endgame doesn't always give a sequence with one single tile left #283

Closed domino14 closed 1 year ago

domino14 commented 1 year ago

we already know the PV gets swallowed up partially, but with one tile left and lazysmp on, sometimes sequences get swallowed up:

macondo> load cgp 11CHOW/5J4GAED1/4VaQUEROS3/3OOBIT3I3/4U4GIN3/4L1P1EE1OI2/4UNEYED2N2/s4AEON3CAZ/I4ID5L1E/R4V5KO1R/R3BI1FUGLES1D/A2FAS5ME1A/HM1LET1TWERPS2/1A1A3I3T3/OATY3X7 N/ 324/399 0 lex CSW21; ld english; tmr 253401/1000;

macondo> endgame -plies 5 -threads 4

{"level":"info","num-elems":134217728,"desired-num-elems":134217728,"estimated-total-memory-bytes":2147483648,"reset":true,"time":"2023-08-26T22:15:11-04:00","message":"transposition-table-size"}
{"level":"info","threads":4,"time":"2023-08-26T22:15:11-04:00","message":"using-lazy-smp"}
{"level":"info","plies":2,"time":"2023-08-26T22:15:11-04:00","message":"deepening-iteratively"}
{"level":"info","spread":-63,"ply":2,"pv":"PV; val 12; 1:  5D N. (4); ","time":"2023-08-26T22:15:11-04:00","message":"best-val"}
{"level":"info","plies":3,"time":"2023-08-26T22:15:11-04:00","message":"deepening-iteratively"}
{"level":"info","spread":-63,"ply":3,"pv":"PV; val 12; 1:  5D N. (4); ","time":"2023-08-26T22:15:11-04:00","message":"best-val"}
{"level":"info","plies":4,"time":"2023-08-26T22:15:11-04:00","message":"deepening-iteratively"}
{"level":"info","spread":-63,"ply":4,"pv":"PV; val 0; ","time":"2023-08-26T22:15:11-04:00","message":"best-val"}
{"level":"info","plies":5,"time":"2023-08-26T22:15:11-04:00","message":"deepening-iteratively"}
{"level":"info","spread":-63,"ply":5,"pv":"PV; val 0; ","time":"2023-08-26T22:15:11-04:00","message":"best-val"}
{"level":"info","ttable-created":11,"ttable-lookups":94,"ttable-hits":14,"ttable-t2collisions":0,"time-elapsed-sec":0.54339125,"time":"2023-08-26T22:15:11-04:00","message":"solve-returning"}
Best sequence has a spread difference of 12
Final spread after seq: -63
Best sequence:

macondo>

Note the final sequence is empty, and so is the sequence after 4 plies (although the spread is still correct).

domino14 commented 1 year ago

this happens in prod sometimes, but since the lambda panics it succeeds on one of the 3 retries afterwards

domino14 commented 1 year ago

This only seems to happen in multi-threaded mode.

domino14 commented 1 year ago

very likely seems to just be the transposition table lookup succeeding on the first try and the PV doesn't get updated.

domino14 commented 1 year ago

https://github.com/domino14/macondo/blob/master/endgame/negamax/solver.go#L551-L569

other threads can update the TT before the main thread does (since the other threads can look a level or two deeper and thus ttEntry.depth() >= uint8(depth) can be true. The negamax function would return immediately with the score but not the PV.