Detected draw by repetition.
Tim Foden
Hi,
I have just completed changes to my transition table and
searching code that allows storage and detection of
positions that have been seen before in the game. This
is of course to allow draw by repetition to be detected
during the search.
When a search node finds that its current position has
occurred before in the game, it immediately returns with
an evaluation of zero.
I expected that this would reduce the number of nodes
searched, but the opposite seems to occur. My prog
ends up searching slightly more nodes, although it
does now correctly steer around repetition draws when
it is ahead in material.
Is this a normal occurance (the increase in nodes
searched), or does this imply that I still have
a bug somewhere in the new code?
Cheers, Tim.
--
Tim Foden
http://www2.prestel.co.uk/diamond/index.html
Chess programming. Arcade gaming. Other stuff.
Robert Hyatt
Tim Foden (ne...@diamond.prestel.co.uk) wrote:
: Hi,
: I have just completed changes to my transition table and
: searching code that allows storage and detection of
: positions that have been seen before in the game. This
: is of course to allow draw by repetition to be detected
: during the search.
: When a search node finds that its current position has
: occurred before in the game, it immediately returns with
: an evaluation of zero.
: I expected that this would reduce the number of nodes
: searched, but the opposite seems to occur. My prog
: ends up searching slightly more nodes, although it
: does now correctly steer around repetition draws when
: it is ahead in material.
: Is this a normal occurance (the increase in nodes
: searched), or does this imply that I still have
: a bug somewhere in the new code?
Doesn't sound very odd to me. Although you should try it over
several positions before you decide this is really happening.
In a single position this might turn a fail low into a fail
high or something, simply because of the 0.000 score you
return.
Tim Foden
Robert Hyatt wrote:
[snip]
]Doesn't sound very odd to me. Although you should try it over
]several positions before you decide this is really happening.
]In a single position this might turn a fail low into a fail
]high or something, simply because of the 0.000 score you
]return.
I will illustrate my point using this position (it is
a mate in 4 that was posted elsewhere in rgcc):
5rk1/1pnqb1r1/p2pRp2/2pP1PpQ/P1P1NpP1/3B1P2/1P1K4/7R w - - 0 1
I chose this position as an example becuse it has an obvious
draw by repetition (DBR) in it: 1. Qh8+ Kf7 2. Qh5+ Kg8 2. Qh8+ etc..
(my prog returns 0.00 as soon as it sees the second repition)
which I expect gets hit all over the search. Thus I expected
this position to be much faster using the DBR code.
Here is an example log output of my prog (extensions have been
switched off) with the DBR code in:
>>>>
Game stage: Middle game
Current eval: 0.25
Depth Time Eval Move
1: 0:00:00.030 0.26 Qh8+
2: 0:00:00.060 0.26 Qh8+
3: 0:00:00.280 0.25 Qh8+
4: 0:00:00.561 0.00 Qh8+
5: 0:00:06.099 0.27 Qh8+
6: 0:00:11.627 0.27 Qh8+
7: ++ Nxg5 (a=-23 b=77 e=0.98)
7: 0:00:34.650 320.93 Nxg5
local: t=0:00:34.650 nps=26123.6 n=905183 (f=122313 q=782870)
total: t=0:00:34.650 nps=26123.6 n=905183
extensions: check=0 recap=0
thread: user=0:00:33.488 kernel=0:00:00.000 cpu=96.6%
thread: cpu nps=27029.9
>>>>
Note that at 4 ply the value goes to 0.00, but at 5 ply
it goes back to 0.27. This is another reason I have to
believe I still have a bug somewhere. Surely if a
particular move has been shown to be a draw at 4 ply it
would should still be a draw at 5 no?
Here is the output without the DBR code:
>>>>
Game stage: Middle game
Current eval: 0.25
Depth Time Eval Move
1: 0:00:00.020 0.26 Qh8+
2: 0:00:00.050 0.26 Qh8+
3: 0:00:00.201 0.25 Qh8+
4: 0:00:00.541 0.25 Qh8+
5: 0:00:06.379 0.27 Qh8+
6: 0:00:11.897 0.27 Qh8+
7: ++ Nxg5 (a=-23 b=77 e=0.98)
7: 0:00:32.667 320.93 Nxg5
local: t=0:00:32.667 nps=26099.0 n=852577 (f=119818 q=732759)
total: t=0:00:32.667 nps=26099.0 n=852577
extensions: check=0 recap=0
thread: user=0:00:31.345 kernel=0:00:00.000 cpu=96.0%
thread: cpu nps=27199.7
>>>>
As you can see it looks at fewer nodes. This seems to happen
all the way through a game as far as I have tested. I expected
that the node the 0.00 eval is returned to may then cause more
more nodes to be searched, but thought that the fact that the
node that returned the 0.00 didn't search any further
would more than offset this. (note: I don't use PV search yet,
just normal AB).
With check and recap extensions switched on the prog does
even worse (aaaargh!!):
>>>>
Game stage: Middle game
Current eval: 0.25
Depth Time Eval Move
1: 0:00:00.030 0.26 Qh8+
2: 0:00:00.120 0.25 Qh8+
3: 0:00:01.011 0.00 Qh8+
4: 0:00:09.423 0.27 Qh8+
5: 0:01:09.840 0.28 Qh8+
6: ++ Qh8+ (a=-22 b=78 e=1.02)
6: 0:03:01.821 320.89 Nxg5
local: t=0:03:01.821 nps=27323.3 n=4967953 (f=874181 q=4093772)
total: t=0:03:01.821 nps=27323.3 n=4967953
extensions: check=45834 recap=28318
thread: user=0:02:59.969 kernel=0:00:00.010 cpu=99.0%
thread: cpu nps=27603.0
>>>>
This is where I hoped that detecting DBR would cut down the
search to enable the version with extensions to be
useful in this kind of position.
(I think there is still some sort of bug in the extension
code as theoretically it should see the checkmate at 5 ply)
Realistically I think I have more debugging to do, but I
am wondering whether the DBR code has introduced more bugs
or not. Isn't programming wonderful!
Robert Hyatt
Tim Foden (ne...@diamond.prestel.co.uk) wrote:
No. IE suppose you do the 4 ply search and you only have two legal
moves to try. One says 0.000, the other says -.3, so you take the
0.000 move. But when you go to depth=5, the -.3 move suddenly looks
better because now you can see deep enough to see some tactical
opportunity you didn't see before.
In your case, it is likely that you are varying at ply=3 on
this move, because the deeper search shows you how to avoid the
draw *and* get a score > 0, while the previous iteration could not
see how to do this...
: Here is the output without the DBR code:
: >>>>
: Game stage: Middle game
: Current eval: 0.25
: Depth Time Eval Move
: 1: 0:00:00.020 0.26 Qh8+
: 2: 0:00:00.050 0.26 Qh8+
: 3: 0:00:00.201 0.25 Qh8+
: 4: 0:00:00.541 0.25 Qh8+
: 5: 0:00:06.379 0.27 Qh8+
: 6: 0:00:11.897 0.27 Qh8+
: 7: ++ Nxg5 (a=-23 b=77 e=0.98)
: 7: 0:00:32.667 320.93 Nxg5
: local: t=0:00:32.667 nps=26099.0 n=852577 (f=119818 q=732759)
: total: t=0:00:32.667 nps=26099.0 n=852577
: extensions: check=0 recap=0
: thread: user=0:00:31.345 kernel=0:00:00.000 cpu=96.0%
: thread: cpu nps=27199.7
: >>>>
: As you can see it looks at fewer nodes. This seems to happen
: all the way through a game as far as I have tested. I expected
: that the node the 0.00 eval is returned to may then cause more
: more nodes to be searched, but thought that the fact that the
: node that returned the 0.00 didn't search any further
: would more than offset this. (note: I don't use PV search yet,
: just normal AB).
node counts here won't mean anything, because your new 4 ply search
(0.000) is more accurate. But even more important, it represents a
totally different value for alpha, which is going to change the shape
of the tree, possibly significantly..
: With check and recap extensions switched on the prog does