If we wanted to create a robot, an android, how woudl you program it to have free will?
How would you program it to imprvise a solution to a problem?
Well, according to the Hitchhiker's Guide, they went about it by programming a robot to scoop up a herring sandwich from the floor. The scoop was designed to drop the sandwich once the robot straightened up again. So, the robot would see the sandwich, say to itself "Oh, look. A herring sandwich." It would then bend over to scoop it up, straighten up, drop the sandwich, see the herring sandwich on the floor and say... They soon learned that they had discovered boredom and many more emotions came soon after.

(Hey, at least I dredged up HHttG reference more obscure than 42.)
Seriously, I would try to model the human brain as closely as possible. Build up the seperate parts of the mind, one on top of each other. Make them unaware of each other. Object oriented programming so to speak. Then place the chatterbox on top of the whole mess and convince it that it was in charge. Would have to experiment with how to provide an emotional feedback loop. Probably something similar to Aasimov's method of increasing positronic flow or whatever. Allow the juice to flow more freely.
Perhaps that would be the toughest nut to crack. Emotional response. If there is no way to accomplish this through hardware, it might take wetware. Add some biologic elements that can "feel" for the machine.
By the way, way to quote Don Qijote.

I've never seen it, but I vividly recall Sam Beckett performing it in Quantum Leap. Chasing windmills... Good way to look at improvisation.