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

["Persson, Magnus" <persson@xxxxxxxxxxxxxxxxxx>]

> -----Original Message-----
> From: Antti Huima [mailto:antti.huima@xxxxxxxxxxxxxxxxx]
> It is common knowledge that increasing search depth when evaluation
> function is kept fixed raises game play strength. But what is the
> mathematical reason for that?

The evaluation function E(t) is correlated with G(t) and if the
evaluation function is reasonable (as in most game program with some
effort put in them) they tend to converge to the same value as t
approaches the end of the game.

As a consequence, although a bad position might have a wrong positive
evaluation (such that a shallow search causes a bad move to be played),
deeper in the tree E(x) and G(x) will eventually converge for all leaves
such that the bad move is not considered.

An empirical observation is that deeper search rarely improves the
probability of the best move been selected, but it may reduce the
probability of a really bad move being selected.

So program with pattern based move generation (my Viking) with shallow
full board search will often play very good moves but sometimes plays
extremely bad ones.

A program using deeper search (Viking evaluation function + alfabeta)
will often play a little bit strange moves rather than the best ones but
never plays those extremely bad ones. 

Check out this paper at the link below. I think it tries to go a little
deeper with these kinds of questions.

http://www.cs.ualberta.ca/~jonathan/Papers/Papers/svsk.ps

--
Magnus Persson
Center for Adaptive Behavior and Cognition
Tel: +49-(30)-82406-350
Cell phone: +49 163 6639868


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