Page 1 of 2

MultiCut pruning

PostPosted: 08 Jun 2005, 19:22
by Daniel Mehrmann
Hello,

who tryed "MultiCut pruning" and can tell me more about his experience ?

Does it pay off at all in modern engines ?


Thanks
Daniel

Re: MultiCut pruning

PostPosted: 08 Jun 2005, 20:16
by Reinhard Scharnagl
Hi Danieal,

who tryed "MultiCut pruning" and can tell me more about his experience ?


this is unknown to me. Where could I read about it (no sources please)?

Reinhard.

Re: MultiCut pruning

PostPosted: 08 Jun 2005, 20:45
by Anonymous

Re: MultiCut pruning

PostPosted: 08 Jun 2005, 20:48
by Reinhard Scharnagl
Hello Dieter,

thank you, but I am not able to read this.

Reinhard.

Re: MultiCut pruning

PostPosted: 08 Jun 2005, 20:56
by Anonymous
You need a compression program, that can decompress .Z files (the classical Unix compression method). I believe many modern comression programs can do it. You also need a postscript reader (or a postscript printer). I'd suggest ghostview. It is no small download, however.

You could try to google for "Marsland multicut" and click on "text version".

Regards,
Dieter

Re: MultiCut pruning

PostPosted: 08 Jun 2005, 21:00
by Daniel Mehrmann
Reinhard Scharnagl wrote:Hi Danieal,

who tryed "MultiCut pruning" and can tell me more about his experience ?


this is unknown to me. Where could I read about it (no sources please)?

Reinhard.


You will find a PDF document on my Homer webpage: http://www.homerchess.com (see Chessprogramming link)

Re: MultiCut pruning

PostPosted: 08 Jun 2005, 22:09
by Tord Romstad
Daniel Mehrmann wrote:Hello,

who tryed "MultiCut pruning" and can tell me more about his experience ?

Early versions of Scatha and Glaurung used MultiCut pruning. At first it seemed to improve the engines a little bit, but when I tested again in later and more mature versions it no longer seemed to work very well, and I removed it.

It is very possible that my implementation was less than optimal, though. I believe that the idea has some potential, and I will probably experiment with it again some time.

If somebody is interested, I can add back my old MultiCut code and release a special non-tournament version of Glaurung for those who want to experiment.

Tord

Re: MultiCut pruning

PostPosted: 08 Jun 2005, 22:45
by Reinhard Scharnagl
Hi all,

I have not yet fully understood the text, but it is very possible, that there is some relation to search method's details in Smirf. Here one problem has been to combine nullmove pruning with it. It took me a long serie of experiments until I could figure out, how that cooperation could been established to finally gain improvements by a multiple concurrent pruning strategy.

Reinhard.

Re: MultiCut pruning

PostPosted: 08 Jun 2005, 23:15
by Robert Allgeuer
In the Crafty (18.15) reference implementation MPC does not pay off. As a matter of interest I have included this Crafty MPC version in the YABRL rating list: 7 ELO or so improvement over the standard 18.15, hence no improvement.

The MPC version searches one or even two plies deeper, which is probably a gain, but MPC wrecks at the same time the engine?s tactical capabilities, which apparently "compensates" this gain.

Robert

Re: MultiCut pruning

PostPosted: 08 Jun 2005, 23:33
by Piotr Cichy
I use MultiProbCut (MPC) in nanoSzachy (from version 1.2). When the engine did not use NullMove, the gain of using MPC was visible, but only on higher depths, at least 7. In version 1.3 I added NullMove and tested 3 different versions:

a) only MPC
b) only NullMove
c) MPC + NullMove

My results:
* on lower depths version b is stronger than a
* on higher depths b and a are equally strong ( or weak ;-) )
* on all depths c is as strong as b

Conclusion: MPC works similiar to NullMove, but needs higher depths. When using NullMove, MPC gives almost nothing.

I left MPC in my engine because number of visited nodes is usually ~10% smaller. In some very rare cases number of nodes is significantly smaller, allowing 2-3 ply deeper search in the same time.

The test had 2 parts:
* 50 games for each pair at 1h per game
* 100 games for each pair at 5min per game
I don't know whether it is statistically enough.

Re: MultiCut pruning

PostPosted: 09 Jun 2005, 00:07
by Tord Romstad
Robert Allgeuer wrote:In the Crafty (18.15) reference implementation MPC does not pay off.

MPC (MultiProbCut) is not the same as MultiCut , despite the similar names. As far as I know, nobody has experimented with MultiCut in Crafty.

Tord

Re: MultiCut pruning

PostPosted: 09 Jun 2005, 01:02
by Daniel Mehrmann
Robert Allgeuer wrote:In the Crafty (18.15) reference implementation MPC does not pay off. As a matter of interest I have included this Crafty MPC version in the YABRL rating list: 7 ELO or so improvement over the standard 18.15, hence no improvement.

The MPC version searches one or even two plies deeper, which is probably a gain, but MPC wrecks at the same time the engine?s tactical capabilities, which apparently "compensates" this gain.

Robert


Well, i've playing a little with MultiCut and it shows me different results. Sometimes it clear faster and sometimes not. Allso i must check about te tactical problems that comes with a short search. I allso added some own idea if we do a MultiCut and how many moves we should search.

After this it looks not bad for the beginning. Here are a testposition of my private collection:

FEN: 3r1rk1/1bq2ppp/pp1ppb2/N1n2P2/4P3/2N1BBQ1/1PPR2PP/3R2K1 b - - 0 1

Without MultiCut pruning:
1/16 0:00 +1.15 1...Bxc3 (196.810) 341
2/02 0:00 +1.15 1...Bxc3 2.bxc3 (196.847) 341
3/03 0:00 +1.15 1...Bxc3 2.bxc3 (196.884) 341
4/17 0:00 0.00 1...Rde8 (210.088) 337
5/19 0:00 +0.50++ 1...Bxc3 (225.267) 337
5/19 0:00 +1.02 1...Bxc3 2.bxc3 bxa5 3.f6 g6 (239.564) 341
5/19 0:00 +1.02 1...Bxc3 2.bxc3 bxa5 3.f6 g6 (247.663) 338
6/19 0:00 +0.52-- 1...Bxc3 (259.023) 339
6/19 0:00 +0.48 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Rxd6 4.Qxd6 Qxd6 5.Rxd6 Nxe4 (308.293) 353
7/21 0:01 -0.01 1...Bxc3 2.bxc3 Nxe4 3.Bxe4 Bxe4 4.f6 g6 5.Qf4 Bxg2 6.Kxg2 bxa5 7.Rxd6 Rxd6 8.Rxd6 Qxc3 (469.038) 371
8/21 0:01 +0.47 1...Bxc3 2.bxc3 bxa5 3.Bh6 f6 4.Rxd6 Rxd6 5.Rxd6 e5 6.Rd4 (596.732) 383
8/21 0:02 +0.47 1...Bxc3 2.bxc3 bxa5 3.Bh6 f6 4.Rxd6 Rxd6 5.Rxd6 e5 6.Rd4 (805.861) 380
9/22 0:02 +0.19 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Rxd6 4.Qxd6 Qxd6 5.Rxd6 Nxe4 6.Bxe4 Bxe4 7.fxe6 fxe6 8.Rxa6 Rf5 9.Rxe6 Bxc2 (1.080.298) 391
9/24 0:04 +0.19 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Rxd6 4.Qxd6 Qxd6 5.Rxd6 Nxe4 6.Bxe4 Bxe4 7.fxe6 fxe6 8.Rxa6 Rf5 9.Rxe6 Bxc2 (1.719.515) 389
10/24 0:05 +0.19 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Nxe4 4.Bxe4 Rxd6 5.Qxd6 Qxd6 6.Rxd6 Bxe4 (2.390.690) 417
10/26 0:12 +0.19 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Nxe4 4.Bxe4 Rxd6 5.Qxd6 Qxd6 6.Rxd6 Bxe4 (5.314.001) 422
11/27 0:16 +0.19 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Nxe4 4.Bxe4 Rxd6 5.Qxd6 Qxd6 6.Rxd6 Bxe4 (7.117.702) 426
11/27 0:21 +0.19 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Nxe4 4.Bxe4 Rxd6 5.Qxd6 Qxd6 6.Rxd6 Bxe4 (9.274.558) 424
12/28 0:44 +0.10 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Nxe4 4.Bxe4 Rxd6 5.Qxd6 Qxd6 6.Rxd6 Bxe4 7.fxe6 fxe6 8.Rxa6 Rf5 9.c4 Re5 (19.567.391) 438
12/28 1:12 +0.10 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Nxe4 4.Bxe4 Rxd6 5.Qxd6 Qxd6 6.Rxd6 Bxe4 7.fxe6 fxe6 8.Rxa6 Rf5 9.c4 Re5 (31.710.366) 436
13/29 1:38 +0.12 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Nxe4 4.Bxe4 Rxd6 5.Qxd6 Qxd6 6.Rxd6 Bxe4 (43.786.912) 444

With MultiCut pruning:

1/16 0:00 +1.15 1...Bxc3 (196.810) 350
2/02 0:00 +1.15 1...Bxc3 2.bxc3 (196.847) 350
3/03 0:00 +1.15 1...Bxc3 2.bxc3 (196.884) 350
4/17 0:00 0.00 1...Rde8 (210.088) 354
5/19 0:00 +0.50++ 1...Bxc3 (225.267) 354
5/19 0:00 +1.02 1...Bxc3 2.bxc3 bxa5 3.f6 g6 (239.564) 349
5/19 0:00 +1.02 1...Bxc3 2.bxc3 bxa5 3.f6 g6 (239.856) 349
6/19 0:00 +0.52-- 1...Bxc3 (251.109) 350
6/19 0:00 +0.48 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Rxd6 4.Qxd6 Qxd6 5.Rxd6 Nxe4 (280.347) 352
7/21 0:01 -0.01 1...Bxc3 2.bxc3 Nxe4 3.Bxe4 Bxe4 4.f6 g6 5.Qf4 Bxg2 6.Kxg2 bxa5 7.Rxd6 Rxd6 8.Rxd6 Qxc3 (460.769) 374
8/21 0:01 +0.48 1...Bxc3 2.bxc3 bxa5 3.Bh6 (622.252) 383
8/21 0:02 +0.48 1...Bxc3 2.bxc3 bxa5 3.Bh6 (908.182) 375
9/21 0:03 +0.75 1...Bxc3 2.bxc3 bxa5 3.f6 g6 4.Bh6 Rfe8 5.Rxd6 Rxd6 6.Qxd6 Qxd6 7.Rxd6 Nxe4 8.Bxe4 Bxe4 9.Rxa6 (1.233.098) 384
9/21 0:03 +0.75 1...Bxc3 2.bxc3 bxa5 3.f6 g6 4.Bh6 Rfe8 5.Rxd6 Rxd6 6.Qxd6 Qxd6 7.Rxd6 Nxe4 8.Bxe4 Bxe4 9.Rxa6 (1.523.078) 387
10/22 0:04 +0.75 1...Bxc3 2.bxc3 bxa5 3.f6 g6 4.Bh6 Rfe8 5.Rxd6 Rxd6 6.Qxd6 Qxd6 7.Rxd6 Nxe4 (1.998.670) 400
10/23 0:06 +0.75 1...Bxc3 2.bxc3 bxa5 3.f6 g6 4.Bh6 Rfe8 5.Rxd6 Rxd6 6.Qxd6 Qxd6 7.Rxd6 Nxe4 (2.756.170) 406
11/24 0:09 +0.31 1...Bxc3 2.bxc3 bxa5 3.f6 g6 4.Rxd6 Rxd6 5.Qxd6 Qxd6 6.Rxd6 Nxe4 7.Bxe4 Bxe4 8.Rxa6 Ra8 9.Rxa8+ Bxa8 10.Kf2 (4.073.462) 414
11/24 0:16 +0.31 1...Bxc3 2.bxc3 bxa5 3.f6 g6 4.Rxd6 Rxd6 5.Qxd6 Qxd6 6.Rxd6 Nxe4 7.Bxe4 Bxe4 8.Rxa6 Ra8 9.Rxa8+ Bxa8 10.Kf2 (6.767.633) 414
12/25 0:23 +0.29 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Rxd6 4.Qxd6 Qxd6 5.Rxd6 Nxe4 6.Bxe4 Bxe4 7.fxe6 fxe6 8.Rxa6 Ra8 9.Rxe6 Bxc2 10.Re7 Rd8 (9.948.118) 424
12/25 0:36 +0.29 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Rxd6 4.Qxd6 Qxd6 5.Rxd6 Nxe4 6.Bxe4 Bxe4 7.fxe6 fxe6 8.Rxa6 Ra8 9.Rxe6 Bxc2 10.Re7 Rd8 (15.205.220) 417
13/27 0:49 +0.14 1...Bxc3 2.bxc3 bxa5 3.Rxd6 Nxe4 4.Bxe4 Rxd6 5.Qxd6 Qxd6 6.Rxd6 Bxe4 (20.973.511) 421

Re: MultiCut pruning

PostPosted: 09 Jun 2005, 08:08
by Grzegorz Sidorowicz
MPC (MultiProbCut) is not the same as MultiCut , despite the similar names. As far as I know, nobody has experimented with MultiCut in Crafty.


Tomasz Michniewski experimented with MultiProbCut and conlucion was there is no too much gain. I tested it myself. Below results:
Code: Select all
MPC
-----------------------------------------------------------------------
Rank   Engine              Games   Wins   Draws   Points   Score %   
-----------------------------------------------------------------------
  1.   Tytan Chess 2.76      220     91      51    116,5     52,95
  2.   KnightDreamer 3.0      20     11       6     14,0     70,00
  3.   Bringer 1.9            20      8       8     12,0     60,00
  4.   Averno 040             20      8       6     11,0     55,00
  5.   Horizon 3.0            20      8       5     10,5     52,50
  6.   Amateur 2.3            20      9       3     10,5     52,50
  7.   Resp                   20     10       0     10,0     50,00
  8.   Ant 6.06               20      7       5      9,5     47,50
  9.   Baron 0.99.2           20      6       7      9,5     47,50
 10.   ButcherMPPS            20      5       4      7,0     35,00
 11.   Beowolf 2.2            20      4       5      6,5     32,50
 12.   Ax                     20      2       2      3,0     15,00

without MPC
-----------------------------------------------------------------------
Rank   Engine              Games   Wins   Draws   Points   Score %   
-----------------------------------------------------------------------
  1.   Tytan Chess 2.76      220     96      35    113,5     51,59
  2.   Bringer 1.9            20     14       3     15,5     77,50
  3.   Baron 0.99.2           20     12       4     14,0     70,00
  4.   Beowolf 2.2            20     10       5     12,5     62,50
  5.   KnightDreamer 3.0      20      8       7     11,5     57,50
  6.   Horizon 3.0            20     10       1     10,5     52,50
  7.   Ant 6.06               20      9       3     10,5     52,50
  8.   ButcherMPPS            20      8       1      8,5     42,50
  9.   Resp                   20      5       4      7,0     35,00
 10.   Amateur 2.3            20      5       3      6,5     32,50
 11.   Ax                     20      4       2      5,0     25,00
 12.   Averno 040             20      4       2      5,0     25,00

Re: MultiCut pruning

PostPosted: 09 Jun 2005, 18:09
by Anonymous
[quote="Daniel MehrmannYou will find a PDF document on my Homer webpage: http://www.homerchess.com (see Chessprogramming link)[/quote]

Daniel, is it the same article, I mentioned? When I click on the link above, I get the infamous: "Die Seite kann nicht angezeigt werden."

Cheers,
Dieter

Re: MultiCut pruning

PostPosted: 09 Jun 2005, 18:58
by Daniel Mehrmann
Dieter B?r?ner wrote:[quote="Daniel MehrmannYou will find a PDF document on my Homer webpage: http://www.homerchess.com (see Chessprogramming link)


Daniel, is it the same article, I mentioned? When I click on the link above, I get the infamous: "Die Seite kann nicht angezeigt werden."

Cheers,
Dieter[/quote]

Ops, here are the correct link: http://www.homer-chess.com

sorry.

Re: MultiCut pruning

PostPosted: 09 Jun 2005, 21:15
by Anonymous
Daniel Mehrmann wrote:
Dieter B?r?ner wrote:
Daniel Mehrmann wrote:You will find a PDF document on my Homer webpage: http://www.homerchess.com (see Chessprogramming link)


Daniel, is it the same article, I mentioned? When I click on the link above, I get the infamous: "Die Seite kann nicht angezeigt werden."

Ops, here are the correct link: http://www.homer-chess.com


Thanks Daniel - it works now. Also sorry for f+#ing up the quoting.

The article on your page is not identical to the article I cited above in this discussion. Googling for Marsland multicut did not seem to find the article on your page. I wonder: Where do you get this article? Why doesn't google find it? (Google typically has no problems to find .pdf and .ps(.?) files).

Cheers,
Dieter

Re: MultiCut pruning

PostPosted: 10 Jun 2005, 00:10
by Peter Fendrich
Dieter B?r?ner wrote:The article on your page is not identical to the article I cited above in this discussion. Googling for Marsland multicut did not seem to find the article on your page. I wonder: Where do you get this article? Why doesn't google find it? (Google typically has no problems to find .pdf and .ps(.?) files).

For you who don't want to download Ghostview or other .ps viewers.
I uploaded the first document (about MultiCut) in pdf-format to my Alaric site http://alaric.fendrich.se
See under "Documents"
/Peter

Re: MultiCut pruning

PostPosted: 10 Jun 2005, 21:32
by Daniel Mehrmann
Dieter B?r?ner wrote:
Daniel Mehrmann wrote:
Dieter B?r?ner wrote:
Daniel Mehrmann wrote:You will find a PDF document on my Homer webpage: http://www.homerchess.com (see Chessprogramming link)


Daniel, is it the same article, I mentioned? When I click on the link above, I get the infamous: "Die Seite kann nicht angezeigt werden."

Ops, here are the correct link: http://www.homer-chess.com


Thanks Daniel - it works now. Also sorry for f+#ing up the quoting.

The article on your page is not identical to the article I cited above in this discussion. Googling for Marsland multicut did not seem to find the article on your page. I wonder: Where do you get this article? Why doesn't google find it? (Google typically has no problems to find .pdf and .ps(.?) files).

Cheers,
Dieter


mmhhh, sorry dieter but i can't remember where i found this stuff.

daniel

Re: MultiCut pruning

PostPosted: 10 Jun 2005, 23:47
by Dann Corbit
The "ABS algorithm" link on your page fails with the dreaded 404 error.

Re: MultiCut pruning

PostPosted: 11 Jun 2005, 07:27
by Jim Ablett