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.

No comments:

Locations of visitors to this page