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.bob wrote: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...
Selective techniques
Moderators: hgm, Rebel, chrisw
-
- Posts: 344
- Joined: Wed Sep 23, 2009 5:56 pm
- Location: Germany
Re: Selective techniques
-
- Posts: 10309
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: Selective techniques
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.metax wrote: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?Uri Blass wrote: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
Uri
-
- Posts: 344
- Joined: Wed Sep 23, 2009 5:56 pm
- Location: Germany
Re: Selective techniques
Maybe Bob could explain that...?
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Selective techniques
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???metax wrote: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.bob wrote: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...
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Selective techniques
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:Uri Blass wrote: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)bob wrote:I reduce everywhere, and prune in the last 4 plies. Crafty still sees this instantly:metax wrote: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...only takes 2 plies and 10 milliseconds (or less, since this is rounded).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#
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.
Uri
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#
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#
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Selective techniques
Already done. "operator error".metax wrote:Maybe Bob could explain that...?
-
- Posts: 344
- Joined: Wed Sep 23, 2009 5:56 pm
- Location: Germany
Re: Selective techniques
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!
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!
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Selective techniques
No clue what you are doing wrong. But here is my output with all reductions and pruning turned on:metax wrote: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!
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
With reductions, all you are doing is reducing the remaining depth, correct? And not just throwing the moves away completely???
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Selective techniques
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.metax wrote: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.
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?
-
- Posts: 344
- Joined: Wed Sep 23, 2009 5:56 pm
- Location: Germany
Re: Selective techniques
I _am_ throwing away the moves completely. That's why I didn't call it 'reductions':bob wrote:With reductions, all you are doing is reducing the remaining depth, correct? And not just throwing the moves away completely???
In ChessMind, I have even more conditions:mcostalba wrote:...
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:
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 !!!!!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?
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.
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;
}