Author: Uri Blass
Date: 12:14:48 09/05/01
Go up one level in this thread
On September 05, 2001 at 12:46:29, Adam Oellermann wrote: >On September 05, 2001 at 12:15:37, Uri Blass wrote: > >>On September 05, 2001 at 07:53:50, guy haworth wrote: >> >>> >>>In the Ken-Thompson-themed ICGA Journal (June, 2001), Ernst Heinz published his >>>latest self-play experiment results. >>> >>>Engines with different guaranteed-depth(?)-parameters were pitted against each >>>other. >>> >>>The matches of the experimetn (3,000 games each) suggest that: >>> >>> 12-ply was 84 ELO points better than 11 ply >>> 11-ply was 92 ELO points better than 10 ply >>> 10-ply was 115 ELO points better than 9 ply >>> >>>Fairly strong indications of decreasing returns from increasing search. No >>>doubt a proper statistical analysis will follow. >>> >>> >>>An extra ply seems to require 4-6 times the 'effective power', so a factor of 36 >>>- if realised across the system - is only 2 plies. >> >>I know that the top programs of today have usually branching factor that is >>close to 3 and not 4-6 so a factor of 36 is more than 3 plies. > >Ernst Heinz probably used Dark Thought for this research - while perhaps not a >top program these days, I reckon it's branching factor must be comparable to the >top programs. The article didn't say that the branching factor was 3, but that >the "effective power" (I'm guessing CPU time and memory utilisation are factors >in "effective power"), determined empirically, required for an extra ply is 4 - >6. >> >>I also know that based on the ssdf results 70 elo per doubling the speed makes >>more sense. >> >>70 elo per doubling means something like 110 elo per ply. >>84 elo per ply when going from 11 plies to 12 plies seems to be wrong because >>the programs in the ssdf games get deeper than 12 plies. > >He's not saying 84 elo per ply; he's saying that once you hit 11 ply, the next >ply will buy you around 84 elo. > >>Uri > >I think discounting the results published by Ernst Heinz because of the SSDF's >figures is dangerous. The SSDF, after all, is an experiment to test relative >performance of different chess engines. Ernst Heinz's experiment is clearly >designed to determine the performance improvements obtained by increased search >depth, and in this domain his data are probably more accurate than SSDF figures. > >- Adam There are other possible explanations. Maybe my assumption that 70 elo per doubling means more than 100 elo per ply is wrong. I used the assumption that the average branching factor is 3 but maybe the average branching factor is smaller and even if it is 3 the average branching factor may be misleading and maybe being exactly 3 times faster when it sometimes earns 2 plies and sometimes earns 0 plies gives better result than a constant 1 ply. It is also possible that the improvement is bigger than the speed difference because the faster machine is more often correct in pondering. My impression is that the main mistake here is assuming that the branching factor of deep Fritz is 3. I believe that in important cases the branching factor of Deep Fritz is smaller than 2 and here is an example from Deeper blue-kasparov match. Note that Deep Fritz can find 44.Kh1 that is winning in 550 seconds on pentium800 and it means that it can find it at tournament time control on fast hardware. Other top programs like Junior and tiger are even faster than Deep Fritz. Deeper blue could not find Kh1 in the game. [D]R7/1r3kp1/1qQb1p1p/1p1PpP2/1Pp1B3/2P4P/6P1/6K1 w - - 0 1 Analysis by Deep Fritz: 44.Qxb6 Rxb6 45.Ra7+ Kf8 ± (0.94) Depth: 2/7 00:00:00 44.Qxb6 Rxb6 45.Ra7+ Kf8 ± (0.94) Depth: 2/7 00:00:00 44.Qxb6 Rxb6 45.Ra7+ Kf8 ± (0.94) Depth: 2/7 00:00:00 44.Qxb6 Rxb6 45.Ra7+ Kf8 46.Kf2 ± (1.13) Depth: 3/9 00:00:00 44.Qxb6 Rxb6 45.Ra7+ Kg8 46.Kf2 Kh7 ± (1.03) Depth: 4/9 00:00:00 44.Qxb6 Rxb6 45.Ra7+ Be7 46.Kf2 Rd6 47.g3 ± (0.84) Depth: 5/11 00:00:00 2kN 44.Kf1! ± (0.88) Depth: 5/12 00:00:00 3kN 44.Kf1! Qxc6 45.dxc6 Rc7 46.Ra5 Ke7 47.Rxb5 ± (1.28) Depth: 5/13 00:00:00 5kN 44.Kf1 Qxc6 45.dxc6 Rc7 46.Ra5 Ke7 47.Rxb5 ± (1.28) Depth: 6/14 00:00:00 7kN 44.Kf1 Rb8 45.Qd7+ Kg8 46.Ra7 Bf8 47.Qe6+ Kh7 48.Qxb6 Rxb6 ± (1.34) Depth: 7/16 00:00:01 17kN 44.Kf1 Rb8 45.Qd7+ Kg8 46.Ra7 Bf8 47.Qe6+ Kh7 48.Qxb6 Rxb6 49.g3 +- (1.44) Depth: 8/18 00:00:01 37kN 44.Kf1 Rb8 45.Qxb6 Rxb6 46.Ra7+ Kf8 47.g3 h5 48.Ke2 h4 49.gxh4 ± (1.25) Depth: 9/19 00:00:02 84kN 44.Kf1 Rb8 45.Ra6 Qxc6 46.dxc6 Kf8 47.g3 Rc8 48.Ra5 Rb8 49.Ra7 Rc8 ± (1.38) Depth: 10/25 00:00:03 212kN 44.Kf1 Rb8 45.Ra6 Qxc6 46.dxc6 Kf8 47.Ra7 Rc8 ± (1.38) Depth: 11/25 00:00:03 392kN 44.Kf1 Rb8 45.Ra6 Qxc6 46.dxc6 Bc7 47.Ra7 Rc8 +- (1.44) Depth: 12/28 00:00:04 859kN 44.Kf1 Rb8 45.Ra6 Qxc6 46.dxc6 Kf8 47.Ra7 Rc8 +- (1.50) Depth: 13/30 00:00:06 1917kN 44.Kf1 Rb8 45.Ra6 Qxc6 46.dxc6 Kf8 47.Ra7 Rc8 48.Rb7 Ra8 +- (1.59) Depth: 14/34 00:00:09 4077kN 44.Kf1 Rb8 45.Ra6 Qxc6 46.dxc6 Kf8 47.Ra7 Rc8 48.Rb7 Rc7 49.Rxb5 Ke7 +- (1.66) Depth: 15/38 00:00:16 8762kN 44.Kf1 Rb8 45.Ra6 Qxc6 46.dxc6 Kf8 47.Ra7 Rc8 48.Rb7 Rc7 49.Rxb5 +- (1.78) Depth: 16/37 00:00:38 22540kN 44.Kf1 Rb8 45.Ra6 Qxc6 46.dxc6 Kf8 47.Ra7 Rc8 48.Rb7 Rc7 49.Rxb5 Ke7 +- (1.78) Depth: 17/39 00:01:10 43120kN 44.Kf1-- +- (1.47) Depth: 18/44 00:03:32 131479kN 44.Kf1-- Rb8 45.Qd7+ Kg8 46.Ra7 Bf8 47.Qf7+ Kh7 48.Ke2 Rd8 49.Qb7 Rb8 ± (1.31) Depth: 18/45 00:07:15 272559kN 44.Kh1! ± (1.34) Depth: 18/45 00:09:10 346790kN 44.Kh1! Rb8 45.Ra6 Qxc6 46.dxc6 Kf8 47.Ra7 Rc8 48.g3 Rc7 49.Ra8+ Kf7 +- (1.50) Depth: 18/45 00:10:39 402006kN 44.Kh1 Rb8 45.Ra6 Qxc6 46.dxc6 Kf8 47.Ra7 Rc8 48.g3 Rc7 49.Ra5 Ke7 +- (1.63) Depth: 19/46 00:13:29 512685kN 44.Kh1 Rb8 45.Ra6 Qxc6 46.dxc6 Kf8 47.Ra7 Rc8 48.g3 Rc7 49.Ra5 Ke7 +- (1.63) Depth: 20/48 00:22:01 842954kN 44.Kh1 Rb8 45.Ra6 Qxc6 46.dxc6 Rc8 47.Ra5 Ke8 48.Kh2 Ke7 49.Rxb5 Rb8 +- (1.78) Depth: 21/50 00:40:58 1579956kN 44.Kh1 Rb8 45.Ra6 Qxc6 46.dxc6 Rc8 47.Ra5 Ke7 48.Rxb5 h5 49.Kh2 h4 +- (1.81) Depth: 22/51 01:44:09 4053399kN 44.Kh1 Rb8 45.Ra6 Qxc6 46.dxc6 Rc8 47.Ra5 Ke7 48.Rxb5 h5 49.g3 Bc7 +- (1.88) Depth: 23/53 03:11:14 7470799kN 44.Kh1 Rb8 45.Ra6 Qxc6 46.dxc6 Rc8 47.Ra5 Ke7 48.Rxb5 h5 49.g3 Bc7 +- (1.91) Depth: 24/53 06:27:16 15175713kN (Blass, Tel-aviv 04.09.2001) Here is another example of the search of Deep Fritz. You can see that even in the middle game the branching factor of Deep Fritz is often clearly smaller than 3 and it even can happen in the middle game. Dov Rozenberg - Uri Blass 3r1r1k/p4qpp/8/2p1Rp2/4n3/1P2PPP1/PB5P/4QBK1 b - - 0 1 Analysis by Deep Fritz: 29...Qxb3-- +- (4.34) Depth: 1/3 00:00:00 29...Qxb3-- 30.axb3 +- (7.00) Depth: 1/3 00:00:00 29...Nxg3! +- (4.00) Depth: 1/3 00:00:00 29...Nxg3! 30.Qxg3 +- (1.59) Depth: 1/3 00:00:00 29...c4! +- (1.50) Depth: 1/3 00:00:00 29...Rd2! +- (1.47) Depth: 1/10 00:00:00 29...Rd2! 30.fxe4 ³ (-0.56) Depth: 1/10 00:00:00 29...Nd2! ³ (-0.66) Depth: 1/10 00:00:00 29...Nd2! µ (-0.75) Depth: 1/10 00:00:00 29...Nd2 30.Bg2 µ (-0.72) Depth: 2/6 00:00:00 29...Nd2 30.Bg2 c4 31.bxc4 µ (-0.81) Depth: 3/13 00:00:00 29...Nd2 30.Bg2 c4 31.bxc4 Nxc4 µ (-0.81) Depth: 4/13 00:00:00 1kN 29...Nd2 30.Bg2 Qb7 31.Rxc5 Qxf3 32.Bxf3 µ (-0.75) Depth: 5/15 00:00:00 10kN 29...Nd2 30.Bg2 Qh5 31.Re7 Rf7 32.Rxf7 Qxf7 ³ (-0.69) Depth: 6/15 00:00:00 23kN 29...Nd2 30.Bg2 Rd5 31.Rxd5 Qxd5 32.Qa1 Rf7 33.Qd1 ³ (-0.50) Depth: 7/19 00:00:00 87kN 29...Rd2! ³ (-0.53) Depth: 7/24 00:00:00 149kN 29...Rd2! 30.fxe4 Rxb2 31.exf5 Rxa2 32.Bc4 µ (-0.81) Depth: 7/24 00:00:00 187kN 29...Rd2 30.fxe4 Rxb2 31.exf5 Rxa2 32.Rxc5 Qh5 33.Bg2 Rxf5 µ (-0.75) Depth: 8/21 00:00:00 261kN 29...Rd2 30.fxe4 Rxb2 31.Rxf5 Qe7 32.Qc3 Rxf5 33.exf5 Rxa2 34.Bc4 ³ (-0.56) Depth: 9/28 00:00:01 677kN 29...Nd2! ³ (-0.59) Depth: 9/28 00:00:01 941kN 29...Nd2 30.Bg2 Rd5 31.Qc1 Rfd8 32.Qc2 c4 33.bxc4 Rxe5 34.Bxe5 Nxc4 35.Bd4 ³ (-0.63) Depth: 10/27 00:00:02 1673kN 29...Nd2 30.Bg2 Rd5 31.Qc1 Re8 32.Rxe8+ Qxe8 33.Qc3 Qg6 34.e4 Rd7 35.e5 ³ (-0.56) Depth: 11/27 00:00:05 3639kN 29...Nd2 30.Bg2 Rd5 31.Qc1 Rxe5 32.Bxe5 Qd5 33.f4 Ne4 34.g4 Qd3 35.gxf5 ³ (-0.53) Depth: 12/29 00:00:13 9142kN 29...Nd2 30.Bg2 Rd5 31.Qc1 Rfd8 32.Rxd5 Qxd5 33.Qc3 Rd7 34.Qe5 Qxe5 35.Bxe5 ³ (-0.56) Depth: 13/33 00:00:39 26763kN 29...Nd2 30.Bg2 Rd5 31.Qc1 Rfd8 32.Rxd5 Qxd5 33.Qc3 Rd7 34.Qe5 Qxe5 35.Bxe5 ³ (-0.53) Depth: 14/35 00:01:41 68782kN 29...Nd2 30.Bg2 Rd5 31.Qc1 Rfd8 32.Rxd5 Qxd5 33.Qc3 Rd7 34.Qe5 Qxe5 35.Bxe5 ³ (-0.53) Depth: 15/35 00:04:20 177075kN 29...Nd2 30.Be2 Rfe8 31.Rxe8+ Qxe8 32.Kf2 Qh5 33.h4 Qf7 34.Qc1 Qd5 35.Qc3 ³ (-0.28) Depth: 16/39 00:18:18 743380kN 29...Rd2! ³ (-0.31) Depth: 16/39 00:22:00 902040kN 29...Rd2! 30.fxe4 Rxb2 31.Rxf5 Qe7 32.Qc3 Rxf5 33.exf5 Rxa2 34.b4 Qf8 35.Qxc5 ³ (-0.47) Depth: 16/39 00:26:12 1078382kN 29...Rd2 30.fxe4 Rxb2 31.Rxf5 Qe7 32.Qc3 Rxf5 33.exf5 Rxa2 34.b4 Qf8 35.Qb3 ³ (-0.56) Depth: 17/41 00:47:53 1986680kN 29...Rd2 30.fxe4 Rxb2 31.Rxf5 Qe7 32.Qc3 Rxf5 33.exf5 Rxa2 34.b4 Qf8 35.Qxc5 ³ (-0.53) Depth: 18/40 01:32:09 3842011kN 29...Rd2 30.fxe4 Rxb2 31.Rxf5 Qe7 32.Qc3 Rxf5 33.exf5 Rxa2 34.b4 Qf8 35.Qb3 ³ (-0.53) Depth: 19/45 04:02:27 10204554kN 29...Rd2 30.fxe4 Rxb2 31.Rxf5 Qe7 32.Qc3 Rxf5 33.exf5 Rxa2 34.b4 Qf8 35.Qb3 ³ (-0.47) Depth: 20/45 09:25:47 23890386kN (Blass, Tel-Aviv 21.06.2001) Uri
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.