Alver Valley Software Limited

Month: March 2016

  • Why is the recent ‘Go’ victory so important for AI? (Part 2)

    (Since I wrote Part 1 of this article, the ‘AlphaGo’ AI won the 5th game in the series, giving a 4:1 victory over one of the top human players, Lee So-dol).

    We have already discussed how ‘Go’ is much more difficult for a computer to play than Chess – mainly because the number of possible different moves per turn is so much bigger (and so the total ‘game space’ is even more vast), and because deciding how ‘good’ a particular board position is, is so much harder with ‘Go’.

    First, let’s address one of the points the mainstream press have been making:  No, the ‘artificial intelligence’ computers are not coming to get us and annihilate the human race (I’ve seen articles online that pretty much implied this was the obvious next step).  Or at least, not because of this result.  ‘Go’ is still a ‘full information, deterministic’ game, and these are things computers are good at, for all ‘Go’ is about as hard as such games get.  This is very different from forming a good understanding of a ‘real world’ situation such as politics, business or even ‘human’ actions such as finding a joke funny, or enjoying music.

    But back to ‘Go’.  With Chess, the number of possible moves per turn means that looking at all possible moves beyond about 6 moves out is not a sensible approach.  So, pre-programmed approaches (‘heuristics’) are used to decide which moves can safely be ignored, and which need looking at more closely.

    With ‘Go’, even this is not possible, as no simple rules can be programmed.  So, how did ‘AlphaGo’ tackle the problem?

    The basic approach (searching the ‘game tree’) remained similar, but more sophisticated.  Decisions about which parts of the tree to analyse in more detail (and which to ignore) were made by neural networks (of which more later).

    Similarly, the ‘evaluation function’ which tries to ‘score’ a given board position had to be more sophisticated than for Chess.  In Chess, the evaluation function is usually written (i.e. programmed into the software) by humans – indeed, in the 1997 Kasparov match won by IBM’s Deep Blue, the evaluation function was even changed between games by a human Grand Master, a cause of some controversy at the time (i.e. had the computer really won ‘alone’, or had the human operators helped out, albeit only between games).

    In ‘AlphaGo’, another neural network (a ‘deep’ NN) was employed to analyse positions.  And here lies the real difference.  With AlphaGo, the software analysed a vast number of real games, and learned by itself what are features of good board positions.  Having done this, it then played against itself in millions more games, and in doing so was able to fine tune this learning even further.

    It learned how to play ‘Go’ well, rather than being programmed.

    This ‘deep neural network’ approach is the hallmark of many modern ‘deep learning’ systems.  ‘Deep’ is really just the latest buzzword, but the underlying concept is that the software was able to learn – and not just learn specific features, like a traditional neural network, but also to learn which features to choose in the first place, rather than having features hand-selected by a programmer.

    We’ve probably got to the stage now where the perennial argument – are computers ‘really intelligent’, or just good at computing – has become fairly irrelevant.  AI systems are now able to not only learn a given set of features, but to choose those features themselves – this is how human (and other animal) brains work.   This is undoubtedly a very powerful technique, which will guide the future of AI for the next few years.

     

     

     

  • Why is the recent ‘Go’ victory so important for AI? (Part 1)

    Anyone who has seen any news in the last few days will know that a computer has for the first time beaten a top human player at the ancient Chinese game of ‘Go’.  In fact, at the time of writing, the AI (let’s call it by its name:  AlphaGo) has beaten its opponent 3 times, and the human (Lee So-dol) has won one – the fifth in the series takes place shortly.  But why is this such important news for AI?

    After all, AI has been beating top grand-masters at Chess for a while now – Gary Kasparov was beaten by a computer in 1997, and although the exact ‘fairness’ of those matches has been questioned by some, it’s certainly been the case since about 2006 that a ‘commercially available’ computer running standard software can beat any human player on the planet.

    So why is ‘Go’ so different?  In many ways, it’s a very similar game.  It’s ‘zero-sum’ (meaning one player’s loss exactly matches the other players gain), deterministic (meaning there is no random element to the game), partisan (meaning all moves are available to both players), and ‘perfect-information’ (meaning both players can see the whole game state – there are no hidden elements or information).   Just like Chess.

    From an AI point of view, two things make ‘Go’ vastly more difficult than Chess.

    Firstly, the board is a lot bigger (19×19), meaning that the average number of legal moves per turn is around 200 (compared to an average of 37 for chess).  This means that the ‘combinatorial explosion’ (which makes chess difficult enough) is much worse for ‘Go’:  to calculate the next 4 moves (2 each for each player) would need 320,000,000,000 board positions to be analysed – and looking ahead 2 moves each would give a pathetically weak game.

    The second factor is that for Chess, analysing the ‘strength’ of a board position is fairly easy.  The material ‘pieces’ each player owns are all worth something that can be approximated with a simple scoring system, and that can be made more elaborate with some simple extra strategic rules (knights are more valuable near the centre, pawns are best arranged in diagonals, etc).  But for ‘Go’, a simple ‘piece counting’ system is nothing like a useful enough indicator of the advantage a player has in the game, and no ‘simple rules’ can be written which help.

    Instead, good human players (and even relative amateurs) can assess a board position, more or less just by using their intuition, and that intuition is where a lot of the best play comes from.  Computers, of course, are not well known for their use of ‘intuition’.

    I’ll write more about the approach ‘AlphaGo’ used – and why this has wider implications for AI in general – in a follow-up article in the next few days.