Happy 2015! If you are reading this it means I actually got to finish writing this blog post and it did not go to that Graveyard of Unpublished Posts in my server.
I started 2015 (the first few hours of January 1st) finishing off a phase of a personal project I’ve been working on for a few months now. World, meet Chess Templar.
So well, I guess its time for some public documentation. That’s what this post is exactly.
So what is this project all about?
Around August of 2014 (August 18, 2014, to be precise), I got fascinated with Chess. I’ve had bouts of fascination with Chess before this but I did not push it that much. I remember spending a chunk of my after-school Grade 6 time playing Chessmaster 5500. During my third year in college, I had the idea that if I play a game of chess everyday, by the end of a month, I would’ve played 30 games, and I’m 30 games more experienced than I was a month ago; I played against the Chess program in Windows Vista and against GNU Chess. I had the same idea in 2013, only that time I played against Chess Free in Android.
The thing with those bouts is that they did not last because, I guess, I was ill-equipped to study Chess. Reading reviews of Chessmaster 5500, I keep running across the remark that it has an excellent tutorial mode. I have vague recollections of using that mode but I think I just did not see the reason behind the moves the AI was coaching. Besides, will you ever trust an AI that it will coach you to defeat itself?
Sure now there are lots of software out there for studying Chess, some even free. But then, I don’t find that they have the features I’d like to have while I study Chess.
What features?
For one, I’d really like an engine that will help me practice a particular opening. Or annotate games. And I’d like to be able to tinker with the algorithms (not just the parameters) of my engine.
Hey, I found this Chess software that does exactly that and it’s free and open-source!
Oh. I forgot to say that this is also my rather-lengthy exercise on artificial intelligence. There’s a reason I wrote it in Java (not my usual Python project).
To note: Had I only wanted a Chess engine to play with, I would’ve forked PyChess.
What do you have now? What’s coming up next?
The biggest chunk of Chess Templar right now is the GameArbiter, which enforces the rules of Chess. I have tried to be as meticulous as possible in encoding creating the arbiter. To mind it can take account of:
- En passant captures
- Subtleties of castling: you cannot castle out of, through, or into a check.
- Rules on dealing with checks.
Notably, it cannot yet account for:
- Draws. Man, draws must be among Chess’ most complicated rules.
- Pawn promotions. Actually, I have not yet decided where in my code should I handle Pawn promotions.
That said, at 317 commits at press time, GameArbiter would still handle endgames poorly.
Also, coming up next is adding rudimentary AIs. I’m still studying Chess-playing algorithms. Chess is a well-known example of combinatorial explosion so it automatically rules out basic minimax, unless maybe if I limit the depth (but how much good will that be?).
To count, there are 20 possible first moves:
- each of the eight pawns can either advance one or two squares -> 16 moves
- the two knights have two squares each to move to -> 4 moves.
Black, in reply, have the same 20 choices.
Any metrics you are using to evaluate your output?
In the long run, if I make it good enough, I want to pit whatever engine I come up with in the Thoresen Chess Engine Competition. For now I’m settling with getting good unit-test coverage.
(Note: This is a fault of the Maven coveralls plug-in I am using but the badge at the repo’s README is misleading in terms of my current code coverage. Check the last link to see that I am at 91.86% coverage at press time).
Any algorithms/tricks/hacks you would like to note?
To check on the King’s safety, I modeled the relationship of pieces and squares in the board as a directed graph. For every square in the board, an edge is incident to it if any piece can move to it on a side’s next turn. Only squares with pieces occupying them can have an edge incident from them. (So, if an occupied square has an edge incident to it, it means that that particular piece is in danger of being captured.)
With this representation, I want to check on “hotspots” in the board: squares with the most pressure, pieces under the most pressure. Just a gut feel that I could make an engine take advantage of this.
So there, everything of note in my project so far. Happy new year and, if you’re interested, fork me on GitHub!