World smallest chess program

[james of tucson]

IIRC, the ZX-81 chess program didn't allow en passant and/or castling
and/or underpromotion, so can't really be called `legal chess'.

The 1978 Sargon I that, I believe, the ZX-81 chess was based on,
supported E-P and castling. You could implement Sargon I in 8K RAM.
It was not *that* bad. You could beat it easily in the opening of
course, and alpha-beta pruning doesn't really work for endgames, but its
tactics are not all that bad. I believe that in 1980, a Sargon-I on a
Z-80 microcomputer had a rating in the 1600's. I suspect it was the
basis for some of the purpose-built chess computers of the day.

Sargon does a pretty good job of pruning loss-lines, provided they are
evaluated as losses early enough. It is a very good example of
Alpha-Beta pruning, and does what I would call a magnificent job of
pushing the limits of a small memory space for evaluating board
positions. I mean, GNUChess does essentially the same thing (I know PVS
is more than just an optimization of Alpha-Beta, but it's still
essentially the same approach to evaluation).

I've seen smarter guys than myself be beaten time and time again by
GNUChess. Also, I suspect that there are problem setups you could feed
to Sargon that would allow its tactics to play quite strongly, even on a
16K machine.

I'm not seriously trying to compare Sargon I to a computer chess program
that can be configured with hundreds of megabytes of opening book,
complete solutions for 5-piece endgames, and that can exploit
multi-gigahertz processors and gigabytes of ram for tactical evaluation.
But I still say that Sargon and its variants might surprise you. Yeah,
you can beat it every time -- but if you refrain from confusing it in
the opening, you may find it quite surprisingly "strong" in midgame
tactics.

I'm no chess champion, by any means (I play in the 1400's), and I only
dabble in game programming, so don't contribute to the conversation by
tearing my analysis to shreds. I'd actually like to read on this topic
from people who have implement a-b on a board game, for instance.

 

[dcorbit]

IIRC, the ZX-81 chess program didn't allow en passant and/or castling
and/or underpromotion, so can't really be called `legal chess'.


Dave.

Rybka, the strongest chess engine in the world, ignores some
underpromotions (at one point it ignored all of them).
Is it therefore not a chess program?

Similarly, the chess program Junior won the world championship without
performing underpromotions -- even when an underpromotion is the best
move.
Is Junior therefore not a chess program?

Both of these programs are sold commercially and even used by chess
experts to analyze games.

My two line chess program obeys the FIDE rules of chess and is
therefore a complete and working chess program.
It loses every game, but that is beside the point.

 

[dcorbit]

Rybka, the strongest chess engine in the world, ignores some
underpromotions (at one point it ignored all of them).
Is it therefore not a chess program?

Similarly, the chess program Junior won the world championship without
performing underpromotions -- even when an underpromotion is the best
move.
Is Junior therefore not a chess program?

Both of these programs are sold commercially and even used by chess
experts to analyze games.

My two line chess program obeys the FIDE rules of chess and is
therefore a complete and working chess program.
It loses every game, but that is beside the point.

From:
http://www.chessvariants.com/fidelaws.html
We have this:
"Article 10: The Completed Game
10.1
The game is won by the player who has checkmated his opponent's king.
This immediately ends the game.
10.2
The game is won by the player whose opponent declares he resigns. This
immediately ends the game.
...."

From article 10.2, it is very clear that:

#include <stdio.h>
int main(void){puts("I resign");return 0}
is a legal chess program. It also works fine for thematic tournaments.

 

[Guy Macon]

10.2
The game is won by the player whose opponent declares he resigns. This
immediately ends the game.
..."

#include <stdio.h>
int main(void){puts("I resign");return 0}
is a legal chess program. It also works fine for thematic tournaments.

Legal, but far from small. stdio.h is *huge*.

 

[Richard Heathfield]

Legal, but far from small. stdio.h is *huge*.

puts(const char *);main(){puts("I resign");return 0;}

 

[Guy Macon]

puts(const char *);main(){puts("I resign");return 0;}

Now *that's* what I call a small chess-playing program! <grin>

And, as an added bonus, it wins against my computer as often
as I do...

 

[Richard Bos]

Rybka, the strongest chess engine in the world, ignores some
underpromotions (at one point it ignored all of them).
Is it therefore not a chess program?

If it allows you to under-promote, but does not choose to do so itself,
that's legal.

Richard

 

[jaapsch]

Was that a derivative of Sargon?

No it wasn't actually. The 1K zx81 chess program used no look ahead (or
rather just 1-ply). Iit just evaluated a score for each of its
available moves.

Since the screen contents also were stored in that 1k memory, this
program cleverly didn't have any code to draw the board. You had to
reload the program from tape to play another game. It also used that
screen memory directly for its board representation, i.e. it did not
have any other copy of the board contents in memory.

It was fun to completely disassemble it to see how it worked.

There were versions of Sargon as early
as 1978. Sargon is actually not that difficult to digest. I read the
book in 1980, and actually considered implementing a version.

I still have that book, full of pencil annotations. I also wanted to
implement it, but as an 11-year-old that was a daunting task that I
never got around to. It taught me a lot though.

 

[David Richerby]

IIRC, the ZX-81 chess program didn't allow en passant and/or
castling and/or underpromotion, so can't really be called `legal
chess'.

I see now that there was more than one commercially available chess
program for the ZX81. At least one of these implemented all legal
moves but it is implied in

http://www.sincuser.f9.co.uk/016/mindgms.htm

that this required 16KB RAM. I infer this because the article then
goes on to say,

``Artic also produces a technically-excellent game which fits into
the 1K ZX-81. It may not play brilliantly but it is fascinating to
watch the computer scan the moves available to it graphically on
the screen. The computer makes moves very quickly, although it
will not allow the usual en passant and castling which are
available on the bigger games. The game loads very quickly and at
GBP2.95 it is worth the money.''

I suspect that this is the program I was thinking of.


Dave.

 

[David Richerby]

If it allows you to under-promote, but does not choose to do so
itself, that's legal.

Exactly. (Sorry for the `me too' but the question was kind of
directed at me.)


Dave.

 

[CBFalconer]

Legal, but far from small. stdio.h is *huge*.

But puts is not. The remainder is a linking problem, and OT.

 

[h.g.muller]

max schreef:

No idea how small micro-Max is, but back in the 1980s there was a chess
program that fitted within the 1K ZX-81 memory - Z80 machine code, but
making use of the 16K ZX-81 ROM, for IO. Apparently it played legal but bad
chess.

One should distingush the sizes of the source code, the executable and
the memory size used including data. The 1KB ZX81 program was a real
achievement, since the 1KB had to hold both the program code and the
data. I am not sure if it was written (entirely) in assembler, though,
because I seem to recall that the ZX-81 had a BASIC interpreter in ROM,
so the program could also have been encoded BASIC instructions (which
could do more per byte than Z80 machine instructions).

In those days I had written a 2KB chess program (code + data) for the
6800 micro-processor, called Usurpator I. The micro-Max project was
actually inspired by the question if I could rival such code density in
a high-level language. The source of such assembly programs was much
larger, of course, since a single-byte assembly instruction typically
took 5 characters to write down. On the other hand, micro-Max is very
memory-hungry for data: in just a few characters you can declare an
array of hundreds of megabytes (int A[1<<26], and this is exactly
what micro-Max does. So in that sense the comparison is not fair.

Dan and I simply disagree about whether resigning should count as
playing Chess. In my opinion playing Chess is what you do *before* you
resign. That the FIDE rules stipulate that you are allowed to stop
playing Chess any time you like during a game (by resigning) does not
convince me that the stopping itself is part of the game. I would
reserve the term Chess program for a program that can play a game of
Chess to the very end without resigning.

 

[dcorbit]

Exactly. (Sorry for the `me too' but the question was kind of
directed at me.)

How is it differnt than a program that resigns (plays fully under the
FIDE rules of chess)?
It also is simply not exercising every possible rule of the game. In
both cases the programs are simply choosing not to perform some of the
alternatives that are available to them.

If you fail to see the full correspondence between these two
situations, then I am at a loss as to how to make it clear.

Another even shorter alternative is:

int main(void) (while(1);return 0;}

This program always loses the game on time.

 

[David Richerby]

Dan and I simply disagree about whether resigning should count as
playing Chess. In my opinion playing Chess is what you do *before*
you resign. That the FIDE rules stipulate that you are allowed to
stop playing Chess any time you like during a game (by resigning)
does not convince me that the stopping itself is part of the game. I
would reserve the term Chess program for a program that can play a
game of Chess to the very end without resigning.

In that case,

int main() {while (1);}

is a chess program: it will lose every game on time. I think the best
way to proceed is to use the term `non-trivial chess program'.


Dave.

 

[David Richerby]

How is it differnt than a program that resigns (plays fully under the
FIDE rules of chess)?
It also is simply not exercising every possible rule of the game. In
both cases the programs are simply choosing not to perform some of the
alternatives that are available to them.

As far as I can see, we're in complete agreement! My objection to the
ZX-81 program was that not allow its opponent to castle, capture en
passant or underpromote. If a program wishes to avoid making certain
types of moves itself or to resign without even considering the
position, that's perfectly within its prerogative.

If you fail to see the full correspondence between these two
situations, then I am at a loss as to how to make it clear.

Another even shorter alternative is:

int main(void) (while(1);return 0;}

This program always loses the game on time.

Indeed -- as I posted myself earlier. (This is not a criticism of you
for posting the same program; just an observation that I was already
aware of this idea.)


Dave.

 

[CBFalconer]

But puts is not. The remainder is a linking problem, and OT.

In fact, to elaborate, the following is a satisfactory puts:

int puts(char *s) {
int err;

while (*s && (EOF != (err = putchar(*s++)))) continue;
if (err > 0) err = putchar('\n');
return err;
}

For many non-hosted systems, it suffices to code putchar(), which
will usually reduce to a half-dozen lines of assembly at worst.

 

[h.g.muller]

If you fail to see the full correspondence between these two

situations, then I am at a loss as to how to make it clear.

There is nothing to make clear. We just don't agree on the definition
of Chess.

In my view the rules of Chess are a subset of the FIDE rules. There are
other FIDE rules that prescribe how participants in events organized by
FIDE should behave. These FIDE rules have nothing to do with Chess. The
Dutch Bridge Society has rules for when Bridge players can smoke during
a Bridge game. That dosn't mean that smoking a cigarete is playing
Bridge.

FIDE rules about offering draws, resigning, and other player
interactions that can determine the entry that goes in the score table
of a tournament by negociation without playing, have nothing to do with
Chess. FIDE rules allow you to participate in a FIDE tournament without
playing Chess.

Resigning is *not* a Chess move, it is merely exercising your right to
stop playing Chess. At any turn someone playing a Chess game has the
choice to play (a move) or to resign or forfeit on time (= not play).
Not playing does not violate FIDE rules. But that does not make not
playing playing Chess.

 

[james of tucson]

How is it differnt than a program that resigns (plays fully under the
FIDE rules of chess)?
It also is simply not exercising every possible rule of the game.

The difference is, a reasonable person will call you an idiot for making
that program, whereas a program that makes some attempt at actually
playing, might garner some respect.

If you honestly do not see the difference between, say, a one-statement
program that "just resigns", versus say, a one-liner that actually
*plays chess*, 100% completely or otherwise, you have a perception
problem, or you are merely being a clown.

 

[Ben Pfaff]

For many non-hosted systems, it suffices to code putchar(), which
will usually reduce to a half-dozen lines of assembly at worst.

However: the putchar and puts functions are in the hosted
library, which freestanding implementations don't have to support
at all.

 

[CBFalconer]

The difference is, a reasonable person will call you an idiot for
making that program, whereas a program that makes some attempt at
actually playing, might garner some respect.

If you honestly do not see the difference between, say, a
one-statement program that "just resigns", versus say, a one-liner
that actually *plays chess*, 100% completely or otherwise, you have
a perception problem, or you are merely being a clown.

Allright. Using the principal of successive refinement:

#include <stdio.h>

int turn;

int main(void)
{
do {
if (!turn++) puts("1: P-K4");
else {
puts("I resign");
return 0;
}
} while (1);
} /* main, fully tested */

Note that it works when playing either white or black. The
next refinement is to get the players move, which will upset the
above universality. Algebraic notation will also upset that.

Ignore any compiler warnings about failure to return a value. The
compiler is confused.

In seriousness, is there an available system for playing postal
chess, which avoids the temptation of letting the program analyze?