RE: computer-go: hascoding under the super-ko rule

[met@xxxxxxxxxxxxxx]

Jean-Pierre wrote:

> About the hashcoding issue, I would be very interested if you could
explain
> in a few words how your hashtable manages big problems. One big problem
with
> tsumego solvers is the huge size of the search space in go. The number of
> nodes quickly reaches several million nodes,

Yes it does!

> even for average sized problems
> (15-20 points of playing-space). For example GoTools, Thomas Wolf's
> excellent solver uses a hashtable of fixed size (maximum = 65535
entries).
> The solving speed is incredibly fast for small problems, but slows too
much
> on bigger problems.

I don't think that the fact that GoTools slows down on "bigger" probles is
due to the "small" fixed size transpositiontable. I rater think it is
because
the effort is at least: (n-1) * (n-3) * (n-5) * ...  * (k+1). Going from
n=15 to n=20
makes it a lot harder. For n=25 its relly hard.

> Is your hashtable size adaptative?

No, it is not adaptive!

Rigth now the transpositiontable have a size of 1 000 000 entries but
for that problems my program is able to solve it rarly us more than
50 000 - 100 000 entries.

> Do you increase it until it explodes ? Do
> you drop the oldest positions to make room for newer ones ?

Right now I have a very simple strategy. I just trows away the entry
that occupies the slot I need. That is quite sufficient as I just use
a thenth of the tablesize. In other similar program that I have
written I have used the more sophisticated 8-probe scheme
described by Mr Hyat. Similar to the scheme used by the nice
chessprogram Hitech (and John Tromps Connect4 solver)
The scheme ensure that you throws away the "least usefull"
entry of 8 "randomly" choosed candidates. How you define
"least usefull" is up to your implementation. The size of the
tree to solve the position is a good candidate to decide that
but in a playing (not a solving) program there might be other
more usefull criteria as the table is resued between different
searches.

Regards,
Mikael Thulin