Thu, 20 Jan 2011
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.
Tue, 04 Jan 2011
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 bit more robust.
Mon, 06 Dec 2010
Blunder, Chess, Java, Architecture and Construction
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 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:
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.