In building intelligent tutoring systems, it is critical to be able to understand and diagnose student responses in interactive problem solving. However, building this understanding into a computer-based intelligent tutor is a time-intensive process usually conducted by subject experts. Much of this time is spent in building production rules that model all the ways a student might solve a problem. In our prior work, we proposed a novel application of Markov decision processes (MDPs) to automatically generate hints for an intelligent tutor that learns. We demonstrate the feasibility of this approach by extracting MDPs from four semesters of student solutions in a logic proof tutor, and calculating the probability that we will be able to generate hints for students at any point in a given problem. Our past results indicated that extracted MDPs and our proposed hint-generating functions will be able to provide hints over 80% of the time. Our results also indicated that we can provide valuable tradeoffs between hint specificity and the amount of data used to create an MDP. (Contains 12 tables and 1 figure.)