Wednesday 13 November 2013

How computers help the thinking game

Viswanathan Anand gestures during his third match against Magnus Carlsen at the FIDE World Chess Championship in Chennai. Photo: R. Ragu


Computer chess is powered by engines ranging from simple algorithms to hardware- and power-intensive ones

Right from the 18th Century, lovers of the regal game have invested time and resources in researching chess automatons. There appeared to be a breakthrough of sorts in 1769, when author-inventor Wolfgang von Kempelen claimed to have built the first chess engine. Famously a hoax, his ‘Turk’ was a contraption that tricked people into believing that the match was played by a machine, when behind the scenes all the while the moves were being made by a man hidden inside the “automaton”.
Computer chess has since come a long way with online chess becoming a staple offering with most operating systems. This is powered by chess engines, which range from relatively simpler algorithms that run online chess apps to highly complex chess engines requiring sophisticated hardware and high processing power.

TWO APPROACHES

Serious research on chess engines began around the 1950s when Claude Shannon estimated the approximate number of possible positions in a chess game, and classified chess moves responding to a current chess position, into two categories. While Type A moves examined every possible position that could be a response to the current position, Type B moves examined only the best possible response to the current position. Most chess engines today use an evolved Type B approach.
Chess software comprises the chess engine in the back end, a user interface, and a communication protocol that bridges the two. The chess engine is nothing but a console application that takes the current position of the board as input and outputs the best possible response position after making the right strategic calculations. Apart from this board position analysis, chess engines use tables containing all the possible opening moves and concluding moves for five pieces, or fewer, to make the next move. It also analyses the advantage of a certain response position by giving values to pieces involved in the position. For example, a pawn may have 1 point, a bishop may have 5 points, the queen 9 points and so on, and select the best response position on the basis of the highest total of the evaluation points.

HASH TABLES

The results of all these analysis are stored in hash tables, where it is likely that a certain position is mapped to a list of the best response positions, making it easy to decide the next position to choose.
However, it is important to note that the chess engine performs not one, but a sequence of searches on the hash table to analyse all possible responses to a response position and recursively analyse the advantage from different responses to the new set of responses and so on up to a certain level of depth before choosing the best move. These analysis results can also be stored on your computer, to be studied later or used in another game.
In spite of the influence of computers in the game of chess, different people have different opinions about playing against a chess engine. Vivek, a keen chess enthusiast, says: “Games against a computer are a little unfair and unrealistic because computers do not get tired and can continuously utilise significant processing power and memory before making their moves. Magnus Carlsen does not prefer playing against computers!”

HARDWARE REQUIREMENTS

More complex chess software needs sophisticated hardware to optimise the response speed and performance. Houdini Pro, the best chess engine at this time can utilise up to 32 processor cores for performing computations and up to 256 GB of hash memory for storing analysis results. The engine also limits the number of cores to the number of logical processors on your machine, if your machine has a multi-processor with fewer cores.
The Houdini, and Houdini Pro, can be set to lower levels of chess strength, in which case the engine purposely makes bad moves and makes less comprehensive searches for response positions. It can also be set to think during its opponent’s playing time, avoid draws, set to be used for analysis and learning instead of competing, and use artificial intelligence to learn and record advantageous variations of board positions if they haven’t been recorded.
The Houdini pro is also NUMA aware which enables processors to access local or unshared memory faster than memory shared with other processors, improving response speeds by 5 to 15 per cent.

INTERFACE AND PROTOCOL

Front ends of various chess applications provide the required graphical user interface for the console-based chess engine. These front ends can work with locally available chess engines, chess servers on the Internet and even with chess games played by correspondence. Popular front ends for chess software include the open-source Xboard, the WinBoard and Arena.
Communication protocols for chess engines help protect the familiar look and feel of a chess game across the chess engine spectrum by enabling the UI and the chess engine to communicate effectively. This means that the same UI will work with several back-end chess engines.
Common communication protocols include the Chess Engine Communication Protocol that works with Xboard and over 250 other chess engines and its rival Universal Chess Interface that supports over 100 chess engines.

0 comments :