Selective techniques

[metax]

You have to get it. Before you make any decisions, you can at least make the move, then you can determine whether it checked the opponent or not, and if so refuse to prune/reduce it, since it should trigger a check extension anyway...

I solved it through adding another parameter to my alpha-beta function, which indicates if the conditions for a reduction (except for the condition that the move should not give check) are fulfilled. If there is no check, the reduction is done.

[Uri Blass]

I do not understand how you get mate in 8 in 2 plies espacially when not all the moves in the main line are checks or reply to check(4...Qg4 and 8.f5 Qxf5 9.a4)

Uri

Even if all moves _were_ checks or replies to check, I would not understand it, because only the checks are free, but not the replies. Or do I miss something?

There are programs that also extend single replies to check but based on my memory crafty removed single reply to check extensions so I agree that even in the case that all moves are checks and reply to check I do not understand it.

Uri

[metax]

Maybe Bob could explain that...?

[bob]

You have to get it. Before you make any decisions, you can at least make the move, then you can determine whether it checked the opponent or not, and if so refuse to prune/reduce it, since it should trigger a check extension anyway...

I solved it through adding another parameter to my alpha-beta function, which indicates if the conditions for a reduction (except for the condition that the move should not give check) are fulfilled. If there is no check, the reduction is done.

I'm not quite following. When you call alpha/beta, you pass it a new position P. Inside that node, you will try a set of moves one at a time. I reduce each move (or not) based on the characteristics of the position _after_ the move, not before. For example, I don't reduce captures, or some passed pawn pushes, or moves that give check to my opponent. It _sounds_ like you might be using what I call an "inverted" search (perfectly OK if a little hard for those that don't use that approach to follow) where you make a move, recursively call search, and there you either reduce everything or reduce nothing???

[bob]

I tried the idea with the pruning of moves whose index is greater than 2 + the remaining distance to horizon. But I have tactical problems, for example in that position:

http://tinyurl.com/yj8k9gr

FEN: 4r1k1/pp1qrp2/2p2b1p/2Pp4/1P1N1P2/6Pb/P4Q1P/1BR1R1K1

ChessMind without that pruning sees the move 1...Rxe1! after some seconds and the mate in 9 after about 5 minutes on ply 13, which is very slow. I hoped to get a better performance with that trick, but now it doesn't even see the move 1...Rxe1 in 10 minutes even though it reaches ply 17. That seems to need some extra pruning...

I reduce everywhere, and prune in the last 4 plies. Crafty still sees this instantly:

Code: Select all

                2     0.01 -Mat08   2. Rxe1 Rxe1+ 3. Qxe1 Bxd4+ 4. Kh1
                                    Qg4 5. Qe8+ Kg7 6. Qxf7+ Kxf7 7. Bg6+
                                    Qxg6 8. f5 Qxf5 9. a4 Qb1# 

only takes 2 plies and 10 milliseconds (or less, since this is rounded).

You just have to be selective in what you reduce or prune. Never when in check. Never if a move gives check. Never if the move might become a best move because of current material score and alpha/beta bounds comparison, etc.

I do not understand how you get mate in 8 in 2 plies espacially when not all the moves in the main line are checks or reply to check(4...Qg4 and 8.f5 Qxf5 9.a4)

Uri

Actually, I don't. I am not sure what I did, but it probably started to ponder before I said "go". I re-ran the position correctly and got this:

Code: Select all

               11     0.60 -Mat09   1. ... Rxe1+ 2. Rxe1 Rxe1+ 3. Qxe1   
                                    Bxd4+ 4. Kh1 Qg4 5. Qe8+ Kg7 6. Qxf7+
                                    Kxf7 7. Bg6+ Qxg6 8. f5 Qxf5 9. a4
                                    Qb1#

Score prior to the finding Re1 was -11.19 for Bxd4 at depth 9, but at depth 9 it changed its mind to Rxe1. Here is the complete output:

Code: Select all

                                    4. Kf2 Rf1+ 5. Ke3 Qe6+ 6. Kd2 Rxb1
                6->   0.08 -10.46   1. ... Bxd4 2. Qxd4 Rxe1+ 3. Rxe1 Rxe1+
                                    4. Kf2 Rf1+ 5. Ke3 Qe6+ 6. Kd2 Rxb1
                7     0.08 -10.63   1. ... Bxd4 2. Qxd4 Rxe1+ 3. Rxe1 Rxe1+
                                    4. Kf2 Rf1+ 5. Ke3 Qe6+ 6. Be4 Re1+
                                    7. Kf2 Rxe4
                7->   0.08 -10.63   1. ... Bxd4 2. Qxd4 Rxe1+ 3. Rxe1 Rxe1+
                                    4. Kf2 Rf1+ 5. Ke3 Qe6+ 6. Be4 Re1+
                                    7. Kf2 Rxe4
                8     0.08 -11.00   1. ... Bxd4 2. Qxd4 Rxe1+ 3. Rxe1 Rxe1+
                                    4. Kf2 Rf1+ 5. Ke3 Qe6+ 6. Be4 dxe4
                                    7. Qd8+ Kh7
                8->   0.09 -11.00   1. ... Bxd4 2. Qxd4 Rxe1+ 3. Rxe1 Rxe1+
                                    4. Kf2 Rf1+ 5. Ke3 Qe6+ 6. Be4 dxe4
                                    7. Qd8+ Kh7
                9     0.09 -11.19   1. ... Bxd4 2. Qxd4 Rxe1+ 3. Rxe1 Rxe1+
                                    4. Kf2 Rf1+ 5. Ke3 Qe6+ 6. Be4 dxe4
                                    7. Qd8+ Kh7 8. a4 Rf3+ 9. Kd2
                9     0.11     -1   1. ... Rxe1+!                        
                9     0.11     -3   1. ... Rxe1+!                        
                9     0.12 -12.76   1. ... Rxe1+ 2. Rxe1 Rxe1+ 3. Qxe1   
                                    Bxd4+ 4. Qf2 Bxf2+ 5. Kxf2 Bf5 6. Bxf5
                                    Qxf5 7. h3 Qc2+ 8. Kf3 Qc3+ 9. Kf2
                                    Qxb4
                9->   0.12 -12.76   1. ... Rxe1+ 2. Rxe1 Rxe1+ 3. Qxe1   
                                    Bxd4+ 4. Qf2 Bxf2+ 5. Kxf2 Bf5 6. Bxf5
                                    Qxf5 7. h3 Qc2+ 8. Kf3 Qc3+ 9. Kf2
                                    Qxb4
               10     0.12     -1   1. ... Rxe1+!                        
               10     0.13     -3   1. ... Rxe1+!                        
               10     0.13     -M   1. ... Rxe1+!                        
               10     0.14 -16.62   1. ... Rxe1+ 2. Rxe1 Rxe1+ 3. Qxe1   
                                    Bxd4+ 4. Qf2 Qg4 5. Bh7+ Kxh7 6. Qxd4
                                    Qf3 7. Qd3+ Qxd3 8. Kf2 Qd2+ 9. Kf3
                                    Bg2+ 10. Kg4 Qxb4
               10->   0.14 -16.62   1. ... Rxe1+ 2. Rxe1 Rxe1+ 3. Qxe1   
                                    Bxd4+ 4. Qf2 Qg4 5. Bh7+ Kxh7 6. Qxd4
                                    Qf3 7. Qd3+ Qxd3 8. Kf2 Qd2+ 9. Kf3
                                    Bg2+ 10. Kg4 Qxb4
               11     0.15     -1   1. ... Rxe1+!                        
               11     0.16     -3   1. ... Rxe1+!                        
               11     0.17     -M   1. ... Rxe1+!                        
               11     0.60 -Mat09   1. ... Rxe1+ 2. Rxe1 Rxe1+ 3. Qxe1   
                                    Bxd4+ 4. Kh1 Qg4 5. Qe8+ Kg7 6. Qxf7+
                                    Kxf7 7. Bg6+ Qxg6 8. f5 Qxf5 9. a4
                                    Qb1#
               11->   0.60 -Mat09   1. ... Rxe1+ 2. Rxe1 Rxe1+ 3. Qxe1   
                                    Bxd4+ 4. Kh1 Qg4 5. Qe8+ Kg7 6. Qxf7+
                                    Kxf7 7. Bg6+ Qxg6 8. f5 Qxf5 9. a4
                                    Qb1#

So 0.11 seconds to find the move, 0.6 seconds to see the mate. Run using one CPU on my 2.0ghz core2 duo laptop. The 8-core box needs 0.01 seconds to find Re1 and less than .1 seconds to see the mate, using all 8 cores.

I suspect what I did was to run on the 8-core box which defaults to ponder=on since it is the box that I use on ICC and in tournaments. When I drag and drop the EPD into the thing, it instantly starts to search. It apparently found the mate very quickly. So quickly my "noise" setting caused it to produce no output at all to that point so I didn't notice it had already cooked the thing. I reran without pondering on my laptop to get the right answer.

[bob]

Maybe Bob could explain that...?

Already done. "operator error".

[metax]

I implemented that pruning trick. But now my engine loses pieces senselessly...

For example in that position:
r1bqkb1r/pppp1ppp/1nn5/3PP3/5P2/8/PP4PP/RNBQKBNR b KQkq -

it wants to play 1...Qh4? with an evaluation of -2.69. After 2.g3 it realizes that it loses the Nc6 and evaluates +1.60.
Without the pruning, it proposes 1...Bb4+ with an evaluation of -0.12, which most other engines prefer, too.

edit: I added some conditions to the pruning. I don't prune if
-I am in check
-the move gives check
-the move is a capture
-the best value until now is a checkmate, so I want to find an escape.

I thought these conditions were enough, but now ChessMind wants to play 1...Nxd5? in the above position... at ply 13 with an evaluation of -1.7!

[bob]

I implemented that pruning trick. But now my engine loses pieces senselessly...

For example in that position:
r1bqkb1r/pppp1ppp/1nn5/3PP3/5P2/8/PP4PP/RNBQKBNR b KQkq -

it wants to play 1...Qh4? with an evaluation of -2.69. After 2.g3 it realizes that it loses the Nc6 and evaluates +1.60.
Without the pruning, it proposes 1...Bb4+ with an evaluation of -0.12, which most other engines prefer, too.

edit: I added some conditions to the pruning. I don't prune if
-I am in check
-the move gives check
-the move is a capture
-the best value until now is a checkmate, so I want to find an escape.

I thought these conditions were enough, but now ChessMind wants to play 1...Nxd5? in the above position... at ply 13 with an evaluation of -1.7!

No clue what you are doing wrong. But here is my output with all reductions and pruning turned on:

Code: Select all

              depth   time  score   variation (1)
                1     0.03  -0.58   1. ... Bb4+ 2. Nc3 Qh4+ 3. g3       
                1     0.03  -0.69   1. ... Qh4+ 2. g34Knps)             
                1->   0.03  -0.69   1. ... Qh4+ 2. g36Knps)             
                2     0.03  -0.58   1. ... Qh4+ 2. g3 Bb4+ 3. Nc3       
                2->   0.03  -0.58   1. ... Qh4+ 2. g3 Bb4+ 3. Nc3       
                3     0.03     +1   1. ... Qh4+?                        
                3     0.04   0.46   1. ... Qh4+ 2. g3 Bb4+ 3. Nd2 Bxd2+ 
                                    4. Bxd2
                3     0.04  -0.19   1. ... Bb4+ 2. Nc3 Bxc3+ 3. bxc3 Qh4+
                                    4. g3
                3     0.04  -0.68   1. ... Nb4 2. Nc3 Bc5s)             
                3->   0.04  -0.68   1. ... Nb4 2. Nc3 Bc5ps)             
                4     0.04  -0.36   1. ... Nb4 2. Nc3 d6 3. Bb5+ Bd7     
                4->   0.04  -0.36   1. ... Nb4 2. Nc3 d6 3. Bb5+ Bd7     
                5     0.05     -1   1. ... Nb4!                          
                5     0.05  -0.96   1. ... Nb4 2. Nc3 Bc5 3. Nf3 O-O     
                5->   0.05  -0.96   1. ... Nb4 2. Nc3 Bc5 3. Nf3 O-O     
                6     0.06  -0.75   1. ... Nb4 2. Nc3 Bc5 3. Nf3 O-O 4.  
                                    Bb5
                6->   0.06  -0.75   1. ... Nb4 2. Nc3 Bc5 3. Nf3 O-O 4.  
                                    Bb5
                7     0.07     +1   1. ... Nb4?                          
                7     0.08  -0.08   1. ... Nb4 2. Nc3 Bc5 3. a3 Bxg1 4.  
                                    axb4 Qh4+ 5. g3
                7     0.10  -0.29   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 O-O 5. Nf3
                7->   0.11  -0.29   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 O-O 5. Nf3
                8     0.12  -0.49   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 O-O 5. Nf3 Bc5
                8->   0.14  -0.49   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 O-O 5. Nf3 Bc5
                9     0.18  -0.45   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 O-O 5. Nf3 Bc5 6. Ne4
                9->   0.22  -0.45   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 O-O 5. Nf3 Bc5 6. Ne4
               10     0.29  -0.44   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 O-O 5. Nf3 Bc5 6. Ne4 cxd6 7. Nxd6
               10->   0.39  -0.44   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 O-O 5. Nf3 Bc5 6. Ne4 cxd6 7. Nxd6
               11     0.56  -0.50   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 cxd6 5. Nxd5 Nxd5 6. Bxb4 Nxb4
                                    7. Nf3
               11->   0.74  -0.50   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 cxd6 5. Nxd5 Nxd5 6. Bxb4 Nxb4
                                    7. Nf3
               12     1.20  -0.59   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 cxd6 5. Nxd5 Nxd5 6. Bxb4 Nxb4
                                    7. Nf3 d5
               12->   1.58  -0.59   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 cxd6 5. Nxd5 Nxd5 6. Bxb4 Nxb4
                                    7. Nf3 d5
               13     2.37  -0.55   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 cxd6 5. Nxd5 Nxd5 6. Bxb4 Nxb4
                                    7. exd6 O-O 8. Nf3 Re8+ 9. Ne5
               13->   3.54  -0.55   1. ... Bb4+ 2. Nc3 Ne7 3. d6 Ned5 4. 
                                    Bd2 cxd6 5. Nxd5 Nxd5 6. Bxb4 Nxb4
                                    7. exd6 O-O 8. Nf3 Re8+ 9. Ne5
               14     5.88  -0.54   1. ... Bb4+ 2. Nc3 Ne7 3. d6 cxd6 4. 
                                    exd6 Ned5 5. Qe2+ Kf8 6. Qe5 Qh4+ 7.
                                    g3 Qh6 8. Nf3 Bxd6 9. Qd4 Qh5
               14->   9.43  -0.54   1. ... Bb4+ 2. Nc3 Ne7 3. d6 cxd6 4. 
                                    exd6 Ned5 5. Qe2+ Kf8 6. Qe5 Qh4+ 7.
                                    g3 Qh6 8. Nf3 Bxd6 9. Qd4 Qh5
               15    16.19  -0.45   1. ... Bb4+ 2. Nc3 Ne7 3. d6 cxd6 4. 
                                    exd6 Ned5 5. Qe2+ Kf8 6. Qe5 Qh4+ 7.
                                    g3 Qh6 8. Nf3 Bxd6 9. Qd4 Nb4 10. Qe4
               15->  24.83  -0.45   1. ... Bb4+ 2. Nc3 Ne7 3. d6 cxd6 4. 
                                    exd6 Ned5 5. Qe2+ Kf8 6. Qe5 Qh4+ 7.
                                    g3 Qh6 8. Nf3 Bxd6 9. Qd4 Nb4 10. Qe4
              time=30.87  mat=0  n=69002310  fh=92%  nps=2.2M            
              extensions=2.3M qchecks=2.8M reduced=5.8M pruned=23.9M
              predicted=0  evals=33.9M  50move=0  EGTBprobes=0  hits=0

That is on my laptop, but it is a slow executable as I am debugging something unrelated to search.

With reductions, all you are doing is reducing the remaining depth, correct? And not just throwing the moves away completely???

[michiguel]

Hello,

since about 4 months, I am developing my engine ChessMind now. I implemented null move with R=3 (without verification), transposition tables and Futility pruning. The problem is the following:
I currently search at least 250 kilonodes per second, in a normal middlegame position 300 on average. That is not a very good value, but still OK in my opinion. My problem is the tree explosion. Other programs easily reach search depths of at least 14-15 in a few seconds, ChessMind reaches ply 7-8 in that time. This is because I need about 1.000.000 nodes to reach ply 8 or 9 in most middlegame positions, whereas other engines need 1.000.000 nodes to reach ply 14. My conclusion is that I have to improve my selective techniques, but how? I experimented a bit with some reductions if one side has lost too much material, but that either gave me not much performance or had very high tactical risks. For example, I found out that to reduce the tactical risk, I should not reduce captures, check or transposition table moves. I only allowed one reduction per branch and even if I reduced two plies if there was a very high material imbalance, that gave me not much and was tactically risky anyway.

Maybe I am wrong, but ply ~9 with a million nodes does not look bad for an engine without LMR. My engine gaviota does not have implemented LMR and behaves that way. If you try to compare your engine with super sophisticad ones, you can come up with wrong conclusions. It is better, IMHO, to compare it with engines at similar degrees of development. Compare the nodes with Fruit 1.0, for instance.

Miguel

What I do in the search is: At the root, I search the first move with an aspiration window of 200 centipawns around alpha. If it fails high or low, I open the window completely and search the first move again. After having searched the first move, I close the window. When a fail-high occurs, I search the move again with an open window. In the tree, I simply do "normal" alpha-beta, which means I take the given window.
I'm not sure if this is optimal because quite often, the engine isn't sure which one of two moves is better, and then fail-highs at the root occur which seems to take some performance.
As move ordering, I take the transposition table move (if available), then the two killer moves and MVV-LVA. I have no history heuristic or anything else than killer moves to order the non-captures because many people say that at today's search depths, history is only a random noise (would it be an idea to only count history moves until a given ply?).

I'm not sure about the different search algorithms, but I think PVS is to do at every node what I do only only at the root (correct me if I am wrong). I have heard that PVS is faster than alpha-beta if over about 90% of first moves in the tree fail high and slower at less than 90%. As my move ordering success is about 80-85% in middlegame, I haven't tried PVS yet.

Any ideas how I could reduce the number of nodes that have to be searched without dramatically increasing tactical risks?

[metax]

With reductions, all you are doing is reducing the remaining depth, correct? And not just throwing the moves away completely???

I _am_ throwing away the moves completely. That's why I didn't call it 'reductions':

...

If you are slow to go deep perhaps you don't prune enough. For instance in Stockfish there is a terribly crude pruning rule that is:

Code: Select all

          // History pruning. See ok_to_prune() definition
          if (   moveCount >= 2 + int(depth)
              && ok_to_prune(pos, move, ss[ply].threatMove, depth)
              && bestValue > value_mated_in(PLY_MAX))
              continue;    // which means I _am_ throwing away the move completely, correct?

This rule it means that if you are for instance at depth 2*OnePly (OnePly in Stockfish is 2) then after the move 2 + 4 = 6 you prune everything !!!!!

The only moves that are not pruned are the ones with a good history so that ok_to_prune() returns false.

You can imagine that with such a rule it is very easy to go deep with search and incredibly (at least for me) search quality doesn't seems to be too badly affected.

In ChessMind, I have even more conditions:

Code: Select all

             if (distance > 0 &&
             moveCount > 2 + distance &&
             !check &&
             !moveGivesCheck // this is actually more complicated, but not important here
             moveList[i].CapturedPiece == EMPTY &&
             bestValue > -MATEVAL + 100)
             {
                  continue;
             }