Today (14:00, 07 Mar 2016 in F1A09 at the University of Nottingham Malaysia Campus) I am giving a two hour lecture on Computers and Game Playing.
This lecture could not have come at a better time.
At the end of January, Google’s DeepMind reported that AlphaGo had beaten the top European Go player (Fan Hui) 5-0. This was probably about ten years earlier than most people expected a computer to defeat a human expert at Go. This You Tube video gives a very good overview of the achievement.
This development is, in my view and the view of many others, one of the most significant landmarks since Gary Kasparov was defeated by Deep Blue in May 1997.
The defeat of Fan Hui has generated so much interest that the World’s best player (Lee Sedol) has agreed to play AlphaGo in March (9th – 15th) 2016.
My lecture is nicely sandwiched between the recent defeat and the upcoming match against the current best player in the world.
In the lecture I will still cover the material that I need to get across (such as mini-max, alpha-beta search) but it would be remiss of me not to talk about the recent successes of AlphaGo and the technologies that have led to this remarkable achievement.
Indeed, in my next lecture, I will be talking about Deep Blue (Chess), Chinook (Checkers) and Blondie24 (Checkers), where some of the methodologies that led to their successes will be discussed. No doubt AlphaGo will also get a mention and, by then, we should have some more knowledge about it it has performed against Lee Sedol.
It’s a great time to be a student who is interested in game playing and artificial intelligence!
Finally, a plug. I am the Editor-in-Chief of the IEEE Transactions of Computational Intelligence and AI in Games (TCIAIG) and we would welcome any articles that are motivated by the recent successes in Go.
Deep Knowledge Ventures has appointed an algorithm called VITAL (Validating Investment Tool for Advancing Life Sciences) as a member of its board. It uses state-of-the-art analytics to assist in the process of making investment decisions in a given technology.
Of course, companies have used computer assisted analysis to analyse investment opportunities for a long time, but is the vision of a computer with equal voting rights as human board members a bit far-fetched?
Defining artificial intelligence
What does the future hold with regard to the influence of computers on business decisions – and can they ever be used in place of a human board member? The Turing Test, formulated by Alan Turing in the 1950s, provides a strict interpretation of machine intelligence. A human participant must be unable to tell whether they are communicating (through a typed, text medium) with a computer or a human. If the human participant cannot reliably tell whether their conversation partner is a computer, then Turing would argue the computer has demonstrated intelligence.
Not everybody agrees that passing the Turing Test is enough for a computer to exhibit intelligence. In his Chinese Room argument, the Stanford philosopher John Searle described a closed room, into which a sentence written in Chinese is fed. A response emerges from the room, written in Chinese, that correctly answers the questions or conversational cues in the sentence submitted. The assumption could be made that inside the room is someone that can speak Chinese.
Instead, inside the room is a human who cannot speak Chinese but is equipped with manuals that exhaustively provide the appropriate Chinese characters to produce in response to those received. The argument holds that an appropriately programmed computer (the person in the room) could pass the Turing Test (by producing convincing Chinese) but would still not have an intelligent mind that we would regard as human intelligence (by understanding Chinese).
A computer in the boardroom
If we want computers to make business decisions and even have equal voting rights on a company board, what would it have to do in order for the other board members to have confidence in its decisions?
Part of the challenge of the Turing Test is syntax versus semantics. Compare the sentences “Fruit flies like bananas” and “Time flies like an arrow”. The sentence structure is similar but the meaning is entirely different, making it a linguistic challenge.
Even a very simple conversation relies upon a substantial amount of linguistic knowledge and understanding. Consider the following questions:
What was the result of the big match last night?
I have K at my K1, and no other pieces. You have only K at K6 and R at R1. It is your move. What do you play? (these chess moves are from Turing’s original paper)
What book do you think of if I say 42?
These might seem easy for humans to understand, but are challenging for a computer. Thankfully, a computer making business decisions is not faced with such a general task as the Turing Test. But if we are serious about having a computer as a full member of a company board, what are the hurdles that need to be addressed? Here is a (almost certainly not complete) list.
Access to LOTS of data: An automated approach to decision-making will require the use of big data. Company reports and accounts, economic data such as share prices, interest rates and exchange rates, and government statistics such as employment rates and house prices would all be obvious inputs. More subjective data such as newspapers, social media feeds and blogs might also be useful. Peer-reviewed scientific papers might also provide insight. Of course as always, the challenge with big data is to process the large quantities of data that will be be of different types (figures, text, charts), stored in different ways, and have missing elements.
Cost: Much of the data required is likely to generate significant costs. Social media feeds may be free (but not always), but stock market information, company accounts, government data, scientific papers and so on are generally commercial products that must be paid for. In addition, there is the cost of developing and maintaining the system. The algorithm is likely to require continual development by highly skilled analysts and programmers.
Complexity: Big data algorithms will be central to the boardroom decision support algorithm, but they will be underpinned by advanced analytics, many of which we are only just starting to understand and develop. To have a real impact there is likely to be some research required which would require staff with the relevant skills.
So, are we really at a point where a computer could take its place on the board? Technically it’s possible but the costs to develop and maintain, as well as subscribe to the data that is required, probably means that it is not within the reach of most companies and I suspect that the money would be better spent on a human decision maker – at least for now.
Take a set of chess pieces and throw them all away except for one knight. Place the knight on any one of the 64 squares of a chess board.
Can you make 63 legal moves so that you visit every square on the chess board exactly once? As a reminder, a knight can move two squares in a straight line, followed by a ninety degree turn and a move of one further square. It might seem like a hard task, but this set of moves, called the knight’s tour, can be achieved in too many ways to count.
If you are able to make the 63 moves and end up on a square from which you can move back to the original square with the 64th legal move, then this is known as a closed tour. Other tours are called open tours.
Mathematicians have pondered how many closed tours exist, and they have come up with an astonishing number: more than 26 trillion. There are so many more open tours that we do not know the exact number.
Both Philip Hingston and I were so captivated by the knight’s tour problem that we wanted to find a different way to solve it. We found that motivation in nature – specifically in ants.
Here’s how that algorithm works: a computer program is used to simulate a population of ants. These ants are assigned the task to find a solution to a problem. As each ant goes about their task they lay a pheromone trail – a smelly substance that ants use to communicate with each other. In the simulated algorithm, the most successful ants (the ones that solve the problem better), lay more pheromone than those that perform poorly.
We repeat this procedure many times (perhaps millions of times). Through repetitions, the pheromone trails on good solutions increase and they decrease on the poorer solutions due to evaporation, which is also programmed in the simulation algorithm.
In the simulation to solve the knight’s tour problem, the ants could only make legal knight moves and were restricted to stay within the confines of the chess board. If an ant successfully completes a tour then we reinforce that tour by depositing more pheromone on that tour, when compared to a tour that was not a full tour.
Ants which attempt to find later tours are more likely to follow higher levels of pheromone. This means that they are more likely to make the same moves as previously successful ants.
There is a balance to be struck. If the ants follow the successful ants too rigidly, then the algorithm will quickly converge to a single tour. If we encourage the ants too much, not to follow the pheromone of previous ants, then than they will just act randomly. So it is a case of tuning the algorithm’s parameters to try and find a good balance.
Using this algorithm, we were able to find almost half a million tours. This was a significant improvement over previous work, which was based on a genetic algorithm. These algorithms emulate Charles Darwin’s principle of natural evolution – survival of the fittest. Fitter members (those that perform well on the problem at hand) of a simulated population survive and weaker members die off.
It is not easy to say why the ant algorithm performed so well, when compared to the genetic algorithm. Perhaps it was down to tuning the algorithmic parameters, or perhaps ants really do like to play chess!
The knight’s tour problem was being worked on as far back as 840 AD. Little did those problem-solvers know that ants, albeit simulated ones, would be tackling the same puzzle more than 1,000 years in the future.
Graham Kendall does not work for, consult to, own shares in or receive funding from any company or organisation that would benefit from this article, and has no relevant affiliations.