Author: Dan Honeycutt
Date: 20:39:10 04/26/04
Go up one level in this thread
On April 26, 2004 at 17:09:53, Andrew Wagner wrote:
>On April 26, 2004 at 14:02:58, Dan Honeycutt wrote:
>
>>Andrew:
>>You cost me a lot of work. After your post re Fine#70 I carefully reread all my
>>code, single stepped everything and still couldn't find the problem. So I
>>scrapped my entire hash code and rewrote it using a two part table modelled
>>after Pepito. The other thing I did that Pepito does: in debug mode every store
>>does a probe to make sure that what just went in to the hash table is what comes
>>out. That brought several bugs to light right away. Took a little longer to
>>discover that storing a negative depth caused a blowup.
>>
>>Bruja now finds Kb1! with better than +2 score in about 130k nodes. I've just
>>started testing but results look good - new hash leads old hash 14-9. Thanks
>>for your post and I hope you have had success with Trueno.
>>
>>Dan H.
>
>
>Hi Dan. Glad to hear you're getting good results now. I'm still having some
>troubles with Trueno, but I just found a big bug, so maybe I'm heading in the
>same direction. Can you possibly give some more details on this debug test
>you're doing? I'm not sure I'm following that. And when you talk about storing a
>negative depth...that's from null-move reduction I assume? I hadn't thought of
>that, I should check that. Thanks! Andrew
Hi Andrew:
Omitting the frills (mate score adjustment, move store for ordering, null move
stuff etc) and translating to psudo VBasic, below is what I'm doing. The two
part table turned out to be quite simple once I understood it. The negative
depth (which in the code below wouldn't happen and wouldn't matter if it did)
resulted because I do fractional ply extensions. Instead of a Type/struct for
the hash entry I shift/and/or the values in and out of a 64 bit integer. This
makes the entry a bit more compact but when I or'd in the (unexpected) negative
value it caused havoc.
Hope this helps.
Dan H
Type hash_entry
key
depth
flag
score
End Type
Dim table(num_entrys) As hash_entry
Const num_entrys = power_of_two
Const mask = (num_entrys - 1) Xor 1 'two slots per key
Sub HashStore(depth, flag, score)
Dim index, depth1, flag1, score1
index = key And mask
If table(index).key <> key Then
'slot 1 is either empty or occupied by a different position
If table(index).depth > depth Then
'slot 1 is occupied and the present occupant is greater depth
'so leave it alone and put the new data in slot 2
index = index + 1
Else
'the new data looks better. move existing occupant (if any)
'to slot 2
table(index + 1).key = table(index).key
table(index + 1).depth = table(index).depth
'etc flag, score
End If
End If
table(index).key = key
table(index).depth = depth
'etc flag, score
If debug_mode Then
HashProbe depth1, flag1, score1
If (depth1 <> depth) Or (flag1 <> flag) Or (score1 <> score) Then
Stop 'Uh oh
End If
End If
End Sub
Sub HashProbe(ByRef depth, ByRef flag, ByRef score)
Dim index
index = key And mask
'try slot 1 where we put the "better" data
If table(index).key = key Then
depth = table(index).depth
'etc flag, score
Exit Sub
End If
'no hit on slot 1, try slot 2
index = index + 1
If table(index).key = key Then
depth = table(index).depth
'etc flag, score
Exit Sub
End If
flag = no_info
End Sub
Function AlphaBeta(alpha, beta, depth)
Dim temp, flag, score
HashProbe temp, flag, score
If (flag <> no_info) And (temp >= depth) Then
Select Case flag
Case exact
AlphaBeta = score
Exit Function
Case lower
If score >= beta then
AlphaBeta = score
Exit Function
End If
Case upper
If score <= alpha then
AlphaBeta = score
Exit Function
End If
End Select
End If
If depth <= 0 Then
AlphaBeta = Evaluate()
Exit Function
End If
GenerateMoves
temp = False 'no score > alpha so far
While MovesLeft()
MakeMove
score = -AlphaBeta(-beta, -alpha, depth - 1)
UnmakeMove
If score > alpha Then
If score >= beta Then
HashStore depth, lower, score
AlphaBeta = beta
Exit Function
End If
temp = True
alpha = score
End If
Wend
If temp Then
flag = exact
Else
flag = upper
End If
HashStore depth, flag, alpha
AlphaBeta = alpha
End Function
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.