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

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

The whole question is very interesting. I recently came to the conclusion
that more understanding of this problem could be a key point to improve
computer skills. I suggest you read Bouzy's papers about monte-carlo Go
(he made a very interesting talk 2 months ago). I also remember someone
giving references about bayesian approaches to play games (on this list,
maybe one or two years ago): the parper described some attempt to deal
with the fact that players (computer or human) are never perfect players.

Regarding the probability of winning, I will second Antti Huima. The fact
that a given position is a game theoretic win is not a probability. A position
is either a win or a loss (even if you don't know it, which is another point).

So the only probabilities I can think about are:

given some evaluation function,
given some algorithm to select a move at any position,
given some opponent:

1. what is the probability I will get better / same / worse result than game
theoretical value when playing a whole game
2. what is the probability I will reach the next position with better / same /
worse theoretical result than the one I could have reached with perfect play,
when using the evaluation function to select the move
[single move problem]

First one: if both players are perfect probability is 1 for same result. If one
player is not perfect probability is 1 for the opponent to get the same or a better
result than the theoretical value. If neither are perfect, we come back to reality,
and here comes the question of opponent model. In the paper I was refering
to (unfortunately I don't remember the reference), I understood the opponent
model was the program itself in a process of bayesian learning. With monte-
carlo Go approach I understood the opponent model is a random player with
basic domain-dependent knowledges (Bruno could probably confirm or
provide a correct description). With SlugGo, I guess the opponent model
is GnuGo?

Second definition is probably what Don is refering to (or some equivalent
definition). It is independent of the opponent model (which can be considered
as a desirable property).

Antoine.

What is a probability of winning?

Probability that a given position is a game theoretic win.  I assumed
that the context of the discussion (evaluation function confidence)
made this clear.

- Don

[...]


  Probability that the playing algorithm will win against a hypothetical,
  fixed opponent mechanism---which is circular, because the evaluation
  function affects this probability? And what is the opponent model?

  Or probability that the game tree node is a game-theoretic win? What
  does this mean? One game node is either win or not, so there is no
  stochastic experiment. You need to have a repeated experiment or a
  population larger than one object to be able to speak of probabilities.

  I'm not being rude. I think this is one of the key points. "Probability
  of winning" is often mentioned, but what does it mean? Every node is a
  game-theoretic win or not, so no probability here. Results from actual
  game play, with our imperfect algorithms, depend on the opponents. Is
  there an opponent model implied? Against a perfect opponent, all
  algorithms that can make mistakes should evaluate the probability of
  winning to zero!

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