Posts With Tag: Algorithms

Everyone knows about Deep Blue; it is the first chess computer that beat a reigning world champion—Garry Kasparov. Although losing to Kasparov in 1996, Deep Blue came on top in the rematch in 1997. The matches, however, are not the whole story. Creating this computer engine took decades of work from researchers and the chess world. Feng-hsiung Hsu—the man who started the project—said that the team “had spent close to 30 man-years on the project when Deep Blue won the match.”[^1] Further from that, some ideas used in Deep Blue were theorised nearly half a century earlier. We will look at those ideas and how the current computer engines came to be—the ones that now shape how chess is played.

During my last data structures lecture, our professor was talking about priority queues, selection and insertion sorts. And he mentioned, as a non-examable material, how we might achieve a faster insertion when considering a sorted sequence-based priority queueue.

I’m using bit boards to represent the board and the pieces. I’m following the alpha-beta algorithm with multiple optimisations, ranging from transposition tables and iterative deepening, with a heuristic move generator.