Futility pruning idea

[maksimKorzh]

Hi Guys

I've been researching CPW for the last few days to make sure the idea I'd like to ask your opinion about is not present there (please correct me if I'm wrong!)

So the idea is to DROP moves scored as 0 (so I know for sure they are not PV/Captures/killers/history) when depth is greater than 3 (assuming IID implemented so PV/killer/history has been initialized).
Here's how I'm trying it now:

Code: Select all

    // loop over move list
    for (int count = 0; count < move_list->count; count++)
    {                                                                     
        // "Futility?" pruning
        if (depth > 3  && score_move(move_list->moves[0]) == 20000 && !score_move(move_list->moves[count]))
            continue;
    }

Now here're the results of this for "tricky position":
[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1

My move list after getting sorted:

Code: Select all

    // my idea is to drop moves starting from a2a4 and NOT MAKE/NOT EVALUATE them AT ALL
     move: e2a6   score: 20000
     move: f3f6   score: 10201
     move: d5e6   score: 10105
     move: g2h3   score: 10105
     move: e5g6   score: 10104
     move: e5d7   score: 10104
     move: e5f7   score: 10104
     move: f3h3   score: 10101
     move: f3h5   score: 6
     move: a2a4   score: 0
     move: e5c6   score: 0
     move: b2b3   score: 0
     move: e5c4   score: 0
     move: e5g4   score: 0
     move: e5d3   score: 0
     move: c3b5   score: 0
     move: c3a4   score: 0
     move: c3b1   score: 0
     move: c3d1   score: 0
     move: d2h6   score: 0
     move: d2g5   score: 0
     move: d2f4   score: 0
     move: d2e3   score: 0
     move: d2c1   score: 0
     move: g2g3   score: 0
     move: e2b5   score: 0
     move: e2c4   score: 0
     move: e2d3   score: 0
     move: e2d1   score: 0
     move: e2f1   score: 0
     move: a1b1   score: 0
     move: a1c1   score: 0
     move: a1d1   score: 0
     move: h1f1   score: 0
     move: h1g1   score: 0
     move: g2g4   score: 0
     move: f3f5   score: 0
     move: d5d6   score: 0
     move: f3f4   score: 0
     move: f3g4   score: 0
     move: f3d3   score: 0
     move: f3e3   score: 0
     move: f3g3   score: 0
     move: a2a3   score: 0
     move: e1g1   score: 0
     move: e1c1   score: 0
     move: e1d1   score: 0
     move: e1f1   score: 0

Code: Select all

// PRUNING
info score cp 30 depth 1 nodes 774 pv e2a6 b4c3 
info score cp 30 depth 2 nodes 2919 pv e2a6 b4c3 
info score cp 15 depth 3 nodes 13444 pv e2a6 b4c3 b2c3 e6d5 
info score cp 15 depth 4 nodes 37675 pv e2a6 b4c3 b2c3 e6d5 
info score cp 0 depth 5 nodes 143033 pv e2a6 e6d5 c3d5 b6d5 e4d5 e7e5 
bestmove e2a6

// NO PRUNING
info score cp 30 depth 1 nodes 774 pv e2a6 b4c3 
info score cp 30 depth 2 nodes 2919 pv e2a6 b4c3 
info score cp 15 depth 3 nodes 13444 pv e2a6 b4c3 b2c3 e6d5 
info score cp 15 depth 4 nodes 88274 pv e2a6 b4c3 b2c3 e6d5 
info score cp 0 depth 5 nodes 372537 pv e2a6 e6d5 c3d5 b6d5 e4d5 e7e5 
bestmove e2a6

VIsually when my engine plays vs itself at say depth 6 it makes almost the same moves.
But feel that something might be wrong with this approach because it's too easy.

Please tell me what do you think?
Did anybody apply this technique (maybe with some modifications) ?

THANKS IN ADVANCE!

[Kieren Pearson]

I'm assuming that PV gets assigned a score of 20000, captures a score of 10000 + captured piece value and then killers / history a small positive score.

After some thought, this seems like a psudo-implementation of LMR. Instead of searching with a reduced depth, you are completely cutting off if they are far enough down the move order, but we still search PV, captures, killers and history to full depth.

I would look into and implement LMR, which will be even better than this in actual games. If I understand the implementation, any of those quiet moves will NEVER be searched no matter the depth, which is a very big issue if one of those moves for example gave check and delivered checkmate and your engine missed that

[maksimKorzh]

I'm assuming that PV gets assigned a score of 20000, captures a score of 10000 + captured piece value and then killers / history a small positive score.

After some thought, this seems like a psudo-implementation of LMR. Instead of searching with a reduced depth, you are completely cutting off if they are far enough down the move order, but we still search PV, captures, killers and history to full depth.

I would look into and implement LMR, which will be even better than this in actual games. If I understand the implementation, any of those quiet moves will NEVER be searched no matter the depth, which is a very big issue if one of those moves for example gave check and delivered checkmate and your engine missed that

Hi Kieren

Yes, all of your assumptions are correct.
Could you please point out to LMR implementation (didactic one would be perfect)

[Kieren Pearson]

https://web.archive.org/web/20150212051 ... m/lmr.html

Not sure what didactic means but here you go

[maksimKorzh]

https://web.archive.org/web/20150212051 ... m/lmr.html

Not sure what didactic means but here you go

Just perfect! Exactly what I was looking for!
Thanks you so much, Kieren!

[hgm]

Does this work? It seems to me it should completely cripple the engine. It would be blind to any tactics deeper than 3 ply.

[maksimKorzh]

Does this work? It seems to me it should completely cripple the engine. It would be blind to any tactics deeper than 3 ply.

I've tested my engine vs TSCP with this weird idea and without.
The games are pretty similar (well my engine still getting mated due to the poor evaluation)
With this weird idea or without my engine is getting mated almost exactly the same
The only difference is that with this idea it plays 2 2.5 faster than TSCP at the same fixed depth
while without it takes about the same time for both engines to make a move.

I've already realized that this is a BAD idea. I'm now researching LMR.
While I love the idea (hemce this weird idea) still I'm encountering some issues with understanding the implementation.
Any additional help regarding how to implement LMR is appreciated.

[maksimKorzh]

OMG!

I've just implemented LMR:

Code: Select all

            // First move, use full-window search
            if(moves_searched == 0) 
            {                        
                // recursive negamax call
                score = -negamax(-beta, -alpha, depth - 1);
            }   
            // LMR
            else {   
                if (moves_searched >= full_depth_moves &&
                    depth >= reduction_limit &&
                    in_check == 0 &&
                    get_move_capture(move_list->moves[count]) == 0 &&
                    get_move_promoted(move_list->moves[count]) == 0
                   )
                {
                    // Search this move with reduced depth:
                    score = -negamax(- alpha - 1, -alpha, depth-2);
                }
                
                else score = alpha + 1;  // Hack to ensure that full-depth search is done
        

                if(score > alpha)
                {
                    score = -negamax(-alpha - 1, -alpha, depth-1);
                    
                    // research on fail    
                    if((score > alpha) && (score < beta))
                        score = -negamax(-beta, -alpha, depth-1);
                }      
            }

And now while my engine hits depth 7 in 2+0 blitz TSCP only goes depth 6
My engine has mated TSCP and the clock at the end of game is:
TSCP: 15 sec left
BBC(my engine): 56 sec left

AMAZING!
Thanks for providing an amazing resource so I could make use of it!!!


[pgn][Event "Computer chess game"]
[Site "maksim-Inspiron-3582"]
[Date "2020.09.09"]
[Round "?"]
[White "TSCP"]
[Black "BBC"]
[Result "0-1"]
[BlackElo "?"]
[ECO "B00"]
[Opening "Nimzowitsch Defence"]
[Time "21:41:36"]
[Variation "Bogoljubow, 3...Nf6"]
[WhiteElo "1650"]
[TimeControl "120+0"]
[Termination "normal"]
[PlyCount "134"]
[WhiteType "program"]
[BlackType "program"]

1. e4 Nc6 {(Nb8-c6 Ng1-f3 Ng8-f6 e4-e5 Nf6-d5 c2-c4 Nd5-f4) -0.10/7 0} 2.
Nc3 {(d2d4 e7e5 d4d5 c6e7 b1c3 g8f6) +0.22/6 3} Nf6 {(Ng8-f6 Ng1-f3 d7-d5
e4-e5 d5-d4 e5xf6 d4xc3) -0.10/7 0} 3. d4 {(d2d4 e7e6 c1g5 f8b4 g5f6 b4c3)
+0.31/6 3} d5 {(d7-d5 e4xd5 Nf6xd5 Nc3xd5 Qd8xd5 Ng1-f3 Bc8-f5) -0.10/7 0}
4. e5 {(f1b5 d8d7 e4e5 f6e4 c3e4 d5e4 b5c6 d7c6) +0.48/6 3} Ne4 {(Nf6-e4
Ng1-f3 Bc8-f5 Bf1-d3 Nc6-b4 O-O Nb4xd3 c2xd3) -0.10/7 2} 5. Nxe4 {(f1b5
e4c3 b5c6 b7c6 b2c3 e7e6 g1f3) +0.47/6 3} dxe4 {(d5xe4 Bc1-e3 f7-f6 f2-f3
Bc8-f5 f3xe4 Bf5xe4) -0.00/7 1} 6. Bb5 {(f1b5 c8d7 b5c6 d7c6 c1g5 c6d5)
+0.38/6 3} a6 {(a7-a6 Bb5xc6+ b7xc6 f2-f3 Bc8-f5 Bc1-f4 e7-e6 f3xe4 Bf5xe4)
+0.25/7 0} 7. Bxc6+ {(b5c6 b7c6 g1e2 c8g4 c1e3 a8b8 a1b1) +1.39/6 3} bxc6
{(b7xc6 f2-f3 Bc8-f5 f3xe4 Bf5xe4 Ng1-f3 e7-e6) +0.15/7 0} 8. Ne2 {(g1e2
c8g4 c1g5 d8b8 d1c1 e7e6) +1.14/6 3} f5 {(f7-f5 O-O e7-e6 Ne2-f4 Ke8-d7
Rf1-e1 Bc8-b7) +0.15/7 1} 9. Bg5 {(e1g1 e7e6 e2f4 e8f7 c1e3 f7g8) +1.54/6
3} Rb8 {(Ra8-b8 b2-b3 Bc8-b7 Ne2-f4 Ke8-f7 O-O Kf7-g8) +0.25/7 2} 10. b3
{(b2b3 h7h6 g5e3 e7e6 e1g1 f8e7) +1.36/6 3} Bb7 {(Bc8-b7 Ne2-f4 g7-g6
Nf4-e6 Qd8-c8 Ne6xf8 Ke8xf8) +0.20/7 0} 11. Nf4 {(e2f4 e8f7 e1g1 h7h6 d1h5
f7g8 f4g6) +1.45/6 2} Kf7 {(Ke8-f7 Qd1-h5+ Kf7-g8 O-O-O h7-h6 Bg5-h4 g7-g5)
+0.15/7 1} 12. O-O {(e1g1 h7h6 g5h4 g7g5 d1h5 f7g8 f4e6) +1.52/6 2} g6
{(g7-g6 e5-e6+ Kf7-g8 Qd1-d2 Bf8-g7 Ra1-d1 a6-a5 Qd2xa5 Bg7xd4 Bg5xe7
Bd4xf2+) +0.35/7 0} 13. c3 {(c2c3 h7h6 e5e6 f7g8 f4g6 h6g5 g6h8 g8h8)
+1.70/6 2} Bg7 {(Bf8-g7 e5-e6+ Kf7-g8 Rf1-e1 h7-h6 Bg5-h4 g6-g5) +0.40/7 0}
14. Qc1 {(d1e2 d8c8 f2f3 c6c5 e5e6) +1.88/5 2} Re8 {(Rh8-e8 Rf1-d1 Qd8-c8
e5-e6+ Kf7-g8 b3-b4 h7-h5) +0.55/7 1} 15. Ne2 {(f4e2 f7g8 e5e6 d8d6 e2f4
e8d8) +1.34/6 2} Kg8 {(Kf7-g8 Rf1-d1 Qd8-d7 Bg5-h6 Bg7xh6 Qc1xh6 Rb8-d8)
+0.75/7 1} 16. a3 {(a2a3 d8c8 c3c4 e7e6 g5f6 c8d7) +1.22/6 2} a5 {(a6-a5
b3-b4 a5xb4 a3xb4 Rb8-a8 Ne2-f4 Ra8xa1 Qc1xa1) +0.80/7 1} 17. c4 {(c3c4
c6c5 f1d1 c5d4 d1d4 d8c8) +1.26/6 2} c5 {(c6-c5 Rf1-d1 c5xd4 Ne2xd4 Qd8-c8
Bg5-f4 e7-e6) +0.75/7 1} 18. dxc5 {(f1d1 c5d4 d1d4 d8c8 g5f4 e7e6) +1.01/6
2} Qd3 {(Qd8-d3 Ne2-f4 Qd3xb3 Ra1-b1 Qb3-a2 e5-e6 a5-a4) +0.85/7 1} 19. Qb2
{(c1b2 b7a6 f1b1 a6c4 e2c1 d3f1) +0.99/6 2} Ba6 {(Bb7-a6 Qb2-a2 Bg7xe5
Ra1-b1 a5-a4 b3xa4 Rb8xb1 Rf1xb1 Ba6xc4) +1.00/7 3} 20. b4 {(e2c1 d3c4 f1d1
c4c5 g5f4) +0.25/5 2} Qxc4 {(Qd3xc4 Ne2-f4 Qc4xc5 Qb2-a2+ Qc5-c4 Rf1-c1
Qc4xa2 Ra1xa2) +1.75/7 3} 21. Nf4 {(e2f4 c4c5 b2a2 c5c4 f1c1 c4a2 a1a2 a5b4
a3b4) +0.02/6 2} Qxc5 {(Qc4xc5 Qb2-a2+ Qc5-c4 Rf1-c1 Qc4xa2 Ra1xa2 Bg7xe5
b4xa5) +1.75/7 1} 22. Qa2+ {(b2a2 c5c4 f1c1 c4a2 a1a2 h7h6 g5h4 a5b4 a3b4
g7e5 f4g6) -0.18/6 2} Qc4 {(Qc5-c4 Rf1-c1 Qc4xa2 Ra1xa2 Bg7xe5 b4xa5
Ba6-b7) +2.05/7 0} 23. Rfc1 {(f1c1 c4a2 a1a2 h7h6 g5e7 e8e7 f4g6) -0.40/7
1} Qxa2 {(Qc4xa2 Ra1xa2 h7-h6 Bg5-h4 g6-g5 b4-b5 Ba6xb5) +2.85/7 0} 24.
Rxa2 {(a1a2 h7h6 f4g6 h6g5 b4a5 b8b7 a3a4) -0.34/7 1} h6 {(h7-h6 Nf4xg6
h6xg5 Rc1xc7 Kg8-f7 Rc7-a7 Ba6-b7) +3.15/7 0} 25. Bh4 {(f4g6 h6g5 b4a5 g8f7
c1c6 e7e6) -0.60/6 1} g5 {(g6-g5 Nf4-e6 g5xh4 Ne6xg7 Kg8xg7 Rc1xc7 a5-a4)
+3.25/7 0} 26. Nd5 {(f4d5 g5h4 d5c7 e8c8 c1c5 a5b4 c7a6 c8c5 a6c5 b4a3 a2a3
g7e5) -1.19/6 1} gxh4 {(g5xh4 Nd5xc7 Re8-c8 Rc1-c5 Ba6-d3 b4xa5 Rb8-b1+)
+3.75/7 0} 27. bxa5 {(d5c7 e8c8 c1c5 a5b4 c7a6 c8c5 a6c5 b4a3 a2a3 g7e5)
-1.19/6 1} Bxe5 {(Bg7xe5 Ra2-c2 Ba6-d3 Rc2-c6 Be5-d6 a3-a4 Rb8-b2 Nd5xc7)
+4.80/7 1} 28. a4 {(a3a4 a6d3 a2d2 b8b7 f2f3 e7e6) -2.29/6 1} e6 {(e7-e6
Nd5-e3 Ba6-b7 Ra2-d2 Rb8-d8 Rc1-d1 Rd8xd2 Rd1xd2) +5.65/7 2} 29. Ne3 {(d5e3
c7c5 a2d2 e5d4 c1e1 a6d3) -2.81/6 1} Rbd8 {(Rb8-d8 g2-g3 h4xg3 h2xg3 Ba6-b7
Rc1-c5 Be5-d6) +5.65/7 1} 30. Rc6 {(c1c6 a6b7 c6c5 b7d5 a2d2 c7c6) -2.63/6
1} Bb7 {(Ba6-b7 Rc6-c5 Be5-d6 Rc5-b5 Bb7-a6 Rb5-b3 Bd6-e5) +5.75/7 1} 31.
Rc1 {(c6c1 b7d5 a2d2 h4h3 g2h3 c7c6) -2.65/6 1} c6 {(c7-c6 Ra2-e2 Be5-g7
Rc1-b1 Bb7-a6 Re2-c2 Ba6-d3) +5.85/7 2} 32. Rb1 {(c1b1 e8e7 a2c2 e5d4 b1d1
e7d7) -2.68/6 1} Re7 {(Re8-e7 Ra2-c2 Be5-g7 Rb1-e1 Rd8-d4 Ne3-c4 e6-e5)
+5.90/7 1} 33. Nc4 {(e3c4 e7d7 a2e2 d7d1 e2e1 d1e1 b1e1 e5d4) -2.82/6 1}
Bg7 {(Be5-g7 Rb1-e1 Rd8-d4 Ra2-c2 Re7-d7 f2-f4 Rd4-d1) +6.00/7 2} 34. Rc2
{(a2c2 c6c5 c4e3 g7d4 c2d2 e7d7) -2.86/6 1} c5 {(c6-c5 Nc4-b6 Re7-c7 Rb1-e1
h6-h5 f2-f4 Rd8-d4) +5.90/7 2} 35. Rcc1 {(c2c1 h4h3 g2h3 g7d4 b1b6 e7g7)
-2.93/6 1} f4 {(f5-f4 Rb1-b6 Bb7-d5 Rb6-d6 Rd8xd6 Nc4xd6 Re7-d7) +5.90/7 1}
36. Rb6 {(b1b6 e7d7 b6b1 g7d4 c4b6 d7d6) -3.00/6 1} Red7 {(Re7-d7 Nc4-d6
Bb7-a8 Nd6-c4 e6-e5 Rb6-e6 Ba8-d5) +6.05/7 1} 37. Rbb1 {(b6b1 g7d4 b1b3
b7c6 c4b6 d7d6) -3.05/6 1} Ba6 {(Bb7-a6 Nc4-b6 Rd7-c7 Rc1-e1 Rd8-d4 Rb1-d1
Ba6-b7) +5.85/7 1} 38. h3 {(h2h3 d7a7 c4b2 d8d2 b2d1 c5c4) -3.32/6 1} Rd3
{(Rd7-d3 Kg1-h2 Rd3-d4 Nc4-b6 Ba6-d3 Rb1-b3 c5-c4) +6.25/7 1} 39. Nb2
{(c4b2 d3d5 b2c4 e4e3 f2e3 a6c4 c1c4 f4e3 c4h4) -3.62/6 1} Rb3 {(Rd3-b3
Nb2-d1 Rb3-d3 Nd1-b2 Rd3-d2 Nb2-c4 Rd2-a2) +6.20/7 1} 40. Nd1 {(b2d1 c5c4
b1b3 c4b3 d1c3 b3b2) -3.46/6 1} Rxb1 {(Rb3xb1 Rc1xb1 Ba6-e2 Nd1-b2 Rd8-d2
f2-f3 Bg7xb2 f3xe4) +7.50/7 0} 41. Rxb1 {(c1b1 a6e2 d1e3 f4e3 f2e3 c5c4
a5a6) -4.96/7 1} Be2 {(Ba6-e2 Nd1-e3 f4xe3 f2xe3 Be2-d1 Rb1-c1 Rd8-d2
Rc1xc5 Bd1xa4) +7.90/7 0} 42. a6 {(a5a6 e2d1 a6a7 g7e5 a4a5 e4e3 g1h2)
-5.38/7 1} e3 {(e4-e3 f2xe3 Rd8xd1+ Rb1xd1 Be2xd1 e3xf4 Bd1xa4) +7.30/7 0}
43. a7 {(a6a7 g7e5 d1c3 e2h5 c3e4 h5g6 b1b8 d8b8 a7b8q e5b8 e4c5 e3f2 g1f2)
-3.15/7 0} Be5 {(Bg7-e5 Nd1-b2 Be5-c3 f2xe3 f4xe3 Kg1-h2 Rd8-d2) +5.80/7 0}
44. Nxe3 {(d1e3 f4e3 f2e3 c5c4 g1f2 e2d3) -3.88/6 0} fxe3 {(f4xe3 f2xe3
Be2-a6 a4-a5 c5-c4 Rb1-e1 Rd8-d2) +6.30/7 0} 45. fxe3 {(f2e3 e2a6 a4a5 d8a8
b1c1 a8a7 c1c5) -3.93/6 0} Ba6 {(Be2-a6 e3-e4 c5-c4 Kg1-h1 c4-c3 Rb1-e1
Rd8-d2) +6.40/7 0} 46. a5 {(a4a5 d8a8 b1b6 a8a7 b6e6 e5g7) -4.34/6 0} Bc7
{(Be5-c7 e3-e4 c5-c4 Rb1-a1 Rd8-a8 Ra1-e1 Ra8xa7) +6.75/7 0} 47. e4 {(e3e4
d8a8 b1b6 c7b6 a5b6 c5c4) -4.87/6 0} Ra8 {(Rd8-a8 Rb1-c1 Bc7-e5 g2-g3
Be5-d4+ Kg1-g2 h4xg3) +7.00/7 0} 48. Rb6 {(b1b6 c7b6 a5b6 a8f8 e4e5 c5c4
g1h2) -4.88/7 0} Bxb6 {(Bc7xb6 a5xb6 Ba6-b7 e4-e5 Ra8-d8 Kg1-f2 Rd8-d2+)
+7.95/7 0} 49. axb6 {(a5b6 a6b7 g1f2 b7e4 f2f1 a8f8 f1g1 e6e5 g1h2) -6.55/8
0} Bb7 {(Ba6-b7 Kg1-f2 Bb7xe4 g2-g3 h4xg3+ Kf2xg3 Ra8-d8) +8.65/7 0} 50.
Kf2 {(g1f2 b7e4 g2g3 h4g3 f2g3 e6e5 g3g4 c5c4) -6.82/7 0} Bxe4 {(Bb7xe4
g2-g3 h4xg3+ Kf2xg3 Ra8-f8 Kg3-g4 Rf8-f2) +8.90/7 0} 51. Ke3 {(f2e3 e4d5
e3f4 a8d8 g2g4 d8d6 g4g5 h6g5) -7.34/7 0} Bxg2 {(Be4xg2 Ke3-d3 Ra8-c8
Kd3-c4 e6-e5 Kc4-d3 Bg2xh3) +10.40/7 0} 52. Kf2 {(e3f2 g2d5 f2e3 a8f8 e3d3
f8f3 d3d2 f3h3) -8.85/7 0} Bd5 {(Bg2-d5 Kf2-e3 Ra8-f8 Ke3-d3 Rf8-f3+ Kd3-c2
Rf3xh3) +10.50/7 0} 53. Ke3 {(f2e3 a8f8 e3e2 e6e5 b6b7 d5b7 e2d3) -9.37/7
0} Rf8 {(Ra8-f8 Ke3-d3 Rf8-f3+ Kd3-c2 Rf3xh3 Kc2-b2 Rh3-h2+) +11.00/7 0}
54. Kd2 {(e3d2 e6e5 d2e2 e5e4 b6b7 d5b7 e2e3) -9.61/7 0} Rf3 {(Rf8-f3
Kd2-c1 Rf3xh3 Kc1-c2 e6-e5 Kc2-b2 Rh3-h2+) +11.15/7 0} 55. Kd1 {(d2d1 f3h3
d1c1 c5c4 b6b7 d5b7 c1d2) -11.18/7 0} Rb3 {(Rf3-b3 Kd1-d2 Rb3xb6 Kd2-c2
Rb6-a6 Kc2-d3 Ra6xa7) +11.95/7 0} 56. Kc2 {(d1c2 b3b6 c2d2 e6e5 a7a8b d5a8
d2d3) -11.32/7 0} Rxb6 {(Rb3xb6 a7-a8B Bd5xa8 Kc2-d3 Rb6-b2 Kd3-c4 Rb2-c2+)
+12.25/7 0} 57. Kd2 {(c2d2 e6e5 d2c2 e5e4 a7a8b d5a8 c2d2) -11.66/7 0} Ra6
{(Rb6-a6 Kd2-e3 e6-e5 Ke3-d3 Ra6xa7 Kd3-e3 Ra7-a2) +12.60/7 0} 58. Ke3
{(d2e3 d5g2 a7a8b a6a8 e3f4 g2h3 f4e5) -12.85/7 0} e5 {(e6-e5 Ke3-f2 Ra6xa7
Kf2-g1 Ra7-a2 Kg1-f1 Bd5-b7) +12.80/7 0} 59. Kd3 {(e3d3 a6a7 d3c2 e5e4 c2b2
d5e6 b2c3 e6h3) -13.67/7 0} Rxa7 {(Ra6xa7 Kd3-e3 Ra7-a3+ Ke3-f2 Ra3xh3
Kf2-g1 Rh3-h1+) +13.60/7 0} 60. Kc2 {(d3c2 e5e4 c2b1 d5e6 b1c2 h6h5 c2c3
e6h3) -13.88/7 0} Ra3 {(Ra7-a3 Kc2-b2 Ra3xh3 Kb2-c2 Bd5-b7 Kc2-b2 Rh3-h2+)
+13.75/7 0} 61. Kd2 {(c2d2 c5c4 d2c2 e5e4 c2b2 a3h3 b2c2) -14.05/7 0} Rxh3
{(Ra3xh3 Kd2-c2 Bd5-b7 Kc2-d2 Rh3-h2+ Kd2-d3 h4-h3) +13.80/7 0} 62. Ke2
{(d2e2 h3f3 e2d2 h4h3 d2e2 h3h2 e2e1 h2h1q) -21.60/7 0} Rf3 {(Rh3-f3 Ke2-d2
h4-h3 Kd2-d1 h3-h2 Kd1-c1 h2-h1Q+) +22.15/7 0} 63. Kd2 {(e2d2 h4h3 d2e2
h3h2 e2d2 e5e4 d2e1 h2h1q) -21.84/7 0} h3 {(h4-h3 Kd2-c2 h3-h2 Kc2-b2
h2-h1Q Kb2-c2 Rf3-f1) +22.55/7 0} 64. Ke2 {(d2e2 h3h2 e2d2 e5e4 d2e2 e4e3
e2e1 h2h1q) -22.08/7 0} h2 {(h3-h2 Ke2-d1 h2-h1Q+ Kd1-c2 Bd5-b7 Kc2-b2
Rf3-f2+) +22.65/7 0} 65. Kd2 {(e2d2 h2h1q d2e2 h1g2 e2e1 f3f1) -99.94/6 0}
h1=Q {(h2-h1Q Kd2-c2 Rf3-f2+ Kc2-d3 Qh1-f3+) +M500/7 0} 66. Ke2 {(d2e2 h1g2
e2d1 f3f1) -99.96/4 0} Bb3 {(Bd5-b3 Ke2-d2 Qh1-d1+) +M500/7 0} 67. Kd2
{(e2d2 h1d1) -99.98/3 0} Qd1# {(Qh1-d1+) +M500/7 0} 0-1
[/pgn]

[No4b]

OMG!

I've just implemented LMR:

Code: Select all

            // First move, use full-window search
            if(moves_searched == 0) 
            {                        
                // recursive negamax call
                score = -negamax(-beta, -alpha, depth - 1);
            }   
            // LMR
            else {   
                if (moves_searched >= full_depth_moves &&
                    depth >= reduction_limit &&
                    in_check == 0 &&
                    get_move_capture(move_list->moves[count]) == 0 &&
                    get_move_promoted(move_list->moves[count]) == 0
                   )
                {
                    // Search this move with reduced depth:
                    score = -negamax(- alpha - 1, -alpha, depth-2);
                }
                
                else score = alpha + 1;  // Hack to ensure that full-depth search is done
        

                if(score > alpha)
                {
                    score = -negamax(-alpha - 1, -alpha, depth-1);
                    
                    // research on fail    
                    if((score > alpha) && (score < beta))
                        score = -negamax(-beta, -alpha, depth-1);
                }      
            }

And now while my engine hits depth 7 in 2+0 blitz TSCP only goes depth 6
My engine has mated TSCP and the clock at the end of game is:
TSCP: 15 sec left
BBC(my engine): 56 sec left

AMAZING!
Thanks for providing an amazing resource so I could make use of it!!!


[pgn][Event "Computer chess game"]
[Site "maksim-Inspiron-3582"]
[Date "2020.09.09"]
[Round "?"]
[White "TSCP"]
[Black "BBC"]
[Result "0-1"]
[BlackElo "?"]
[ECO "B00"]
[Opening "Nimzowitsch Defence"]
[Time "21:41:36"]
[Variation "Bogoljubow, 3...Nf6"]
[WhiteElo "1650"]
[TimeControl "120+0"]
[Termination "normal"]
[PlyCount "134"]
[WhiteType "program"]
[BlackType "program"]

1. e4 Nc6 {(Nb8-c6 Ng1-f3 Ng8-f6 e4-e5 Nf6-d5 c2-c4 Nd5-f4) -0.10/7 0} 2.
Nc3 {(d2d4 e7e5 d4d5 c6e7 b1c3 g8f6) +0.22/6 3} Nf6 {(Ng8-f6 Ng1-f3 d7-d5
e4-e5 d5-d4 e5xf6 d4xc3) -0.10/7 0} 3. d4 {(d2d4 e7e6 c1g5 f8b4 g5f6 b4c3)
+0.31/6 3} d5 {(d7-d5 e4xd5 Nf6xd5 Nc3xd5 Qd8xd5 Ng1-f3 Bc8-f5) -0.10/7 0}
4. e5 {(f1b5 d8d7 e4e5 f6e4 c3e4 d5e4 b5c6 d7c6) +0.48/6 3} Ne4 {(Nf6-e4
Ng1-f3 Bc8-f5 Bf1-d3 Nc6-b4 O-O Nb4xd3 c2xd3) -0.10/7 2} 5. Nxe4 {(f1b5
e4c3 b5c6 b7c6 b2c3 e7e6 g1f3) +0.47/6 3} dxe4 {(d5xe4 Bc1-e3 f7-f6 f2-f3
Bc8-f5 f3xe4 Bf5xe4) -0.00/7 1} 6. Bb5 {(f1b5 c8d7 b5c6 d7c6 c1g5 c6d5)
+0.38/6 3} a6 {(a7-a6 Bb5xc6+ b7xc6 f2-f3 Bc8-f5 Bc1-f4 e7-e6 f3xe4 Bf5xe4)
+0.25/7 0} 7. Bxc6+ {(b5c6 b7c6 g1e2 c8g4 c1e3 a8b8 a1b1) +1.39/6 3} bxc6
{(b7xc6 f2-f3 Bc8-f5 f3xe4 Bf5xe4 Ng1-f3 e7-e6) +0.15/7 0} 8. Ne2 {(g1e2
c8g4 c1g5 d8b8 d1c1 e7e6) +1.14/6 3} f5 {(f7-f5 O-O e7-e6 Ne2-f4 Ke8-d7
Rf1-e1 Bc8-b7) +0.15/7 1} 9. Bg5 {(e1g1 e7e6 e2f4 e8f7 c1e3 f7g8) +1.54/6
3} Rb8 {(Ra8-b8 b2-b3 Bc8-b7 Ne2-f4 Ke8-f7 O-O Kf7-g8) +0.25/7 2} 10. b3
{(b2b3 h7h6 g5e3 e7e6 e1g1 f8e7) +1.36/6 3} Bb7 {(Bc8-b7 Ne2-f4 g7-g6
Nf4-e6 Qd8-c8 Ne6xf8 Ke8xf8) +0.20/7 0} 11. Nf4 {(e2f4 e8f7 e1g1 h7h6 d1h5
f7g8 f4g6) +1.45/6 2} Kf7 {(Ke8-f7 Qd1-h5+ Kf7-g8 O-O-O h7-h6 Bg5-h4 g7-g5)
+0.15/7 1} 12. O-O {(e1g1 h7h6 g5h4 g7g5 d1h5 f7g8 f4e6) +1.52/6 2} g6
{(g7-g6 e5-e6+ Kf7-g8 Qd1-d2 Bf8-g7 Ra1-d1 a6-a5 Qd2xa5 Bg7xd4 Bg5xe7
Bd4xf2+) +0.35/7 0} 13. c3 {(c2c3 h7h6 e5e6 f7g8 f4g6 h6g5 g6h8 g8h8)
+1.70/6 2} Bg7 {(Bf8-g7 e5-e6+ Kf7-g8 Rf1-e1 h7-h6 Bg5-h4 g6-g5) +0.40/7 0}
14. Qc1 {(d1e2 d8c8 f2f3 c6c5 e5e6) +1.88/5 2} Re8 {(Rh8-e8 Rf1-d1 Qd8-c8
e5-e6+ Kf7-g8 b3-b4 h7-h5) +0.55/7 1} 15. Ne2 {(f4e2 f7g8 e5e6 d8d6 e2f4
e8d8) +1.34/6 2} Kg8 {(Kf7-g8 Rf1-d1 Qd8-d7 Bg5-h6 Bg7xh6 Qc1xh6 Rb8-d8)
+0.75/7 1} 16. a3 {(a2a3 d8c8 c3c4 e7e6 g5f6 c8d7) +1.22/6 2} a5 {(a6-a5
b3-b4 a5xb4 a3xb4 Rb8-a8 Ne2-f4 Ra8xa1 Qc1xa1) +0.80/7 1} 17. c4 {(c3c4
c6c5 f1d1 c5d4 d1d4 d8c8) +1.26/6 2} c5 {(c6-c5 Rf1-d1 c5xd4 Ne2xd4 Qd8-c8
Bg5-f4 e7-e6) +0.75/7 1} 18. dxc5 {(f1d1 c5d4 d1d4 d8c8 g5f4 e7e6) +1.01/6
2} Qd3 {(Qd8-d3 Ne2-f4 Qd3xb3 Ra1-b1 Qb3-a2 e5-e6 a5-a4) +0.85/7 1} 19. Qb2
{(c1b2 b7a6 f1b1 a6c4 e2c1 d3f1) +0.99/6 2} Ba6 {(Bb7-a6 Qb2-a2 Bg7xe5
Ra1-b1 a5-a4 b3xa4 Rb8xb1 Rf1xb1 Ba6xc4) +1.00/7 3} 20. b4 {(e2c1 d3c4 f1d1
c4c5 g5f4) +0.25/5 2} Qxc4 {(Qd3xc4 Ne2-f4 Qc4xc5 Qb2-a2+ Qc5-c4 Rf1-c1
Qc4xa2 Ra1xa2) +1.75/7 3} 21. Nf4 {(e2f4 c4c5 b2a2 c5c4 f1c1 c4a2 a1a2 a5b4
a3b4) +0.02/6 2} Qxc5 {(Qc4xc5 Qb2-a2+ Qc5-c4 Rf1-c1 Qc4xa2 Ra1xa2 Bg7xe5
b4xa5) +1.75/7 1} 22. Qa2+ {(b2a2 c5c4 f1c1 c4a2 a1a2 h7h6 g5h4 a5b4 a3b4
g7e5 f4g6) -0.18/6 2} Qc4 {(Qc5-c4 Rf1-c1 Qc4xa2 Ra1xa2 Bg7xe5 b4xa5
Ba6-b7) +2.05/7 0} 23. Rfc1 {(f1c1 c4a2 a1a2 h7h6 g5e7 e8e7 f4g6) -0.40/7
1} Qxa2 {(Qc4xa2 Ra1xa2 h7-h6 Bg5-h4 g6-g5 b4-b5 Ba6xb5) +2.85/7 0} 24.
Rxa2 {(a1a2 h7h6 f4g6 h6g5 b4a5 b8b7 a3a4) -0.34/7 1} h6 {(h7-h6 Nf4xg6
h6xg5 Rc1xc7 Kg8-f7 Rc7-a7 Ba6-b7) +3.15/7 0} 25. Bh4 {(f4g6 h6g5 b4a5 g8f7
c1c6 e7e6) -0.60/6 1} g5 {(g6-g5 Nf4-e6 g5xh4 Ne6xg7 Kg8xg7 Rc1xc7 a5-a4)
+3.25/7 0} 26. Nd5 {(f4d5 g5h4 d5c7 e8c8 c1c5 a5b4 c7a6 c8c5 a6c5 b4a3 a2a3
g7e5) -1.19/6 1} gxh4 {(g5xh4 Nd5xc7 Re8-c8 Rc1-c5 Ba6-d3 b4xa5 Rb8-b1+)
+3.75/7 0} 27. bxa5 {(d5c7 e8c8 c1c5 a5b4 c7a6 c8c5 a6c5 b4a3 a2a3 g7e5)
-1.19/6 1} Bxe5 {(Bg7xe5 Ra2-c2 Ba6-d3 Rc2-c6 Be5-d6 a3-a4 Rb8-b2 Nd5xc7)
+4.80/7 1} 28. a4 {(a3a4 a6d3 a2d2 b8b7 f2f3 e7e6) -2.29/6 1} e6 {(e7-e6
Nd5-e3 Ba6-b7 Ra2-d2 Rb8-d8 Rc1-d1 Rd8xd2 Rd1xd2) +5.65/7 2} 29. Ne3 {(d5e3
c7c5 a2d2 e5d4 c1e1 a6d3) -2.81/6 1} Rbd8 {(Rb8-d8 g2-g3 h4xg3 h2xg3 Ba6-b7
Rc1-c5 Be5-d6) +5.65/7 1} 30. Rc6 {(c1c6 a6b7 c6c5 b7d5 a2d2 c7c6) -2.63/6
1} Bb7 {(Ba6-b7 Rc6-c5 Be5-d6 Rc5-b5 Bb7-a6 Rb5-b3 Bd6-e5) +5.75/7 1} 31.
Rc1 {(c6c1 b7d5 a2d2 h4h3 g2h3 c7c6) -2.65/6 1} c6 {(c7-c6 Ra2-e2 Be5-g7
Rc1-b1 Bb7-a6 Re2-c2 Ba6-d3) +5.85/7 2} 32. Rb1 {(c1b1 e8e7 a2c2 e5d4 b1d1
e7d7) -2.68/6 1} Re7 {(Re8-e7 Ra2-c2 Be5-g7 Rb1-e1 Rd8-d4 Ne3-c4 e6-e5)
+5.90/7 1} 33. Nc4 {(e3c4 e7d7 a2e2 d7d1 e2e1 d1e1 b1e1 e5d4) -2.82/6 1}
Bg7 {(Be5-g7 Rb1-e1 Rd8-d4 Ra2-c2 Re7-d7 f2-f4 Rd4-d1) +6.00/7 2} 34. Rc2
{(a2c2 c6c5 c4e3 g7d4 c2d2 e7d7) -2.86/6 1} c5 {(c6-c5 Nc4-b6 Re7-c7 Rb1-e1
h6-h5 f2-f4 Rd8-d4) +5.90/7 2} 35. Rcc1 {(c2c1 h4h3 g2h3 g7d4 b1b6 e7g7)
-2.93/6 1} f4 {(f5-f4 Rb1-b6 Bb7-d5 Rb6-d6 Rd8xd6 Nc4xd6 Re7-d7) +5.90/7 1}
36. Rb6 {(b1b6 e7d7 b6b1 g7d4 c4b6 d7d6) -3.00/6 1} Red7 {(Re7-d7 Nc4-d6
Bb7-a8 Nd6-c4 e6-e5 Rb6-e6 Ba8-d5) +6.05/7 1} 37. Rbb1 {(b6b1 g7d4 b1b3
b7c6 c4b6 d7d6) -3.05/6 1} Ba6 {(Bb7-a6 Nc4-b6 Rd7-c7 Rc1-e1 Rd8-d4 Rb1-d1
Ba6-b7) +5.85/7 1} 38. h3 {(h2h3 d7a7 c4b2 d8d2 b2d1 c5c4) -3.32/6 1} Rd3
{(Rd7-d3 Kg1-h2 Rd3-d4 Nc4-b6 Ba6-d3 Rb1-b3 c5-c4) +6.25/7 1} 39. Nb2
{(c4b2 d3d5 b2c4 e4e3 f2e3 a6c4 c1c4 f4e3 c4h4) -3.62/6 1} Rb3 {(Rd3-b3
Nb2-d1 Rb3-d3 Nd1-b2 Rd3-d2 Nb2-c4 Rd2-a2) +6.20/7 1} 40. Nd1 {(b2d1 c5c4
b1b3 c4b3 d1c3 b3b2) -3.46/6 1} Rxb1 {(Rb3xb1 Rc1xb1 Ba6-e2 Nd1-b2 Rd8-d2
f2-f3 Bg7xb2 f3xe4) +7.50/7 0} 41. Rxb1 {(c1b1 a6e2 d1e3 f4e3 f2e3 c5c4
a5a6) -4.96/7 1} Be2 {(Ba6-e2 Nd1-e3 f4xe3 f2xe3 Be2-d1 Rb1-c1 Rd8-d2
Rc1xc5 Bd1xa4) +7.90/7 0} 42. a6 {(a5a6 e2d1 a6a7 g7e5 a4a5 e4e3 g1h2)
-5.38/7 1} e3 {(e4-e3 f2xe3 Rd8xd1+ Rb1xd1 Be2xd1 e3xf4 Bd1xa4) +7.30/7 0}
43. a7 {(a6a7 g7e5 d1c3 e2h5 c3e4 h5g6 b1b8 d8b8 a7b8q e5b8 e4c5 e3f2 g1f2)
-3.15/7 0} Be5 {(Bg7-e5 Nd1-b2 Be5-c3 f2xe3 f4xe3 Kg1-h2 Rd8-d2) +5.80/7 0}
44. Nxe3 {(d1e3 f4e3 f2e3 c5c4 g1f2 e2d3) -3.88/6 0} fxe3 {(f4xe3 f2xe3
Be2-a6 a4-a5 c5-c4 Rb1-e1 Rd8-d2) +6.30/7 0} 45. fxe3 {(f2e3 e2a6 a4a5 d8a8
b1c1 a8a7 c1c5) -3.93/6 0} Ba6 {(Be2-a6 e3-e4 c5-c4 Kg1-h1 c4-c3 Rb1-e1
Rd8-d2) +6.40/7 0} 46. a5 {(a4a5 d8a8 b1b6 a8a7 b6e6 e5g7) -4.34/6 0} Bc7
{(Be5-c7 e3-e4 c5-c4 Rb1-a1 Rd8-a8 Ra1-e1 Ra8xa7) +6.75/7 0} 47. e4 {(e3e4
d8a8 b1b6 c7b6 a5b6 c5c4) -4.87/6 0} Ra8 {(Rd8-a8 Rb1-c1 Bc7-e5 g2-g3
Be5-d4+ Kg1-g2 h4xg3) +7.00/7 0} 48. Rb6 {(b1b6 c7b6 a5b6 a8f8 e4e5 c5c4
g1h2) -4.88/7 0} Bxb6 {(Bc7xb6 a5xb6 Ba6-b7 e4-e5 Ra8-d8 Kg1-f2 Rd8-d2+)
+7.95/7 0} 49. axb6 {(a5b6 a6b7 g1f2 b7e4 f2f1 a8f8 f1g1 e6e5 g1h2) -6.55/8
0} Bb7 {(Ba6-b7 Kg1-f2 Bb7xe4 g2-g3 h4xg3+ Kf2xg3 Ra8-d8) +8.65/7 0} 50.
Kf2 {(g1f2 b7e4 g2g3 h4g3 f2g3 e6e5 g3g4 c5c4) -6.82/7 0} Bxe4 {(Bb7xe4
g2-g3 h4xg3+ Kf2xg3 Ra8-f8 Kg3-g4 Rf8-f2) +8.90/7 0} 51. Ke3 {(f2e3 e4d5
e3f4 a8d8 g2g4 d8d6 g4g5 h6g5) -7.34/7 0} Bxg2 {(Be4xg2 Ke3-d3 Ra8-c8
Kd3-c4 e6-e5 Kc4-d3 Bg2xh3) +10.40/7 0} 52. Kf2 {(e3f2 g2d5 f2e3 a8f8 e3d3
f8f3 d3d2 f3h3) -8.85/7 0} Bd5 {(Bg2-d5 Kf2-e3 Ra8-f8 Ke3-d3 Rf8-f3+ Kd3-c2
Rf3xh3) +10.50/7 0} 53. Ke3 {(f2e3 a8f8 e3e2 e6e5 b6b7 d5b7 e2d3) -9.37/7
0} Rf8 {(Ra8-f8 Ke3-d3 Rf8-f3+ Kd3-c2 Rf3xh3 Kc2-b2 Rh3-h2+) +11.00/7 0}
54. Kd2 {(e3d2 e6e5 d2e2 e5e4 b6b7 d5b7 e2e3) -9.61/7 0} Rf3 {(Rf8-f3
Kd2-c1 Rf3xh3 Kc1-c2 e6-e5 Kc2-b2 Rh3-h2+) +11.15/7 0} 55. Kd1 {(d2d1 f3h3
d1c1 c5c4 b6b7 d5b7 c1d2) -11.18/7 0} Rb3 {(Rf3-b3 Kd1-d2 Rb3xb6 Kd2-c2
Rb6-a6 Kc2-d3 Ra6xa7) +11.95/7 0} 56. Kc2 {(d1c2 b3b6 c2d2 e6e5 a7a8b d5a8
d2d3) -11.32/7 0} Rxb6 {(Rb3xb6 a7-a8B Bd5xa8 Kc2-d3 Rb6-b2 Kd3-c4 Rb2-c2+)
+12.25/7 0} 57. Kd2 {(c2d2 e6e5 d2c2 e5e4 a7a8b d5a8 c2d2) -11.66/7 0} Ra6
{(Rb6-a6 Kd2-e3 e6-e5 Ke3-d3 Ra6xa7 Kd3-e3 Ra7-a2) +12.60/7 0} 58. Ke3
{(d2e3 d5g2 a7a8b a6a8 e3f4 g2h3 f4e5) -12.85/7 0} e5 {(e6-e5 Ke3-f2 Ra6xa7
Kf2-g1 Ra7-a2 Kg1-f1 Bd5-b7) +12.80/7 0} 59. Kd3 {(e3d3 a6a7 d3c2 e5e4 c2b2
d5e6 b2c3 e6h3) -13.67/7 0} Rxa7 {(Ra6xa7 Kd3-e3 Ra7-a3+ Ke3-f2 Ra3xh3
Kf2-g1 Rh3-h1+) +13.60/7 0} 60. Kc2 {(d3c2 e5e4 c2b1 d5e6 b1c2 h6h5 c2c3
e6h3) -13.88/7 0} Ra3 {(Ra7-a3 Kc2-b2 Ra3xh3 Kb2-c2 Bd5-b7 Kc2-b2 Rh3-h2+)
+13.75/7 0} 61. Kd2 {(c2d2 c5c4 d2c2 e5e4 c2b2 a3h3 b2c2) -14.05/7 0} Rxh3
{(Ra3xh3 Kd2-c2 Bd5-b7 Kc2-d2 Rh3-h2+ Kd2-d3 h4-h3) +13.80/7 0} 62. Ke2
{(d2e2 h3f3 e2d2 h4h3 d2e2 h3h2 e2e1 h2h1q) -21.60/7 0} Rf3 {(Rh3-f3 Ke2-d2
h4-h3 Kd2-d1 h3-h2 Kd1-c1 h2-h1Q+) +22.15/7 0} 63. Kd2 {(e2d2 h4h3 d2e2
h3h2 e2d2 e5e4 d2e1 h2h1q) -21.84/7 0} h3 {(h4-h3 Kd2-c2 h3-h2 Kc2-b2
h2-h1Q Kb2-c2 Rf3-f1) +22.55/7 0} 64. Ke2 {(d2e2 h3h2 e2d2 e5e4 d2e2 e4e3
e2e1 h2h1q) -22.08/7 0} h2 {(h3-h2 Ke2-d1 h2-h1Q+ Kd1-c2 Bd5-b7 Kc2-b2
Rf3-f2+) +22.65/7 0} 65. Kd2 {(e2d2 h2h1q d2e2 h1g2 e2e1 f3f1) -99.94/6 0}
h1=Q {(h2-h1Q Kd2-c2 Rf3-f2+ Kc2-d3 Qh1-f3+) +M500/7 0} 66. Ke2 {(d2e2 h1g2
e2d1 f3f1) -99.96/4 0} Bb3 {(Bd5-b3 Ke2-d2 Qh1-d1+) +M500/7 0} 67. Kd2
{(e2d2 h1d1) -99.98/3 0} Qd1# {(Qh1-d1+) +M500/7 0} 0-1
[/pgn]

Great work! Code is really simple, understandable and effective.

[No4b]

It just happens that this evening i decided to implement LMR for my Drofa project,
so i figured i could write in this topic as well.

I used more complex approach using some almalgamm of ideas i found on the CPW and from a Weiss engine.

First, in the initiation of the Search class i calculate base reduction array:

Code: Select all

void Search::init_LMR_array(){
  for (int i = 0; i < 34; i++){
    for (int j = 0; j< 34; j++){
      _lmr_R_array[i][j] = 0.1 + (pow(i, 0.15) * pow(j, 0.15))/1.75;
    }
  }
}

It looks fancy, but in fact for now its mostly should be either 0 or 1(mostly) and may be 2 sometimes.
I will try to tune this later.

Than in the _negamax function

Code: Select all

        
        //LATE MOVE REDUCTIONS
        //mix of ideas from Weiss code and what is written in the chessprogramming wiki
        //
        //For now we dont reduce in the PV, if depth too low, when extention is triggered
        //and when move give check.
        //This can be a subject for a later tuning
        //
        //Currently we try to reduce 4th move and beyond.

        doLMR = !pvNode && depth > 2 && LegalMoveCount > 3 && 
        Extension == 0 && !movedBoard.colorIsInCheck(movedBoard.getActivePlayer());
        if (doLMR){

          //Basic reduction is done according to the array
          //Initiated at the ini() of the Search Class
          //Now mostly 0 -> 1
          int reduction = _lmr_R_array[std::min(33, depth)][std::min(33, LegalMoveCount)];

          //if move is quiet, reduce a bit more
          if (!move.getFlags()){
            reduction++;
          }
          //Avoid to reduce so much that we go to QSearch right away
          int fDepth = std::max(1, depth - 1 - reduction);
          
          //Search with reduced depth around alpha in assumtion
          // that alpha would not be beaten here
          score = -_negaMax(movedBoard, fDepth, -alpha - 1 , -alpha, ply + 1, false);
        }
        
        // Code here is restructured based on Weiss
        // First part is clear here: if we did LMR and score beats alpha
        // We need to do a re-search.
        // 
        // If we did not do LMR: if we are in a non-PV our we already have alpha == beta - 1,
        // and if we are searching 2nd move and so on we already did full window search - 
        // So for both of this cases we do limited window search. 
        //
        // This system is implemented instead of fullDepth = true/false basic approach.
        if (doLMR){
          if (score > alpha){
            score = -_negaMax(movedBoard, depth - 1 + Extension, -alpha - 1, -alpha, ply + 1, false);
          }
        } else if (!pvNode || LegalMoveCount > 1){
          score = -_negaMax(movedBoard, depth - 1 + Extension, -alpha - 1, -alpha, ply + 1, false);
        }

        // If we are in the PV 
        // Search with a full window the first move to calculate bounds
        // or if score improved alpha during the current round of search.
        if  (pvNode) {
          if ((LegalMoveCount == 1) || (score > alpha && score < beta)){
            score = -_negaMax(movedBoard, depth - 1 + Extension, -beta, -alpha, ply + 1, false );  
          }
        }

I reduce here everything (captures, promotions, etc), starting from the 4th move in the overall list.
Moves that are PVnode, cause extension or give check are not reduced.
Quiet moves are reduced with R+1, and now move can be reduced to have depth = 0.

In startpos it gives Drofa +2 depth in the same amount of time spend in comparation to the current tested 1.0.3 version.
I started a testrun to confirm elogain, for now things looks really good. Like super good:

Code: Select all

Score of Drofa_dev vs Drofa_1.0.3: 27 - 9 - 24  [0.650] 60
Elo: 107 +/- 71

If this holds, I really should think on finding some opponents for my engine that are stronger than VICE