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.]


Loomis said...

This was something I found to be slow about my program as well. For example, my original method for doing a material evaluation was to loop over all the squares of the board and count up the pieces. Clearly it's more efficient to loop over a list of the pieces and add up their values. Of course you can roll a rudimentary positional evaluation into either method as well.

Keeping a running count of material that is updated every time a capture is made or un-made seems like it would be faster, but didn't give any noticeable increase in speed in my program and was significantly more complex to program without error. Also, the simple positional bonus can't be rolled into this method so you also have to keep a running count of positional bonuses to get any benefit.

Determining whether one side or the other is in check was also something I did very inefficiently at the start. In the end, the fastest thing I found was to utilize attack tables to determine if the king and the opponents pieces were lined up and along which direction, then to just check the squares in-between for interposing pieces. (I use an 0x88 board representation if that's meaningful to you.)

Of course, I didn't write the world's greatest chess engine. Good luck streamlining your operations, it can make a big difference in performance.

XY said...

I've created a huge increase in performance by handling 'checks' by letting it capture the king. Earlier, just before I made the switch, I was down at 1-2k positions/s, and now the average is perhaps 30-35k positions/s (not just from that particular change, but that was the major one).

I'm happy with that increase in performance (even if it still isn't the fastest program on the block) so I'll keep the current sweeper for the time being.

I used a simple 8x8 array of ints until recently, and then I changed to an almost as simple 12x12 array in order to simplify checking for off-the-board coordinates. Maybe I'll go for some of that more advanced stuff later, but that's not my priority right now. I still have some glaring problems with the program, including mating with queen+king against king (which I know in principle how to fix, just haven't gotten around to it...)

Locations of visitors to this page