Some more thoughts. I am splitting a long post in two.
Scaling is not the problem (please reread the first post in a previous
thread for arguments).
I think the problem of MCTS is search instability due to selectivity.
A couple of authors hinted on this. But was never able to search wider
without making the program weaker. I think it is very important to
search deep in go. So the question is can we search deep and wide at
the same time? I think so but not in the same search. but using
results from previous searches in a way that does not hinder selective
search for doing its job I believe progress can be made.
The problem with selective search is that it may play different moves
every time the same position is searched. This is caused by the very
nature of random playouts (as long as different seeds are used)
because in a huge tree there are always moves that are overlooked just
because the samples turned out the wrong estimate of the true win
rate. This is a fact of statistical sampling that cannot be overcome.
Since we have a distribution of moves one move must be the best and
one move must be the worst (ignoring cases where moves are equivalent.
I also consider complexity important. Two moves may be equal with
perfect play but against a non-perfect player the moves may be very
different).
And even if the best move is played in 85% of the positions in a good
game there will then on average always be a couple of mistakes.
Valkyria has this problem no matter for how deep it searches. There
are many positions where moves are forced and there is no choice. But
in high quality games on 9x9 the majority of positions have a choice
between 2 or more moves.
Note that this is not an argument that the program does not scale. The
distribution of moves considered narrows as thinking time increases so
it scales properly. This is more an argument that we might improve
search so that scales even better.
Also there is a problem of limited memory (I am now thinking of
correspondence games on Little Golem where a day of computation can be
spent on a single move).
Valkyria will run out of memory in a couple of minutes. A simple fix
is to prune the oldest nodes in the tree and reuse the nodes. This
works very well but it has the limitations that after a while the
program will re-search pruned positions and "rediscover the wheel"
over and over again.
***
In the next part I will explain what I have been experimenting with on
CGOS and Little Golem for over half a year with Valkyria to overcome
theses issues. The goal is simply to play perfectly on 9x9.
Best
Magnus
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
