Tag Archives: programming

Programming++: building on what has gone before

When learning to program, the earliest struggles are often with the mechanics of simply generating valid code. This can be deeply frustrating to novices because programming language translators (compilers) are unwaveringly rigid in what they are prepared to accept and will reject everything that does not conform. But once those syntactic basics have been acquired, the door is open to creating new and exciting programs that no one has ever written before.

One of the ways in which programmers create new programs is to pay attention to what others have written in the past. By building on what others have already written, they can often save themselves a lot of time and, thereby, focus their creative energies on those parts that are novel in their own particular programs. As a teacher, I encourage this approach early on when I advise my students to make use of library classes for storing collections of data, for instance. While it is certainly important to understand how those library classes work, that doesn’t mean you have to write the code from scratch every time you need to use a collection. The key is to take what is available and either write your code around it or adapt it to fit your needs.

I applied this principle recently when I was asked to add some new functionality to a program that I have been maintaining on-and-off for the past 20 years. It is an open-source project written in C called pgn-extract. It allows chess players to search files of chess games for matches on all sorts of different criteria, such as particular players, openings, endings, etc. One of the program’s users (JS) asked me if it would be possible make it look for particular board positions arising during a game. For instance, it might be interesting to look for examples of how a tricky endgame was played out by expert players where the pieces were in a particular configuration. The complicated part was that JS didn’t want users to have to specify the exact position of every piece on the board. Rather, there would be a few pieces they were interested in but the rest didn’t matter.

To my knowledge there wasn’t anything like this already in existence but the task reminded me of the familiar Computer Science topic of pattern matching. This is where you want to look for something that matches a fuzzy pattern rather than something exact, often using regular expression notation. For instance, using the pattern “[cC]at*" to match words starting with “cat” or “Cat”, such as “cattle” and “Catcher”. The notation is well-known in computing through the Unix command grep. While this notation is generally used for matching ordinary text, I thought it might be possible to adapt the idea to match chess boards – particularly if a board could be represented in a text-like form.

My starting point was a nice description of the implementation of grep written by Rob Pike (documented by Brian Kernighan). Representing a board textually is actually fairly easy and chess players do it all the time. For instance P6r means: “white pawn, six empty squares and then a black rook”. I adapted the familiar grep notation to better fit a chess context to be able to distinguish between black and white pieces, and then added it to my program – acknowledging the dependence on Rob Pike, of course!

Happily the original requester, JS, was pleased with the result but then he went on to demonstrate a nice serendipitous use of the new feature that I would never have thought of. He sent me a picture of former world champion Mikhail Tal staring hard at an unseen opponent. The picture is fairly well known, but who was the opponent on the receiving end of Tal’s menacing stare? JS encoded the part of the board visible in the picture using the new notation (*/*/*/*/????b??q/*/????N??P/R??Q1BR1) and ran the program over all the games that Mikhail Tal ever played! The result was the game against Nikola Padevsky, played in Leipzig in 1960.

Programming++ is not just about the mechanics of writing correct code, it is about taking and adapting existing ideas to create something new, and sometimes something fun!