Futility Pruning for Alpha-Beta

[RedBedHed]

Hello there!

I've decided to take a break from bandit algorithms and focus solely on developing a deeper alpha-beta search. I've been doing a lot of reading, and I've managed to implement a basic iterative-deepening search. It is a fail-soft negamax with a transposition table, PV-move, mvv-lva, killers, history, quiescence, null-move pruning, PVS, etc. It is single-threaded. It uses the Pesto tables. It reaches about depth of 15 in five seconds on my laptop, and it can draw with Zeta-dva.

I am now trying to implement futility pruning. But I don't know if I am doing it right. I currently evaluate the board first and then iterate through the moves. I search the first move (possibly the PV move) and all of the attacks. Then, if the current side isn't in check, the current move doesn't give check, and the evaluation plus a constant is less than alpha, I skip searching the move.

Does that sound right? Or am I misunderstanding?

[hgm]

Well, you should only do that at if the remaining depth is small enough usually depth <= 1). And captures can be futile as well, if currentEval + capturedMaterial + constant is less than alpha.

[RedBedHed]

Well, you should only do that at if the remaining depth is small enough usually depth <= 1). And captures can be futile as well, if currentEval + capturedMaterial + constant is less than alpha.

Oh whoops, I forgot to add that I'm only doing it on the second to last ply. Thank you for this info about the captures! I'll try it out!