Hi,
My engine has and average branching factor between 3 and 4,5. As I have read this is quit bad compared with good engines that may be between 2 and 3.
Last year I have implemented all typical features (eval, IID, SEE, Hast table, Null move, lazy eval, etc etc.) and until now I am lucky because have no bugs. During this time I have tryed to speed up code, but now I am unable to get more speed. Profile output now dont show bottle-necks or big time-consuming functions. So now my main problem is how to reduce the braching factor, as that could improve nps.
Now, I am lost. What would you do to improve BF? what strategy can I follow? what are most important indexs and test to examine? In terms of speed, I see profile output, but for BF improve I dont exactly what to look.
Any help will be wellcome.
FS
Reducing branching factor
Moderator: Ras
-
Kempelen
- Posts: 620
- Joined: Fri Feb 08, 2008 10:44 am
- Location: Madrid - Spain
-
Harald Johnsen
Re: Reducing branching factor
What about the quality of the move ordering ?
One way to look at it is to count the percentage of cutoffs you had on the first move examined in all positions. I think that this percentage sould be at least 90% for a 'good' ordering (at least but you'll never have more than say 95%).
If you have like 80% or 85% then there is a lot of room for improvement.
You are supposed to have (a lot of) cuttofs from the hash move and from winning captures. Verify that the hash move you store in the hash table is correct and not zeroed if you overwrite the position from an all node.
Verify that your winning captures are sorted first.
If the move ordering is ok and still have lot of nodes then perhaps something else is wrong like :
- null move not triggered ?
- fat quiescent search ?
- hash table stuffed with wrong score bounds ?
- pvs or window search bugged ?
- forgot lmr or futility pruning ?
HJ.
One way to look at it is to count the percentage of cutoffs you had on the first move examined in all positions. I think that this percentage sould be at least 90% for a 'good' ordering (at least but you'll never have more than say 95%).
If you have like 80% or 85% then there is a lot of room for improvement.
You are supposed to have (a lot of) cuttofs from the hash move and from winning captures. Verify that the hash move you store in the hash table is correct and not zeroed if you overwrite the position from an all node.
Verify that your winning captures are sorted first.
If the move ordering is ok and still have lot of nodes then perhaps something else is wrong like :
- null move not triggered ?
- fat quiescent search ?
- hash table stuffed with wrong score bounds ?
- pvs or window search bugged ?
- forgot lmr or futility pruning ?
HJ.
-
Kempelen
- Posts: 620
- Joined: Fri Feb 08, 2008 10:44 am
- Location: Madrid - Spain
Re: Reducing branching factor
I have a few datas which maybe of interest (level set to 'sd 8'):
1) "rnbq3r/ppp3pp/6k1/2bpP3/8/2PQ4/PP3PPP/RN2K1NR b KQ - 0 1"
Nodes: 222298 (68.9%q), 127KNPS, EBF: 4.3, Evals: 118360, Hash hits: 21.5%
Null move attempts: 26511, Null Move Hits: 17060 (64.4%)
Mov order hits: 1 (82.7%) 2 (10.7%) 3 (2.2%) ...N (4.4%)
Time for this position: 1.765 secs.
2) "r1bq4/1p4kp/3p1n2/p4pB1/2pQ4/8/1P4PP/4RRK1 w - - bm Re8"
Nodes: 959772 (65.2%q), 157KNPS, EBF: 3.8, Evals: 511527, Hash hits: 18.9%
Null move attempts: 38382, Null Move Hits: 24953 (65.0%)
Mov order hits: 1 (89.4%) 2 (6.5%) 3 (1.3%) ...N (2.8%)
Time for this position: 6.140 secs.
3) "r3k2r/2p2p2/p2p1n2/1p2p3/4P2p/1PPPPp1q/1P5P/R1N2QRK b kq - bm Ng4"
Nodes: 2387573 (53.8%q), 177KNPS, EBF: 3.8, Evals: 954420, Hash hits: 10.6%
Null move attempts: 148554, Null Move Hits: 83459 (56.2%)
Mov order hits: 1 (80.9%) 2 (9.9%) 3 (4.2%) ...N (5.0%)
Time for this position: 13.593 secs.
4) "r6k/pp3p1p/2p1bp1q/b3p3/4Pnr1/2PP2NP/PP1Q1PPN/R2B2RK b - - bm Nxh3"
Nodes: 187905 (77.6%q), 100KNPS, EBF: 2.6, Evals: 136468, Hash hits: 19.4%
Null move attempts: 24528, Null Move Hits: 17912 (73.0%)
Mov order hits: 1 (71.7%) 2 (18.5%) 3 (6.1%) ...N (3.6%)
Time for this position: 2.078 secs.
5) "4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/3B1P2/PP3PK1/2Q4R w - - bm Qxf4"
Nodes: 510533 (53.3%q), 180KNPS, EBF: 4.0, Evals: 241275, Hash hits: 6.4%
Null move attempts: 35276, Null Move Hits: 21641 (61.3%)
Mov order hits: 1 (85.3%) 2 (8.8%) 3 (2.0%) ...N (4.0%)
Time for this position: 3.031 secs.
6) "2r3k1/1qr1b1p1/p2pPn2/nppPp3/8/1PP1B2P/P1BQ1P2/5KRR w - - bm Rxg7+"
Nodes: 704392 (68.9%q), 130KNPS, EBF: 3.4, Evals: 381607, Hash hits: 21.0%
Null move attempts: 75398, Null Move Hits: 50032 (66.4%)
Mov order hits: 1 (74.6%) 2 (16.6%) 3 (4.5%) ...N (4.3%)
Time for this position: 5.578 secs.
7) "2r3k1/pbr1q2p/1p2pnp1/3p4/3P1P2/1P1BR3/PB1Q2PP/5RK1 w - - bm f5"
Nodes: 151930 (72.1%q), 109KNPS, EBF: 2.8, Evals: 96725, Hash hits: 27.6%
Null move attempts: 22192, Null Move Hits: 16635 (75.0%)
Mov order hits: 1 (90.5%) 2 (6.1%) 3 (1.7%) ...N (1.8%)
Time for this position: 1.485 secs.
8) "6k1/p4pq1/2n1p1p1/1p1pP1N1/3P1QPP/8/P3K3/8 w - - bm Qc1"
Nodes: 407561 (57.3%q), 148KNPS, EBF: 3.1, Evals: 205024, Hash hits: 23.0%
Null move attempts: 21559, Null Move Hits: 11741 (54.5%)
Mov order hits: 1 (92.5%) 2 (4.6%) 3 (0.7%) ...N (2.1%)
Time for this position: 2.781 secs.
9) "q1r3k1/2r4p/2p3pP/2Qp1p2/PRn5/4P1P1/5PB1/1R4K1 w - - bm Rxc4"
Nodes: 702940 (69.6%q), 130KNPS, EBF: 3.5, Evals: 433327, Hash hits: 20.6%
Null move attempts: 69756, Null Move Hits: 48193 (69.1%)
Mov order hits: 1 (89.2%) 2 (7.2%) 3 (1.6%) ...N (2.1%)
Time for this position: 5.609 secs.
10) "1rb3k1/2r2pbp/p2q1npn/P1pPp1N1/2B1P3/2P1B1NP/5QP1/3R1RK1 w - - bm Ne6"
Nodes: 203419 (76.4%q), 110KNPS, EBF: 2.6, Evals: 136694, Hash hits: 19.8%
Null move attempts: 25497, Null Move Hits: 17947 (70.4%)
Mov order hits: 1 (86.4%) 2 (9.7%) 3 (2.8%) ...N (1.2%)
Time for this position: 2.047 secs.
NOTE: If I change eval function to pieze-square-table+material the nps doubles, but with it, looks like nps is very slow.
Does anybody with more experience than me suppose where slow-nps ratio come from? any advice?
1) "rnbq3r/ppp3pp/6k1/2bpP3/8/2PQ4/PP3PPP/RN2K1NR b KQ - 0 1"
Nodes: 222298 (68.9%q), 127KNPS, EBF: 4.3, Evals: 118360, Hash hits: 21.5%
Null move attempts: 26511, Null Move Hits: 17060 (64.4%)
Mov order hits: 1 (82.7%) 2 (10.7%) 3 (2.2%) ...N (4.4%)
Time for this position: 1.765 secs.
2) "r1bq4/1p4kp/3p1n2/p4pB1/2pQ4/8/1P4PP/4RRK1 w - - bm Re8"
Nodes: 959772 (65.2%q), 157KNPS, EBF: 3.8, Evals: 511527, Hash hits: 18.9%
Null move attempts: 38382, Null Move Hits: 24953 (65.0%)
Mov order hits: 1 (89.4%) 2 (6.5%) 3 (1.3%) ...N (2.8%)
Time for this position: 6.140 secs.
3) "r3k2r/2p2p2/p2p1n2/1p2p3/4P2p/1PPPPp1q/1P5P/R1N2QRK b kq - bm Ng4"
Nodes: 2387573 (53.8%q), 177KNPS, EBF: 3.8, Evals: 954420, Hash hits: 10.6%
Null move attempts: 148554, Null Move Hits: 83459 (56.2%)
Mov order hits: 1 (80.9%) 2 (9.9%) 3 (4.2%) ...N (5.0%)
Time for this position: 13.593 secs.
4) "r6k/pp3p1p/2p1bp1q/b3p3/4Pnr1/2PP2NP/PP1Q1PPN/R2B2RK b - - bm Nxh3"
Nodes: 187905 (77.6%q), 100KNPS, EBF: 2.6, Evals: 136468, Hash hits: 19.4%
Null move attempts: 24528, Null Move Hits: 17912 (73.0%)
Mov order hits: 1 (71.7%) 2 (18.5%) 3 (6.1%) ...N (3.6%)
Time for this position: 2.078 secs.
5) "4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/3B1P2/PP3PK1/2Q4R w - - bm Qxf4"
Nodes: 510533 (53.3%q), 180KNPS, EBF: 4.0, Evals: 241275, Hash hits: 6.4%
Null move attempts: 35276, Null Move Hits: 21641 (61.3%)
Mov order hits: 1 (85.3%) 2 (8.8%) 3 (2.0%) ...N (4.0%)
Time for this position: 3.031 secs.
6) "2r3k1/1qr1b1p1/p2pPn2/nppPp3/8/1PP1B2P/P1BQ1P2/5KRR w - - bm Rxg7+"
Nodes: 704392 (68.9%q), 130KNPS, EBF: 3.4, Evals: 381607, Hash hits: 21.0%
Null move attempts: 75398, Null Move Hits: 50032 (66.4%)
Mov order hits: 1 (74.6%) 2 (16.6%) 3 (4.5%) ...N (4.3%)
Time for this position: 5.578 secs.
7) "2r3k1/pbr1q2p/1p2pnp1/3p4/3P1P2/1P1BR3/PB1Q2PP/5RK1 w - - bm f5"
Nodes: 151930 (72.1%q), 109KNPS, EBF: 2.8, Evals: 96725, Hash hits: 27.6%
Null move attempts: 22192, Null Move Hits: 16635 (75.0%)
Mov order hits: 1 (90.5%) 2 (6.1%) 3 (1.7%) ...N (1.8%)
Time for this position: 1.485 secs.
8) "6k1/p4pq1/2n1p1p1/1p1pP1N1/3P1QPP/8/P3K3/8 w - - bm Qc1"
Nodes: 407561 (57.3%q), 148KNPS, EBF: 3.1, Evals: 205024, Hash hits: 23.0%
Null move attempts: 21559, Null Move Hits: 11741 (54.5%)
Mov order hits: 1 (92.5%) 2 (4.6%) 3 (0.7%) ...N (2.1%)
Time for this position: 2.781 secs.
9) "q1r3k1/2r4p/2p3pP/2Qp1p2/PRn5/4P1P1/5PB1/1R4K1 w - - bm Rxc4"
Nodes: 702940 (69.6%q), 130KNPS, EBF: 3.5, Evals: 433327, Hash hits: 20.6%
Null move attempts: 69756, Null Move Hits: 48193 (69.1%)
Mov order hits: 1 (89.2%) 2 (7.2%) 3 (1.6%) ...N (2.1%)
Time for this position: 5.609 secs.
10) "1rb3k1/2r2pbp/p2q1npn/P1pPp1N1/2B1P3/2P1B1NP/5QP1/3R1RK1 w - - bm Ne6"
Nodes: 203419 (76.4%q), 110KNPS, EBF: 2.6, Evals: 136694, Hash hits: 19.8%
Null move attempts: 25497, Null Move Hits: 17947 (70.4%)
Mov order hits: 1 (86.4%) 2 (9.7%) 3 (2.8%) ...N (1.2%)
Time for this position: 2.047 secs.
NOTE: If I change eval function to pieze-square-table+material the nps doubles, but with it, looks like nps is very slow.
Does anybody with more experience than me suppose where slow-nps ratio come from? any advice?
-
michiguel
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Reducing branching factor
Fermin, what hardware are you using?Kempelen wrote:I have a few datas which maybe of interest (level set to 'sd 8'):
1) "rnbq3r/ppp3pp/6k1/2bpP3/8/2PQ4/PP3PPP/RN2K1NR b KQ - 0 1"
Nodes: 222298 (68.9%q), 127KNPS, EBF: 4.3, Evals: 118360, Hash hits: 21.5%
Null move attempts: 26511, Null Move Hits: 17060 (64.4%)
Mov order hits: 1 (82.7%) 2 (10.7%) 3 (2.2%) ...N (4.4%)
Time for this position: 1.765 secs.
2) "r1bq4/1p4kp/3p1n2/p4pB1/2pQ4/8/1P4PP/4RRK1 w - - bm Re8"
Nodes: 959772 (65.2%q), 157KNPS, EBF: 3.8, Evals: 511527, Hash hits: 18.9%
Null move attempts: 38382, Null Move Hits: 24953 (65.0%)
Mov order hits: 1 (89.4%) 2 (6.5%) 3 (1.3%) ...N (2.8%)
Time for this position: 6.140 secs.
3) "r3k2r/2p2p2/p2p1n2/1p2p3/4P2p/1PPPPp1q/1P5P/R1N2QRK b kq - bm Ng4"
Nodes: 2387573 (53.8%q), 177KNPS, EBF: 3.8, Evals: 954420, Hash hits: 10.6%
Null move attempts: 148554, Null Move Hits: 83459 (56.2%)
Mov order hits: 1 (80.9%) 2 (9.9%) 3 (4.2%) ...N (5.0%)
Time for this position: 13.593 secs.
4) "r6k/pp3p1p/2p1bp1q/b3p3/4Pnr1/2PP2NP/PP1Q1PPN/R2B2RK b - - bm Nxh3"
Nodes: 187905 (77.6%q), 100KNPS, EBF: 2.6, Evals: 136468, Hash hits: 19.4%
Null move attempts: 24528, Null Move Hits: 17912 (73.0%)
Mov order hits: 1 (71.7%) 2 (18.5%) 3 (6.1%) ...N (3.6%)
Time for this position: 2.078 secs.
5) "4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/3B1P2/PP3PK1/2Q4R w - - bm Qxf4"
Nodes: 510533 (53.3%q), 180KNPS, EBF: 4.0, Evals: 241275, Hash hits: 6.4%
Null move attempts: 35276, Null Move Hits: 21641 (61.3%)
Mov order hits: 1 (85.3%) 2 (8.8%) 3 (2.0%) ...N (4.0%)
Time for this position: 3.031 secs.
6) "2r3k1/1qr1b1p1/p2pPn2/nppPp3/8/1PP1B2P/P1BQ1P2/5KRR w - - bm Rxg7+"
Nodes: 704392 (68.9%q), 130KNPS, EBF: 3.4, Evals: 381607, Hash hits: 21.0%
Null move attempts: 75398, Null Move Hits: 50032 (66.4%)
Mov order hits: 1 (74.6%) 2 (16.6%) 3 (4.5%) ...N (4.3%)
Time for this position: 5.578 secs.
7) "2r3k1/pbr1q2p/1p2pnp1/3p4/3P1P2/1P1BR3/PB1Q2PP/5RK1 w - - bm f5"
Nodes: 151930 (72.1%q), 109KNPS, EBF: 2.8, Evals: 96725, Hash hits: 27.6%
Null move attempts: 22192, Null Move Hits: 16635 (75.0%)
Mov order hits: 1 (90.5%) 2 (6.1%) 3 (1.7%) ...N (1.8%)
Time for this position: 1.485 secs.
8) "6k1/p4pq1/2n1p1p1/1p1pP1N1/3P1QPP/8/P3K3/8 w - - bm Qc1"
Nodes: 407561 (57.3%q), 148KNPS, EBF: 3.1, Evals: 205024, Hash hits: 23.0%
Null move attempts: 21559, Null Move Hits: 11741 (54.5%)
Mov order hits: 1 (92.5%) 2 (4.6%) 3 (0.7%) ...N (2.1%)
Time for this position: 2.781 secs.
9) "q1r3k1/2r4p/2p3pP/2Qp1p2/PRn5/4P1P1/5PB1/1R4K1 w - - bm Rxc4"
Nodes: 702940 (69.6%q), 130KNPS, EBF: 3.5, Evals: 433327, Hash hits: 20.6%
Null move attempts: 69756, Null Move Hits: 48193 (69.1%)
Mov order hits: 1 (89.2%) 2 (7.2%) 3 (1.6%) ...N (2.1%)
Time for this position: 5.609 secs.
10) "1rb3k1/2r2pbp/p2q1npn/P1pPp1N1/2B1P3/2P1B1NP/5QP1/3R1RK1 w - - bm Ne6"
Nodes: 203419 (76.4%q), 110KNPS, EBF: 2.6, Evals: 136694, Hash hits: 19.8%
Null move attempts: 25497, Null Move Hits: 17947 (70.4%)
Mov order hits: 1 (86.4%) 2 (9.7%) 3 (2.8%) ...N (1.2%)
Time for this position: 2.047 secs.
NOTE: If I change eval function to pieze-square-table+material the nps doubles, but with it, looks like nps is very slow.
Does anybody with more experience than me suppose where slow-nps ratio come from? any advice?
Miguel
-
Dann Corbit
- Posts: 12778
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Reducing branching factor
Most of the very successful ways to reduce branching factor are reduction or pruning techniques.Kempelen wrote:Hi,
My engine has and average branching factor between 3 and 4,5. As I have read this is quit bad compared with good engines that may be between 2 and 3.
Last year I have implemented all typical features (eval, IID, SEE, Hast table, Null move, lazy eval, etc etc.) and until now I am lucky because have no bugs. During this time I have tryed to speed up code, but now I am unable to get more speed. Profile output now dont show bottle-necks or big time-consuming functions. So now my main problem is how to reduce the braching factor, as that could improve nps.
Now, I am lost. What would you do to improve BF? what strategy can I follow? what are most important indexs and test to examine? In terms of speed, I see profile output, but for BF improve I dont exactly what to look.
Any help will be wellcome.
FS
Actually, the basic idea is very simple and very sound. Suppose that I set my queen into attack by your pawn. This is unlikely to be a good move (though, of course, it is also possible that it is the only winning move). On the other hand, suppose that I can capture your queen with my pawn. This is likely to be a very good move (though it is also possible that it is the only move that loses the game). The obvious outcome of situations like this is that it is clear we should not search the two situations in exactly the same way. So the question arises, how much should we reduce various moves? What happens if we are zugzwang at the moment?
I actually find nearly every current pruning scheme to be somewhat distasteful, because they are so herky-jerky. What I mean is that bad moves cause sudden, large reductions but somewhat less bad moves may cause no reductions at all. I would like to see a smooth and continuous scheme (though I doubt that the relation should be linear).
Anyway, the programs with the best branching factors all use reductions or pruning techniques. Of course, you already have null move, which is one of the most powerful. For the other techniques, I suggest this link, which appears to be very well done to me:
http://chessprogramming.wikispaces.com/Reductions
-
Harald Johnsen
Re: Reducing branching factor
1) info depth 8 seldepth 19 score cp 256 time 10 nodes 56352 pv c8f5 d3g3 d8g5 g3g5 g6g5 g1f3 g5h6 f3d4 f5e4 f2f3 e4d3 b1d2
Hcut=1302 hits 1 (89.1%) 1..5 (98.8%) inQS=42263
nm1=2894 nmb=2204 nmr=22 ex+=2354
2) info depth 8 seldepth 28 score cp 1276 time 37 nodes 267661 pv e1e8 h7h6 g5h6 g7h6 e8d8 h6g6 d8d6 g6h7 d6f6 b7b5 f6f7 h7h6
Hcut=3587 Hits 1 (89.5%) 1..5 (97.8%) inQS=229002
nm1=7844 nmb=7114 nmr=41 ex+=10543
3) info depth 8 seldepth 16 score cp 726 time 6 nodes 38825 pv f6g4 g1g2 f3g2 f1g2 h8g8 c1e2 h3e3 a1f1 e3d3 b3b4
Hcut=701 Hits 1 (91.1%) 1..5 (99.0%) inQS=29432
nm1=2522 nmb=2197 nmr=40 ex+=1265
4) info depth 8 seldepth 14 score cp 390 time 7 nodes 39689 pv f4h3 d1g4 h6d2 g2h3 d2b2 g4e6 f7e6 a1b1 b2f2 b1b7 a5c3
Hcut=654 Hits 1 (89.1%) 1..5 (98.8%) inQS=30432
nm1=3944 nmb=3075 nmr=35 ex+=339
5) info depth 8 seldepth 19 score mate 6 time 65 nodes 376957 pv c1f4 d6e7 h4h5 e7f6 f4f6 g6h5 h1h5 c7h2 g2h2 d7d5 h5h8
Hcut=6106 Hits 1 (72.2%) 1..5 (96.8%) inQS=312977
nm1=6212 nmb=4000 nmr=4 ex+=12415
6) info depth 8 seldepth 20 score cp -128 time 29 nodes 153373 pv c3c4 a5c4 b3c4 b5c4 e3h6 e7d8 f2f4 b7d5 d2d5 f6d5 f4e5 d6e5 h1h2
info depth 8 seldepth 32 score cp 244 time 93 nodes 551016 pv g1g7 g8f8 h1g1 e7d8 g7g8 f6g8 e3h6 c7g7 h6g7 b7g7 g1g7 f8g7 f2f4 e5f4 d2f4 d8e7
Hcut=5899 Hits 1 (86.1%) 1..5 (98.1%) inQS=444582
nm1=21464 nmb=18169 nmr=133 ex+=24130
7) info depth 8 seldepth 16 score cp 86 time 15 nodes 90861 pv f4f5 f6e4 d3e4 d5e4 f5f6 e7d6 e3h3 g8h8 f6f7 b7d5
Hcut=4015 Hits 1 (93.7%) 1..5 (99.1%) inQS=64607
nm1=8284 nmb=6927 nmr=45 ex+=1747
8) info depth 8 seldepth 16 score cp -68 time 15 nodes 108222 pv f4c1 c6d4 e2d3 g7e5 c1c8 g8g7 c8h8 g7h8 g5f7 h8g7 f7e5 d4f5 g4f5 g6f5 d3d4
Hcut=2157 Hits 1 (90.5%) 1..5 (98.2%) inQS=86715
nm1=4579 nmb=3062 nmr=14 ex+=2803
9) info depth 8 seldepth 24 score cp 194 time 18 nodes 116236 pv b4c4 d5c4 g2f1 c7f7 f1c4 c8e8 c4f7 g8f7 c5c4 f7f6 b1d1 c6c5 d1d6 f6e7 c4c5 a8a4
Hcut=2561 Hits 1 (90.1%) 1..5 (98.0%) inQS=90285
nm1=6201 nmb=4846 nmr=69 ex+=3488
10) info depth 8 seldepth 22 score cp 232 time 34 nodes 161250 pv g5f3 c8b7 f3h4 f6d7 f2d2 d6f8 d5d6 c7c8
Hcut=4953 Hist 1 (95.6%) 1..5 (99.3%) inQS=118798
nm1=9143 nmb=6899 nmr=27 ex+=1723
Hcut:number of hash table cuttoffs, hits 1:% of cuttoffs on first move, 1..5:percentage of cuttoff on first 5 moves
nm1:null move attemps, nmb:null move hit, nmr:null move research, ex+:check extension count
I see that all those positions are tactical ones, i don't think that you can tune your move ordering on them.
HJ.
Hcut=1302 hits 1 (89.1%) 1..5 (98.8%) inQS=42263
nm1=2894 nmb=2204 nmr=22 ex+=2354
2) info depth 8 seldepth 28 score cp 1276 time 37 nodes 267661 pv e1e8 h7h6 g5h6 g7h6 e8d8 h6g6 d8d6 g6h7 d6f6 b7b5 f6f7 h7h6
Hcut=3587 Hits 1 (89.5%) 1..5 (97.8%) inQS=229002
nm1=7844 nmb=7114 nmr=41 ex+=10543
3) info depth 8 seldepth 16 score cp 726 time 6 nodes 38825 pv f6g4 g1g2 f3g2 f1g2 h8g8 c1e2 h3e3 a1f1 e3d3 b3b4
Hcut=701 Hits 1 (91.1%) 1..5 (99.0%) inQS=29432
nm1=2522 nmb=2197 nmr=40 ex+=1265
4) info depth 8 seldepth 14 score cp 390 time 7 nodes 39689 pv f4h3 d1g4 h6d2 g2h3 d2b2 g4e6 f7e6 a1b1 b2f2 b1b7 a5c3
Hcut=654 Hits 1 (89.1%) 1..5 (98.8%) inQS=30432
nm1=3944 nmb=3075 nmr=35 ex+=339
5) info depth 8 seldepth 19 score mate 6 time 65 nodes 376957 pv c1f4 d6e7 h4h5 e7f6 f4f6 g6h5 h1h5 c7h2 g2h2 d7d5 h5h8
Hcut=6106 Hits 1 (72.2%) 1..5 (96.8%) inQS=312977
nm1=6212 nmb=4000 nmr=4 ex+=12415
6) info depth 8 seldepth 20 score cp -128 time 29 nodes 153373 pv c3c4 a5c4 b3c4 b5c4 e3h6 e7d8 f2f4 b7d5 d2d5 f6d5 f4e5 d6e5 h1h2
info depth 8 seldepth 32 score cp 244 time 93 nodes 551016 pv g1g7 g8f8 h1g1 e7d8 g7g8 f6g8 e3h6 c7g7 h6g7 b7g7 g1g7 f8g7 f2f4 e5f4 d2f4 d8e7
Hcut=5899 Hits 1 (86.1%) 1..5 (98.1%) inQS=444582
nm1=21464 nmb=18169 nmr=133 ex+=24130
7) info depth 8 seldepth 16 score cp 86 time 15 nodes 90861 pv f4f5 f6e4 d3e4 d5e4 f5f6 e7d6 e3h3 g8h8 f6f7 b7d5
Hcut=4015 Hits 1 (93.7%) 1..5 (99.1%) inQS=64607
nm1=8284 nmb=6927 nmr=45 ex+=1747
8) info depth 8 seldepth 16 score cp -68 time 15 nodes 108222 pv f4c1 c6d4 e2d3 g7e5 c1c8 g8g7 c8h8 g7h8 g5f7 h8g7 f7e5 d4f5 g4f5 g6f5 d3d4
Hcut=2157 Hits 1 (90.5%) 1..5 (98.2%) inQS=86715
nm1=4579 nmb=3062 nmr=14 ex+=2803
9) info depth 8 seldepth 24 score cp 194 time 18 nodes 116236 pv b4c4 d5c4 g2f1 c7f7 f1c4 c8e8 c4f7 g8f7 c5c4 f7f6 b1d1 c6c5 d1d6 f6e7 c4c5 a8a4
Hcut=2561 Hits 1 (90.1%) 1..5 (98.0%) inQS=90285
nm1=6201 nmb=4846 nmr=69 ex+=3488
10) info depth 8 seldepth 22 score cp 232 time 34 nodes 161250 pv g5f3 c8b7 f3h4 f6d7 f2d2 d6f8 d5d6 c7c8
Hcut=4953 Hist 1 (95.6%) 1..5 (99.3%) inQS=118798
nm1=9143 nmb=6899 nmr=27 ex+=1723
Hcut:number of hash table cuttoffs, hits 1:% of cuttoffs on first move, 1..5:percentage of cuttoff on first 5 moves
nm1:null move attemps, nmb:null move hit, nmr:null move research, ex+:check extension count
I see that all those positions are tactical ones, i don't think that you can tune your move ordering on them.
HJ.
-
Dann Corbit
- Posts: 12778
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Reducing branching factor
p.s.
NPS is a red herring. For that matter, a good hash table implementation will make your search a lot better but you will probably see a drop in NPS.
Branching factor is far, far more important than NPS.
If you can both double your move generation speed and your evaluation speed or you can reduce your branching factor from 4 to 2, the branching factor is a gift that keeps on giving at each new ply, but the other speedups are just a constant linear factor.
Of course, just reducing branching factor is not necessarily a benefit. You can have a branching factor of 1.0 if you only consider the first move in your move list. But that program will play crappy chess. The real trick of it is to spend less energy on the bad moves and more energy on the good moves. So the programs that get a branching factor of 2, and yet the moves they look hardes at tend to be the best moves almost all the time -- those are the fire breathing dragons.
NPS is a red herring. For that matter, a good hash table implementation will make your search a lot better but you will probably see a drop in NPS.
Branching factor is far, far more important than NPS.
If you can both double your move generation speed and your evaluation speed or you can reduce your branching factor from 4 to 2, the branching factor is a gift that keeps on giving at each new ply, but the other speedups are just a constant linear factor.
Of course, just reducing branching factor is not necessarily a benefit. You can have a branching factor of 1.0 if you only consider the first move in your move list. But that program will play crappy chess. The real trick of it is to spend less energy on the bad moves and more energy on the good moves. So the programs that get a branching factor of 2, and yet the moves they look hardes at tend to be the best moves almost all the time -- those are the fire breathing dragons.
-
bob
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Reducing branching factor
LMR and any other sort of pruning approach (futility, razoring, extended futility, etc) will drop the branching factor...Kempelen wrote:Hi,
My engine has and average branching factor between 3 and 4,5. As I have read this is quit bad compared with good engines that may be between 2 and 3.
Last year I have implemented all typical features (eval, IID, SEE, Hast table, Null move, lazy eval, etc etc.) and until now I am lucky because have no bugs. During this time I have tryed to speed up code, but now I am unable to get more speed. Profile output now dont show bottle-necks or big time-consuming functions. So now my main problem is how to reduce the braching factor, as that could improve nps.
Now, I am lost. What would you do to improve BF? what strategy can I follow? what are most important indexs and test to examine? In terms of speed, I see profile output, but for BF improve I dont exactly what to look.
Any help will be wellcome.
FS
-
Kempelen
- Posts: 620
- Joined: Fri Feb 08, 2008 10:44 am
- Location: Madrid - Spain
Re: Reducing branching factor
Pentium 4 at 3.2Ghz, 2GB memory
-
Kempelen
- Posts: 620
- Joined: Fri Feb 08, 2008 10:44 am
- Location: Madrid - Spain
Re: Reducing branching factor
Idem as having hash hits or null move success hits, I am calculating % of nodes which are reduced or extended.
Of the total nodes (excluding quiesce nodes, as there I dont use extension), I am getting around 2% of total nodes are extended and arund 1% reduced.
These datas sound very few for me.
What are good % for extensions and reduccions, in average?
thx.
Of the total nodes (excluding quiesce nodes, as there I dont use extension), I am getting around 2% of total nodes are extended and arund 1% reduced.
These datas sound very few for me.
What are good % for extensions and reduccions, in average?
thx.