Win At Chess tests
Robert Hyatt
Thought I would post a discussion of a couple of win at chess positions,
although this suite has really become too easy for current programs since
nearly everyone gets over 290 correct on reasonable time limits.
0 20 40 60 80 100 120 140 160 180 200 220 240 260 280
+------------------------------------------------------------
1 | 0 0 0 0 0 2 0 -- 0 0 0 0 6 0 0
2 | 0 0 0 0 0 0 0 0 0 1 0 9 0 0 0
3 | 0 0 0 0 0 0 0 0 -- 0 0 2 1 0 12
4 | 0 0 0 0 0 0 0 0 0 0 1 3 0 4 0
5 | 0 0 0 0 0 0 0 10 0 0 0 0 0 56 0
6 | 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0
7 | 0 0 0 0 2 0 0 0 1 0 0 0 0 0 0
8 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
9 | 0 0 3 0 0 0 0 0 0 0 0 16 0 0 0
10 | 0 0 0 0 0 0 1 2 0 3 1 -- 0 19 0
11 | 0 0 0 46 0 0 3 0 0 0 0 2 0 0 12
12 | 0 0 0 0 47 0 0 0 0 0 0 0 4 0 0
13 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 44
14 | 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0
15 | 0 0 6 0 0 0 0 0 0 0 0 40 0 1 0
16 | 0 0 0 0 0 2 0 0 0 50 0 6 1 0 2
17 | 0 0 0 0 0 0 0 0 0 0 0 8 0 1 31
18 | 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0
19 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
20 | 0 0 0 4 0 2 0 0 11 25 0 0 0 0 0
incorrect: 141 163 230
sum of times(squared)=59841
That's the results for the current version of crafty, which is not
yet released, although probably will be this week. The interesting
position, to me, is #141...
BTW, the sume of times squared is the way I compare versions, since
most will get the same number right each time. This tends to
exaggerate long times over shorter times of course, which is what I'm
interested in.
BTW, I've reported that Crafty got 297 right for several weeks. That
was wrong, it's been getting 296 right. I had a small bug in the analysis
program that produces the above chart, that was counting one position as
right when it was not. The above is now correct, and has been verified by
hand by checking each position in the log. It now only misses the 3
positions given above, although at least one is close to being missed as
it takes 56 seconds. If I counted right, only 13 took 10 seconds or
longer and I'd suspect that 3-4 of those will speed up a bit as I finish
cleaning up and optimizing a little more this week...
+---+---+---+---+---+---+---+---+
8 | | | | | *R| | *K| |
+---+---+---+---+---+---+---+---+
7 | *P| | *Q| *R| | *P| | |
+---+---+---+---+---+---+---+---+
6 | | | *P| *B| | B | *P| |
+---+---+---+---+---+---+---+---+
5 | | *P| | | | | | *P|
+---+---+---+---+---+---+---+---+
4 | | | | P | | *N| | R |
+---+---+---+---+---+---+---+---+
3 | | B | | | | P | | |
+---+---+---+---+---+---+---+---+
2 | P | P | | | | P | K | |
+---+---+---+---+---+---+---+---+
1 | | | Q | | | | | R |
+---+---+---+---+---+---+---+---+
a b c d e f g h
White to move...
setboard 4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/1B3P2/PP3PK1/2Q4R w
solution Qxf4
As I've mentioned, this is the "null-move killer" position, because
the winning variation goes like this:
2.464 Qxf4 Bxf4 Rxh5 gxh5 Rxh5 Bh6 Rxh6 Qh2+ Kxh2 Re2
After the first move, Qxf4 Bxf4, white is down 6 points of material. If
you follow the analysis two more plies, after rxh5 gxh5, this is up to
(down to) -10. Now the null-move has a party, because the idea of the
null move is to let one side make two moves in a row, and if that side
can't do anything useful, the position is very bad.
At ply=5 we try any move white can play. Rxh5 for example picks up
one pawn and we are back to -9.
At ply=6 we try a null-move, and reduce the depth by another two plies
as well, At ply=7 we try the second white move (with no intervening
black move) and no matter what we do at ply 5 and ply 7, there's not
much chance of winning back that -9 we've lost. So we conclude that at
ply=6 the null move is ok to play, and at ply=5 white concludes that
this is hopeless.
The null-move is a killer if you toss material like this. It would be
a different story if those two captures were checks, because they would
extend the depth as well. But they aren't, and so white has only the
plies from 5 to the max search depth (9-10 for crafty in 1 min on this
position) to recoup the material or throw up his hands and say this
is awful. So, positions which toss material way early, only to recover
it (with interest, perhaps) out near the search horizon, completely
fool the search when it relies on a null-move search for speed. The
three positions that crafty doesn't solve in one minute all have a
sacrifice early in the PV.
I should add that many of the WAC positions have early sacrifices, but this
is a pathological case, because you toss basically a queen and rook in the
first 4 plies, then jockey for a couple of moves, then win it all back and
then some. That makes this position very unique, in that typically such
a tactical shot is completely forced and obvious.. You are either tossing
stuff, or taking stuff. Here, there's a storm of two sacs, then a lull, then
a worse storm to win it all back. Glad these don't show up in real games
very often... :)
Before you decide that the null-move must suck with two straws, however,
you should notice just how many of those positions are solved in < 1 second,
which is certainly alarming to me as a human looking on. And then I stopped
to think about how many queen sacs I've seen in games Crafty has played, and
I don't remember any at all, although I'm sure there have been one or two
that it's found.
In any case, significantly faster hardware isn't going to make an impact
on these positions. Each requires over 3 minutes to solve on my P6/200,
and a factor of 3x is not in sight yet, except perhaps on a 500mhz alpha
where it just might get one or more.
I've also mentioned another famous null-move problem of overlooking simple
mate threats at the search horizon, such as after black has played g6, and
white gets in f6 and Qh6, and black has no piece that can protect g7 quick
enough. The null move can overlook these positions too, because if white
sacrifices anything to reach the position, the null move can collapse the
branches below that sacrifice so that the q-search gets the position, and
with no captures that produce anything worthwhile, it concludes it is
losing, with a mate in 1 on the board. "You ought to see a mate in 1 in
the q-search" you say... and you might be right. However, it is a much
cleaner approach to let the q-search trade a few pieces and then eval, and
make the basic search responsible for finding mates. This case can probably
be fixed by simply not allowing a null-move when such a position is
reached. But the previous (WAC141) position is simply a stumbling block.
One useful piece of information is to try this position, as you can get a
quick feel for how the program's search you are trying, works. If it sees
this quickly, you know there's no null-move. If it takes a lot longer than
you'd expect, it probably does use null-move. There's not a lot of room
in the middle, but a few are using a restricted null-move that costs lots of
depth in normal positions, but which can see this quicker than a pure null-
move search. Which is better is open for conjecture, but, at present, I'd
rather search deeper in the middlegame/endgame, and miss an occasional
tactical shot like this, than to give up a ply or two in depth to find
something that might come up once in every 1,000 games...
comments?
Moritz Berger
On 25 Feb 1997 16:07:05 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
wrote:
<snip>
>White to move...
>setboard 4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/1B3P2/PP3PK1/2Q4R w
>solution Qxf4
>As I've mentioned, this is the "null-move killer" position, because
>the winning variation goes like this:
> 2.464 Qxf4 Bxf4 Rxh5 gxh5 Rxh5 Bh6 Rxh6 Qh2+ Kxh2 Re2
<snip>
>comments?
P5/133 notebook
Genius 5: 1"
Chessmaster 5000: 1"
Hiarcs 5 aggressive: 2"
Hiarcs 5 normal: 2"
Hiarcs 5 solid: 2"
Hiarcs 3: 3"
Hiarcs 4 (Fritz Engine): 6"
Fritz 3.1: 7"
Fritz 4.01: 12"
M-Chess 6: 16"
M-Chess 5: 20"
Rebel 8: 49"
Rebel 7: 60"
-------------
Moritz...@msn.com
Robert Hyatt
Moritz Berger (Moritz...@msn.com) wrote:
: On 25 Feb 1997 16:07:05 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
: wrote:
: <snip>
: >White to move...
: >setboard 4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/1B3P2/PP3PK1/2Q4R w
: >solution Qxf4
: >As I've mentioned, this is the "null-move killer" position, because
: >the winning variation goes like this:
: > 2.464 Qxf4 Bxf4 Rxh5 gxh5 Rxh5 Bh6 Rxh6 Qh2+ Kxh2 Re2
: <snip>
: >comments?
: P5/133 notebook
: Genius 5: 1"
: Chessmaster 5000: 1"
: Hiarcs 5 aggressive: 2"
: Hiarcs 5 normal: 2"
: Hiarcs 5 solid: 2"
: Hiarcs 3: 3"
: Hiarcs 4 (Fritz Engine): 6"
: Fritz 3.1: 7"
: Fritz 4.01: 12"
: M-Chess 6: 16"
: M-Chess 5: 20"
: Rebel 8: 49"
: Rebel 7: 60"
The fritz part is interesting. If you look at the position, and my
discussion, you can see why the null-move crushes it. It might be that
fritz simply gets deep enough, quickly enough, or he may do something
inside to turn it off at odd places.
Do you know what the "depth" was when it reported finding Qxf4? That
would also be interesting..
brucemo
Robert Hyatt wrote:
>
> Moritz Berger (Moritz...@msn.com) wrote:
> : Fritz 4.01: 12"
> Do you know what the "depth" was when it reported finding Qxf4? That
> would also be interesting..
"Extreme Chess", depth=8, 12 seconds, +2.91, PV Qf4 Bf4 Rh5 gh5 Rh5 Bh6
Rh6 Qh2.
It failed high at 12 seconds, took a while to come back. It does a
little better at depth 9, but doesn't see the mate. I didn't try to
figure out where it did see the mate.
bruce
Moritz Berger
On 25 Feb 1997 18:55:42 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
wrote:
<snip>
>: >White to move...
>
>: >setboard 4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/1B3P2/PP3PK1/2Q4R w
>: >solution Qxf4
<snip>
>: P5/133 notebook
< snip>
>: Fritz 3.1: 7"
>: Fritz 4.01: 12"
>The fritz part is interesting. If you look at the position, and my
>discussion, you can see why the null-move crushes it. It might be that
>fritz simply gets deep enough, quickly enough, or he may do something
>inside to turn it off at odd places.
>Do you know what the "depth" was when it reported finding Qxf4? That
>would also be interesting..
Both Fritz 3.1 and Fritz 4.01 find the move at 8 ply depth.
Moritz
-------------
Moritz...@msn.com
Robert Hyatt
Moritz Berger (Moritz...@msn.com) wrote:
: On 25 Feb 1997 18:55:42 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
: wrote:
: <snip>
: >: >White to move...
: >
: >: >setboard 4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/1B3P2/PP3PK1/2Q4R w
: >: >solution Qxf4
: <snip>
: >: P5/133 notebook
: < snip>
: >: Fritz 3.1: 7"
: >: Fritz 4.01: 12"
: >The fritz part is interesting. If you look at the position, and my
: >discussion, you can see why the null-move crushes it. It might be that
: >fritz simply gets deep enough, quickly enough, or he may do something
: >inside to turn it off at odd places.
: >Do you know what the "depth" was when it reported finding Qxf4? That
: >would also be interesting..
: Both Fritz 3.1 and Fritz 4.01 find the move at 8 ply depth.
Yes another case where Frans is better than I am... <sigh> :)
: Moritz
: -------------
: Moritz...@msn.com
Robert Hyatt
brucemo (bru...@nwlink.com) wrote:
: > : Fritz 4.01: 12"
: > Do you know what the "depth" was when it reported finding Qxf4? That
: > would also be interesting..
: "Extreme Chess", depth=8, 12 seconds, +2.91, PV Qf4 Bf4 Rh5 gh5 Rh5 Bh6
: Rh6 Qh2.
: It failed high at 12 seconds, took a while to come back. It does a
: little better at depth 9, but doesn't see the mate. I didn't try to
: figure out where it did see the mate.
: bruce
third question. :) wonder if Frans uses negascout, which is yet another thing
that when coupled with null-move causes more problems. This gives a very tiny
"edge" for the null-move to fail over...
B. Bauer
Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
many lines deleted.
> Before you decide that the null-move must suck with two straws, however,
> you should notice just how many of those positions are solved in < 1 second,
> which is certainly alarming to me as a human looking on. And then I stopped
> to think about how many queen sacs I've seen in games Crafty has played, and
> I don't remember any at all, although I'm sure there have been one or two
> that it's found.
Well, I think it's up to the author what strategie he will use in playing well.
But I would like to see a switch which gives the user the possibility to do
a *save* search even if it costs time.
Now you can play a game using crafty in a limited time. You may analyse this
game with crafty and you may detect some better moves, but you can never be
shure due to the null-move problems. In doing analysis time may be not that
important, because you may analyse only a few moves. Here you would like to
be sure.
Clearly in normal play those null-move killers are seldom, but if you use
your program to solve studies the situation may change.
And you would'nt be blamed for not being able to solve very simple positions:
"Look this program is rated at 2700 and can not solve this!"
many lines deleted.
> comments?
see the above.
Thank you for explaining the problems to the public.
Bernhard
Tord Kallqvist Romstad
: : wrote:
: : <snip>
: : >White to move...
: : >setboard 4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/1B3P2/PP3PK1/2Q4R w
: : >solution Qxf4
: : >As I've mentioned, this is the "null-move killer" position, because
: : >the winning variation goes like this:
: : > 2.464 Qxf4 Bxf4 Rxh5 gxh5 Rxh5 Bh6 Rxh6 Qh2+ Kxh2 Re2
: : <snip>
: : >comments?
: : P5/133 notebook
: : Genius 5: 1"
: : Chessmaster 5000: 1"
: : Hiarcs 5 aggressive: 2"
: : Hiarcs 5 normal: 2"
: : Hiarcs 5 solid: 2"
: : Hiarcs 3: 3"
: : Hiarcs 4 (Fritz Engine): 6"
: : Fritz 3.1: 7"
: : Fritz 4.01: 12"
: : M-Chess 6: 16"
: : M-Chess 5: 20"
: : Rebel 8: 49"
: : Rebel 7: 60"
: The fritz part is interesting. If you look at the position, and my
: discussion, you can see why the null-move crushes it. It might be that
: fritz simply gets deep enough, quickly enough, or he may do something
: inside to turn it off at odd places.
I tested this position on Fritz 3.0 (486/66) some time ago. It found the
right move, but didn't find the mate in reasonable time. After 30 minutes,
F3 still hadn't found the mate. The mate is in six moves, so it should
be found very fast without the null-move.
Tord
Dap Hartmann
hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>third question. :) wonder if Frans uses negascout, which is yet another thing
>that when coupled with null-move causes more problems. This gives a very tiny
>"edge" for the null-move to fail over...
Why would NegaScout give you more problems with the null-move than
regular alpha-beta?
dap
Robert Hyatt
Dap Hartmann (d...@abitibi.harvard.edu) wrote:
: hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
: dap
Because in NegaScout, almost all searching is with a null-window, which
means something either fails low or it fails high. In the case of null-
move, it is more likely to fail high when it shouldn't, if the window is
very narrow. I noticed many more null move problems after going from
straight aspiration alpha beta to negascout, but like the speed and
simplicity of negascout... I tolerate null-move. :)
Tom C. Kerrigan
Well, this is basically more about null move and not WAC, so I'll post
quasi-on topic.
A question I've been toying with is about fail high reductions. Are they
better than null moves, or what? In a way, they're quite similar, but
knowledge plays a much larger role with FHR. So is this knowledge good
enough to not trip over these WAC problems? Will it ever be good enough?
I've had recent experience with FHR programs, and I didn't see them
finding anything my program didn't, but I would like to know what sort of
positions they trip up in.
Cheers,
Tom
Robert Hyatt
Tom C. Kerrigan (kerr...@merlin.pn.org) wrote:
: Well, this is basically more about null move and not WAC, so I'll post
: quasi-on topic.
: Cheers,
: Tom
I tested this about 3 weeks ago. I found it slower than current Crafty
by a significant amount, enough that it changed the WAC result by a
signficant amount. I also didn't find it particularly better than
null-move at avoiding some of the problems. It is easy to insert. I
tried it by replacing the null-move code, and then tried them together,
but didn't see any good results.
Take this with a grain (or bag) of salt and try it yourself. I didn't
spend days studying it to see if negascout was interfering, or if the
hash/no-null trick would apply there, etc...
Brian Sheppard
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article
<5f2hm5$7...@juniper.cis.uab.edu>...
> Tom C. Kerrigan (kerr...@merlin.pn.org) wrote:
> : A question I've been toying with is about fail high reductions. Are
they
> : better than null moves, or what? In a way, they're quite similar, but
> : knowledge plays a much larger role with FHR. So is this knowledge good
> : enough to not trip over these WAC problems? Will it ever be good
enough?
"Fail-high reductions" is not a term I am familiar with. Can you post
a definition?
Thanks,
Brian
Robert Hyatt
Brian Sheppard (bri...@mstone.com) wrote:
: Robert Hyatt <hy...@crafty.cis.uab.edu> wrote in article
: Thanks,
: Brian
It's another sort of depth-reduction trick that behaves like null-move
in some respects. The simple idea is to do a n-2 ply search, rather than
a n-1 ply search from the current position. If this fails high, you might
conclude that doing the search you *really* want to do from this position
(n-1) is not necessary, and since the n-2 ply search takes less effort, you
save some time, at the expense of overlooking something due to the reduced
depth, on occasion (just like null move.)
I have a postscript copy of the paper that appeared in the JICCA, which is
available on the net although I don't have a pointer to it (hopefully someone
can post it here.)
My assessment of the paper would address three points:
1. His algorithm is easy to understand and implement, so that you don't
have to be a search guru to follow it.
2. I had trouble following his data, but that might be more my problem
than the paper's method of presenting it. I gave up on trying to figure
out whether it was worth trying, because it was simple enough I just stuck
the code in and tried it.
3. He does point out one huge shortcoming of his paper, however, in that
the program this is used in does not use null-move. Therefore there's
no comparison between one or the other. Using both didn't seem to help,
although someone once reported that you might try both. IE, do the null-
move search which is very cheap (R=2 chops 2 plies off the search.) If
that fails high, try a ply-1 normal search from here to see if that also
fails high. If both do, it's likely safe to exit. If the null-move
search doesn't fail high, you don't do the fail-high reduction search and
avoid the more expensive 1-ply-deeper search it does. I didn't try this
at all this time, although I tried a variant of it a year ago or so and
didn't like the extra cost...
I can post more technical details if you'd like, but it's easier to find
the postscript file and read the original... I'm not sure it's kosher to
post it here myself since I'm not the author, however...
Bob
brucemo
mclane wrote:
>
> Moritz...@msn.com (Moritz Berger) wrote:
> >On 25 Feb 1997 16:07:05 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
> >>setboard 4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/1B3P2/PP3PK1/2Q4R w
> >P5/133 notebook
>
> >Genius 5: 1"
> >Chessmaster 5000: 1"
> >Hiarcs 5 aggressive: 2"
> >Hiarcs 5 normal: 2"
> >Hiarcs 5 solid: 2"
> >Hiarcs 3: 3"
> >Hiarcs 4 (Fritz Engine): 6"
> >Fritz 3.1: 7"
> >Fritz 4.01: 12"
> >M-Chess 6: 16"
> >M-Chess 5: 20"
> >Rebel 8: 49"
> >Rebel 7: 60"
> ah - come on. this position is obviously tooooooooo easy.
> A position should not be solved faster than the setup of it takes
> time.
No! It's a tough problem, for Bob and I at least.
This is an embarassing problem because any human who can play chess with
reasonable competence will see this in a short time. It is very bad, when
you expect to soundly thrash any human with reasonable competence, when it
takes you ten minutes to find the solution here. But this is how long it
takes my program (on a P6/200!), unless I add some special extensions that
are of dubious utility in normal positions, in which case I can get it down
to perhaps 40 seconds.
Bob and I have been sharing ideas for over a year, so my program and his
program are quite similar, and we both wipe out on this one.
I'm sure that we would both be delighted to hear how any of the programs on
the list do it better. The real surprise is that Fritz can do it, since
you'd expect that he'd be even more minimal than Bob and I.
bruce
mclane
Moritz...@msn.com (Moritz Berger) wrote:
>On 25 Feb 1997 16:07:05 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
>wrote:
><snip>
>>White to move...
>>setboard 4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/1B3P2/PP3PK1/2Q4R w
>>solution Qxf4
>>As I've mentioned, this is the "null-move killer" position, because
>>the winning variation goes like this:
>> 2.464 Qxf4 Bxf4 Rxh5 gxh5 Rxh5 Bh6 Rxh6 Qh2+ Kxh2 Re2
><snip>
>>comments?
>P5/133 notebook
>Genius 5: 1"
>Chessmaster 5000: 1"
>Hiarcs 5 aggressive: 2"
>Hiarcs 5 normal: 2"
>Hiarcs 5 solid: 2"
>Hiarcs 3: 3"
>Hiarcs 4 (Fritz Engine): 6"
>Fritz 3.1: 7"
>Fritz 4.01: 12"
>M-Chess 6: 16"
>M-Chess 5: 20"
>Rebel 8: 49"
>Rebel 7: 60"
>-------------
ah - come on. this position is obviously tooooooooo easy.
A position should not be solved faster than the setup of it takes
time.
Tom C. Kerrigan
Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
> I tested this about 3 weeks ago. I found it slower than current Crafty
> by a significant amount, enough that it changed the WAC result by a
> signficant amount. I also didn't find it particularly better than
> tried it by replacing the null-move code, and then tried them together,
> but didn't see any good results.
You have a funky definition of "easy." Some people spend months working on
it until they get what they consider satisfactory performance.
I only tried it with the check condition and my program fell flat on its
face.
Cheers,
Tom
Robert Hyatt
What's the context here? Still fail high reductions? The code looks just
like the null move code pretty much, stuck in the same place (for me,
anyway)... The null move code in crafty is only 10 lines or so, total.
The FHR code was actually shorter. But with a one ply reduction, I didn't
see anywhere near the performance of the null move with R=2...
Tom C. Kerrigan
Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
> : You have a funky definition of "easy." Some people spend months working on
> : it until they get what they consider satisfactory performance.
> : I only tried it with the check condition and my program fell flat on its
> : face.
> What's the context here? Still fail high reductions? The code looks just
> like the null move code pretty much, stuck in the same place (for me,
> anyway)... The null move code in crafty is only 10 lines or so, total.
> The FHR code was actually shorter. But with a one ply reduction, I didn't
> see anywhere near the performance of the null move with R=2...
Yes, still FHR. Notice in the paper it says they shouldn't be done if the
king is in trouble. It is possible to implement this stuff by only
checking for check. Hell, it's possible to use it 100% of the time, but I
know that Zugzwang has hundreds of lines of code devoted to
controlling FHR...
Cheers,
Tom
Robert Hyatt
: Cheers,
: Tom
They also gave some cheap tricks to handle this, although this is no different
than what we face with null-move search. I was simply comparing the *best*
FHR performance against the *best* null-move performance, as implemented in
Crafty which does no null-move exclusions at all, and which certainly produces
the fastest search (and, on occasion, the fastest blunders, of course.) However,
in that context, FHR was worse. If you work on excluding the test at key
positions, it will only get *worse* in terms of search depth, although it
might obviously get more accurate (best idea is Hsu's of course, which is to
not do any oddball stuff that can ever come back to haunt you, but, so far,
I don't have anywhere near the horsepower to do that and live...
brucemo
Tom C. Kerrigan wrote:
>
> Well, this is basically more about null move and not WAC, so I'll post
> quasi-on topic.
>
> better than null moves, or what? In a way, they're quite similar, but
> knowledge plays a much larger role with FHR. So is this knowledge good
> enough to not trip over these WAC problems? Will it ever be good enough?
>
> finding anything my program didn't, but I would like to know what sort of
> positions they trip up in.
Please post a summary of this algorithm, or at least an ICCAJ reference.
bruce
Vincent Diepeveen
>Tom C. Kerrigan (kerr...@merlin.pn.org) wrote:
>: Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
>
>: > I tested this about 3 weeks ago. I found it slower than current Crafty
>: > by a significant amount, enough that it changed the WAC result by a
>: > signficant amount. I also didn't find it particularly better than
>: > tried it by replacing the null-move code, and then tried them together,
>: > but didn't see any good results.
>
>: You have a funky definition of "easy." Some people spend months working on
>: it until they get what they consider satisfactory performance.
>
>: I only tried it with the check condition and my program fell flat on its
>: face.
>
>What's the context here? Still fail high reductions? The code looks just
>like the null move code pretty much, stuck in the same place (for me,
>anyway)... The null move code in crafty is only 10 lines or so, total.
>The FHR code was actually shorter. But with a one ply reduction, I didn't
>see anywhere near the performance of the null move with R=2...
>
>
I saw however that FHR considerably weakened the program, when used in
combination with nullmove. It needs a huge depth to find even a simplistic
trick. I didn't test the extra playing strength that it gives.
Could be an idea to use FHR last 4 ply for example (forward pruning), simply
accepting that is misses things.
Vincent.
--
+----------------------------------------------------+
| Vincent Diepeveen email: vdie...@cs.ruu.nl |
| http://www.students.cs.ruu.nl/~vdiepeve/ |
+----------------------------------------------------+
Vincent Diepeveen
In <331683...@nwlink.com> brucemo <bru...@nwlink.com> writes:
>mclane wrote:
>>
>> Moritz...@msn.com (Moritz Berger) wrote:
>
>> >On 25 Feb 1997 16:07:05 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
>> >>setboard 4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/1B3P2/PP3PK1/2Q4R w
>
>> >P5/133 notebook
>>
>> >Genius 5: 1"
>> >Chessmaster 5000: 1"
>> >Hiarcs 5 aggressive: 2"
>> >Hiarcs 5 normal: 2"
>> >Hiarcs 5 solid: 2"
>> >Hiarcs 3: 3"
>> >Hiarcs 4 (Fritz Engine): 6"
>> >Fritz 3.1: 7"
>> >Fritz 4.01: 12"
>> >M-Chess 6: 16"
>> >M-Chess 5: 20"
>> >Rebel 8: 49"
>> >Rebel 7: 60"
>
>> ah - come on. this position is obviously tooooooooo easy.
>> A position should not be solved faster than the setup of it takes
>> time.
>
>No! It's a tough problem, for Bob and I at least.
>
>This is an embarassing problem because any human who can play chess with
>reasonable competence will see this in a short time. It is very bad, when
>you expect to soundly thrash any human with reasonable competence, when it
>takes you ten minutes to find the solution here. But this is how long it
>takes my program (on a P6/200!), unless I add some special extensions that
>are of dubious utility in normal positions, in which case I can get it down
>to perhaps 40 seconds.
>
>Bob and I have been sharing ideas for over a year, so my program and his
>program are quite similar, and we both wipe out on this one.
>
>I'm sure that we would both be delighted to hear how any of the programs on
>the list do it better. The real surprise is that Fritz can do it, since
>you'd expect that he'd be even more minimal than Bob and I.
Fritz is not minimal. For this reason the program is so dangerous. It searches
all combinations.
It seems to have some extra checkextensions (besides the normal
checkextension which
sometimes is used) which in 'setup' positions seem to work in certain
mating combinations.
I'm trying to make such a mating extension also in Diep, an extension that
sometimes works, but doesn't use too much systemtime.
Have written down the position. Will try it on Diep.
>bruce
Vincent
Robert Hyatt
brucemo (bru...@nwlink.com) wrote:
: bruce
Simple version:
at any node in the tree, you first do a search to depth D-2 (where you'd
normally do a search to depth D-1) for each legal move at the current
depth. If this search fails high, then we return beta, just like the
null-move search. If this move fails low, we go to the next move. Only
if the search result lands between alpha and beta do we re-search with the
real search depth.
They use a special threat-detection piece of code to disable this at
places where it might cause problems, but also report that a simple
"don't do it if in check" produced results "very well."
Where does this save?
obviously if you reach a ply where the side not on move is in lots
of trouble, any move at the current ply will fail high. FHR will also
fail high, but with one ply less depth of search. Null move fails high
with two plies less depth, so it wins.
If the FHR search returns a value <= alpha, you treat that just like
any normal fail low and keep searching at the current ply, saving 1
ply of search. Null move doesn't help here, but it will fail high at
the next ply and make up for it.
I tried this in place of the null-move search code, and simply found
that the trees were larger. Sometimes very much larger, sometimes
just larger. I think that R=2 is the killer here, but I did not go
into trying the equivalent with FHR since the paper didn't mention it.
It might be interesting, it might not be.
That's a very brief description of what this is. I can post the
psuedo-code from the paper if it would help...
Tom C. Kerrigan
Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
> Simple version:
> at any node in the tree, you first do a search to depth D-2 (where you'd
> normally do a search to depth D-1) for each legal move at the current
> depth. If this search fails high, then we return beta, just like the
> null-move search. If this move fails low, we go to the next move. Only
> if the search result lands between alpha and beta do we re-search with the
> real search depth.
[etc.]
This is Rainer Feldmann's idea and he wrote a paper about it and gave me a
copy when I visited him in late October. Since then I think he published
it in the ICCAJ, but I can't tell you which one because I don't get it any
more. The coauthor of Zugzwang (Peter with a last name that I can't spell)
wrote a huge king safety threat detection function to control FHR and the
results that were published against a "generic program" (Cheiron) were
quite promising. I know of other programs that use it with quite a bit of
success, but I don't care to print the names here. In most cases, though,
programs simply fall on their faces when the pseudocode is inserted...
(and even after it's translated to actual code :)
Cheers,
Tom
Robert Hyatt
: Cheers,
: Tom
I got the info from a paper of his dated 1996, so it must have been published
last year. Unfortunately the .ps file I have doesn't have a citation for where
it appeared, although I believe I have seen the JICCA mentioned elsewhere as
a target...
Dennis Breuker
It will be published in the forthcoming
Advances in Computer Chess 8 Proceedings...
Dennis.