12 October 2015

Chess Engines : Bitboards

In this series of posts on Modern Chess Engines, of which the most recent was LMR (Late Move Reductions), the emphasis has been on software, i.e. algorithms. The engines are as strong as they are because (1) their static evaluations of specific positions are amazingly accurate, and (2) they can focus on the variations that are the most critical.

Not all of the engines' strength can be attributed to software. In parallel with algorithmic discoveries, computer hardware has also been advancing rapidly. Not only are processors smaller and faster, they are also more versatile.

A few years ago I was impressed by the diagram on the left. It shows the increase in Elo by chess engines over the 20 years 1990-2010. A larger diagram, including a legend for the individual lines that represent different engines, can be found in the original article on Chessbase.com, A Gross Miscarriage of Justice in Computer Chess (Part 2), aka The Rybka Affair. Was it a coincidence that the mid-2000s spurt in computer chess happened with the introduction of 64-bit processors?

In 'Modern Chess Engines', I picked up two factors related to advances in hardware. Again relying on chessprogramming.wikispaces.com for definitions:-

Bitboards • Also called bitsets or bitmaps, are among other things used to represent the board inside a chess program in a piece centric manner. Bitboards, are in essence, finite sets of up to 64 elements - all the squares of a chessboard, one bit per square. Other board games with greater board sizes may be use set-wise representations as well, but classical chess has the advantage that one 64-bit word or register covers the whole board.
Population Count (popcount, popcnt) • Determines the cardinality of a bitboard, also called Hamming weight or sideways sum. How many one bits exists in a 64-bit computer word? In computer chess, population count is used to evaluate the mobility of pieces from their attack sets. [...] Future or recent x86-64 processors provide a 64-bit popcount instruction.

The overhead of tracking and analyzing constantly shifting chess positions has been simplified and streamlined by these basic tools.

No comments: