On AlphaGo. Part I

We present to your attention an article by Thomas, Student at Concord College. UK, applying to study Material Sciences. He talks about AlphaGo, an artificially intelligent program that plays the board game "Go".

A basic definition of Artificial Intelligence is the ability of some sort of program or machine to improve its ability to perform a particular task by itself over time when exposed to some form of data, often created by itself or in its environment. Neural networks and their ability to learn from their own generated results has presented a fantastic example of this ability in recent years, moving from simple character recognition to mastery of strategic board games such as Chess and Go. Neural networks are comprised of layers of ‘nodes’ which were designed to model neurons in an animal brain, connected by ‘edges’. The first layer of nodes is the input, where the raw data is inputted into the network with one node for each value. At each node, a function determines a specific ‘weight’ to be added to the raw data value, as does an edge which connects each individual node to all nodes of the next layer. This continues for each node and edge until the output layer, where the result is outputted. Often the input and output layers are the only layers needed, if the data is easily related between the two. In more complex networks the layers between input and output are known as hidden layers. AlphaGo was a project developed by the Deep Mind subsidiary of Alphabet (Google) and utilised a neural network alongside a usual Go brute force engine to quickly become one of the most powerful engines at the Chinese board game Go, showing the potential of neural networks. In 2016 the program beat Go World Champion Lee Sedol and was the first time a computer had managed this in a game without handicaps. This showed the potential of using neural networks in complex strategy board games, and soon enough a version called AlphaZero was created which could play Go, Chess and Shogi (Japanese Chess). While in Go, professional human players had until recently had the edge over computers, in chess, engines capable of beating the best humans in the world had been around for some time. A simple knowledge of board game programs and the differences between Go and Chess can easily explain this. Firstly, board game engines usually utilise a brute force approach, where they test every possible move, and every move from that, and from that and so on until they run out of time and have to choose the best move based on a value assigned to each position. If the engine could see every single possible move and reply until the end of the game, then it would obviously always get the best possible result (depending what results from perfect play, and this could even be a loss). If this was possible the game would be ‘solved’ and an example of a game where this has been done is Connect Four or Four in a Row, where with perfect play the person to move first wins, no matter what the opponent does. (Of course in actual gameplay with humans this is not true, as even if you had practised how to win the ‘perfect game’ where your opponent also plays best, you will not be able to remember what move to make in the case of every non-perfect move by your opponent.) There are ways to refine the process of checking each move, by ‘pruning’ the ‘tree’ of moves that the engine creates when a particular branch provides a negative outcome with no foreseeable compensation. However, due to the sheer amount of possible moves in Chess and Go the engine will never be able to see that far, despite engines existing such as Stockfish, Houdini etc. which have the capability to process tens of millions of moves per second. If we estimate that there are perhaps 10 possible moves at any point in the game, and we can easily see that it becomes increasingly more difficult to look at the next layer of moves. For example even looking 5 moves ahead would give an approximate 10^(5*2) or 10 billion moves to calculate as both black and white have a choice each move. The implications of this are that at the start of the game where there are many good moves and responses the engines have a hard time calculating what is good for the future, and they are supplied with opening ‘books’ created by people to help them at this stage. They are also supplied with endgame ‘tablebases’ which include millions of possible endgame positions when there are few pieces left on the chessboard, which seems to be cheating but it is to make up for the difficulty in processing so many moves. However it also makes engines amazing at tactical play where they can calculate accurately ahead to obtain a clear advantage when an opponent makes a mistake, and this is the key point.

To be continued in the next post...