Tuesday, August 07, 2007

Babylon : Report

A new post on my chess program. I've mostly been improving the design, but some improvement in playing strength too.

New games included in the end.

Most of what I've done since my last report is structuring the code. The major change is large scale modularization (my fifth design principle, identified here .) Earlier I had all code in the same unit (which also means same file), as it's called in Delphi. Now it's divided into 6-7 units (one main unit, one unit with classes related to evaluation of a position, and so on), and the best part is that no two units are dependent on each other. It's always one way only. This meant I had to spend considerable time decoupling different parts of the program; unnecessary connections I've made out of laziness. (That's often the case in programming -- ugly and complex solutions are often easier and faster to make, until the program starts to breakdown out of sheer complexity, in which case finding bugs and making modifications start to take much time. On the other hand, simplicity in structure and design is more difficult to achieve, but much easier to maintain, understand and modify.) Took considerable time, but it could've been far worse. I feel I understand the code better now.

Decent before, better now. So on a global level I'm pretty happy with the design now. On the level of algorithms it's still pretty messy (you wouldn't believe some of the solutions I've created and still use). But that's within controlled areas so to speak, so it's not urgent to fix.

The improvement in strength consists of two things: improvement in evaluation, and more importantly: iterative deepening. It is a complete iterative deepening with extraction and insertion of a principal variation (these terms are explained below). However, it doesn't work as it should. The PV thing is actually making it somewhat slower that before (the opposite should be the case). But, the improved time management inherent in iterative deepening is a big improvement, especially in the end game.

What iterative deepening is: playing without it (usually) means searching to a fixed depth. For example, the chess engine always thinks 5 plies deep (+ quiescence search, if included), regardless of position. But that makes no sense, because in some positions 5 plies may take 400 seconds, and in others only 4 seconds. Iterative deepening solves this problem: it means to start with 1 ply deep, and then 2, then 3, and so on, until the time runs out, and then choose the best move from whatever depth you managed to achieve given that amount of time. (In the games below Babylons depth varied from 1-9. Without iterative deepening I would have had to go no deeper than 3 plies, to be sure it doesn't get stuck in some time consuming analysis. And going 9 instead of 3 is a huge benefit.).

That thing "extraction and insertion of a principal variation" means the following: when the engine goes, say, 3 plies deep (expecting to go more), it extracts what is considered at that point to be the best variation (both sides playing the best possible moves). And then at the next iteration (4 plies deep), the variation extracted the iteration before is the first variation to be tried. This improves the move order, which improves speed. In fact, it's the (by far) best move ordering principle that chess engine programmers have come up with so far.

Time for the games, three of them.

Against Raspoeting (one level in the chess program called Nagaskaki, which is free for for download . It's a very nice chess program.) A draw!

Another Game. Same enemy as once before, The Thinking Machine. Some funny moves, including a gambit (?) of some sort by TTM early in the game. It's a draw, but only because Babylon, who is two queens ahead in the game, can't differentiate between mate and stalemate.

Below a win against another old enemy, Homeostatic Computer Chess Player. It's very slow, so I stopped when Babylon had rook + three pawns against a lone king. (Technically it could have ended in a stalemate for the reason mentioned above. I'll fix that some day, just a detail.)

It's a long and somewhat boring game. A fierce warrior Babylon isn't. It's the most cautious engine around (and always ready to accept a draw, judging from all attempted threefold repetitions. But the enemy wouldn't have any of that, luckily.)


Blue Devil Knight said...

Very interesting! I'm a little unclear on why PV analysis ordering helps. Why does the order of search matter if it's going to get to the non-PVs eventually anyway?

XY said...

No it actually analyzes fewer variations when using the PV. Or any other move ordering improvement -- all of them lead to fewer variations being analyzed (while getting the exact same result; the same move is chosen in the end, so it's a 'safe' improvement).

The reason for this is somewhat complicated, at least in all its algoritmic details. But maybe a simple example can give an idea.

Let's assume it's white's turn, and there are 35 available moves. One of these moves, Nb5, wins a piece, and one, Qe7, loses a piece. Now, if it tries Nb5 first (good move ordering) it will find the variation with the won piece, and remember that result. And then eventually it will analyze Qe7. As soon as it finds out that this move loses a piece (which it could do while still having 85% left of a complete analysis of Qe7) it can quit searching the remaining lines in the Qe7 variation, because it knows that it's worse than Nb5, and knows that it will never play Qe7 because of that.

However, the opposite isn't true.

If it begins with Qe7 it has to complete the search because it needs to know the result of Qe7 in greater detail (in order to be able to correctly relate it to later analyzed moves). And then it also needs to analyze Nb5 in full detail to see just how good it is. So the net result is fewer cutoffs; more analysis.

Blue Devil Knight said...

I understand. This doesn't lead to bad horizon effects, cutting off the search in a line that appears to lose a piece?

XY said...

No, because it does analyze at least one variation in its full depth.

If the response to Qe7 that wins a piece is Rxe7 (so it's 1.Qe7 Rxe7), then it may analyze all moves that follows after Rxe7. So it knows for sure that 1.Qe7 Rxe7 loses a piece. And when it does, no other move at that depth than Rxe7 needs to be considered (which can result in a huge cutoff), because it assumes that black will not respond to Qe7 with a move that's worse (from blacks perspective) than Rxe7 (but possibly with an even better one!). So Qe7 is out of the question.

Locations of visitors to this page