RE: [computer-go] Addressing the root of the problem

["Daniel Burgos" <Daniel_Burgos@xxxxxxxxx>]

Hi Campbell,

These are the terms:

I'm trying to find a board evaluation function that applied to a board
configuration allows to a player to decide where is worth to play
(tactic approach).

My hypotheses are:

1) For each board configuration there is a set of optimal positions
where to play. In other words, each position has a fitness (i.e. can be
scored).

2) The function to score the board can be expressed as a set of
patterns.

3) If function A is better scoring the board than function B, then the
players using function A will win players using function B most of the
times.

To find this function (or functions) I will use an evolutive algorithm
because I know what I want but I don't know how to design it or if it
even exists.

To compare two functions what I do is:

- Each player plays its stones in the valid board position that has the
highest score. If there are many, just take one (like an improved random
player). 

- The game ends when there are not more valid positions of after a max
number of movements; for instance, twice the area of the board.

- At that point, the function with more territory* wins. In the case
that both functions have the same territory, the one with more stone
liberties wins. If both have the same liberties then wins the
faster/shorter function.

*By territory I mean empty positions surrounded by one color stones plus
the number of prisoners. 
Dead stones with liberties are not removed; this is a hard problem that
cannot be solved only with an evaluation function but using a tree
search algorithm. I think this is the point that make go so hard,
because introduce some way of recursion: you cannot evaluate until you
know when a stone is dead, but you cannot know when a stone is dead
until you do a tree search, but you cannot do a tree search (because the
force-brute tree is so huge) until you evaluate then you are at the
start line again...

If this algorithm converges to a set of useful functions, then I will
start applying them inside a minimax algorithm. Otherwise (what a pity)
I will try other hypotheses...

I have the code that, given a function, evaluates the board. I will
start working in the evolutive algorithm ASAP.

Daniel

-----Original Message-----
From: computer-go-bounces@xxxxxxxxxxxxxxxxx
[mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx] On Behalf Of Campbell
Macdonald
Sent: Tuesday, October 26, 2004 11:05 AM
To: computer-go@xxxxxxxxxxxxxxxxx
Subject: [computer-go] Addressing the root of the problem

Daniel

I am interested in better understanding this approach
you have proposed.

What can you share in terms of your approach?

Campbell Macdonald
campbell_macdonald@xxxxxxxxxxxxxxxxx




I'm following that approach to solve Go: find a small
set of
rules/patterns (as small as possible) to evaluate a
board in order to
decide where is worth to play. I want to cut down the
decision tree.

I think my hypothesis is the same as yours: because
the complexity of go
is coming from its small set of rules (but very well
designed), its
solution should be something similar.

Something inspired in the small rules that allow
creating complex
figures as the fractals.

But, what is this set of rules? This is the winning
answer, if our
hypothesis are correct I'm afraid...

I'm implementing evolution algorithms for that, but
they are only in
design stage by now.

Daniel


		
__________________________________
Do you Yahoo!?
Yahoo! Mail Address AutoComplete - You start. We finish.
http://promotions.yahoo.com/new_mail 
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/