wacnew.epd & single search improvements (nullmove)

[Stefan Knappe]

Geschrieben von: / Posted by: Stefan Knappe at 17 June 2003 15:24:41:

Hi,
short description of the test:

last week I started to research the effect of isolated improvements
of my program (Matador) on the playing strength of the program.
At first I compiled a version of Matador without any improvements.
This version worked without any kind of sorting, extensions, pruning,
hash … The evalution based exclusively on material.

I have finished the next test. Matador had to search all 300 positions with pure alpha-beta algo with zero window, quiescence search and nullmove (R=2). The results are more than depressing! Can the nullmove effective work without sorting of moves? At the moment I only know, my nullmove does work with sorting. What do you think?
The results of pure alpha-beta algo:
//Test: wacnew.epd / Time: 5s
total solve time : 952.17 s / solved: 115/300
avrg. depth: 5.5 / avrg. max depth: 21.6
avrg. QS: 77.8% / avrg. MO: 61.7%
Okay, these are the results of the test with nullmove:
//Test: wacnew.epd / Time: 5s
total solve time : 940.21 s / solved: 120/300
avrg. depth: 5.9 / avrg. max depth: 21.7
avrg. QS: 80.8% / avrg. MO: 59.8%
From my point of view the small increase of the average depth (without quiescence search) is very remarkable. I have expected an increase of 2-3 plys and some tests with sorting of moves confirmed the expectation.
Probably the expense of the nullmove without sorting is equal the use!? Perhaps someone can check it too?
At next I will research the effect of my search extensions on the playing strength of Matador.
In the past I used the following extensions:
1 ply – OneReplayExtensions
1 ply – CheckExtensions
1/4 ply – 2 or more checks in a line
1/4 ply – Check by other piece (not by the moved piece)
1/4 ply – Check by two pieces
1 ply – PassedPawnExtensions
1/2 ply – RecaptureExtensions
I am afraid, some of these extensions are nearly worthless.
Best regards,
Stefan

[Uri Blass]

Geschrieben von: / Posted by: Uri Blass at 17 June 2003 15:50:59:
Als Antwort auf: / In reply to: wacnew.epd & single search improvements (nullmove) geschrieben von: / posted by: Stefan Knappe at 17 June 2003 15:24:41:

Hi,
short description of the test:

last week I started to research the effect of isolated improvements
of my program (Matador) on the playing strength of the program.
At first I compiled a version of Matador without any improvements.
This version worked without any kind of sorting, extensions, pruning,
hash … The evalution based exclusively on material.

I have finished the next test. Matador had to search all 300 positions with pure alpha-beta algo with zero window, quiescence search and nullmove (R=2). The results are more than depressing!
Can the nullmove effective work without sorting of moves? At the moment I >only know, my nullmove does work with sorting. What do you think?

Why?

I think that you should give the program more time.
It is logical to expect bigger gain with bigger depthes and if your inital depth is only 5.5 you can expect small gains in depth.
I also think that the wac suite is a bad suite for your tests because a lot of the problems can be solved at depth

[Sune Fischer]

Geschrieben von: / Posted by: Sune Fischer at 17 June 2003 15:59:50:
Als Antwort auf: / In reply to: wacnew.epd & single search improvements (nullmove) geschrieben von: / posted by: Stefan Knappe at 17 June 2003 15:24:41:

Hi,
short description of the test:

last week I started to research the effect of isolated improvements
of my program (Matador) on the playing strength of the program.
At first I compiled a version of Matador without any improvements.
This version worked without any kind of sorting, extensions, pruning,
hash … The evalution based exclusively on material.

I have finished the next test. Matador had to search all 300 positions with pure alpha-beta algo with zero window, quiescence search and nullmove (R=2). The results are more than depressing! Can the nullmove effective work without sorting of moves? At the moment I only know, my nullmove does work with sorting. What do you think?
The results of pure alpha-beta algo:
//Test: wacnew.epd / Time: 5s
total solve time : 952.17 s / solved: 115/300
avrg. depth: 5.5 / avrg. max depth: 21.6
avrg. QS: 77.8% / avrg. MO: 61.7%
Okay, these are the results of the test with nullmove:
//Test: wacnew.epd / Time: 5s
total solve time : 940.21 s / solved: 120/300
avrg. depth: 5.9 / avrg. max depth: 21.7
avrg. QS: 80.8% / avrg. MO: 59.8%
From my point of view the small increase of the average depth (without quiescence search) is very remarkable. I have expected an increase of 2-3 plys and some tests with sorting of moves confirmed the expectation.
Probably the expense of the nullmove without sorting is equal the use!? >Perhaps someone can check it too?
At next I will research the effect of my search extensions on the playing strength of Matador.
In the past I used the following extensions:
1 ply – OneReplayExtensions
1 ply – CheckExtensions
1/4 ply – 2 or more checks in a line
1/4 ply – Check by other piece (not by the moved piece)
1/4 ply – Check by two pieces
1 ply – PassedPawnExtensions
1/2 ply – RecaptureExtensions
I am afraid, some of these extensions are nearly worthless.
Stefan

I think one usually tries a nullmove before generating the moves, to see if a quick cutoff is possible. So I don't understand what you mean by sorting the moves, what moves?
Sorting of moves has nothing to do with nullmove or qsearch.
You need good move ordering in the alpha-beta search to be effective. Try the most aggressive moves first, like captures and promotions. If you are lucky one of them will "fail-high" so you don't have to search the rest.
probably too much, try 3/4 ply
Gosh! At every rank?
Yeah try removing or limiting them, some of them might do more damage then good actually.
IMO it's better to start with something simple and then build on that.
You should get at least 200-230 no problem on wac, wac is one of the easier ones:
Best regards,

[Uri Blass]

Geschrieben von: / Posted by: Uri Blass at 17 June 2003 16:32:26:
Als Antwort auf: / In reply to: Re: wacnew.epd & single search improvements (nullmove) geschrieben von: / posted by: Sune Fischer at 17 June 2003 15:59:50:

Hi,
short description of the test:

last week I started to research the effect of isolated improvements
of my program (Matador) on the playing strength of the program.
At first I compiled a version of Matador without any improvements.
This version worked without any kind of sorting, extensions, pruning,
hash … The evalution based exclusively on material.

I have finished the next test. Matador had to search all 300 positions with pure alpha-beta algo with zero window, quiescence search and nullmove (R=2). The results are more than depressing! Can the nullmove effective work without sorting of moves? At the moment I only know, my nullmove does work with sorting. What do you think?
The results of pure alpha-beta algo:
//Test: wacnew.epd / Time: 5s
total solve time : 952.17 s / solved: 115/300
avrg. depth: 5.5 / avrg. max depth: 21.6
avrg. QS: 77.8% / avrg. MO: 61.7%
Okay, these are the results of the test with nullmove:
//Test: wacnew.epd / Time: 5s
total solve time : 940.21 s / solved: 120/300
avrg. depth: 5.9 / avrg. max depth: 21.7
avrg. QS: 80.8% / avrg. MO: 59.8%
From my point of view the small increase of the average depth (without quiescence search) is very remarkable. I have expected an increase of 2-3 plys and some tests with sorting of moves confirmed the expectation.
Probably the expense of the nullmove without sorting is equal the use!? >Perhaps someone can check it too?
At next I will research the effect of my search extensions on the playing strength of Matador.
In the past I used the following extensions:
1 ply – OneReplayExtensions
1 ply – CheckExtensions
1/4 ply – 2 or more checks in a line
1/4 ply – Check by other piece (not by the moved piece)
1/4 ply – Check by two pieces
1 ply – PassedPawnExtensions
1/2 ply – RecaptureExtensions
I am afraid, some of these extensions are nearly worthless.

I think one usually tries a nullmove before generating the moves, to see if a quick cutoff is possible. So I don't understand what you mean by sorting the moves, what moves?
Sorting of moves has nothing to do with nullmove or qsearch.
You need good move ordering in the alpha-beta search to be effective. Try the most aggressive moves first, like captures and promotions. If you are lucky one of them will "fail-high" so you don't have to search the rest.
probably too much, try 3/4 ply
Gosh! At every rank?
Yeah try removing or limiting them, some of them might do more damage then good actually.
IMO it's better to start with something simple and then build on that.
You should get at least 200-230 no problem on wac, wac is one of the easier ones:

You do not understand
The programmer already got clearly more than 230
see http://f11.parsimony.net/forum16635/messages/49820.htm
It seems that only now he tries to test seriously the things that he put in the program by comparing the program without them with the program with them.
Uri

[Stefan Knappe]

Geschrieben von: / Posted by: Stefan Knappe at 17 June 2003 17:41:09:
Als Antwort auf: / In reply to: Re: wacnew.epd & single search improvements (nullmove) geschrieben von: / posted by: Uri Blass at 17 June 2003 15:50:59:

Hi Uri,

I have finished the next test. Matador had to search all 300 positions with pure alpha-beta algo with zero window, quiescence search and nullmove (R=2). The results are more than depressing!

Why?
I also think that the wac suite is a bad suite for your tests because a lot of the problems can be solved at depthAfter finding mates there is no importance for the question if you use null move pruning.
You may try harder test suite that includes no simple mates at 10 minute per position.

In the past I tried the same test with some kind of sorting - I forgot to deactivate it. The results were very good compared to the version without nullmove. 2-3 plys more depth and approximately 50 aditional solved positions. I had expected similar increased results.
I chosed the wac, because it is the easiest test I know! There are approx. 100 positions with a mate or a loss of material in the first 5 plys. Of course these positions I could delete. However I am interested in the other 200 positions and in the time I need to solve them.
Regards,
Stefan

[Stefan Knappe]

Geschrieben von: / Posted by: Stefan Knappe at 17 June 2003 17:57:11:
Als Antwort auf: / In reply to: Re: wacnew.epd & single search improvements (nullmove) geschrieben von: / posted by: Sune Fischer at 17 June 2003 15:59:50:

Hi Sune,

I think one usually tries a nullmove before generating the moves, to see if a quick cutoff is possible. So I don't understand what you mean by sorting the moves, what moves?

1 ply – OneReplayExtensions
1 ply – PassedPawnExtensions
I am afraid, some of these extensions are nearly worthless.

probably too much, try 3/4 ply
Gosh! At every rank?
Yeah try removing or limiting them, some of them might do more damage then good actually.

of course I use the nullmove before I generate the moves. Perhaps my explanation of the bad results was not correct! The reason of them was not the missing of sorting. Probably the reason was the small depth, which based on the missing of sorting.
I will try it later with a 3/4 ply again.
This extension works if the pawn pushed the second or the seventh rank.
Normaly I limit the extensions. But at the moment I only use one of these extensions in the test. There is no necessary to limit it.
Regards,
Stefan

[Charles Roberson]

Geschrieben von: / Posted by: Charles Roberson at 17 June 2003 18:54:05:
Als Antwort auf: / In reply to: wacnew.epd & single search improvements (nullmove) geschrieben von: / posted by: Stefan Knappe at 17 June 2003 15:24:41:


Move ordering effects the performance of most everything in chess programs.
In the case of nullmove prunning, move ordering improves it as well. Sure
a null move is no move, but you need the move ordering for the opponent's
free move. Also, the effectiveness of null move pruning is more noticable
at deeper plys. As Sune suggested, try another test suite. I beleive PET
may be good.

[Sune Fischer]

Geschrieben von: / Posted by: Sune Fischer at 17 June 2003 19:05:50:
Als Antwort auf: / In reply to: Re: wacnew.epd & single search improvements (nullmove) geschrieben von: / posted by: Stefan Knappe at 17 June 2003 17:57:11:

Hi Sune,

I think one usually tries a nullmove before generating the moves, to see if a quick cutoff is possible. So I don't understand what you mean by sorting the moves, what moves?

1 ply – OneReplayExtensions
1 ply – PassedPawnExtensions
I am afraid, some of these extensions are nearly worthless.

probably too much, try 3/4 ply
Gosh! At every rank?
Yeah try removing or limiting them, some of them might do more damage then good actually.

of course I use the nullmove before I generate the moves. Perhaps my explanation of the bad results was not correct! The reason of them was not the missing of sorting. Probably the reason was the small depth, which based on the missing of sorting.
I will try it later with a 3/4 ply again.
This extension works if the pawn pushed the second or the seventh rank.
Normaly I limit the extensions. But at the moment I only use one of these extensions in the test. There is no necessary to limit it.
Regards,
Stefan

Oh in that case, I think it is hard to say what to expect with only a 5.5 ply search. I guess one would have to go over the positiones one by one and figure out how much depth, using certain extensions, are needed.
Sometimes nullmove will delay the tactics one ply, but most often the speedup is closer to two plies, so it still remains a gain.
Are you testing it in the configuration you plan to use it?
I think there is reason to invent schemes to limit these things, or they might become too expensive, it's a question of balance of course.
-S.