Tuesday, January 28, 2020

A conversation with Alan Turing

I was recently rummaging around some old half-completed projects when I came across an idea for a chess-playing computer program that had been lying around for years. It hinged on a single hunch that I thought might be worth exploring, but before I can explain that I need to provide a bit of background on how chess-playing programs work.

The classic chess playing program (chess engine) relies on two basic ideas:

The Search. For any given position, the program examines all the legal moves available and, for each of these moves, looks at all the moves available to the opponent and, for each of these in turn, looks at each of the possible responses. As there might be around 30 moves to choose from at any one time, the number of possibilities rapidly grows to be in the millions so eventually you have to stop, at which point, we come to the second idea:

The Evaluation. For every possible outcome in this rapidly branching tree of moves and counter moves you work out a score for the position - high if the side whose move it is is winning, low if it is losing. All that remains is to choose which of the first moves is the one that leads to the position with the highest score.

Evaluation functions differ from one chess program to another but they all examine the layout of pieces and calculate a score based on a number of factors - the first being a simple totting up of pieces that remain on the board. Others factors typically involve looking at the placement of pawns (pawn structure), whether major pieces are in strong, central positions and so on. There are many variants and it is probably true to say that chess engines are primarily distinguished by their evaluation functions. Nevertheless, given the evaluation has to be repeated millions of times, it needs to be fairly succinct.

My own idea for a chess program proposed an extremely straightforward (and fast) evaluation function that simply counts the number of moves available to each side and calculates the difference. Of course, since capturing a piece immediately eliminates it from making any further moves, the hope was that my program would automatically try to make captures as a consequence of minimising the moves available to the opponent. The appeal of checkmate is even easier to understand, as that occurs when the losing side has absolutely no moves left.

So in mid-December I set about trying to write my engine which I had decided to call Moby on account of the fact that the evaluation function measures mobility.

I didn’t start from scratch but from a previous well-documented engine called Vice which I partly rewrote and adapted over the course of a few weeks. It took me longer than expected, as my programming skills have grown a bit rusty.

I embarked on this adventure in the drab, gloomy days following the election, possibly as a means of distracting my thoughts from the prospect of 5 more years of Conservative government. And so, as each dreary, rain-sodden day was followed by the next, through long nights when every line I wrote seemed riddled with errors, I began to question whether the project was less a genuine investigation and more an attempt to prove that I had still got it when it comes to programming (or coding as it is called these days). And each night, as tiredness took a grip, I would take myself to bed only to lie, raking through the code in my head, in search of what was going wrong.

But I did get it working eventually and what a strange game of chess it played. For example, when considering positions in which a rook happened to have no immediate moves available (as is often true near the start of a game) it was quite happy to sacrifice it in order to let another piece move into a slightly more open position. It wasn’t all hopeless however; it would occasionally make a clever move. I began to see that some of the more ridiculous mistakes could be avoided by combining mobility with a simple count of the pieces remaining on the board.

So have I gone ahead and made this improvement? Well no — but I probably will. But that’s not the point right now because here the story takes a different turn.


I thought it might be a good idea to share my investigations with the world or, more precisely, the chess programming forum on a website called TalkChess, and so I submitted a contribution describing my approach and invited people to make comments. I had a number of responses the majority of which could be characterised as:

“That’s interesting but it’s unlikely to get you very far.” 

Another person wanted to know what it was that had drawn me to such an austere choice of evaluation function to which I responded that it was largely aesthetic, or the appeal of seeing complex behaviour emerge from a simple rule.

But it was one of the later responses that I found most enlightening. A respondent from Germany (Gerd Isenberg) wrote:

“Maybe you aware that programs like Barricelli’s Freedom and Marsland’s Wita used mobility as the evaluation term.”

I replied that I was not aware of these programs, to which he replied

“Yes, the idea of using mobility in evaluation is old. Also note Slater’s ‘Statistics for the Chess Computer and the Factor of Mobility’ and the discussion with Alan Turing.”

My interest was immediately sparked by mention of Alan Turing, widely considered to be ‘the mother and father’ of theoretical computer science and artificial intelligence. The discussion referred to was documented under an item on Eliot Slater who, as well as having an interest in a chess playing machine, was mainly known as a psychiatrist with some questionable views on eugenics. Slater, it appears, felt that mobility was a key indicator of the strength of a chess position and suggested that a chess playing machine programmed to maximise its advantage in mobility would play a strong game - just as I was speculating.

To this, Alan Turing replied:

“Although the immediate mobility is a useful measure of the relative advantage of the players in normal play it by no means follows that it is wise to direct one's play to maximising such a measure. To do so would be like taking a statistical analysis of the laundry of men in various positions and deciding, from the data collected, that an infallible method of getting ahead in life was to send a large number of shirts to the wash each week.”

So that’s that - done and dusted. I’m not inclined to argue with Alan Turing and in any case his laundry simile, despite being somewhat quaint by today’s norms, is pretty deflating.

But the startling fact is that the discussion between Slater and Alan Turing took place 70 years ago, in 1950, at a time when the number of computers in the world could be counted on the fingers of one hand! The whole episode felt like an immense cycle that had taken an unexpected turn and had transported me back to the time of my birth. And despite the fact that my speculations appeared to have been thoroughly dispensed with around the time I was learning to walk, I was left with a feeling of quiet contentment - happiness even.

Maybe it also had something to do with the fact that the sun had begun to shine again, bringing a lightness in the air and the first intimations of spring.

3 comments:

  1. In case you missed it, this Turing recent Turing related news is extraordinarily weird!
    https://www.theregister.co.uk/2020/01/22/alan_turing_belongings_found/

    ReplyDelete
  2. Anonymous1:39 pm

    Like a well-written and insightful poem, the final lines land beautifully.
    Maxine

    ReplyDelete
  3. I agree, those last lines settle the adventure, along with knowing that it began the day you were born, dear David.

    ReplyDelete