On Sat, 2006-10-14 at 14:21 -0700, Dave Dyer wrote:
> If the search was depth first, and you seeded the search with some
> well played games, then alpha beta pruning ought to result in some
> truely enormous reductions in the search space.
Hi Dave,
I want the hybrid system to be able to evaluate ANY position, not just
starting from the opening.
Once the system is completed a search will work like this:
1. From the supplied position, we perform an exhaustive alpha/beta
search.
2. As we encounter each node, we check to see if the current
position
matches the bloom filter. We have 2 cases:
A) The position gets a positive hit in the bloom filter.
If a position gets inserted into the bloom filter it's
because the evaluation is known to be incorrect - so we
continue searching.
A bloom filter occasionally returns a false positive, but
that does not affect the admissibility of the algorithm.
B) The position is NOT in the bloom filter. In this case we
have the assurance that the score bound returned from the
evaluation function is correct. So we stop searching if
the lower bound is >= beta, or the upper bound is <= alpha.
Of course we may be required to continue searching.
The hope is that we will perform a relatively small search, which
likely will be deep and narrow and be able to solve any position in a
short amount of time.
The static evaluation is what is "judged" and sometimes veto'd by the
bloom filter.
The static evaluation will return a LOWER bound and an UPPER bound on
the score, and will sometimes be WRONG. The required size of the
bloom filter is a function of how many times the evaluation function
returns the bounds incorrectly.
The conflicting goals of the evaluation function is to be RIGHT as
often as possible and still return the tightest possible bounds
reasonably possible.
Someone mentioned KO positions as needing to be represented in the
table. My solution (and I'm still thinking this through) is to only
consider simple KO and consider each position in the "pseudo database"
as a position with no history. If a position is encountered that is
dependent on history (a potential capture is illegal due to simple KO)
then it is treated as if it were found in the filter - we consider it
as not being understood and continue to search.
I'm more optimistic about this than I was before. This is because I
can imagine that a standard searching program with a good evaluation
might play close to perfect even with a realtively shallow search. So
I can also imagine a program using this "heuristic database" might be
able to do an exhaustive search taking advantage of the bounds and
scores that the database can understand which are perfect. We know a
program already exists that can ALMOST do an exahustive search from
the opening position without such a database.
- Don
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
