A story about Python... sort of

[Russell Reagan]

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.

 

[Dave Brueck]

After thinking about it I tend to agree. I'm a little partial to C/C++
because I develop (as a hobby) a chess playing program, and I like
tinkering with it to see how fast it can go, and finding clever ways of
doing things. A chess program is different from a 3D game in that with a 3D
game, you can stop at some point and say, "ok, this is fast enough." There
is little point in making the game run at 1000 frames per second if no
human eye can see more than 60 (or whatever the number is).

True, although rather than let the frame rate continue up the game designers
will simply add more polygons, more actors, more textures, greater viewable
distance, etc. so they won't ever reach the "fast enough" point either.
Instead you always reach the "fast enough for now" limit.

There will remain *some* cases where you need a lower-level language in order
to get more speed, but those cases are becoming less frequent - for each one
there comes a time when the cost of that extra speed becomes too much. Also,
some projects (like Pysco) open the possibility of on-par (or even greater,
in theory) speed by using a higher-level language.

But my main point was that, at least for the stuff I do, there's never any
point in writing all or even most of an application in C++ anymore (and the
few parts that do need more speed would be in a dumbed-down, simplified C++
at that). If I were writing the chess game I'd probably write the entire
thing in Python to begin with anyway, just to get it working. Having a slow,
but working app would either help maintain my interest in the project or let
me know early on that it's not something I really want to do.

If I kept at it then I could, at some point, move some speed-critical code to
C or C++, but I'd try to avoid it for as long as possible. For example, you
mentioned that your interest was at least in in part about finding ways to do
things faster or to make the game smarter. In a higher-level language like
Python that sort of expermimentation is relatively cheap - in C++ you might
avoid radical experiments because the cost of change is too high. Your
biggest speed and smartness improvements after picking the low-hanging fruit
are likely to be algorithmic in nature (e.g. using a more ingenious heuristic
to reduce the search space of next moves) as opposed to low-level tuning of
loops or data storage, so it would be advantageous to do that work at as high
a level as possible (and you can always translate those algorithmic
optimizations to a lower-level language someday if you want).

Just my two cents of course,
-Dave