What is best possible with minimal programming

[P.K. Mukhopadhyay]

Hi all,

I am curious to know how far a chess program can go in ELO rating with minimal programming. I am assuming that a program in the making may not have the following features:

1. Bitboard based move generation
2. LMR
3. EGTB support

The best example I know of is Phalanx XXII with a rating of 2455 in WBEC Ridderkerk. To find if anything better is possible it would perhaps be necessary to strip an existing strong program of these features. This would be an expert's job. Readers familiar with published source codes may please comment.

Regards

[H.G.Muller]

I wonder why you associate those restrictions with 'minimal programming' on the one hand, or engine strength on the other.

The way of move generation is usually totally irrelevant for the speed, and hence strength of a program. Bitboard is usually slower than mailbox.

It has never been shown conclusively that EGTBs add any strength to engines whatsoever.

LMR is only a single line of code in micro-Max, where it adds significant strength. It is 4-5 lines in Joker, where I never could show that it adds any strength at all. Many top engines do not use LMR.

Minimal programming would be something like micro-Max.

[Roman Hartmann]

Hi,
you should not point out what you don't include in your minimal programming but rather what you consider to be minimal programming.

Personally I consider a chess engine with the following features basic/minimal:

-board represantation (any will do)
-move generation (any should do)
-move ordering: mvv/lva
-search: negamax with beta-cutoffs
-quiescent search
-eval: material + mobility
-nullmove
-hash table

If you don't have bugs, this should be good for 2400, maybe even more. Btw, that's what I'm doing and my engine is around 1800 ...

Regarding your points 1.-3. I second H.G. Mullers statement.

LMR is more than 5 Lines for me though (still easy to implement) but it doesn't seem to add any playing strength to my engine even though it looks like a real winner at first sight as I get at least 2 extra plies in most positions. But the drawback is that it will overlook a lot of shallow tactics in play.

best regards
Roman

[P.K. Mukhopadhyay]

I wonder why you associate those restrictions with 'minimal programming' on the one hand, or engine strength on the other.

I should have defined 'minimal programming' clearly - I meant a minimal set of ideas used even by today's weak programs. When I look at the huge chasm between the top programs and my program(or Phalanx XXII for that matter), I feel the weaker programs lack some good ideas used in the top programs. LMR etc., seemed to be the most obvious ones, there may be others.

Minimal programming would be something likeMinimal programming would be something like micro-Max.

I am aware that micro-Max is very strong in relation to its size. Perhaps it incorporates most of the good current ideas within its small size and may not be minimal in that sense - you would know best.

Regards

[P.K. Mukhopadhyay]

Personally I consider a chess engine with the following features basic/minimal:

-board represantation (any will do)
-move generation (any should do)
-move ordering: mvv/lva
-search: negamax with beta-cutoffs
-quiescent search
-eval: material + mobility
-nullmove
-hash table

I should have stated what is 'minimal' more clearly, but your definition (along with opening book) will do. I started my program in the simplest way - with minimax search and material only eval. As I added the further features one by one, the program improved steadily in strength - untill now. I now wonder whether my program is extracting the best possible performance out of the above ideas or whether it has subtle bugs. I also wonder whether all of the 500 Elo difference between phalanx and the top programs is accounted for just by the three ideas I mentioned. A strong program using none but the above ideas would be a good point of reference.

If you don't have bugs, this should be good for 2400, maybe even more.

What you say about strength up to 2400 may be true, but I wonder about the "maybe even more" part. Earlier my program used to be mauled by phalanx, but no more. However if I select a slightly stronger program such as Gromit 382 or Arasan 9.5 the result drops to 30% in spite of all my efforts.

LMR is more than 5 Lines for me though (still easy to implement) but it doesn't seem to add any playing strength to my engine even though it looks like a real winner at first sight as I get at least 2 extra plies in most positions. But the drawback is that it will overlook a lot of shallow tactics in play.

Agreed. I have tried simple LMR and temporarily stopped. Perhaps when not to use LMR is as important as using it.

[H.G.Muller]

If you even add opening book to it, what actually do you exclude? It seems to me the list is approximately complete. That is, if you add Pawn structure. (An engine that will not recognize Passers, or will not give a huge bonus for highly advanced Pawns, will be slaughtered even by uMax. And advanced POawns have lower mobility than Pawns in their opening position, so this aspect is not covered by mobility.)

As you don't mention Pawn evaluation in your original list of things to leave out, I would say that the limit is basically 'no limit'. No reason why you should not be able to write a 3100 Elo engine just using the things Roman mentions. Even if you leave out the things you initially mentioned, as they would hardly add any Elo. I think the key difference between the top engines and the 2400 Elo engines is a well-tuned mobility evaluation. So if mobility is on the list, there is no limit.

[Andrew Fan]

Hi all,

I am curious to know how far a chess program can go in ELO rating with minimal programming. I am assuming that a program in the making may not have the following features:

1. Bitboard based move generation
2. LMR
3. EGTB support

The best example I know of is Phalanx XXII with a rating of 2455 in WBEC Ridderkerk. To find if anything better is possible it would perhaps be necessary to strip an existing strong program of these features. This would be an expert's job. Readers familiar with published source codes may please comment.

Regards

Yes, I have the same feeling too but not of chess program. I like some Windows features and some Linux feature, I am think about removing the not so useful stuff and merging them together to one super OS - Winux(tm).

I'll can sell you a copy after I am done.

[Uri Blass]

If you even add opening book to it, what actually do you exclude? It seems to me the list is approximately complete. That is, if you add Pawn structure. (An engine that will not recognize Passers, or will not give a huge bonus for highly advanced Pawns, will be slaughtered even by uMax. And advanced POawns have lower mobility than Pawns in their opening position, so this aspect is not covered by mobility.)

As you don't mention Pawn evaluation in your original list of things to leave out, I would say that the limit is basically 'no limit'. No reason why you should not be able to write a 3100 Elo engine just using the things Roman mentions. Even if you leave out the things you initially mentioned, as they would hardly add any Elo. I think the key difference between the top engines and the 2400 Elo engines is a well-tuned mobility evaluation. So if mobility is on the list, there is no limit.

I disagree
Better evaluation is only one of the differences.
Better search is another important difference and I guess that everyone of them can give more than 300 elo.

I think that EGTB support is clearly unimportant and the importance of LMR is probably not more than 200 elo(I guess that the top programs earn more from LMR because they have better conditions when to reduce so LMR is not only adding few lines of code for them) but there are more search trick except LMR.

Uri

[P.K. Mukhopadhyay]

I disagree
Better evaluation is only one of the differences.
Better search is another important difference and I guess that everyone of them can give more than 300 elo.

I think that EGTB support is clearly unimportant and the importance of LMR is probably not more than 200 elo(I guess that the top programs earn more from LMR because they have better conditions when to reduce so LMR is not only adding few lines of code for them) but there are more search trick except LMR.
Uri

I find your post reassuring - I hope I shall get some more improvement without implementing EGTB etc.

Thanks

[Dann Corbit]

Hi all,

I am curious to know how far a chess program can go in ELO rating with minimal programming. I am assuming that a program in the making may not have the following features:

1. Bitboard based move generation
2. LMR
3. EGTB support

The best example I know of is Phalanx XXII with a rating of 2455 in WBEC Ridderkerk. To find if anything better is possible it would perhaps be necessary to strip an existing strong program of these features. This would be an expert's job. Readers familiar with published source codes may please comment.

Regards

If you are looking for Elo per Kilobyte, then I think that Thinker is probably the champion (some people get similar ratios, but they are using executable squeezers).
http://www.geocities.com/thechessthinker/download.html

[H.G.Muller]

If you are looking for Elo per Kilobyte, then I think that Thinker is probably the champion (some people get similar ratios, but they are using executable squeezers).

Why are you saying that? What Elo and what size do you assume? It seems to me that Thinker does not get even close to a good Elo/kbyte.

The smallest version of Thinker 5.2 I could find had an executable of 62KB. PikoSzachy has only 8KB. Thinker does not even have 20% of the Elo/KB that PikoSzachy has. It is in fact questionable if it does even better than Joker (the executable of which is 51KB), and of the intermediateElo engines NanoSzachy 3.4 is slightly stronger than Joker, and has only 31KB.

The difference becomes even more dramatic if you realize that in most compilers, a program that does absolutely nothing ('hello World', without the printf statement...) already measures 3KB for executable, due to linking to the startup file and run-time system. So in terms of the actual Chess code, Thinker lags behind by an order of magnitude.

[Uri Blass]

If you are looking for Elo per Kilobyte, then I think that Thinker is probably the champion (some people get similar ratios, but they are using executable squeezers).

Why are you saying that? What Elo and what size do you assume? It seems to me that Thinker does not get even close to a good Elo/kbyte.

The smallest version of Thinker 5.2 I could find had an executable of 62KB. PikoSzachy has only 8KB. Thinker does not even have 20% of the Elo/KB that PikoSzachy has. It is in fact questionable if it does even better than Joker (the executable of which is 51KB), and of the intermediateElo engines NanoSzachy 3.4 is slightly stronger than Joker, and has only 31KB.

The difference becomes even more dramatic if you realize that in most compilers, a program that does absolutely nothing ('hello World', without the printf statement...) already measures 3KB for executable, due to linking to the startup file and run-time system. So in terms of the actual Chess code, Thinker lags behind by an order of magnitude.

I think that it does not make sense to divide elo by kbytes because you may get a different order if you add 200 elo to all the programs.

I suggest another test.

do tournaments with unequal time when you give players time that is proportional to the inverse of the size of the exe and see who is the winner.

Let decide that
1 mbyte gets 1 minute per game and it means that 62 kbytes get 1024/62 minute per game when 8 kbyte get 1024/8=128 minutes per game.

Things may be dependent on the hardware but I guess thinker can beat PikoSzachy or Joker on hardwares that people practically use.

Uri

[Dann Corbit]

If you are looking for Elo per Kilobyte, then I think that Thinker is probably the champion (some people get similar ratios, but they are using executable squeezers).

Why are you saying that? What Elo and what size do you assume? It seems to me that Thinker does not get even close to a good Elo/kbyte.

The smallest version of Thinker 5.2 I could find had an executable of 62KB. PikoSzachy has only 8KB. Thinker does not even have 20% of the Elo/KB that PikoSzachy has. It is in fact questionable if it does even better than Joker (the executable of which is 51KB), and of the intermediateElo engines NanoSzachy 3.4 is slightly stronger than Joker, and has only 31KB.

The difference becomes even more dramatic if you realize that in most compilers, a program that does absolutely nothing ('hello World', without the printf statement...) already measures 3KB for executable, due to linking to the startup file and run-time system. So in terms of the actual Chess code, Thinker lags behind by an order of magnitude.

PikoSzachy cheats, it is actually 20K:

Code: Select all

C:\chess\winboard\pikoszachy>upx -d pikoSzachy.exe -o p.exe
                       Ultimate Packer for eXecutables
                          Copyright (C) 1996 - 2008
UPX 3.03w       Markus Oberhumer, Laszlo Molnar & John Reiser   Apr 27th 2008

        File size         Ratio      Format      Name
   --------------------   ------   -----------   -----------
     19968 <-     10240   51.28%    win32/pe     p.exe

Unpacked 1 file.

C:\chess\winboard\pikoszachy>dir
 Volume in drive C has no label.
 Volume Serial Number is 4CCE-339A

 Directory of C:\chess\winboard\pikoszachy

07/29/2008  12:58 PM    <DIR>          .
07/29/2008  12:58 PM    <DIR>          ..
09/14/2004  01:07 AM           474,664 Book
01/24/2005  12:21 AM            19,968 p.exe
07/28/2006  05:25 PM             1,049 pikoSzachy.dat
01/24/2005  12:21 AM            10,240 pikoSzachy.exe


Using the same methodology, Thinker is only 48K:

Code: Select all

C:\chess\winboard\thinker>upx -9 "(Active)Thinker_32-bit.exe" -o t.exe
                       Ultimate Packer for eXecutables
                          Copyright (C) 1996 - 2008
UPX 3.03w       Markus Oberhumer, Laszlo Molnar & John Reiser   Apr 27th 2008

        File size         Ratio      Format      Name
   --------------------   ------   -----------   -----------
     74240 ->     48640   65.52%    win32/pe     t.exe

Packed 1 file.

C:\chess\winboard\thinker>dir
 Volume in drive C has no label.
 Volume Serial Number is 4CCE-339A

 Directory of C:\chess\winboard\thinker

07/29/2008  01:00 PM    <DIR>          .
07/29/2008  01:00 PM    <DIR>          ..
07/23/2008  10:58 AM            74,240 (Active)Thinker_32-bit.exe
07/23/2008  10:58 AM            84,480 (Active)Thinker_64-bit.exe
07/23/2008  10:58 AM            63,488 (Passive)Thinker_32-bit.exe
07/23/2008  10:58 AM            72,704 (Passive)Thinker_64-bit.exe
09/30/2004  09:57 PM            20,992 BookThinker.exe
07/20/2008  11:42 PM             5,632 CreateBook.exe
09/26/2004  02:58 AM               811 display.ini
06/05/2008  08:22 PM    <DIR>          displays
09/26/2004  03:28 AM             7,955 Language.ini
06/05/2008  08:22 PM    <DIR>          languages
09/26/2004  02:47 AM           379,318 Main.bmp
09/30/2004  09:57 PM            13,312 MakeBook.exe
07/28/2008  11:03 PM             1,378 miniuins.dat
07/28/2008  11:02 PM             5,632 miniuins.exe
07/14/2002  04:07 AM             6,986 MoveSound.wav
09/01/2003  04:53 PM             9,216 RemoteThinker.exe
07/23/2008  10:58 AM            48,640 t.exe


Elo is a logarithmic scale. A 2500 Elo program is not twice as strong as a 1250 Elo program. More like 25x stronger.

Thinker is the strongest program per byte, in my opinion.

[Dann Corbit]

If you are looking for Elo per Kilobyte, then I think that Thinker is probably the champion (some people get similar ratios, but they are using executable squeezers).

Why are you saying that? What Elo and what size do you assume? It seems to me that Thinker does not get even close to a good Elo/kbyte.

The smallest version of Thinker 5.2 I could find had an executable of 62KB. PikoSzachy has only 8KB. Thinker does not even have 20% of the Elo/KB that PikoSzachy has. It is in fact questionable if it does even better than Joker (the executable of which is 51KB), and of the intermediateElo engines NanoSzachy 3.4 is slightly stronger than Joker, and has only 31KB.

The difference becomes even more dramatic if you realize that in most compilers, a program that does absolutely nothing ('hello World', without the printf statement...) already measures 3KB for executable, due to linking to the startup file and run-time system. So in terms of the actual Chess code, Thinker lags behind by an order of magnitude.

I think that it does not make sense to divide elo by kbytes because you may get a different order if you add 200 elo to all the programs.

I suggest another test.

do tournaments with unequal time when you give players time that is proportional to the inverse of the size of the exe and see who is the winner.

Let decide that
1 mbyte gets 1 minute per game and it means that 62 kbytes get 1024/62 minute per game when 8 kbyte get 1024/8=128 minutes per game.

Things may be dependent on the hardware but I guess thinker can beat PikoSzachy or Joker on hardwares that people practically use.

Uri

As I demonstrated with upx, Thinker is only twice the size of PikoSzachy. Given half the time per move, Thinker will slaughter PikoSzachy.

Now, PikoSzachy is not a terribly weak program. And it is truly incredible that someone can make a program small enough to run on a toaster IC. But Thinker is an elite program.

You are right that we can use either time or CPU cycles to determine a fair handicap that is linear in scale.

[Dann Corbit]

If you are looking for Elo per Kilobyte, then I think that Thinker is probably the champion (some people get similar ratios, but they are using executable squeezers).

Why are you saying that? What Elo and what size do you assume? It seems to me that Thinker does not get even close to a good Elo/kbyte.

The smallest version of Thinker 5.2 I could find had an executable of 62KB. PikoSzachy has only 8KB. Thinker does not even have 20% of the Elo/KB that PikoSzachy has. It is in fact questionable if it does even better than Joker (the executable of which is 51KB), and of the intermediateElo engines NanoSzachy 3.4 is slightly stronger than Joker, and has only 31KB.

The difference becomes even more dramatic if you realize that in most compilers, a program that does absolutely nothing ('hello World', without the printf statement...) already measures 3KB for executable, due to linking to the startup file and run-time system. So in terms of the actual Chess code, Thinker lags behind by an order of magnitude.

I think that it does not make sense to divide elo by kbytes because you may get a different order if you add 200 elo to all the programs.

I suggest another test.

do tournaments with unequal time when you give players time that is proportional to the inverse of the size of the exe and see who is the winner.

Let decide that
1 mbyte gets 1 minute per game and it means that 62 kbytes get 1024/62 minute per game when 8 kbyte get 1024/8=128 minutes per game.

Things may be dependent on the hardware but I guess thinker can beat PikoSzachy or Joker on hardwares that people practically use.

Uri

As I demonstrated with upx, Thinker is only twice the size of PikoSzachy. Given half the time per move, Thinker will slaughter PikoSzachy.

Now, PikoSzachy is not a terribly weak program. And it is truly incredible that someone can make a program small enough to run on a toaster IC. But Thinker is an elite program.

You are right that we can use either time or CPU cycles to determine a fair handicap that is linear in scale.

Oops. Make that 4 times the size. But 4x time is only 100 Elo handicap.
NanoSzachy is stonger than PicoSzachy, and we have this from Leo's list:
Thinker 5.0m-x64 2824
nanoSzachy 3.1 2338
which is about 500 Elo. That makes Thinker about 10x stronger, considering the rough guestimate of 50 Elo per double of CPU speed.

[Dann Corbit]

I found a list with both engines:
http://www.husvankempen.de/nunn/40_4_Ra ... liste.html
Thinker 5.1c x64 passive 2787 28 28 400 50.9% 2781 33.8%
PikoSzachy 2.2 2194 31 31 394 35.9% 2295 21.6%

Thinker is +593 Elo
That is around 11-12x stronger.

Lance Perkins' engine is a miracle of strength for its size.

[Uri Blass]

I found a list with both engines:
http://www.husvankempen.de/nunn/40_4_Ra ... liste.html
Thinker 5.1c x64 passive 2787 28 28 400 50.9% 2781 33.8%
PikoSzachy 2.2 2194 31 31 394 35.9% 2295 21.6%

Thinker is +593 Elo
That is around 11-12x stronger.

Lance Perkins' engine is a miracle of strength for its size.

This is clearly more than it.
Let say 50 elo better is twice stronger

let define the playing strength of 2200 as 1
We have the following table

2200 1
2250 2
2300 4
2350 8
2400 16
2450 32
2500 64
2550 128
2600 256
2650 512
2700 1024

You can see that being 500 elo better is equivalent to being more than 1000 times stronger.


practically I believe in deminishing returns and you get more than 50 elo per doubling at the low level but it does not change the fact that the gap is bigger than the gap that you suggest.

Uri

[H.G.Muller]

Elo is a logarithmic scale. A 2500 Elo program is not twice as strong as a 1250 Elo program. More like 25x stronger.

Thinker is the strongest program per byte, in my opinion.

It seems to me you abandon your earlier statement with this, and are now claiming that Thinker has the most Elo per log(size). That is an entirely different claim. (Or equivalently, that it has the highest exp(Elo)/kB.)

And it is just as non-sensical. Your claim that a 2500 Elo program is 25x stronger than a 1250 Elo program is totally arbitrary. How do you define that? That they become equaly strong when the stronger program has to face 25-fold time odds? For one, such statements cannot be generally made, as the rating of different programs (especially of very differnet programs) depend differently on time control (usually logarithmically, but with different base log).

So it would already be rather dubious math to apply this kind of reasoning when comparing different programs running on different CPUs (i.e. talking about Elo per MHz, even when it is understood that you mean Elo / log(MHz)).

Applying it to size, however, is completely ridiculous. In a recursive language, expressive power is just as much an exponential function of size as your notion of 'strength' is an exponntial function of Elo. There is no reason at all why a twice bigger program shoud only be twice 'stronger'. It should square the strength. Micro-Max 1.6 is 1433 characters, and has an Elo of about 1200. Micro-Max 4.8 is 1966 characters (a factor 1.64 larger), and it has around 2000 Elo. If you would reduce its search time by a factor 1.64, its Elo would drop 50 points, to 1950, and it would still totally crush uMax 1.6, being still 750 Elo stronger.

So time and size are not interchangeble at all. With more time you can only do more of the same, (brute force), and it hardly helps. With a little bit of extra size you you can make it more smart, and the strength explodes. You can add a small routine that does something useful (say a SEE, or a piece list, better scorng for move sorting to reduce the branching rtio), and call it from many places with almost no size for the calling, making all of your code smarter.

So if you want to weight in Elo exponentially (for which I agree there are good arguments), you should also weight in program size exponentially in the denominator.

[Dann Corbit]

Elo is a logarithmic scale. A 2500 Elo program is not twice as strong as a 1250 Elo program. More like 25x stronger.

Thinker is the strongest program per byte, in my opinion.

It seems to me you abandon your earlier statement with this, and are now claiming that Thinker has the most Elo per log(size). That is an entirely different claim. (Or equivalently, that it has the highest exp(Elo)/kB.)

And it is just as non-sensical. Your claim that a 2500 Elo program is 25x stronger than a 1250 Elo program is totally arbitrary. How do you define that? That they become equaly strong when the stronger program has to face 25-fold time odds? For one, such statements cannot be generally made, as the rating of different programs (especially of very differnet programs) depend differently on time control (usually logarithmically, but with different base log).

So it would already be rather dubious math to apply this kind of reasoning when comparing different programs running on different CPUs (i.e. talking about Elo per MHz, even when it is understood that you mean Elo / log(MHz)).

You are right, Uri has the correct mathematics.

Applying it to size, however, is completely ridiculous. In a recursive language, expressive power is just as much an exponential function of size as your notion of 'strength' is an exponntial function of Elo. There is no reason at all why a twice bigger program shoud only be twice 'stronger'. It should square the strength. Micro-Max 1.6 is 1433 characters, and has an Elo of about 1200. Micro-Max 4.8 is 1966 characters (a factor 1.64 larger), and it has around 2000 Elo. If you would reduce its search time by a factor 1.64, its Elo would drop 50 points, to 1950, and it would still totally crush uMax 1.6, being still 750 Elo stronger.

So time and size are not interchangeble at all. With more time you can only do more of the same, (brute force), and it hardly helps. With a little bit of extra size you you can make it more smart, and the strength explodes. You can add a small routine that does something useful (say a SEE, or a piece list, better scorng for move sorting to reduce the branching rtio), and call it from many places with almost no size for the calling, making all of your code smarter.

So if you want to weight in Elo exponentially (for which I agree there are good arguments), you should also weight in program size exponentially in the denominator.

There is no connection at all between Elo and size. There are huge programs that are weak as a babe and teeny-tiny programs that are awesome tigers.

At any rate, Thinker is (in my opinion and by whatever arbitrary measure I choose) the strongest program for its size.

[H.G.Muller]

Well, a lot of programs are the best program for their size. In fact, probably every program is, as no two sizes are exactly the same. (Clones exempted. )

So no doubt you are right. But without a theoretical framework for size dependence, that would allow us to compare programs of different sizes, this does not mean a thing.

I don't think that the fact that some large programs are weak means there is no relation between size and strength. There are also programs that are weak even in the face of being allowed to think very long, and yet there is a very general relation between thinking time and strength for the same engine. To discover a relation between size and strength, one should also first look to different versions of the same engine, during their development.