Another story from my college days. Be warned, long article.
Engineering colleges in Kerala require students to submit a mini project in the third year of their computer science and engineering courses. This is in addition to the main project which is to be submitted in the last year of the course.
Two of my classmates – Praveen Kumar (who in our circles is regarded equal to Jon Skeet), Philip and I formed our team for this mini project. We were very much excited about this project that we started discussions about it a lot earlier than the official project start time. After a lot of late night debates we decided to develop a chess playing program.
Three of us were sharing a rented house near college and we used to develop software utilities for various purposes#1. The main point to note here is that we developed these programs in – wait for it – Visual Basic 6.
We were very much comfortable in Visual Basic, and since it is very easy to develop a good chess UI in Visual Basic, we started building a prototype of the application in VB6. We thought that once the basic logic is done and working, we would port it to a better and faster language. Unfortunately, we worked on the code for very long and hard that the code base grew larger and longer.
Testing the program was somewhat tricky. The alpha-beta based algorithm was in a working condition and the program was generating and making some basic moves, but we were facing two problems:
Problem 1: How do we know if the computer has played correctly? There is no way to really make sure that the computer has played the correct move (for any given depth) because we ourselves don’t know the correct move! Of course if you are a good chess player you can find out a good move for a particular board position, but that does not solve the problem. First of all you cannot be sure that your move is the best move. What if there were better moves that you just did not see? Secondly, chess players do not think exactly like a computer. They do not calculate the moves strictly using an algorithm. Some of their decisions are based on intuition.
The very best chess players can just look at a chess position and see the 2-3 lines of play that they should analyze instead of analyzing all the 30+ available moves. Computers cannot do that. Computers should look at all the moves to decide whether to analyze that line of play to more depths or not. Humans are good in chess strategy while computers are good in the tactics. This means that a human cannot tell whether a computer is playing the perfect game (for any given depth) or not.
Problem 2: Since our implementation was not complete and no optimizations were made initially, the computer would take very long time to think and make its move. We had to wait something like 4 minutes or so to get each move from the computer and it was taking up much of our development time. Verifying the correctness of the program was going to take a lot of time.
One good way to test a Chess program is to make it play against itself#2. So we would code till late nights and in the mornings when we go to college we would start the program and make it play against itself. When we come back we would look at the logs and see what happened. As much as excited we were, the results were often depressing. Most of the time the game will go into a loop where each player played (back and forth) the same moves. The reason was that once the chess AI#3 found the best move for a particular board position, it just plays the move disregarding any other facts like the history. The best way to fix this is to tell the program to consider the move history too in making its decision about which piece to move.
Another reason for frequent loops was that both the players in the game were of the same strength (they were both thinking x moves ahead). To fix this and to see some real results we made them of different strengths. One of the players will think x moves ahead while the other would think x-2 or something like that. This improvement helped us see some real results. When we came back to check the results at the end of the day, we could see one of the players checkmated!
If you are into computers, chess programming is one of the best ways to have fun. There are a lot of intricacies in the implementation so that you can tweak the program again and again to get performance improvements. The best chess programming tutorial (for beginners) I have come across is the one from GameDev.net.
I remember one other small bug we faced. Here is how a computer chess program finds out the best possible move:
Find out all the valid moves available to the player. Assume that you played the move and find out the new board position. Now look at the new board position from the perspective of the opponent and try to figure out what move he is most likely to make. If he makes that move, what will the new board position look like? What move will you make to counter his move?
You can go on and on iteratively deeper and deeper into this search tree#4 . The deeper you search, the better your decision (move) will be. For each board position the algorithm will assign a score. The score determines how good the board position is. If one of your pieces is captured, you lose that much score. For example if you lose a pawn, you lose 1 point.
Now look at the following game tree. Blue represents a move by the computer and red, a move by the opponent. The numbers indicate the points gained by the computer in each step.
For example in the first line of play, the computer gains 5 points in the first move (probably by capturing a rook) and in the counter-move the opponent fights back by gaining 3 points (probably by capturing a bishop/knight). Now as you may remember, the algorithms just looks at the total points of the player at the end of each line of play. In both of the above cases, the total gain by the computer is 2 points.
If the computer chooses between these two lines of play randomly, you are in for trouble. The problem is that the computer does not know what happens after the last move in the line of play. This means that if you follow the first line of play you are almost certain to have gained 2 points after the next two moves while in the second line of play you will lose 3 points after the next two moves. May be you can gain 5 points later in the game, but what if after two more moves when you can see further in the tree you realize that the move you saw earlier would be disastrous? Then you will have to change your game and this means that you cannot get those points.
There are two ways to solve this issue. The first is to prefer early points to later ones. In our example, it is better to choose the first line of play over the second one.
The second way is to use quiescence search:
The horizon effect can be mitigated by extending the search algorithm with a quiescence search. This gives the search algorithm ability to look beyond its horizon for a certain class of moves of major importance to the game state, such as captures.
We did a lot of modifications to the code. We used to take the printed versions of the source code (about a 100 pages) to our college and tried to find optimizations that can be applied to the code. Chess programming is one of the areas where over-optimization is not frowned upon.
So after all the hard work, the program was working fine and it could play a decent game of chess (given enough time of course).
Translating the source code
We were just about being happy at how the project was going on when it hit us – the college put a restriction that all projects must be done using Java. We had to port the application to Java soon.
Rewriting the whole application from scratch seemed time consuming and demotivating. We needed a faster way. What about converting the source VB6 source code to Java code automatically? Of course for this to work we would have to write a VB to Java language translator. It seemed too difficult considering the fast approaching deadline for project submission. We downloaded some code translation software from the internet and tried them out, but none of them seemed to work perfectly. Converting a complex VB6 UI having a fair amount of custom animations to Java is almost impossible even for an advanced translator.
Then we had an idea. Regex!
Of course Regular Expressions are not ideal for parsing source code of any kind. We had no time, so we decided to try anyway.
In the case of any decent chess playing program, there are two basic parts: a chess engine and the UI module. The chess engine does all the complex calculations – recording the user moves, finding out whether a move is valid or not, thinking about the best move for the computer etc. The UI module displays the chess board to the user and allows the user to make a move using the mouse. Now as you may have already inferred, the UI part is not very translatable between VB6 and Java. We decided to develop the UI from scratch in Java.
The interesting thing about the chess engine is that it contains lots and lots of calculations, conditions and loops which help it to make an intelligent move. I should probably note that a chess engine cannot be considered intelligent as such. A chess engine crunches millions of number very fast and finds out the best move the computer can make against a human opponent. The moves may look intelligent to a human player, but a chess engine cannot be regarded as an example of an AI engine. It is just a number cruncher beneath its layers. Anyway the point is that we had hundreds of pages of code that consisted purely of algorithms which aided the computer in playing a better game of chess.
As we found out, converting these algorithms from VB6 code to Java was not that hard as it seemed. We employed the powers of Regular Expressions to do that. Here is a glimpse of what we did.
1. Replaced:
If with if(
For with for(
Then with {
Else with } else {
End if, Next, End Function etc with }
True with true
False with false
And with &&
Or with ||
Mod with %
Exit For with break;
= in conditional statements with ==
etc.
2. Added ; (semicolon) at the end of lines which did not start with any of the above keywords.
3. Changed the array referencing code. Something like Board(x,y) in vb6 code became board[x][y] in Java code.
4. There were some complex conditional statements in the VB code that we thought would be impossible to convert to Java using Regex. We had to convert these manually.
5. Converted looping statements of the form
For i = 0 To NumMoves - 1 to
for(int i = 0; i < numMoves-1; i++){
6. Variable declarations of the form
Dim index As Integer to
int index = 0;
There was more of this kind.
Of course it was not all Regex stuff. It is impossible to get it right with Regex alone. The small program we wrote to translate the code read each line of VB code separately and converted it to Java, mostly using Regex. The whole translation (Regex replacement) was done in several passes. We never implemented a full-blown translator or language parser.
Even after this entire Regex circus the translation was not complete. We had to read through most of the code and change a lot of things to get it working correctly. There are many differences between the languages (like array indexes started 0 in Java and 1 in VB6) and those needed to be taken care of. It did take us a bit of effort to get the details correct, but finally we completed converting the code to Java with much less effort than completely rewriting it.
Please don’t let this article make you think that I advocate using the Regex for this type of work. I don’t.
#1More on that later. Remind me if I forget. I promise that this will change the life of many undergraduates. 
#2Another good way is to pit it against better chess engines.
#3I included the word “AI” there just so that I could write this note. Chess playing algorithm cannot be considered Artificial Intelligence. Computer chess is a number crunching problem. Implementing the algorithms in the most efficient manner is the best way to get good results. There is no intelligence involved (compared to real AI techniques such as Neural Networks).
#4It is limited by the computing power you have. On an average the number of valid moves you have for each chess move is about 30. If you are going to search 8 moves ahead, you will have to search through 30^8 nodes, which is a very large number.
