Memories of Lyn Thomas

Earlier this year, Lyn Thomas, one of the UK's leading researchers in Operational Research, died.   He had been professor at the University of Southampton, and a prolific writer about many topics in O.R., particularly about credit scoring, start-up firms and finance  His contribution through articles, books and lectures over the past 30 years has been immense.

I met Lyn many times and he was always a perfect gentleman and good correspondent.  I was thinking about him recently when I recalled correspondence we had exchanged about the lighter side of O.R.  I had presented a paper at a conference about dynamic programming and board games, which was eventually to become a published survey paper on the subject.  Lyn was researching and modelling for his paper "The best banking strategy when playing The Weakest Link" published in the Journal of the Operational Research Society (July 2003, Volume 54 (issue 7) pp 747–750) whose abstract reads: The paper uses dynamic programming to investigate when contestants should bank their current winnings in the TV quiz show, ‘The Weakest Link’. It obtains the optimal strategy for the team as a whole and then looks at two possible reasons why the contestants tend to use other strategies in reality.

He sent me his models to test and comment, and that led to a further exchange about models for the Microsoft online solitaire game "Freecell".  In my presentation I had commented on the original version of this which had 32,768 starting positions and all but one were soluble.  He asked about the way that this analysis had been done, and whether some starting positions were harder than others.  The answer to the first question is that people had solved the 32,767 soluble cases, and then had used a Dynamic Programming approach to show that the final one was not soluble.  For the second question, I could point him to some analyses of the moves to a solution.  Solving a given starting position requires a sequence of moves.  For some starts, there are numerous possible opening moves, and the tree of possible moves becomes very broad.  For others, there is a unique sequence of moves which transforms the starting position into one from which a tree of possible moves follows on.  The longer that sequence, the harder the problem.  Other problems have a diversity of opening moves, which converge on one bottleneck position, which all sequences pass through.  Lyn saw parallels between this solitaire game and some of his work on scoring, and I was delighted to be a distant part of that work.  

Why think of this now?   Freecell is one of the solitaire games provided by Microsoft as a free game, but with twists.  Along with other games, there are four standards of difficulty in the "Daily Challenges".  For Freecell, with complete information available to the player, the problem is to find an appropriate sequence, which may be unique or one of a small number, or one of very many.  So, somewhere, Microsoft have access to a solution tool which measures the complexity of the set of possible sequences for this game.  I wonder how it is calibrated.  I am sure that Lyn would have been interested too.