5x5 was solved with a massive brute force search approach. Memory was
used for large hash tables and endgames were scored early using Bensons
algorithm, otherwise it would not have been feasible from what I
understand.
Yes it was "proof" level paper, doing something lot less
mathematically valid for example only some open source code which can
do good search against 7*7 is more realistic. Kind of allowing all
possible short-cuts, like using several patterns to judge board score
even it is not absolutely sure that score is right for combination of
patterns.
Although that's interesting, it's just a search. I would like to try
something a little more clever (I'm just not clever enough to figure out
what that should be!)
I'm thinking perhaps in terms of a database assist. It would be
interesting if we could come up with a small board scoring system that
is very accurate.
Agree that goal, scoring system must be accurate _when_ it thinks it
knows score. I see score meaning minimal score for player archieves
from this position if plays right.
A database system might identify rules and
exceptions that can be applied. For example, we have the eye rule in
our monte carlo programs - although that is extremely powerful it's not
100% admissible - there are some exceptions although they probably occur
only a fraction of a percent of the time. The eye rule would be
powerful in a hybrid system because it is a fairly large class of
positions where we can say, "never move to that point - it will never be
the best move."
But is this other class of used patterns also to guide search, I see
this estimator goal should proof minmum scores for player.
All kind of eye knowledge is offcourse important for minimal scoring
patterns.
A trivial way to include it in a hybrid system is to just put an entry
in a table for the few times that is wrong. Or even better, try to
determine the exact context where it's wrong. Perhaps it's never
wrong in a 5x5 game?
I have thinked patterns which take area of board and proof that
another player can take "X" points from that area/group.
If that player has benson alive groups in other areas on board score
can be proven "benson alive groups" + one group which is not benson
alive but can be proven to get "X" points if only defending that group
for rest of game.
Tables like this can be stored compactly with bloom filters.
Here is a question. How do you determine what a final board looks
like? If you are actually building an endgame table, you start with
all the final positions. But seki seems to be very difficult to
identify.
I am planning partial table patterns. Seki and other consepts should
be used with patterns if possible.
I'm doing a little experiment right now with small boards and a table
with a few million hashed entries. I'm trying to store only perfect
scores in this table but my definition is weak. I search a position
using alpha/beta and if several iterations consecutively return the same
score, I consider it a perfect score. I know this definition is
subject to error.
Yep, such practical problems are intresting, but atleast those are
possible to fix as 5*5 and earlier proofs show.
It can be intresting attack 7*7 from end positions side, trying to
make solver that gives exact score for part of positions and try to
"increase" that procent but keep score exact. When end position
scoring system is good enought then it could be possible try start
search from some near end middle positions. I don't know is anybody
really deebly investigated 7*7, kind of more like started existing go
programs search algorithms from scratch and gived up. I also lack of
7*7 board knowledge, other hand 7*7 sounds practical, fast and light
board.
t. harri
To handle ko, I ignore everything except simple ko. I don't store
positions where the previous move was a single stone capture since it
might be a simple ko. My hope is that long superko loops will be
avoiding by some winning side. This is probably not a correct
assumption, but I have read that it works on 5x5 and less - it's always
better for one side to break the loop.
The evaluation function is to consider every stone alive, and any empty
intersection that touches only one color to belong to that color. The
evaluation function is not really used though - except to identify
perfect scores (where several search iterations return the same
results.)
In all the 4x4 examples I've seen, I've never seen a 3 iterations in a
row return the same score unless it was correct. However, I'm using 4
in a row to determine that a score for a position is exact. If the
last 4 iterations return the same score, I put the root position in the
hash table as a perfect score. I sample the space randomly by
making a random move after searching some position, so that it explores
the full space eventually. This is not very systematic, but it's
just for fun right now.
- Don
Harri Salakoski wrote:
> Has anyone did this before or has anybody thoughts about this?
I have done that for 4*4 and 3*3, my code is not in shape that it
could be used 5*5 but have high believes it is anyway possible used
for 6*6 some day. But this was discussed in this group earlier and
nothing new has occurred since then.
7*7 is solved in ten years ... hahaa no need to reply that. You need
very good solver to proof that in this particular "middle" position
Black or White can archieve better than optimal score and no reason to
continue search. Bigger cut better..
Doing investigations in http://sourceforge.net/projects/narugo
project and happy to co-operate.
t. hArri
----- Original Message -----
*From:* Ben Lambrechts <mailto:[EMAIL PROTECTED]>
*To:* 'computer-go' <mailto:computer-go@computer-go.org>
*Sent:* Wednesday, November 07, 2007 9:03 PM
*Subject:* [computer-go] Solving Go
I want to create a perfect player on board sizes 3x3, 5x5 and
maybe 7x7 and beyond.
But I have no idea how to start. How do I create the move database
and how do I select the perfect move for every position?
I know Go is solved on boards 5x5 and smaller, but there is no
program that plays by this perfect moves.
Has anyone did this before or has anybody thoughts about this?
Ben
------------------------------------------------------------------------
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
------------------------------------------------------------------------
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
