Recent blog entries for dennissheil

Blunder's chess PGN-to-FEN converter nearing completion

The minor re-design, or major refactoring, of Blunder's PGN-to-FEN converter was finished three days after my last blog post about it. It went very well, the new code which replaced the old code is more abstract and flexible, looks better and works better. Funny how these things go together - it seems good coding practices solve a lot of the headaches of coding and things begin working automagically.

I mentioned problems in Lutz Tautenhahn's PGN-to-FEN converter in my last blog post. After writing it, I decided to e-mail him a bug report. Within 14 hours he fixed the bug and posted new code, which I tested, and both problems were fixed. So Lutz's converter is now working without problem, as far as I can see.

I've fixed many things in the PGN-to-FEN converter since the redesign/refactor. I check in every (?) manner if a move would put the king in check. I now handle many (all?) en passant scenarios. I also now deal with PGNs where a FEN position in the middle of a game is given, and where the subsequent moves are from that position (i.e. we start in the middle of the game). I made other changes as well.

I just made my most satisfying commit since the redesign/refactoring. It was the fruit of other commits before. First I began marking games on the linked list as I went, not all in the beginning (which caused an initial delay when parsing large PGNs with many games). Then I pushed code into the Game class that I had wanted to push there for a while. All of this allowed me to do the latest commit.

I was reading the entire PGN into a linked list in the PGN class, and then pushing the entire linked list into other classes like Game. As Game only needs one game, I created a second, short linked list with only one game, and pushed that to Game. As the original data on the first, long list is no longer needed, I removed it. I am always dealing with the head of the linked list in these cases. Anyhow, this process of dealing only with the head of the larger linked list, and shrinking it as the program goes, has made the program over ten times faster.

So what more is there to do? People have their own bizarre implementations of the PGN format. I handle many of them, but there are a few more out there I might do. All of the code is working, but I might clean up some of it so that it is easier to read and cleaner. I also might work on a user interface other than running the jar file from the command line. I might also discover some edge cases of the en passant sort that I am not dealing with. I have tested tens of thousands of games, and have been looking over FIDE chess rules, the specifications and so forth, so I don't think there will be much more of this type. The program is in decent enough shape right now, I guess I just want to deal with a few more of the oddball PGN implementations, and fix up the UI a little bit, before I feel this is fully formed in its first generation. But it is working pretty well as it is.

5 Jan 2011 (updated 5 Jan 2011 at 05:29 UTC) »
Build one to throw away...

Since I have a long way to go before becoming a good programmer, I sometimes refer to Code Complete, The Mythical Man-Month and the like to keep me on the right track.

I think I have reached that point, of throwing away the first one built, with the Blunder PGN to FEN chess translation component I have been programming for the past month.

To be honest with myself, I foresaw these design problems back when I originally did the design. I knew I would have to deal with many of the things I am dealing with now way back when I was doing the original design (although not totally - checking that a piece is pinned to the king is more important than I thought it would be, if I thought of it all). The thing is, designing the program with all of that in mind would be "boring". It would be too abstract initially, it wouldn't DO anything until quite a lot of the program was coded. The way I programmed this, it worked right off the bat - at least with the first PGN I used as a basis. It translated the first ply of the first move correctly, and then the next ply of the first move, then the first ply of the second move and so on. After that all worked, I tried another PGN. As I sought to get it working for my various PGNs, I added more and more functionality to the program.

The method functionality I need now seems rather abstract, or at least more abstract than the functionality I have now. "Check to see if piece (rook or queen) is pinned to king horizontally", "Check to see if piece (bishop or queen) is pinned to king diagonally", and so on. Things are a little more abstract than I'd like, but if I try to keep things very specific, I will have much, much more coding to do.

The program currently does over 95% of PGNs correctly, but there are too many possible corner cases to deal with. The functionality that deals with plies (half-moves), which is most of the program, has to be rewritten.

The main thing I focused on with the initial design was the data structures. I did change things around a bit, especially the Board class, which is my half-way class between the translation of the PGN to FEN. I also realized while programming that I needed a Move class. When functionality got to where over nine out of ten PGNs parsed, I wanted to do PGN files that had multiple games within it - and thus a Game class was created as well.

One nice thing is, aside from the edge cases I have to redesign for, my PGN to FEN converter has some aspects that are superior to the two other converters I've found out there - Lutz Tautenhahn's PGN-to-FEN converter and 7th Sun Green Light Chess's pgn2fen.exe program for Windows (or Linux, with WINE). Tautenhan's program I tested out more - I saw two problems - one, castling ability which is disabled due to a rook move is re-enabled if the rook moves back to the square. I'm fairly sure this is not legal with FIDE rules. Secondly, if a pawn move results in pawn promotion, Tautenhan's converter does not reset the half-move clock due to the pawn move, but in fact increments it. I believe this is not the case with FIDE rules, but am less sure. As far as the Green Light chess converter, I have not looked at it as much as Tautenhan's, but I do know it does not mark en passant squares in the FEN.

Blunder's converter marks en passant squares, disables castling availability properly, and resets the halfmove clock on all pawn moves - even pawn promotions, which I believe is the correct behavior. Now I just have to redesign and abstract the methods that deal with converting a ply to a new configuration for my Board object. Which is most of the methodology for the program. I might tinker a little more with the data structures, perhaps making them a but more robust.

6 Dec 2010 (updated 6 Dec 2010 at 21:29 UTC) »
Blunder, Chess, Java, Architecture and Construction

So, I put Blunder up on Sourceforge.

Blunder is a suite of chess-related tools. Primarily, it helps you go over your games, and see where you made mistakes or missed opportunities. You keep looking at the boards where you made your biggest and/or most recent mistakes, and keep testing that you now know what to do correctly. Most chess teachers say this is one of the main ways to improve your game, and with Blunder it is automated.

Anyhow, the program has been out for almost a year, particularly the main LAMP (Linux, Apache, MySQL, PHP) component. However, one necessary component has been converting files in PGN format (records of games) to FEN format (pictures of individual boards at a set point). I give pointers how to do this, but have not been happy with any of the existing tools, and have begun writing my own one in Java, with GPL version 3 licensing. This was the impetus to put it on Sourceforge actually.

As I said, Blunder is functional already, particularly the LAMP package for going over games. One necessary component for that to work is PGN to FEN conversion, for which there are tools out there. I am unhappy with them, so I am writing my own in Java. If any Java developers want to send git patches, I'd be happy to get them. This second package within the Blunder project is in pre-alpha right now.

While this has all been done pretty loosely, I decided to try for a little bit stricter good practices in the pre-construction part of the project. I have to report - it worked out very well! I began by cheating on the good practices a little - I coded a method that read the PGN file into an array. It was just a detail I didn't want to bother with once requirements and architecture was done as I'd want to get right into the construction beyond that first.

My requirements were:
Read in a pgn (from say, a file), output a series of FENs for every move, or a specific FEN for one move. I might tweak the input or output requirements later, but the middle part, converting one to the other, will remain the heart of the program.

I then did architecture. I sketched out the major classes, their responsibilities and their interactions. Initially there were three classes - Pgn, Board and Fen. I thought about it and realized Pgn should have a helper class, Move, and Pgn would have an array of Move objects. Board is primarily an array of characters representing the board, and Fen is an output String representing the FEN. I think it was helpful thinking about all of this beforehand more than I usually would have. It saved time in the long run. Every minute I spent doing this right off the bat probably saved a multiple of itself so far.

One mistake I made is instead of making the Board array something that would be intuitive to me, I tried to fit its data structure to the other existing data structures. I thought this would make "less work". The problem is, Board's data structure then became inscrutable to me, and I had to bend my mind to figure out what it was, and kept making mistakes. I then decided to rearrange Board's data structure to something I could intuitively understand, and then use methods to do the conversion between it and the other two major data structures. This has worked out much better for me.

Most of the work left to get the program from pre-alpha to alpha is doing the logic (methods) for the various chess moves. I already have methods for PawnMoveNoCapture and KnightMoveNoCapture. My next method will probably be PawnMoveWithCapture - a move where the pawn captures a piece. The program needs methods for all the various moves - Queen move (capture and no capture), Bishop move (capture and no capture), Castling (Queenside or Kingside) and so on. This will be the bulk of the work to get the program into alpha.

I am plowing ahead with those methods right now. There is some code duplication within existing methods, but my concern is not with that but code duplication between methods - I already created a method to convert the letters from the Pgn moves to the numbers the array in Board uses, which both existing chess move methods use. I would like to complete moves for all the pieces, when capturing or not. Anyone who wants to send in git patches for these Java methods should feel free, the two existing methods can serve as a base.

You can grab it from the project's git page on Sourceforge.

Linux desktop/smartphone penetration

This Wikipedia article tells you the share of web browsers from different sources, but clicking through the links you can see what penetrations OS's running web browsers have as well. These web sites give an accounting from their logs of what the OS's are for the people they're serving pages to.

W3counter has 1.49% running Linux and 0.25% running Android in October 2010.

Clicky gives a daily tally, which is 1.25% for Linux today, and has been hovering around 1.25% for the past weeks.

Statcounter has 0.78% running Linux since September. Not sure what they're counting as Linux or why their Linux count is so much lower than the others

Most interesting is Wikimedia, which really breaks down the statistics. They sample 1/1000 of their logs, so every hit they show can be assumed to be multiplied by about 1000. They count Linux, for which they include Android, as 2.04%. The breakdown is 0.75% Ubuntu, 0.47% Android, 0.07% SUSE, 0.06% Fedora, 0.05% Debian, and by the time it gets to Gentoo it is down to 0.02%. Red Hat, CentOS and "Linux Motor" (whatever Wikimedia means by that) comes up with the rest. There's even a breakdown of the different Ubuntu, Fedora and Android versions. Cool. It gives you a general idea of what the penetration rate is any way.

Epdfview

So, I'm happy to have my jhbuild building poppler and its dependencies off their latest commit, and then epdfview and evince on top of that. Of course, if anything is broken anywhere down the chain, things fall apart. I've turned off a lot of the gobject introspection for now....

Epdfview is more lightweight than evince, with a few less dependencies, so I often use it when testing. Epdfview currently compiles against the latest of its dependencies (thankfully no big breakage in gtk+ or glib, as sometimes happens) and can load some PDFs. But a number of PDFs it crashes on. Gdb says:


Program received signal SIGSEGV, Segmentation fault.
[...]
__strlen_sse2 () at ../sysdeps/x86_64/multiarch/../strlen.S:31
31      ../sysdeps/x86_64/multiarch/../strlen.S: No such
file or directory.
        in ../sysdeps/x86_64/multiarch/../strlen.S
(gdb) bt
#0  __strlen_sse2 () at
../sysdeps/x86_64/multiarch/../strlen.S:31
#1  0x00007ffff772f502 in g_strdup (str=0x1 <Address 0x1 out
of bounds>)
    at gstrfuncs.c:101
#2  0x000000000040ad46 in
ePDFView::IDocument::setLinearized(char*) ()
#3  0x0000000000411680 in
ePDFView::PDFDocument::loadMetadata() ()

Hmmm. It took me a little time to figure out why this was breaking every now and then. I am compiled against the latest glib commit - is someone messing with g_strdup or something? Eventually, I tracked it down to a commit in poppler from September 17th. From the message I guess they knew it would break the API - "PopplerDocument:linearized is now a boolean value rather than string, so this commit breaks the API again."

So that's simple enough. I changed the gchar's to gboolean's, and made some other little changes, and sent a patch in to jordi at emmasoft, so maybe it will get applied. My version is working anyhow...

Using jhbuild

So, in the GNOME-and-fd.o(freedesktop.org)-verse, there are a few things I want to run from the latest updates - evince, poppler and cairo. Which means I want to run the latest versions of their dependencies as well. So I decided to use jhbuild to build it all. Last month, GNOME developer André Klapper wrote in his blog about how little fun it is to build GNOME from the latest commits via jhbuild. Perhaps, but I finally did it - a subset of GNOME anyhow.

The default jhbuild moduleset is gnome-3.0, but that builds some of the stuff I'm focused on from tarball's, which is supposed to be deprecated in jhbuild now anyhow. So I remove gnome-3.0 from my .jhbuildrc and put all of the devel modulesets into my .jhbuildrc. But some of the dependencies were missing - they were in the non-devel modules. So I put all of those into my own moduleset. As my moduleset is local, I set use_local_modulesets to True - even if thats not necessary, I git pull from jhbuild before I run a jhbuild, so why not do that? I also put


module_autogenargs['evince'] = autogenargs \
                             + ' --disable-nautilus '
into my .jhbuildrc to avoid those headaches with evince. I skip a number of modules people recommend to put in skip, like mozilla, although I don't believe they're dependencies in my chain. I also add a few pkgconfig path's to .jhbuildrc, on advice from the net. Of course, I also install the packages on Ubuntu that the jhbuild web site recommends for Ubuntu 10.10.

Incidentally, here are the jhbuild dependencies for evince (and epdfview):

Color code for nodes: green are packages in jhbuild "devel" modulesets, red are packages in jhbuild "non-devel" modulesets, brown (libgcrypt and libgpg-error) are also in jhbuild "non-devel" modulesets and they are tarballs there, purple are packages in jhbuild "devel" modulesets which other packages might have a hidden dependency to which is not shown in the current jhbuild modulesets. Finally blue are non-GNOME packages that no GNOME module is dependent on, but which are themselves dependent on some GNOME modules.

I made the above dependency tree with graphviz, a tool which makes doing such dependency charts really easy.

Everything went pretty swimmingly until I started to reach the top of the chain. Poppler busted on some GObject introspection stuff - I installed gobject-introspection as a jhbuild module and updated the poppler gir include from Gdk-2.0 to Gdk-3.0 and it went sailing along.

Next up - gtk+ 3.0 broke. This happened to me a few days before, when I was taking my first stab at jhbuild. At that time, I looked at the recent gtk+ code, saw the stuff breaking had changed recently, and did a hard git reset of gtk+ to a commit from 48 hours before - it installed fine. This time the commit done was the last one. I went on GNOME's IRC network and tracked down the developer who made the bad commit, he fixed it and I was sailing along again.

So now I get to evince. A few days ago I had some problems with deprecated combo box calls that had been removed from the dependency libraries, but there were patches for that in bugzilla. After patching that, this time I get an error that a set_scroll_adjustments call is failing. I look in gtk+ and see that they have been mucking with scrolling there recently, and figure it is due to that. I disable the call and compile. Evince comes up and I can look around, but it hangs on loading anything.

I check poppler's test programs and they are working. So I encapsulate a lightweight PDF viewer that depends on poppler and gtk+, epdfview, into my personal jhbuild moduleset and build it against these libraries. Epdfview comes up, and displays PDFs etc. fine. Ultimately, epdfview and evince are dependent upon almost entirely the same libraries, except evince depends on three more icon-related ones. And epdfview is working. So either evince is broken, or some library it depends on has changed, meaning... evince is broken, for the moment. But Epdfview works.

I just put my program suite Blunder online. Anyone who plays chess can check it out. It is LAMP (PHP, not Perl) based, and also uses the chess engine Crafty. I have to automate and simplify it more, but I was doing all of this manually in a notebook at one point and so Blunder is a lot simpler than that.

Most chess teachers will tell you there are a variety of ways to improve your chess game. One is to look over your tournament length games after they are played, and annotate them, and if possible to have your chess teacher annotate them as well and point out mistakes you made and opportunities you missed. Blunder is for people who don't have a chess teacher available. If someone wants to review a game they played so as to do better next time, they have Crafty annotate the game. Then using WINE and pgn2fen.exe, they pull the relevant moves (FENs) out of the game, where crafty notes they could have made a better move. I thought about rewriting pgn2fen.exe myself in PHP or Perl or something, but it already exists, and is usable with WINE, so I figured why reinvent the wheel? With the FEN and Crafty notation at hand, we now enter Blunder

First we enter the FEN via a web page and it gets a numerical ID and is put into the database. Then we enter the blunder information for that FEN - when the game was played, what move was originally played by us, what move Crafty says would have been better, and how many points Crafty gives to each move (if there is a one point difference in scores, I blundered away a pawn, or missed an opportunity to grab the opponent's pawn - if there is a three point difference, it is a knight or bishop which was squandered etc.) Now all the information is in the database.

So what I then do is go to the trainer, which is sorted by score difference, with my worst blunders at the top. I click on it and the board I was seeing when I made the mistake is displayed. I then ponder the move for a while, then click on the board. It pops up a window which shows what move I made, and what move Crafty advised. I continue revisiting the trainer page, which I am continually updating with bad moves I made from games played. After a while, I begin seeing the correct move, and the recognition gets quicker and quicker. Where I would have made a bad move before, now I am making the correct move. Soon, I start making the correct move in similar games I am playing, where before I may have made a bad move. My chess game improves. Reviewing your blunders like this is a long-time known method of improving your chess game. Psychologists have even done brain scans where they see chess grandmasters hitting the proper associative cerebral cortexes when considering moves.

When putting this together, I assumed there was some simple, free, public PHP program that when given FEN notation would display a chess board on a local web page. I was unable to find a program like that however, or at least one not tangled up in some massive program suite. I have a PHP displayfen() function in this program which will do just that, in case anyone wants to use just that part of the program for some reason.

Right now, the program suite for 0.1 only contains this one aspect of displaying blunders from ones own games. It could easily be modified to show two-to-mate problems or other such chess problems. But aside from that, I have begun writing an opening trainer that may become part of the Blunder suite. It is a little bit harder to do - in the first move of a game between white's opening move and black's, there are 400 possibilities. Chess teachers recommend students not memorize chess openings until they are at a high level anyhow (although they do say people should have a general understanding of openings). The opening component of the suite I have to think about some more - there is no way I can enter all of the opening book manually (although I may put something in for opening choices I favor).

My patch was committed to jEdit, cool.

I was looking through the source code for the latest version (23.0) of Crafty recently. It is a CPU and time sensitive program, so I ran gprof on it to see what it spent its time on. About 85% of the time was spent calling ValidatePosition(), which didn't seem to be doing anything of importance. I looked around a little bit and saw this was happening because the Makefile's -DDEBUG flag was on by default for a make linux, and that this was not well documented (it's not there by default for 22.9). I suspect that the flag was left in there by error before it was packaged for release. Anyhow, I sent them off a note.

1 Aug 2009 (updated 2 Aug 2009 at 16:44 UTC) »

I have been taking a Java class recently, but thus far had not really taken the step of rolling up my sleeves and doing some real coding other than the standard Hello world, Hanoi towers, Fibonacci sequence stuff. I finally settled on trying to take a wack at a bug in jEdit. Much of the problem was solved by the people posting in the thread, especially Denis Dzenskevich. This combined with a little bit of digging in Sun documents on the Pattern and Matcher classes and a good Javaworld article by Cristian Mocanu on regular expressions in Java pointed to the problem. First, I converted the long in-the-wild file this was freezing on to a simple and legal five line Perl program. After doing this, I saw the problem. jEdit was using a greedy quantifier in the regular expression where it should have been using a reluctant quantifier. I sent in a patch, notified the original bug poster and he mailed me that it fixes the jEdit freezing problem for him.

The problem still exists if the Perl code has malformed backslashes in the second field of a tr statement using curly brackets. However, the fixed bug is rare enough that it wasn't discovered until June, and unimportant enough that my patch hasn't been committed over the past week, so this rarer case is an even lower priority to look at. Which brings to mind a jEdit bug "FindBugs" brought to light - two uses of "Math.abs(new Random().nextInt())". Now on the 1 in 4 billion chance the random number is the absolute minimum possible, will Math.abs return a positive number? The answer is no (I tested it). Again, the odds of this happening are low enough that a patch is low priority.

My patch (#1556112) made it into the latest release of GOCR, cool.

Lately I have been working a few things. One of them is chess-related programs. I wrote a PHP program that takes a chess FEN and displays a chessboard based on it.

Right now I am working on a program, with a PHP frontend and MySQL backend, which instructs how to run through the opening properly. It will also have a section showing how often I have played this move.

I also have another program which will use a chess engine (Gnuchess, Crafty or the like) to annotate games, and then on the moves where I blunder (or miss an opportunity), it will save that move. Then it will display all the places I blunder, so that I can look at them and learn what the proper thing to do is.

1 older entry...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!