Author: Sune Fischer
Date: 11:41:48 08/26/02
Go up one level in this thread
On August 26, 2002 at 12:52:40, Steffen Basting wrote: >Hello! >Some days ago, I posted about the bad branching factor in my chess program. >Here's the output of the starting position as an example: > >time depth nodes value principal variation >=============================================================================== >0 1 29 10 g1f3 >0 2 127 -6 b1c3 b8c6 >0 3 380 18 b1c3 b8c6 g1f3 >0 4 2141 0 b1c3 g8f6 g1f3 b8c6 >0 5 9174 16 b1c3 b8c6 g1f3 g8f6 e2e4 >1 6 54535 8 b1c3 d7d5 g1f3 b8c6 e2e4 g8f6 >7 7 408066 21 b1c3 d7d5 g1f3 d5d4 c3b5 b8c6 e2e4 >53 8 3220020 18 b1c3 c7c5 e2e4 b8c6 g1f3 e7e5 f1b5 g8e7 > >3220020 nodes, 53 seconds: 59630 nodes/sec >q-nodes: 2944182 evals: 2944182 >value: 18 >my move: b1c3 >principal variation: b1c3 c7c5 e2e4 b8c6 g1f3 e7e5 f1b5 g8e7 Here's the log from my program, I'm trying different things with the move ordering too. Currently I use hashmove, captures sorted by SEE, 2 killers and non-captures sorted by history table (from, to and type indexed), just using from and to sucked. On your positions I get: depth score time nodes pv 2 -9 3 44 1.a3 d5 2 0 3 77 1.d3 d5 2 0 4 126 1.d4 d5 3 11 4 314 1.d4 d6 2.Bd2 4 0 4 555 1.d4 d5 2.Bf4 Bf5 3.Bxe5 5 11 5 4725 1.d4 d5 2.Bf4 Bf5 3.Nc3 Qxc7 6 0 8 15406 1.d4 d5 2.Nc3 Bf5 3.Bf4 Nc6 4.Qxc2 6 1 12 27589 1.e4 e6 2.d4 Bd6 3.Bd2 Nf6 7 10 40 130713 1.e4 e6 2.Nc3 Bd6 3.Be2 Nf6 4.d4 bxa6 8 3 138 509036 1.e4 e6 2.d4 Nc6 3.d5 exd5 4.exd5 Ne5 Move Ordering: 80.68% > >Here's another output of the following position: >1r3rk1/1q4p1/6P1/8/6P1/8/PPP3P1/1K1QR2R w - - 0 1 > >time depth nodes value principal variation >=============================================================================== >0 1 285 441 h1h7 >0 2 609 441 h1h7 b7b2 >0 3 5207 454 d1d4 b7g2 h1h7 >0 4 12194 479 d1d4 >0 4 31061 536 d1d4 b7c6 d4e4 c6e4 >4 5 241205 511 d1d4 >7 5 450249 451 d1d4 f8f4 d4e5 f4g4 e5e6 >12 6 750245 476 d1d4 >22 6 1329714 514 d1d4 f8f4 d4e5 f4f6 h1h7 f6g6 >130 7 7392912 489 d1d4 >7392912 nodes, 130 seconds: 56434 nodes/sec >q-nodes: 7045522 evals: 7045522 >value: 489 2 -299998 3 73 1.a3 Qxb2++ 2 472 3 108 1.b3 Qxg2 3 478 4 632 1.b3 Qc6 2.Re5 Qxg6 3 542 4 1175 1.Qd4 Rbd8 2.Qe4 Rd5 4 472 5 3616 1.Qd4 Rf4 2.Qe5 Rxg4 4 473 6 5975 1.b3 Qxg2 2.Re5 Rb4 3.Qxh1 5 473 9 14430 1.b3 Qxg2 2.Qe2 Qc6 3.Qd3 Qxg6 5 474 13 27365 1.Qd4 Rf4 2.Qe5 Rxg4 3.Qe6+ 6 480 28 80650 1.Qd4 Rf4 2.Qe5 Rf6 3.Rd1 Rxg6 6 299991 37 109397 1.Rh8+ Kxh8 2.Rh1+ Kg8 3.Rh8+ Kxh8 4.Qh1+ Kg8 5.Qh7++ Move Ordering: 99.41% Notice I'm using a few simple extensions, and nullmove (R=2,recursive) so it's not pure alpha-beta. >my move: d1d4 >principal variation: d1d4 >Well, this is a mate in 5. As i do not use check extensions (yet) i am not >surprised that it doesn't find the mate in less than 10 ply. But what I do not >understand is: why does the branching factor grow from about 2 to 7? > > >In this position - (which is from the first game against a human ;-)), however, >it does fine: >2krr3/2pb2pp/1p1p1p2/p2P4/P1P2PP1/1P2R2P/3B4/2KR4 w - - 0 1 > >time depth nodes value principal variation >=============================================================================== >0 1 234 44 e3c3 >1 2 620 46 e3e8 d7e8 >1 3 2221 47 e3e8 d8e8 d1g1 >1 4 6526 40 e3e8 d7e8 d1e1 c7c5 >2 5 44643 45 d1e1 e8e3 e1e3 d8e8 f4f5 >3 6 138710 51 d1e1 e8e3 e1e3 d8e8 e3e8 d7e8 >7 7 446883 47 d1e1 e8e3 e1e3 d8e8 e3e8 d7e8 d2e3 >20 8 1449252 36 d1e1 e8e3 e1e3 d8e8 e3e8 d7e8 f4f5 c7c5 > >1449252 nodes, 20 seconds: 69012 nodes/sec >q-nodes: 1367941 evals: 1367941 >value: 36 >my move: d1e1 >principal variation: d1e1 e8e3 e1e3 d8e8 e3e8 d7e8 f4f5 c7c5 2 -118 3 82 1.b4 Rxe3 2.Bxe3 axb4 2 -101 4 135 1.c5 Rxe3 2.Bxe3 dxc5 2 4 4 171 1.f5 Re5 2.Bxe3 2 5 4 274 1.Rde1 Kb7 2.Rxe3 2 10 4 330 1.Kb1 Kb7 2.Bxe3 3 10 4 696 1.Kb1 Kb7 2.f5 Rxe3 3.Bxe3 4 3 5 1871 1.Kb1 Rxe3 2.Bxe3 Re8 3.bxa4 5 2 6 5419 1.Kb1 Rxe3 2.Bxe3 Re8 3.Bd4 cxb6 5 4 8 11003 1.Rde1 Rxe3 2.Rxe3 Re8 3.f5 Rxe3 4.Bxe3 6 8 12 30201 1.Rde1 Rxe3 2.Rxe3 Re8 3.Rxe8+ Bxe8 4.Kb1 7 3 20 60253 1.Rde1 Rxe3 2.Rxe3 Re8 3.Rxe8+ Bxe8 4.Kb1 Kb8 5.bxa4 8 3 55 215059 1.Rde1 Rxe3 2.Rxe3 h5 3.Re7 hxg4 4.hxg4 Bxg4 5.Rxg7 Move Ordering: 89.78% I have several drops below 90% on the move ordering, perhaps this is not surprising when the history table is almost empty. In a game or if I run a longer analysis it should kick in a bit more. I'm still not happy about it, the history table is not good enough IMO, I tried running some test suites today, there were some improvements, but also a few bad results. The extra time spent sorting the moves is not always worth it, or at least the history ordering is not good enough to be worth while. I'm considering IID or perhaps I will try the losing captures last and equal captures along with the non-captures. >If you have a look at the q-nodes and evals, they're always the same. Is this >normal behaviour if you call eval from the quiescence search? Does it mean that >all higher plies are always extended with qsearch? Why are there so few "normal" >positions searched, but so many q-nodes?! I get that too, my qsearch is almost 8/10th of the nodes searched, this is way too much I think. I'm even sorting by SEE and culling the losing captures, so I would expect it down around the 50%, but it never is. >And is this strange branching factor due to a bad move ordering? Absolutely, even if you can improve it slightly from say 80% to 85% efficiency you can save _a lot_. >PS: (as reply to Dann Corbit) I don't use hashtables (yet) :-) They will help :) -S.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.