I have been trying to implement Futility pruning (FP) for some time now and have not had much success. I have read almost every post linked on CPW for this subject. I have tried all kinds of variations but when my base engine plays the one with FP, the FP version loses. However, when I compare test searches, the FP version seems better.
A simple background: I use negamax with PVS, null move pruning (no mate threat detection but think I need it), transposition table, and a lot of move ordering tuning.
After various observations of "bad games", I have come to this process which seems to have the least negative impact:
Code: Select all
move Search(board, depth, ply, alpha, beta, state)
(1) … check TT, broken rules, if horizon, perform null move
(2) Flag the node:
if(!inPVNode && !inCheck && !SearchingNullMove && abs(alpha) < MATE-MIN && MyPieceScore > RookValue && depth <=2)
s_eval = evaluate(board)
futileflag = (s_eval + futilemargine[depth] < alpha)
(3) Play out the moves
while(move=getnextmove)
if(futileflag && movesmade > 4 && !move.Checking && !move.Capture && !move.SpecialPawn && !move.Hash
continue; // Skip the move
score = play(move)
*NOTE*
MyPieceScore does not account for pawns, it is the value of all pieces for the side to move.
Also, evaluate is the full evaluation which I have nothing special:
PSQ, mobility, basic pawn structure, and king safety.
* Around 90% of the different positions get to the same depth but FP gets there faster as nodes played decreases. It looks to be around 20% faster.
* Around 5% of these positions, FP gets to one additional ply.
* The rest of the searches, FP still reaches the same depth but a bit slower.
I have tested adjusting the margins and even flagged more moves as not futile. I am under the assumption if this was implemented correctly then I should reach an additional ply on most positions (which I am not). If I over adjust then I just lose speed and in some cases, I lose a ply.
To debug this, instead of pruning the move, I let it play and if the returned score beat alpha, I logged the position with all the values.
Here's a position reached:
[d]4nrk1/2p2p1p/r1p1b1pQ/3pP3/3R4/P1q5/1P3PPP/5RK1 w - - 0 3
Here's the data:
Depth: 2 PLY: 6
Move: d4h4 - Rh4 Flagged: History Move
S_Eval: -576
Margin: 650
Alpha: 382
Score: 390
MoveNumber: 23 (*This is a late move)
As you can see, this silent move would have been pruned but leads to a big swing in score. If the engine could only reach one more ply then it would find this move at depth 3. But, what I have seen is IF the search can reach one more ply and find a late move like this then the search seems to explode a bit and the branching factor increases.
The only thing I could think of to do here was to validate any move before pruning it. So, I perform a QSearch and if that score does not beat alpha then prune it. With this in play, the engine is slightly faster, still does not reach an additional ply, but when playing the base version in games, the FP engine is seriously winning. Interesting, WAC 300 tests are losing by about 30 positions with this flavor of FP.
Here is my dilemma: What I am doing with this qsearch seems more like a reduction than pruning. I'd like to get the natural pruning to work but am not sure what I am doing wrong. Can anyone shed some light on this?
Thank you for the help