1997: the original

NeuroDraughts was my final year project at the University of Limerick: a draughts player that taught itself the game by playing a very long series of matches against copies of itself. By June 1997 it could beat me, which, as will become clear, is a less impressive sentence than it sounds.

The aim

The strong game-playing programs of the day got that way through two things: rules of thumb tuned by hand, and the ability to search through positions at a speed no person could follow. I wanted neither. I wanted a player that was handed the rules and a few simple features, was left to work out the rest by playing, and looked only a move or two ahead, much as a person does.

The report set the bar with some precision:

An acceptable level of play in this case could be defined as being able to beat it's creator.

This was not a high bar. I am no great draughts player, and the program was not required to be one either, only a slightly better one than me.

I chose draughts over chess because the rules are simpler, and simpler rules left more of the year for the parts I actually cared about: how a program learns, and what it should be shown of the board while it does.

Where the idea came from

The method is called temporal difference learning, and it was not mine. Arthur Samuel used the idea in a checkers program in 1959, and Richard Sutton set it on a formal footing in 1988. In the early 1990s Gerald Tesauro used it to train a backgammon player that reached world champion level, and Sebastian Thrun applied it to chess. NeuroDraughts set out to follow them, at a respectful distance.

I can't say now how I first came across any of this. As far as I remember, most of what I knew came from papers and technical reports I tracked down online, and the report lists more than thirty of them, which suggests a persistence I don't recall having. It also says I consulted both Tesauro and Thrun while working out whether the project was feasible. I have no memory of what they said or, if I'm honest, of whether they said anything.

The idea itself is simple to state. After every move, the program's opinion of the position it has just left is nudged toward its opinion of the one it is in now. At the end of the game, the last opinion is nudged toward what actually happened. Nobody has to tell it which moves were good, and it needs no library of expert games. You switch it on, and it plays itself for as long as you are prepared to leave the computer alone.

How it worked

At the centre was a small neural network that looked at a position and produced a single number, from -1 for a certain loss to +1 for a certain win. To choose a move the program tried each one in turn, looked a little further ahead, and played whichever led to the position the network liked best.

• The network. 38 inputs, 12 hidden units and one output, with extra links running straight from the inputs to the output. Samuel had found that a plain weighted sum got much better once a few combined terms were added, so I wanted a network that could do both.
• What it saw. Not the board itself but twelve features of it, cut down from Samuel's list, each spread over a few on-or-off inputs.
• Look-ahead. Three plies: its move, the reply and its next move. The report counts this as one move of look-ahead.

I had hoped to do without features altogether. The program could also be shown the raw board, in two different ways, and I tried both. Neither learned to play, and the report records the surrender in full: "In the end I had to concede and use feature mapping." It would be twenty-nine years before anyone found out why. The rebuild has the answer.

Checking the learning on a toy problem

When I first wired the learning rule into the network I had no way of telling whether it was working, which is an uncomfortable position to be in with a program whose whole job is to improve slowly. So I tried it on something small enough to check by eye: a five-by-five grid in which the program has to find the quickest way to a goal square. It used the same network code, unmodified, and it learned the grid. The original boards for that experiment are dated 23 March 1997.

The grid taught one lesson that carried over. Training went much faster when the program started right beside the goal and was moved further away over time, so that it learned the easy squares first.

Finding a way to train it

My PC was two years old by then. As far as I remember it had a Cyrix 5x86, a cheap processor that fitted a 486 motherboard and was sold as an answer to Intel's Pentium, a question Intel had not asked. A training run took all night. I would start one before bed and get up in the morning genuinely excited to see what it had done. Mostly what it had done was disappoint me. Occasionally there was good news, which kept the whole arrangement going.

Most of what I tried first did not work.

• Learning from expert games. I had about 200 games, which was too few. Experts also have a habit of stopping with seven or more pieces still on the board, so the program never saw how a game is actually won.
• Two networks learning against each other. With both changing there is nothing fixed to measure against. A network that is winning may be improving, or may simply have an opponent who is having a bad week.
• Cloning on a win rate. One network learned while the other stood still, and when the learner won 80 to 90 per cent of a long run of games the other copied it. But a learner could win its first 45 games, lose the last five and still be copied, by which point it had already got worse and was being rewarded for it.
• Three networks. One each for attacking, defending and the middle game. The middle game turned out to get well over half of the training, and I dropped the idea.

What worked was a short match. The learner plays ten training games against its clone. Then the two play a test of two games, one with each colour, with learning switched off. If the learner wins both, the clone copies it, and the learner is rewarded for its success by having to beat itself all over again.

The last piece was look-ahead during training. Without it the network worked out that pressing the opponent was good and then cheerfully gave its pieces away in order to do so. Looking a move ahead let it see to the end of an exchange, and the results were the best I had seen: above average play after only 500 training games.

What it achieved

The final run started every network from the same seed and played 100 matches of ten training games and two test games: 1,200 games in all. I ran it five times, changing only lambda, the setting that controls how far back along a game the final result reaches. Most runs were cloned five times. I then played the last clone of each against all the others.

Against people, it cleared the bar. It beat me easily, and I managed the occasional draw. More usefully, it did well against Dave Harte, an Irish under-18 champion, whose play testing was how I judged its level at all, and against other competent players.

The network that went out with version 1.01 is dated 18 June 1997.

Play against that network.

The programs

NeuroDraughts was five programs, written in Borland C++ for Windows:

• ND ran the cloning tournament.
• Fight played two networks against each other.
• Xtrain trained a network from expert games.
• ConvPDN turned recorded games into training data.
• Neuro let you play against a network.

My brother Daniel and my sister Caragh drew the pieces and the board, which made everything look a great deal nicer than I would have managed. You can switch the board on this site to their artwork.

The release notes were candid about its limits:

Known Bugs
Do anything it's not expecting and god help you ;)

What I planned next

Two things were left undone. I had wanted the program to find its own features, most likely by breeding sets of them against each other in tournaments, and I never got to it. (Somebody else did.) And I still wanted to cut down what it had to be told about draughts while keeping the standard of play. The report ends, with the confidence of someone who has just handed something in, by saying the project "will however remain in development".

It did, eventually. It took twenty-nine years.

What happened instead

After the project I tried to carry on in AI, which is how I came to be commuting to Warrington. I had a job there at Digital Image Design, or D.I.D., who were quite a name at the time, mostly for flight simulators, and I worked on Wargasm. Games, it turned out, had a firm view about AI: it could have whatever processor time was left once everything else had been fed, and it should be grateful. There wasn't much scope for a program that wanted to sit and think.

Later, at Elixir Studios, I worked on Evil Genius, a game in which the player builds a secret lair and then will not stop rebuilding it. This is fun for the player and miserable for anything trying to walk across the map, because the route that existed a moment ago now has a wall in it. I wrote a two-level A*: the full map underneath, and on top a much rougher sketch of it, which could say very quickly whether there was any way from A to B at all before anyone went to the trouble of finding it. The frame rate survived, which in games is the only review that counts.

Elixir was Demis Hassabis's company. He wasn't on the game from day to day, but I knew him, and we talked a great deal about AI, though possibly not as much as we talked about Liverpool, who were making us both suffer at the time. I would love to report that NeuroDraughts came up and that he took notes. I honestly can't remember whether it did. He went on to found DeepMind, which taught a machine to play Go better than any person alive. I went on to mobile games.

I left before Elixir closed, moved to Spain and worked remotely for Shadowlight Games. If a PC was stingy with processor time for AI, a phone of that era regarded the whole idea as a personal insult. It was fun anyway.

In 2008 I ported NeuroDraughts to Linux, changing nothing but the headers and the string handling, and then left it alone for another eighteen years.

About eleven years ago I started my own business in web development, something I had always been curious about and had never once had the time for. That turned into Sonas, software for running wedding venues, now used by hundreds of them across the UK, Ireland and Australia. Weddings, it turns out, need very little reinforcement learning, and AI took a back seat. We're adding AI features now, along with everybody else on Earth.

What finally got a 1997 draughts program off an old hard drive was Claude. I realised I could hand it the original code and ask all the questions I'd wanted answered twenty-nine years ago, and that this time I wouldn't have to wait until morning for each one. So we did, and the rebuild has a page of its own.

First, though, what other people did with it in the meantime.

The archive

The original material is kept with the new code:

• the source of version 1.01 and of the 2008 port;
• the written report;
• the networks, including the one shipped in June 1997;
• the results spreadsheets behind the report's graphs;
• the gridworld experiment.

The report thanks my supervisor, Niall Griffith, for his help and encouragement, Dave Harte for the play testing, and Daniel and Caragh for the artwork.