depthnull

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

depthnull

Postby Pedro Castro » 04 Jul 2005, 19:35

Hi,

I believe that I have something to my works to me in danasah and not if uses somebody, he is relative to the reduction of the null move.

new_depth = depth - 1 - R - (depth>7) - (depth>9) -(depth>11) -(depth>13) -(depth>15)

R = 3, according to this I believe that I am applying until a R = 8.

With this the depth is greater in the same time, the problems are solved before and it does not seem that it causes errors.

I have proven to introduce the code in Fruit 2,1, the bad thing is that I do not make compilations very good, I lose almost 100.000 nps of speed.

Here you have a position analyzed with a version and another one, I have analyzed during 3 minutes, you can observe that the exit is the same one but the version with this change arrives deeper, and that as I say the compilation is 100.000 nps slower. Soon I made play the program with same himself and the result went 10 to 10. Not if with one more a faster compilation he had been favorable to the version that I did.

If somebody can make one more a compilation faster him I can send the modified code.

Who made the compilation of Fruit in the page of Leo? Fabien?

code for fruit:
Code: Select all
   // null-move pruning

   if (UseNull && depth >= NullDepth+(depth>7)+(depth>9)+(depth>11)+(depth>13)+(depth>15) && node_type != NodePV) {

      if (!in_check
       && !value_is_mate(beta)
       && do_null(board)
       && (!UseNullEval || depth <= NullReduction+1+(depth>7)+(depth>9)+(depth>11)+(depth>13)+(depth>15) || eval(board) >= beta)) {

         // null-move search

         new_depth = depth - NullReduction - 1 - (depth>7) - (depth>9) - (depth>11) - (depth>13) - (depth>15);

         move_do_null(board,undo);
         value = -full_search(board,-beta,-beta+1,new_depth,height+1,new_pv,NODE_OPP(node_type));
         move_undo_null(board,undo);




[diag]r2q1rk1/ppp2p2/3pn3/3Np1pn/2B1P3/3PQP2/PPP2P2/1K1R2R1 w - - 0 18[/diag]

FEN: r2q1rk1/ppp2p2/3pn3/3Np1pn/2B1P3/3PQP2/PPP2P2/1K1R2R1 w - - 0 18

Fruit 2.1:
1/1 00:01 2 0 +1,12 Ra1
1/1 00:01 4 0 +1,19 Tc1
1/1 00:01 7 0 +1,20 Td2
1/1 00:01 10 0 +1,24 Th1
1/3 00:01 15 0 +1,25 Tg4
1/3 00:01 16 0 +1,27 a3
1/6 00:01 67 0 +1,35 Ab5
2/10 00:00 714 0 +1,02 Ab5 Chf4
3/10 00:00 1.265 0 +0,89 Ab5 Chf4 Ac4
3/10 00:00 1.559 0 +1,02 a3 Chf4 Th1
3/10 00:00 2.024 0 +1,19 Th1 Chf4 Tdg1
4/12 00:00 4.466 0 +1,06 Th1 Chf4 Tdg1 a5
5/19 00:00 16.786 0 +1,14 Th1 Chf4 Tdg1 c6 Cxf4 Cxf4
6/19 00:00 43.163 0 +1,18 Th1 Chf4 Tdg1 a5 Th6 Cxd5 Axd5
7/22 00:00 149.226 0 +1,30 Th1 Chf4 Th6 Cg2 Dd2 Cgf4 Tg1 Cxd5 Axd5
8/25 00:00 250.478 0 +1,27 Th1 Chf4 Th6 Cg2 Dc1 Ch4 Th1 Cxf3 Cf6+ Rg7 Axe6 fxe6
9/27 00:00 521.749 0 +1,22 Th1 Chf4 Cxf4 exf4 Dd2 Df6 d4 a5 Dc3 c6
9/32 00:01 1.066.210 563.241 +2,31 Cxc7 Dxc7 Txg5+ Chg7 Tdg1 Tfc8 Txg7+ Cxg7 Dh6 Rf8 Txg7 d5 exd5
10/38 00:02 1.680.089 581.222 +3,75 Cxc7 Dxc7 Txg5+ Chg7 Tdg1 Tfd8 Txg7+ Cxg7 Dh6 Rf8 Txg7 d5 Axd5 Db6 Dh8+ Re7 Txf7+ Rd6
11/38 00:06 4.098.118 610.383 +4,21 Cxc7 Chf4 Cxa8 Te8 d4 exd4 Txd4 De7 Axe6 Cxe6 Ta4 Txa8 Txa7 Txa7 Dxa7
12/39 00:09 5.721.050 615.521 +4,21 Cxc7 Chf4 Cxa8 Te8 d4 exd4 Txd4 De7 Axe6 Cxe6 Ta4 Txa8 Txa7 Txa7 Dxa7
13/39 00:13 8.554.609 624.569 +4,24 Cxc7 Chf4 Cxa8 Te8 d4 exd4 Txd4 De7 Axe6 Cxe6 Td5 Txa8 Da3 Tc8 Dxa7
14/39 00:21 13.628.395 632.623 +4,24 Cxc7 Chf4 Cxa8 Te8 d4 exd4 Txd4 De7 Axe6 Cxe6 Td5 Txa8 Da3 Tc8 Dxa7
15/49 00:42 27.649.917 644.771 +4,11 Cxc7 Chf4 Cxa8 Rg7 Dxa7 Dxa8 Db6 Db8 Axe6 Cxe6 d4 exd4 f4 f6 fxg5 fxg5 Db3
16/49 01:21 52.885.587 645.962 +4,20 Cxc7 Chf4 Cxa8 Rg7 c3 f6 Dxa7 Dxa8 Db6 Db8 Axe6 Cxe6 d4 exd4 Db5 Dc7 cxd4



Fruit 2.1_pce:
1/1 00:00 2 0 +1,12 Ra1
1/1 00:00 4 0 +1,19 Tc1
1/1 00:00 7 0 +1,20 Td2
1/1 00:00 10 0 +1,24 Th1
1/3 00:00 15 0 +1,25 Tg4
1/3 00:00 16 0 +1,27 a3
1/6 00:00 67 0 +1,35 Ab5
2/10 00:00 714 0 +1,02 Ab5 Chf4
3/10 00:00 1.265 0 +0,89 Ab5 Chf4 Ac4
3/10 00:00 1.559 0 +1,02 a3 Chf4 Th1
3/10 00:00 2.024 0 +1,19 Th1 Chf4 Tdg1
4/12 00:00 4.466 0 +1,06 Th1 Chf4 Tdg1 a5
5/19 00:00 16.786 0 +1,14 Th1 Chf4 Tdg1 c6 Cxf4 Cxf4
6/19 00:00 43.163 0 +1,18 Th1 Chf4 Tdg1 a5 Th6 Cxd5 Axd5
7/22 00:00 149.226 0 +1,30 Th1 Chf4 Th6 Cg2 Dd2 Cgf4 Tg1 Cxd5 Axd5
8/25 00:00 250.478 0 +1,27 Th1 Chf4 Th6 Cg2 Dc1 Ch4 Th1 Cxf3 Cf6+ Rg7 Axe6 fxe6
9/27 00:01 521.749 494.560 +1,22 Th1 Chf4 Cxf4 exf4 Dd2 Df6 d4 a5 Dc3 c6
9/33 00:02 1.024.580 494.560 +2,31 Cxc7 Dxc7 Txg5+ Chg7 Tdg1 Tfc8 Txg7+ Cxg7 Dh6 Rf8 Txg7 d5 exd5
10/38 00:03 1.560.776 514.173 +3,75 Cxc7 Dxc7 Txg5+ Chg7 Tdg1 Tfd8 Txg7+ Cxg7 Dh6 Rf8 Txg7 d5 Axd5 Db6 Dh8+ Re7 Txf7+ Rd6
11/38 00:07 3.804.891 529.745 +4,21 Cxc7 Chf4 Cxa8 Te8 d4 exd4 Txd4 De7 Axe6 Cxe6 Ta4 Txa8 Txa7 Txa7 Dxa7
12/38 00:08 4.808.296 533.366 +4,21 Cxc7 Chf4 Cxa8 Te8 d4 exd4 Txd4 De7 Axe6 Cxe6 Ta4 Txa8 Txa7 Txa7 Dxa7
13/38 00:12 6.740.823 542.732 +4,24 Cxc7 Chf4 Cxa8 Te8 d4 exd4 Txd4 De7 Axe6 Cxe6 Td5 Txa8 Da3 Tc8 Dxa7
14/40 00:19 10.822.704 544.018 +4,24 Cxc7 Chf4 Cxa8 Te8 d4 exd4 Txd4 De7 Axe6 Cxe6 Td5 Txa8 Da3 Tc8 Dxa7
15/42 00:40 22.444.216 552.738 +4,20 Cxc7 Chf4 Cxa8 Rg7 c3 f6 Dxa7 Dxa8 Db6 Db8 d4 exd4 Axe6 Cxe6 Db5 Dc7 cxd4
16/52 01:02 34.819.733 553.079 +4,20 Cxc7 Chf4 Cxa8 Rg7 c3 f6 Dxa7 Dxa8 Db6 Db8 d4 exd4 Axe6 Cxe6 Db5 Dc7 cxd4
17/56 01:37 54.240.104 555.613 +4,12 Cxc7 Chf4 Cxa8 Rg7 Dxa7 Dxa8 Db6 Db8 Axe6 Cxe6 d4 exd4 f4 f6 f5 Cc5 Txd4 Th8
Best wishes,

Pedro Castro
User avatar
Pedro Castro
 
Posts: 180
Joined: 28 Jan 2005, 01:09
Location: Pays Basque (Spain)

Re: depthnull

Postby Bryan Hofmann » 04 Jul 2005, 20:01

Pedro Castro wrote:Hi,
Who made the compilation of Fruit in the page of Leo? Fabien?


I would be the one you are looking for. I would be happy to compile your mods to the fruit code. I will send you a private message with my email address.


Bryan
Bryan Hofmann
 
Posts: 98
Joined: 02 Oct 2004, 20:26
Location: USA

Re: depthnull

Postby Robert Allgeuer » 04 Jul 2005, 21:55

Is this the only change you have introduced? Your version also seems to extend more than standard Fruit.

Selfplay tests may not tell the full truth. For getting a feel as to whether your version is indeed stronger, one would have to let it play against a relatively large set of different test opponents.

Robert
Robert Allgeuer
 
Posts: 124
Joined: 28 Sep 2004, 19:09
Location: Konz / Germany

Re: depthnull

Postby Uri Blass » 04 Jul 2005, 22:06

It does not seem to me logical that it works at long time control but maybe I am wrong.

I think that null move pruning with R=3 already make it hard for the computer to detect cases when you sacrifice material for some long plan and this additional pruning will make it even harder for the computer to detect threats of long plans.

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: depthnull

Postby Tord Romstad » 04 Jul 2005, 23:04

Pedro Castro wrote:Hi,

I believe that I have something to my works to me in danasah and not if uses somebody, he is relative to the reduction of the null move.

new_depth = depth - 1 - R - (depth>7) - (depth>9) -(depth>11) -(depth>13) -(depth>15)

R = 3, according to this I believe that I am applying until a R = 8.

Hi Pedro,

If I understand correctly, this is the technique which is usually known by the name "adaptive null move pruning". I think this is very commonly used. The unusual thing about your code is that you use it extremely aggressively. Most other people who use adaptive null move do it with R=2 for depths less than 6 plies or so, and R=3 for greater depths.

At first sight, it seems highly unlikely to me that such an aggressive use of adaptive null move is a good idea. The tactical and positional risks look enormous. On the other hand, it wouldn't be the first time an apparently outrageous idea actually works. Yet another thing that needs to be tested some day, I guess.

Thanks for sharing! :D

Tord
User avatar
Tord Romstad
 
Posts: 639
Joined: 09 Oct 2004, 12:49
Location: Oslo, Norway

Re: depthnull

Postby Pedro Castro » 04 Jul 2005, 23:15

Hi Robert, you are right, a position or small match can not say anything, this has proven it much in my program, I has used the code of fruit because it is a well-known program and we can say that it is in English, my program is in Spanish. I am not nothing prepared to make a test, if you wish it I can send the file compiled by Bryan Hofmann to make a test, to you and everybody that wishes it, of course. But I do not promise anything in a matter of improvement of the force of the program. I believe that that code always has helped me and never harmed, I believe that it is a small aid.

I believe that he is something that can make more differences in simple engines with mine where I have single extension of check and and I almost do not have other prunnings.

For Uri, it would say to him that I believe there thati t can have more difference in longer times, where the tree grows exponentially and costs more than the time double to obtain following ply, it is perhaps where it can more help.
Best wishes,

Pedro Castro
User avatar
Pedro Castro
 
Posts: 180
Joined: 28 Jan 2005, 01:09
Location: Pays Basque (Spain)

Re: depthnull

Postby Pedro Castro » 04 Jul 2005, 23:27

Hi Tord,

before when the endgame arrived, I used something less aggressive, but now I am even proving it in the endgame. Whenever the program fault seems that it does by other reasons not related to this, bad evaluation, few extensions...
Best wishes,

Pedro Castro
User avatar
Pedro Castro
 
Posts: 180
Joined: 28 Jan 2005, 01:09
Location: Pays Basque (Spain)

Re: depthnull

Postby Uri Blass » 05 Jul 2005, 00:33

Pedro Castro wrote:Hi Robert, you are right, a position or small match can not say anything, this has proven it much in my program, I has used the code of fruit because it is a well-known program and we can say that it is in English, my program is in Spanish. I am not nothing prepared to make a test, if you wish it I can send the file compiled by Bryan Hofmann to make a test, to you and everybody that wishes it, of course. But I do not promise anything in a matter of improvement of the force of the program. I believe that that code always has helped me and never harmed, I believe that it is a small aid.

I believe that he is something that can make more differences in simple engines with mine where I have single extension of check and and I almost do not have other prunnings.

For Uri, it would say to him that I believe there thati t can have more difference in longer times, where the tree grows exponentially and costs more than the time double to obtain following ply, it is perhaps where it can more help.


I guess that the main reason that it helps to search deeper is that it prune more moves and there are many move that are threats only if you search deep enough.

I think that the price of wrong pruning should be bigger because there are many quiet plans(for example something like Qd2-Qh6-Qg7#)

In this case fruit will find it easily thanks to checks in the qsearch but if you have significantly more moves in the plan then it will not find it in a reasonable time.

Maybe I overestimate the value of long plans and in most cases when the only threat is by some long plan the move is not good move and it is better not to search it because the opponent can prevent the long plan.

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: depthnull

Postby Pedro Castro » 05 Jul 2005, 10:52

Hi,

already that the test is not good, not good computer, they are not sufficient games, nongood time for the test, nonsufficient adversaries, but the result is agreed with the results that I obtain for my engine.

5' in PIII-450 Mhz

Fruit21-pc - Fruit_21 : 27,0/50 16-12-22 (11=0111=11=001=1=1===001111======0=====01=000==010) 54% +28
Best wishes,

Pedro Castro
User avatar
Pedro Castro
 
Posts: 180
Joined: 28 Jan 2005, 01:09
Location: Pays Basque (Spain)

Re: depthnull

Postby Naum » 05 Jul 2005, 22:46

I had this in Naum up to the version 1.5

If I remember correctly, my tests indicated that it's slightly worse then R=3, but not by much.
Naum
 
Posts: 87
Joined: 10 Oct 2004, 04:23
Location: Toronto

Re: depthnull

Postby Pedro Castro » 06 Jul 2005, 02:42

Another little test,

Pentium IV 2400

Danasah 16: --> depth - 1 - R (3) - (depth>6) - (depth>9) - (depth>12) - (depht>15)
Danasah 16b1 --> depth - 1 - R (3)

Danasah16 - Danasah16b1 : 13,0/20 +10-4=6 (1=11=001==10=1110=11) 65% +108

With this result at the moment I cannot quit this aggressive null move :D
I suppose that in other engines the thing can change.
Best wishes,

Pedro Castro
User avatar
Pedro Castro
 
Posts: 180
Joined: 28 Jan 2005, 01:09
Location: Pays Basque (Spain)

Re: depthnull

Postby Fabien Letouzey » 06 Jul 2005, 09:11

Pedro Castro wrote:
Code: Select all
   // null-move pruning

   if (UseNull && depth >= NullDepth+(depth>7)+(depth>9)+(depth>11)+(depth>13)+(depth>15) && node_type != NodePV) {

      if (!in_check
       && !value_is_mate(beta)
       && do_null(board)
       && (!UseNullEval || depth <= NullReduction+1+(depth>7)+(depth>9)+(depth>11)+(depth>13)+(depth>15) || eval(board) >= beta)) {

         // null-move search

         new_depth = depth - NullReduction - 1 - (depth>7) - (depth>9) - (depth>11) - (depth>13) - (depth>15);

         move_do_null(board,undo);
         value = -full_search(board,-beta,-beta+1,new_depth,height+1,new_pv,NODE_OPP(node_type));
         move_undo_null(board,undo);




Hi Pedro,

Bear in mind I have little time to answer right now.

Your idea (roughly dividing search depth by 2 in forward pruning) makes perfect sense and is already used in other games. In chess though tactics are so important it might not work, but who knows? Interestingly, I intended to give it a try at some point (probably with history pruning off).

However your implementation in Fruit looks suspicious. You apply the change 3 times, each with its own meaning.

I think the first application is useless, my goal was only to avoid null move at depth 1.

The second I do not understand, as depth is not supposed to be involved. It's what I call "fail-high null move", i.e. don't apply it when static eval fails low. It can be turned off by UCI option => null move everywhere as in most engines.

The third one is correct, depth reduction as intended.

Fabien.
Fabien Letouzey
 
Posts: 110
Joined: 03 Dec 2004, 10:17
Location: France

Re: depthnull

Postby Uri Blass » 06 Jul 2005, 10:06

Fabien Letouzey wrote:
Pedro Castro wrote:
Code: Select all
   // null-move pruning

   if (UseNull && depth >= NullDepth+(depth>7)+(depth>9)+(depth>11)+(depth>13)+(depth>15) && node_type != NodePV) {

      if (!in_check
       && !value_is_mate(beta)
       && do_null(board)
       && (!UseNullEval || depth <= NullReduction+1+(depth>7)+(depth>9)+(depth>11)+(depth>13)+(depth>15) || eval(board) >= beta)) {

         // null-move search

         new_depth = depth - NullReduction - 1 - (depth>7) - (depth>9) - (depth>11) - (depth>13) - (depth>15);

         move_do_null(board,undo);
         value = -full_search(board,-beta,-beta+1,new_depth,height+1,new_pv,NODE_OPP(node_type));
         move_undo_null(board,undo);




Hi Pedro,

Bear in mind I have little time to answer right now.

Your idea (roughly dividing search depth by 2 in forward pruning) makes perfect sense and is already used in other games. In chess though tactics are so important it might not work, but who knows?
Fabien.


Hi Fabien,

I think it is the opposite.
If tactics is important it can work

In games that long plans are important and not tactics it cannot work because with aggresive pruning you may miss some long plan because of seeing no threat in it because you do not search deep enough.

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: depthnull

Postby Anonymous » 06 Jul 2005, 17:12

I am not much of a programmer ... in fact all i can really do is take a little code and compile it. I ran some test with and without the above code and what i found is ... it indeed does get deeper sooner. But, there seems to be a problem when getting to around depth 17 and 18 .. the simple test of
uci,isready,ucinewgame and go depth 12 revealed somd interesting results.

With the new code the results were:

info depth 12 seldepth 26 time 2656 nodes 1913243 nps 720348
info time 2656 nodes 1913243 nps 720348 cpuload 1000
info hashfull 310
bestmove g1f3 ponder b8c6

With the regular null move pruning:

info depth 12 seldepth 36 time 2875 nodes 2062041 nps 717232
info time 2890 nodes 2062041 nps 713509 cpuload 1000
info hashfull 332
bestmove g1f3 ponder b8c6

I then went to play chess server and i played a few games with it. With the new code I notice lots of tactics being missed. Its possible the time control was too quit for it and that with fruit i use (Always) instead of fail High. I will run more test to see how fail high works. The code that i modified for fruit takes advantage of (always ). Also if i am not mistaken the default setting when running the test i believe is with (fail high). Let me run some test on the server with fail high and see what results i get.
Anonymous
 

Re: depthnull

Postby Pedro Castro » 06 Jul 2005, 18:09

Hi Fabien,

I believe that I very gladly included the code in your program. I have to recognize that I did not understand the second site at least where I included it. The first, I avoided the null move doing ply > 1, I believe that is similar to depth >= Nulldepth, but when adding here the conditions of depth it seems to have improved the engine.

I am in agreement with everything the last post of Uri, I believe that this can work in tactical situations, perhaps is worse for long plans, I believe that in long plans I cannot appreciate it in my engine, because it has too many holes and it fails easier in other things that in this.

A thing I know clearly, to pass of a R = 2 to a R = 3, allows to solve the tactical positions me, I suppose that the problems of mate they are, much smaller time, and if I make the null move more aggressive, perhaps not note as much as to happen from 2 to 3, but also is a little more express.

Example:

r5k1/pp3r1p/q1p2p1B/3pP2p/8/5RPb/PP1QPP1P/4R1K1 w - - 0 1

depth - 1 - R (3) - (depth>6) - (depth>9) - (depth>12) - (depht>15) --> 9 s
depth - 1 - R (3) --> 23 s

I do not know if people in her engines identify as it is the game, if it is tactical or if it plays for a long plan, if somebody identifies these situations could prove single to use more aggressive null move when the situation is tactical, I do not know if that identification is easy or simple.
Best wishes,

Pedro Castro
User avatar
Pedro Castro
 
Posts: 180
Joined: 28 Jan 2005, 01:09
Location: Pays Basque (Spain)

Re: depthnull

Postby Anonymous » 07 Jul 2005, 00:33

The test i ran with the above code didn't turn out too well. I did not win one game while playing online .. it seems to me that it lost out on tactics. Things were going along ok but when things started to get complicated it did not see the complete sequence of move. I am not sure if it was due to herizon effect of some kind or it just totally missed the move. But, the eval would go from eval all the way to -3.00 or more .. I lost game to much slower computer as well. I am running at 3.73 P4 EE over clocked to 4.29.
Anonymous
 

Re: depthnull

Postby Fabien Letouzey » 07 Jul 2005, 09:01

Hi Pedro,

Pedro Castro wrote:I believe that I very gladly included the code in your program. I have to recognize that I did not understand the second site at least where I included it. The first, I avoided the null move doing ply > 1, I believe that is similar to depth >= Nulldepth, but when adding here the conditions of depth it seems to have improved the engine.


About the first change: are you sure you are not confusing NullDepth with NullReduction?

I haven't checked but it looks to me that your first change has no effect. Null move will be applied for depth >= 2 as before (independent of R = NullReduction).

Fabien.
Fabien Letouzey
 
Posts: 110
Joined: 03 Dec 2004, 10:17
Location: France

Re: depthnull

Postby Pedro Castro » 07 Jul 2005, 14:59

Hi,

Fabien, you are right, that first condition that I applied does not have no effect, my excuses if somebody has become crazy with this.

The condition to avoid the null move if depth < 2 to that it must? In order to be able to verify the move? If the move is not verified it is better not to apply it since it is faster, no?
Best wishes,

Pedro Castro
User avatar
Pedro Castro
 
Posts: 180
Joined: 28 Jan 2005, 01:09
Location: Pays Basque (Spain)

Re: depthnull

Postby Fabien Letouzey » 08 Jul 2005, 08:37

Hi Pedro,

Pedro Castro wrote:The condition to avoid the null move if depth < 2 to that it must? In order to be able to verify the move? If the move is not verified it is better not to apply it since it is faster, no?


Not a must. Calling the QS to evaluate threats is too costly for most engines at depth=1. Static threat detection is better in this case, but not doing anything is also OK.

Fabien.
Fabien Letouzey
 
Posts: 110
Joined: 03 Dec 2004, 10:17
Location: France


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 5 guests

cron