One possible explanation is that the introduction of a random element into the cognitive process allows him to generate multiple potential future scenarios which compete deterministically as the actor chooses which to pursue. While the intelligence has no control over how the random element influences the creation of those scenarios, it does have deterministic control over the selection process.
I suppose that the randomness could also be integrated into the choosing process by randomly mutating the mechanism used to choose and selecting those that perform better over time.
All this being said, I still don't see how making an intelligence non-deterministic implies anything similar to "free will." It may be a conflict of definitions, since I take free will not only means that there is some non-deterministic decision making process, but also that the actor actually retains control of that non-deterministic process. I should be able to decide between chocolate and vanilla ice cream consciously and non-deterministically.
As a matter of full disclosure, I should note that I am not convinced of humanity's own free will, since it basically just means having the ability to choose to act in a way that is at odds with the innumerable causes that have led up to the decision to act. Also, I think my definition implies a continuous, identifiable aspect of intelligence which exists outside of physical reality. I don't see any evidence that either of these are necessary to explain what we observe, but thinking about the implications of true randomness in the cognitive process has given me new food for thought.