A story about Python... sort of

Russell Reagan rreagan at attbi.com
Mon Jul 7 05:27:04 CEST 2003


I didn't investigate the python chess program a great deal, since I'm still
learning the language, but it is very likely that it wasn't an efficient
implementation. It takes years to learn how a chess program works, and to
learn all of the tricks you can do to speed things up (and even then you
have to have the programming skill to implement those things).

I agree that it is not good to worry about optimization prematurely, but
computer chess might be a bit of a unique area. Computer chess is the most
heavily researched area of artificial intelligence ever, and as such, there
are tons of "standard" low level tricks or data representations that you can
use to your advantage. For instance, you can use board representation A and
get thing B for "free" (B might be fast attack detection, or the ability to
evaluate some complex aspect of a position quickly). When designing a chess
engine, you have to decide what you want to do, then use the data
representation that gives you the most things you want to do for "free".

This is also why OOP might not be of much use for chess programming. The
goal of OOP is to write correct code by being able to more easily make
modifications to the code by data hiding, writing generalized routines, etc.
Computer chess is so heavily researched, that there are several "standard"
board representations that people use, and they're low level, involving lots
of bit fiddling. Making a board object that doesn't know how a piece object
is implemented serves little purpose other than to slow things down. Part of
a fast chess program is that every part knows how everything else is
implemented, and exploiting that. I'm not discounting anything you said. I'm
just saying that computer chess may be one of the few areas where the
generally good advice doesn't always apply, due to the ridiculous amount of
research. Heck, computer chess was being researched before computers even
existed!

>   - Write a program that does the job at all, paying attention to
>     simplicity and readability and *no* attention to optimisation.

In general, this is good advice, but for reasons explained above, paying no
attention to optimization might be the equivalent of choosing a bad design
for this specific problem. By not paying any attention to efficiency early
on, you effectively limit your top speed later on.

>   - Once the program is correct, and not before, profile it to see where
>     it's slow.

Since computer chess is so heavily researched, I can tell you that the area
consuming the biggest chunk of time will be position evaluation, unless your
program doesn't use a lot of the well known tricks for things like attack
detection, in which case it might spend a ton of time doing that, ensuring
that a move doesn't leave your king in check, that kind of stuff. There is
really not a lot you can do to improve either of those short of starting
over from scratch and creating your data structures in such a way as to
exploit lots of low level tricks.

> at least you've debugged a working algorithm,
> and can treat it as pseudocode for the port to C.

For reasons explained above, I'm not sure that you can make the direct
translation between "python pseudocode" to "C/C++". It sounds like you're
thinking, "I'll just implement this python program in C/C++, and then it
will be faster," but I'm not sure that is the case. Sure it will be faster,
but probably still pretty slow. Making a really fast chess program would
require changing the data structures significantly, and I'm not sure what
use the python code would be after you made a big overhaul of the data
representations.

What do you think? I may be way off. Maybe I'm putting too much emphasis on
speed.






More information about the Python-list mailing list