Jim Jean-Pierre Barthel, doctoral researcher within the Department of Computer Science at the University of Luxembourg, explains algorithms taking the example of chess game between human and machine.
The popular chess-related miniseries The Queen’s Gambit, depicting the life of an orphaned chess prodigy, sparked a great deal of public interest for the game. Many enthusiasts downloaded chess applications to try and learn the rules. « Although an app certainly avoids the problem of finding a chess partner, it also raises the question whether a machine running on simple algorithms can play and win a game in which the first ten moves can result in a total of 69 352 859 712 417 different openings. But first, we’ll need to grasp what algorithms actually are and take a closer look inside a chess computer », explains Jim Jean-Pierre Barthel.
The origin of the algorithm
Algorithms can be thought of as detailed instructions carried out by computer programmes to help us in our daily tasks. Contrary to popular belief, though, algorithms are not an invention of the 21st century and have been around for the last 5 000 years, long before the first computer was ever developed. Indeed, the earliest evidence of an algorithm can be found on a Sumerian clay tablet dating back to 2 500 BC. The carved inscription features a piece of Babylonian mathematics describing an algorithmic procedure on how to divide two numbers. Other historical artefacts, such as the Egyptian Rhind Mathematical Papyrus or the Greek treatise of Euclid’s Elements, show that algorithmic procedures have been used by many high civilisations to describe mathematical solutions. Whilst historically valuable, these early works aren’t exactly the computer algorithms we know today.
Funnily enough, the origin of the word algorithm was the result of an unfortunate Latinisation of a Persian manuscript describing the Hindu-Arabic number system and only denotes the decimal number system. Its modern sense of referring to a procedure didn’t emerge until the 19th century when the first computing devices revolutionised the world. Over the next two centuries, academics tried to formalise the definition of an algorithm, but, believe it or not, there’s still no common consensus. The unexpected difficulty of developing a well-founded definition of an algorithm is due to the versality and variety of modern algorithms. However, apart from a few technicalities, mathematicians and computer scientists agree that an algorithm consists of a finite sequence of well-defined (computer-implementable) instructions to solve a given class of problems.
Modern algorithms and their uses
Nowadays, algorithms are the building blocks of our computers and can be found in any smart machine, from laptops, cell phones and cars to coffee machines. They’re also omnipresent in our daily tasks. Indeed, any recipe can be seen as an algorithm since it consists of a finite sequence of instructions for cooking a dish. Similarly, the instructions for playing chess could be thought of as an algorithm too. However, not every set of instructions fulfils the mathematical conditions for being an algorithm. The condition that the instructions need to be well-defined is particularly difficult to achieve. There should be no space for doubt in the instructions, and this can be tricky. For instance, the rules for playing chess, including the moves of each pawn and the conditions for winning, don’t count as an algorithm because they don’t specify which pawn needs to be moved when.
Precise well-defined instructions avoid misunderstandings and increase repeatability, which is desirable in most contexts, including cooking a meal. More generally, this idea is also the basis for experimental science. In empirical experiments, researchers describe their setup and note their measured outcome in great detail. If the outcome corresponds to their hypothesis, then their experiment is successful and can be repeated by others. If not, the researchers have to check for potential mistakes in their detailed procedures. In that respect, algorithms are a common feature of modern science. To facilitate the design of algorithms, science uses mathematical symbolism to reduce instructions to simple operations which can be executed by machines. This is especially true in computer science where machines are both the means and the purpose of study.
Computer programmes powered by algorithms
A computer, in the modern sense, is any machine that can be instructed to carry out sequences of arithmetic or logical operations. Here algorithms take on the role of these instruction sequences. A collection of one or more algorithms can be called a program and these programs have shaped our world for the last two centuries. The most important scientific achievements of the 20th century have been computer assisted, including the moon landing, the sequencing of the human genome, world-wide telecommunication, and, of course, the creation of the internet. Simple algorithms open almost infinite possibilities.
For example, scholars in Luxembourg are working on algorithms for secure voting systems, internet banking, real world simulations and advanced network analysis, which has been used for early infection rate detection in the ongoing pandemic. Specific algorithms in robotics have been used to develop a paediatric robot for autistic children and biochemical research has been improved with the help of algorithmic big data analysis tools. Artificial intelligence is used for marketing purposes on social networks and learning algorithms can drive autonomous vehicles. Overall, algorithms simplify our everyday life, but they need to be written carefully. In today’s fast-paced world this is often not possible, resulting in daily updates of smart devices, frustration due to malfunctions and security breaches. The good outweighs the bad though and algorithms make it possible for us to communicate, work and play in the digital world.
Can a computer win at chess?
Now that we’ve covered algorithms and computers, it’s time to settle whether or not an algorithm can play – and win – a game of chess. Given that an algorithm consists of a finite sequence of well-defined instructions to solve a particular class of problems, an algorithm clearly is able to play a game of chess, as long as the programmer defines exactly what it needs to do. However, if our virtual opponent were to lose every time, the chess match wouldn’t be very interesting. The chess computer has to be a competitive opponent. Fortunately, this doesn’t mean that the programmer has to be a great chess player, but only that they have to teach the algorithm how to move the pawns strategically.
Usually, a chess computer is instructed to simulate all the possible moves and select the most favourable one, i.e., the one where the opponent loses more pawns than the computer. The success of this strategy was demonstrated in 1996 when IBM’s Deep Blue chess computer won a six-game chess match against the reigning world champion Garry Kasparov. After this victory, the quest for the ultimate chess program really took off. Complex hardware became superfluous and simple programs started to compete at the same level as experienced players. Finally, in 2006 history repeated itself when the widely used chess software Deep Fritz won 4-2 against the new world champion Vladimir Kramnik. Who knows whether the Queen’s Gambit protagonist Beth Harmon could have won against this algorithm – at least in the real world, it has proven its superiority. The reign of algorithms has begun, but it won’t remain unchallenged.