miguel-ambrona / D3-Chess

Chess Unwinnability Analyzer is an implementation of a decision procedure for checking whether there exists a sequence of legal moves that allows a certain player to checkmate their opponent in a given chess position.
https://chasolver.org
GNU General Public License v3.0
51 stars 8 forks source link

Nodes count in full algorithm #14

Closed dlbbld closed 2 years ago

dlbbld commented 2 years ago

"cnt" below is the node count. So the "increase cnt" in the helpmate algorithm should be at the beginning to also include the nodes positively evaluated in steps 1 and 2 (where it matters for step 2). The code is including these nodes (not counting the first node thus).

1: if the intended winner is checkmating their opponent in pos then return true 2: if the intended winner has just the king or the position is unwinnable according to Lemma 5 or Lemma 6 or the position is stalemate or the intended winner is receiving checkmate in the position then return false 3: increase cnt and set d := maxDepth − depth 4: if cnt > nodesBound _ d < 0 then return false

miguel-ambrona commented 2 years ago

Thanks for the suggestion, I updated the PDF.

dlbbld commented 2 years ago

My suggestion is correct but not my proposed realization. Now the nodes count also counts the cached nodes. For me, the below order looks fine.

Actually now the insufficient material positions (line 3) do not end up in the transposition table. Performance-wise that might not harm much, but when already having such an advanced table, I think it is better to include it.

2: if the intended winner is checkmating their opponent in pos then return true 4: set d := maxDepth − depth 6: if (pos, D) ∈ table with D ≥ d then return false . pos was already analyzed 1: increase cnt 5: if cnt > nodesBound ∨ d < 0 then return false . The search limits are exceeded 7: store (pos, d) in table 3: if the intended winner has just the king or the position is unwinnable according to Lemma 5 or Lemma 6 or the position is stalemate or the intended winner is receiving checkmate in the position then return false