Speed/ELO relationship, and question to engine programmers

[rreagan]

Just for fun, one afternoon I wrote a partially working engine in Python (basically a perft calculator). The good news, it was very fast to develop in Python (a few hours). The bad news, it runs at about 2-3Knps. Crafty on the same machine runs about 4.5Mnps. So a few questions:

Is there a rule of thumb or formula that would estimate the ELO improvement for a given speed improvement? Let's say that the slow engine written in Python was 1600 ELO. If I rewrote the entire thing in C/C++ and it was suddenly 2000x faster, could we estimate what the new ELO would be? Or will this be different for each situation?

Is it worth trying to develop new ideas with such a slow engine? My hope was that it would be easier and faster to test ideas in a language like Python, and I expected it to be significantly slower, but I didn't anticipate it being this slow.

[rjgibert]

Maybe you will find this helpful: http://psyco.sourceforge.net/

[Edmund]

What I read in this forum before is that for a doubling of speed (everything else remaining the same) you gain 80 elo.

... log2 2000 = ca 11
11 * 80 = 880

So assuming everything else was the same, there would be an aproximate elo difference of 880

[hgm]

I always assume Elo = 100*ln(speed). That would give you about 70 Elo per doubling. But the exact number is engine-dependent. Engines with a poor move ordering benifit less than those with a good one.

[Don]

I always assume Elo = 100*ln(speed). That would give you about 70 Elo per doubling. But the exact number is engine-dependent. Engines with a poor move ordering benifit less than those with a good one.

That formula is a good rule of thumb.

Engineering a good chess program, in my opinion, is all about increasing the scalability of it. Move ordering is a huge factor and so is how you do selectivity. For instance if you reduce too many of the good moves or not enough of the bad moves, you have crippled the rate of improvement.

As you probably already know, your formula doesn't work across the whole range of levels but is a good rule of thumb. For the python program, if it's written well a doubling is probably worth more, but for a deep searching strong program, doubling the time may be worth much less.

I spoke to Larry Kaufman about this not very long ago and his observation was that it is surprising how "linear" this line of improvement still is, although there has been a slow but gradual drop-off over the years.

[Don]

I always assume Elo = 100*ln(speed). That would give you about 70 Elo per doubling. But the exact number is engine-dependent. Engines with a poor move ordering benifit less than those with a good one.

I have a more definitive answer now. If you are running fast games at low depths the constant 100 should be sometime on the order of 150.

the 100 value that hgm gives is probably pretty accurate at normal time controls for strong programs. As the programs play stronger and stronger and search deeper you should expect to lower that value.

This is another way of saying that you should expect diminishing returns with each doubling of effort, but the decline is very gradual.

You can probably also assume that this number drops to zero as you approach perfect play.

[CRoberson]

I always assume Elo = 100*ln(speed). That would give you about 70 Elo per doubling. But the exact number is engine-dependent. Engines with a poor move ordering benifit less than those with a good one.

I have a more definitive answer now. If you are running fast games at low depths the constant 100 should be sometime on the order of 150.

the 100 value that hgm gives is probably pretty accurate at normal time controls for strong programs. As the programs play stronger and stronger and search deeper you should expect to lower that value.

This is another way of saying that you should expect diminishing returns with each doubling of effort, but the decline is very gradual.

You can probably also assume that this number drops to zero as you approach perfect play.

Yes, you can assume that it drops to zero. A Calculus way
of stating it would be:

the limit of improvement approaches 0 as the speed of the
program approaches infinity.

Example: you have a program that plays perfectly because
it can see from first move to end of game. If you make the program
10 times faster the program can not play any better because it
played perfectly before the speed up.

Also, it is possible to have a program rated around 1700 (arbitrary number)
that doesn't improve even with a 16x speed up. In such a case,
there exist a major bug holding it back. Fix the bug and get a
major strength increase without speed up. Also, a very poorly
tuned eval will have the same effect as a major bug.

[Uri Blass]

I always assume Elo = 100*ln(speed). That would give you about 70 Elo per doubling. But the exact number is engine-dependent. Engines with a poor move ordering benifit less than those with a good one.

I have a more definitive answer now. If you are running fast games at low depths the constant 100 should be sometime on the order of 150.

the 100 value that hgm gives is probably pretty accurate at normal time controls for strong programs. As the programs play stronger and stronger and search deeper you should expect to lower that value.

This is another way of saying that you should expect diminishing returns with each doubling of effort, but the decline is very gradual.

You can probably also assume that this number drops to zero as you approach perfect play.

Yes, you can assume that it drops to zero. A Calculus way
of stating it would be:

the limit of improvement approaches 0 as the speed of the
program approaches infinity.

Example: you have a program that plays perfectly because
it can see from first move to end of game. If you make the program
10 times faster the program can not play any better because it
played perfectly before the speed up.

Also, it is possible to have a program rated around 1700 (arbitrary number)
that doesn't improve even with a 16x speed up. In such a case,
there exist a major bug holding it back. Fix the bug and get a
major strength increase without speed up. Also, a very poorly
tuned eval will have the same effect as a major bug.

very poorly tuned eval can cause the program to play weaker but
I doubt if it can cause the program to earn nothing from being faster.

Note that in theory even with poor evaluation the program may play perfectly if it searches deep enough.

Uri

[rreagan]

Maybe you will find this helpful: http://psyco.sourceforge.net/

Thanks for all of the responses. I have done a bit of experimentation with Python, Psyco, and Cython. For a quick comparison, I wrote what amounts to a tic-tac-toe perft calculator.

Code: Select all

Tic-Tac-Toe
c++     50,063,604 nps
cython   6,995,552 nps
psyco      670,198 nps
python     245,829 nps

Code: Select all

Chess
crafty  5,792,391 nps
psyco       3,483 nps
python      1,336 nps

So while Psyco helped, the program speed is still nothing great, even for testing. However, the Python chess engine was written completely unoptimized to begin with ("simple" bitboards, inefficient loops, etc). There is possibly some potential that if I wrote it more efficiently to begin with, then applied Pysco, it may be worth experimenting with. The Python chess engine would not compile with Cython, because it had some issues with bitboards, and correcting them would probably be about as much work as rewriting it.

Cython is an interesting approach that I may look into more. It essentially lets you write Python code with type declarations (like C/C++), and it creates C code that it compiles into a Python module. As you can see above, it seems to be a good compromise performance wise. Many reports I have read online claim that they get very close to C/C++ speed with Cython after they learn how to use it correctly (I'm still learning).

I will probably work on creating a Python module using Cython for the basic operations (move generation, make/undo, attack/in-check, etc), and then see how that performs. I'll report back at some point in the future.

[rreagan]

I made a mistake. After looking at the C code that Cython generated, I forgot to declare just one int variable so it was being converted to a Python object. After I declared it as a C int variable, here are the (much improved) results:

Code: Select all

Tic-Tac-Toe
c++     50,063,604 nps
cython  46,480,957 nps <--- Not bad!
psyco      670,198 nps
python     245,829 nps