On Sun, 2007-03-11 at 12:03 -0700, Brian Slesinsky wrote:
> With UTC, if I understand correctly, it would eventually try every
> possible sequence, but of course not within the time limit, so it
> isn't clear that it starts with an "imperfect subset of moves" that is
> separate from the other factors.
You mean UCT, not UTC. UCT doesn't try every possible sequence, and
neither does alpha beta. But it will look at enough of the tree
to play as if it had perfect knowledge (given enough time.)
UCT is said to extremely selective, but in a nicely tapered and
controlled
way. It's far more selective that Alpha Beta pruning.
In my opinon there are 3 different definitions of being "selective"
that have caused a great deal of confusion:
1. selective in the alpha beta sense. alpha beta pruning moves
in an admissible way and one could view this as selectivity
but very few people do. A program doing only alpha beta
pruning is considered a brute force tree searching program.
2. selective in the tapered sense - such as null move pruning in
computer chess. UCT is selective in this sense, but it's
actually a brute force technique, becuase it never truly
prunes moves permanently from the tree. Null move pruning
never prunes move permanantly from a tree, so in some sense
a good chess prgramming with null move pruning is still a
brute force searching program.
3. selective in the "true" sense. Such a program tries to
identify bad moves and prune them from the tree, but they
are pruned permanently. NO matter how deep or long you
search they will never be considered.
I think "true" selective programs, unless the pruning criteria
is fully admissible, is self limiting. You can probably build
a strong program but you will be bound strictly to the quality
of your selective algorithm. Such an algorithm would play
imperfectly even on an infinte speed computer.
UCT is admissible - it will ALWAYS find a winning move if you
are in a winning position.
- Don
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
