[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [computer-go] An [open] question on game tree search theory

At 22:19 19/01/2005, Daniel Hallmark wrote:


May I ask a question?

You have defined G(t) as consisting of only 3 discrete values:
Black wins, draw, or White wins.

If it is true that there is such a G(t) for every board state, then
I would agree that probability never enters into the equation except
for the probability that E(t) gives us an answer that directly
correlates to G(t) for that state.

However, and this is most likely my ignorance of Game Theory showing,
can it be conclusively shown that your definition for G(t) is correct
for the game of Go?

Is there not a possibility that for a given game state t, some
percentage of G(t') are unrefutable wins for white, some are
unrefutable wins for black, and some can be fought to a draw?

If I understand you correctly, the following argument should show that
there is no such possiblity.

Suppose for contradiction, that there is some node t for which G(t) is
not one of win lose or draw.

The state t will have some leaves of the tree
as decendents, because play continues for ever from a node with no leaf
decendents, and Antti defined such a node as a draw.

On the other hand, t is not a leaf itself, because all leaves are either win
lose or draw.

Maybe there is there is more than one node for which G(t) is not win lose or draw.
If there is more than one, we let t be one that is as close to a leaf as possible.
It follows that all the children of t are win lose or draw. But G(t) is equal to
G(t') for some child t' of t (it will either be the best G(t') or the worst,
depending on which players turn it is). So we find that after all, G(t) is either
win lose or draw.

--
No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.300 / Virus Database: 265.7.1 - Release Date: 19/01/2005



_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/