> but the program which gets deeper in the movement tree, should always win

It doesn't always work like that. Usually, since examining, the whole move tree is very expensive, heuristics tend to kick in at various points providing assessments for positions (thus helping to prune the tree). It is quite possible to land in a position where your set of heuristics is not quite right.

The decision tree is enormous. One of the ways one can cope with that is to sample it, i.e. use randomness.

http://en.wikipedia.org/wiki/Monte_Carlo_tree_search

Aside - I'm very surprised that this comment got enough downvotes to gray it out. It's sad that someone asking an honest question (and I had the same thought occur to me as well) about a seemingly strange result loses karma for it, when this sort of debate is what should be being encouraged. Fortunately there are a couple of replies that do explain why randomness and luck are a factor in computer chess programming...