Category Archives: computer science

Programming++: building on what has gone before

Leave a reply

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!

Depending on Technology

Last weekend I did something out of the ordinary and attended the FIDE Candidates Chess Tournament in London, where eight participants are currently competing against each other for the right to take on the current World Chess Champion for the title. For just a few years longer than computing has, chess has been part of my life since my teenage years, although I gave up serious competitive chess about 15 years ago when writing my first programming text book. I had been invited to go along by my friend and colleague Julio, and while I am fairly out of touch with the contemporary chess scene, he was easily able to point out the two Grandmasters sitting in corner of Starbucks, or the ‘second’ of one of the tournament favourites as we passed him on the street on our way home in the evening.

Though watching others play chess has famously been compared to being as entertaining as watching paint dry, I have to confess that I found the day enormously enjoyable, despite spending the best part of six hours in a darkened room with practically no conversation! But the day was thought-provoking from the perspective of a Computer Scientist, too, because I was reminded once again of just how dependent we are computer-based technology in practically every area of our lives.

In my youthful, confident years of playing chess, I used to be amused at the idea of taking on a chess-playing computer and would have considered buying one as a waste of money. The technology was so crude and the power so limited that it was easy for an average club player to obtain a better position from the opening and go on to win by either a well-timed attack beyond the program’s limited vision, or better strategic play. However, as everyone now knows since Deep Blue beat Gary Kasparov, the tables have been turned and it is the programs that would laugh if they could! Any chess player who seriously aspires to be any good would be a fool not to use computer analysis and competition in their study to get better.

But therein lies a problem.In a scenario not dissimilar from having covert Google access while playing “Who Wants to be a Millionaire?”, the chess world is now struggling to deal with the fact that players may be tempted not to leave that computer support behind in the training room but to have it with them in a tournament game and depend on it in a game. Such is the concern that someone in the audience might have access to computer analysis and be able to communicate it to the players, that we spectators at the Candidates were not permitted to carry any electronic devices into the tournament hall and had to pass through an airport security gate and be body-searched with hand-held wands. This is the chess-world’s equivalent of doping control; interestingly, not of the participants but of the spectators!

Dependence on technology that has become addictive; the computers are too powerful and unfettered access to them is considered harmful.

Fortunately, there was access in the playing hall to technology considered harmless. To help the spectators follow the games, a large screen displayed the current state of play on each board, with an indication of how much time each player had left. The playing boards and pieces contain electronic sensors to keep the displays up to date. In addition, one of the tournament sponsors – Samsung – had supplied Galaxy tablets that displayed the same board information and provided a video commentary.

Assuming that you are not in the paint-drying camp – from the start it was clear that things were going to get pretty exciting later on as four of the players had a huge time advantage over their opponents, who would likely struggle to complete their required forty moves in two hours.

In the most desperate situation was Vassily Ivanchuk who had about 20 seconds left to complete 15 moves! But, at this point, technological failure struck as the live boards stopped updating and my Galaxy tablet froze, too. Despite repeated reboots it wasn’t going to give me the video feedback, and I could only watch Ivanchuk’s hunched back obscuring the board.

Now I was the one dependent on technology, and when it failed I was completely scuppered. I might as well have been sitting in the dark.

Of course, this sort of situation where technology lets you down is all too familiar – your mobile phone battery is flat and you feel completely isolated. Yet neither situation is a complete disaster. Failure here is really just an inconvenience.

But what happens when dependence on technology is life critical – in a medical situation or when flying, for instance?  And as technological control pushes into more and more areas of our lives (cars, electronic wallets, etc.) the potential for mere inconvenience to become something much more serious increases dramatically.

As I sat in the technological dark, watching Ivanchuk pluck at his eyebrows trying to find his own unassisted way out, I was reminded of the responsibility of those of us who teach Computer Science of the need to inculcate in our students a strong sense of responsibility towards those whose lives might one day be dependent on the quality of the programs they write.