Friday, June 29, 2007

Chess computer and castling

You may have noticed in my last published game by my chess computer that none of the sides castled. That's no accident since I have no particular code to make it value castling (and in fact nothing to even make it understand when it's illegal -- it may, for example, move the king and then go back and then castle. Cheater!) That's because I haven't decided on how to do that.

It's not entirely trivial, for the following reason. You want the computer to value castling, but disvalue losing the ability to castle with a non-castling king move. So, you can't just have a single boolean variable that contains info on whether it has the possibility to castle and make your judgement based on that, because you haven't distinguished losing the ability to castle by castling, and losing it by just moving the king elsewhere, and you have to give points based on having the ability to castle or not having it. Which is best? There is no way to tell just from examining that variable.

At first I solved this by having two booleans. One called "can_castle" and one "have_castled". The default for them is of course "true" and "false", respectively. And then I gave plus for the combination have_castled = true and can_castle = false, and minus for the combination can_castle = false and have_castled = false, and neutral (no value either way) for can_castle = true and have_castled = false (the default). (Observe that the fourth combination -- can_castle = true and have_castled = false -- can never occur since having castled by necessity also means losing the ability to castle.)

Now I've decided to use just one variable, a simple int using the values 0,1,2 to cover the above possibilities. [Edit: 0-3 is better, so I can differentiate between short and long castling.] But I haven't implemented it yet. So I currently have nothing to tell the Ai to value castling specifically, which is why none of the sides castled in the recently published game. And that's that. (It does castle from time to time anyway, to achieve some other goal, like a more active rook.)

Edit: it didn't occur to me until now that there are cases when castling in one direction is all that ever will be allowed (when the castling rook has been moved). That has to be reflected in the code somehow too. Guess I have to use more numbers.

Wednesday, June 27, 2007

Chess computer: null move pruning

I've implemented a feature called "null move pruning" which helps the search algorithm to get rid of ('prune') more unnecessary variations. I'm down to an average branching factor of slightly above 8 (from about 11). That means it's now possible to (within reasonable time) go 6 half-moves deep. And that's reason to celebrate, like every new half-move. Not that long ago 4 half-moves was unplayable (took too long). Six is still not much, but it's better and it's something. More will come.

Now I'm starting to feel a need to be able to measure its performance in some more way than I'm currently doing. As long as I'm just speeding it up in terms of positions analyzed per second it's no problem since it can be measured directly and with little risk of error, but some other changes as not as easily measured (yet). Of course, counting half-moves (or branching factor), as I've done in the current case, is as good as any measure (or even better) as long as it's free of error, but I'm not sure I've implemented the null move pruning correctly and would like to have it verified by some other means. It seems stronger when I'm playing it, but it couldn't beat a chess program that it earlier (without the null move pruning) had a chance to beat (though it didn't). An accurate way to measure its rating would have been great. Maybe it's time to get it ready for FICS, or maybe download one of those packages with test-scenarios that I've read about. Or something.

Saturday, June 23, 2007

GTD -- what I'm still doing

Many GTDers "fall off the wagon" (as it's often called) from time to time. Not quitting completely, but getting sloppier, and the pre-GTD chaos comes back to some degree. It's easy to see why -- GTD is a comprehensive system with clearly defined actions and principles (with some room for tweaking and personalizing). If you adhere to some fuzzy system based on "do your own thing", it is almost impossible to "fall off" since by definition whatever you do is right. Not so with GTD, since it is an evil and cultish system.

I've never been a strict GTDer, but some things have stuck:

I do write down lots of things, and in a more orderly way than disorganized "to-do" lists. Not having to remember things in my mind is very relaxing, especially when the habit is so deeply set that you really trust your external system.

I write down ideas that comes to me, and I have different categories for different types of ideas. Sometimes I do things with these ideas, sometimes I just keep them to later reference. (Strict GTD would require making decisions about these notes more consistently.)

I write a lot of blog och forum comments, and keep a list of links to these posts. After a couple of weeks, sometimes more, of silence (no new comments) I erase that particular link with the assumption that the thread is dead. (Before I started to do this I always felt as if I was about to forget something, and sometimes I did.)

I keep a list of things I want to do with my chess program.

And much more. However, some of what I write down I don't look at again, at least not for a long while, making it almost useless.

And I don't keep all those elaborate lists with "next actions" with different "contexts" and so on. I do have a someday/maybe list, but I rarely read it. Still, knowing that everything I want to achieve someday is written down feels calming somehow. I know I will not wake up in 15 years suddenly remembering I should have achieved something during the latest 10 years. Maybe I won't achieve it, but not because I forgot about it.

The questions "what's the next action" and "what's the purpose" (in any given area) have been valuable, and it's something I ask myself a lot.

I have a much greater understanding of what causes chaos and stress -- lack of equilibrium between input (stuff coming into your life) and handling that stuff. Which means, among other things, that I now more easily can identify problem areas and work on them. (Still have a problem in this area though -- I tend to keep more stuff than I use or organize, especially non-physical stuff like bookmarks.)

And will also write a post on what software I still use. Some GTDers get obsessed with finding "the right software" to enhance their productivity. I didn't become like that, but I have tried (and discarded or kept) some. What you actually keep and discard is not always what you initially think when you try it out.

Thursday, June 21, 2007

Game played by chess computer

Played 2007-06-18, against itself.




4 plies (half-moves) deep.

time avarage per move: 0,613s
position analyzed per second, avarage: 30520
branching factor avarage: 11,0546037560704

Branching factor is how many moves it tries out in a given position. The avarage number of available moves during middlegame is something like 35. An unsophisticated search-algorithm (usually "minimax") tries them all out, whereas the better ones (always some version of "alphabeta") cut off lots of branches. How many branches it after pruning will try out depends on some features in its implementation -- it ranges from about 6 to 36. So my avarage branching factor isn't that bad compared to the worst case scenario. However, there is still a huge difference between 11 and 6. If you go 8 half-moves deep with a branching factor of 6, that's 1.7M moves to analyze, whereas 8 moves deep with a branching factor of 11 is 214M...

(It is possible to let it play 5 plies deep within reasonable time... about 7 seconds in avarage per move. Next game to post will be a game against Fritz, set to play at a lower rating, 5 plies deep.)

Saturday, June 16, 2007

chess program, funny position

Sir Edward Vs farm boy
It was finally dawning upon Sir Edward that he may lose.


Or maybe: "After careful consideration Sir Edward concluded he was worse off."

The above position came up when I was trying out a new method that sets up a position based on a string. Earlier I had few pre-coded positions in order to test the program in different positions, but the information of where to put each piece and pawn was integrated with the instructions that put it there. Now they are separated; one method handles the setting up, based on a string (which represents the position) sent as an argument. At first there was some problem and the position above came up (without the kings). Thought is looked funny. : )

I've started to measure the performance of the chess computer by letting it compete against other chess computers and record the result. I'll be back with some statistics. (It still plays badly, but it's fun to watch nonetheless, at least if you're the creator.)

Sunday, June 10, 2007

Delphi, hallelujah

Still love Borland Delphi. Very easy and intuitive to work with (which is important and leaves more time and energy to the intrinsic difficulties of a chess program, or whatever one is working with), and virtually bug-free. In all this time I still haven't encountered a single bug in the environment. It never hangs or crashes or anything. The chess program itself hangs all the time (because of temporal coding errors, like forgetting to increase the counter variable in a loop) but it never affects the environment within which I'm testing the program.

It is very easy to navigate through the code. The chess program currently exceeds 7000 lines of code, and it would be hopeless to work with without a good navigation system.

Some of the semantic features in Delphi are very useful. I've mentioned in an earlier blog post the possibility of starting an array with any index. I've now seen the usefulness of that. My board-representation was an 8x8 array. With a language that makes you start all arrays at zero, the board representation would range from 0 to 7, which is somewhat anti-intuitive compared to 1-8 (I also use constants a-h to represent 1-8, so to access e4 I simply type board[e,4], which is simple to work with. A language with zero-based arrays would use board[4][3] to access e4.)

But the real power of non-fixed starting index became obvious when I expanded my array to become a 12x12 array (in order to make checking for off-the-board coordinates easier.) With a zero-based array you would have rewrite the code so that board[3][3] becomes board[5][5] and so on for all earlier instructions (unless you've used constants, which I bet you haven't, you slacker). But with Delphi you simply make the new array range from -1 to 10 (assuming the old one ranged from 1-8), which means that the old board still applies in the exact same way. You don't have to rewrite a single line of code to make it work (although you do of course have to rewrite some part of the code in order to benefit from new board).

Okay, now I've spent too much time on a detail when the real strength of Delphi is how intuitive and easy to use it is (while still being powerful, as fast as C++ and so on). But to be honest my experience with other environments is somewhat limited, but I know many Delphi users agree with me. (For the record, I'm using Delphi 7 from 2002, so I don't know about other versions.)

Wednesday, June 06, 2007

chess program, board sweeping, inefficiencies (part 3)

No, not board sweeping of the good kind. And I realize these posts may not be of great interest for the majority of the readers, but since I'm evil I'm posting them anyway (insert maniacal laughter here).

There are a number of places in the program where it needs to have information on all the pieces. For example, when evaluating the position it needs to know what pieces are present on the board, and where (to take doubles pawns, placement of the pieces etc into account when evaluating). And when it checks for checks and for mate (and being in check) it also needs this info, as well as when it is generating all possible moves.

At this stage I 'sweep' the board every time. That is, this information isn't stored, so I go through the board square by square to collect this information. And this is done a lot; for every position evaluated (thousands each second), every time it generates all moves, checking for checks (which is done for each generated move).

I'm not going to do the math, but let's just say that it is sweeping the board *a lot*, and for no good reason since there is a simple way to cut out this operation -- by storing and updating this information as it changes with each new move. That means some adding some new instructions, but that's nothing compared to what I can remove. The net effect is increased efficiency.

And btw, with "checking for checks" for each generated move, I mean examining to see whether the ai will be in check after having performed the move, in which case the move is invalid (and will not be among the generated moves). However, that's fairly expensive, and a more efficient way is to skip that test and let it perform potentially invalid moves, and instead look for positions where the king is taken (which means that the previous position was invalid since it allowed for the king to be taken). [Edit: in fact, I've implemented this now, and it is considerably faster.]

Saturday, June 02, 2007

chess program, inefficiencies (part 2)

When I first implemented the rules (making the server/model -- that's what I call this part of the program, not to be confused with a web server -- recognize the difference between valid and invalid moves) I thought (probably correctly) I was going to have it ready a little sooner if I didn't have to make every method involved side-neutral, being able to handle both black and white. So, I made all the methods white-centric, and simply mirrored the internal board every time it was Black's turn, and then mirrored it back when the move had been examined (accepted or rejected). So: black makes a move, the board and move (and more) is mirrored, the move is examined as though it was White's move and White's turn, then everything is mirrored back, and the move is either executed (if accepted) or not (if not).

That may not sound like much work, after all computers are pretty fast, yes? Well. It isn't, and they are. But when the chess computer is thinking, it is trying out a lot of moves. And every time it's Black's turn to move, that routine is performed (and every time it's White's turn, it has to run several tests to see whose turn it's, to know whether it should switch or not, so computing power is used even when it doesn't switch). It's an essential part of the process, and will be done many times. To make matters worse, I found it to be fairly easy to make those white-centric methods side-neutral (which also takes some computing power, testing for side...), so I implemented that too on top of the mirroring (but not exactly everywhere, so I couldn't cut out off the mirroring...). So I handled the same problem twice, wasting CPU cycles.

That mirroring, which is long gone now, isn't the most interesting example of inefficiency, but illustrative of a general principle in how to gain computational efficiency: to make the computer do as much as possible with as few (and cheap, time-wise) instructions as possible. Referring here to the number of instructions it actually runs, not how many instructions are written in the code (so a loop with three written instructions running 100 times, is counted as 300 instructions, not three.) (In the final analysis the instructions to be concerned about are the ones on assembly-code level, or even machine-code, however that would be waaay overkill at this stage, and perhaps in all future stages as well.)

That principle is btw similar to the GTD principle of trying to get as much as possible done with as little effort as possible, and the scientific principle of trying to explain as much as possible with as few principles as possible.
 
Locations of visitors to this page