Current world's smallest chess program

[biyubi]

Hi, I've recently published my personal web site
at http://nanochess.110mb.com/

It contains my four winning entries from the IOCCC,
and three previously-unreleased chess programs:

o Toledo Nanochess, a chess program in C that
occupies only 1274 non-blank characters, still
being smaller, it beats Micromax v1.6.
o Toledo Picochess, a chess program in C that
fits in 1K of source, but cannot play empassant,
castling or promotion to minor pieces.
o Toledo Javascript Chess, same as Toledo Nanochess
but in Javascript, 2258 bytes.

The three are the current world's smallest chess
programs, of course, until someone does it better.

I'm interested in knowing about any other small
chess programs in C or Javascript, particularly if
them are smaller than mine.

Enjoy it!

Regards,
Oscar Toledo G.

 

[William Hughes]

main(){return puts("(Resigns)"),0;}

(Assumes a pre-C99 implementation. ;-)

This can only play white, as playing black it has
no way of knowing if white's first move was legal.
(you could add a table of the 20 legal first moves,
or something similar to allow it to play black).
Thw question of what qualifies as the "world's smallest
chess program" clearly depends on the definition
of "chess program".

- William Hughes

 

[user923005]

Hi, I've recently published my personal web site
athttp://nanochess.110mb.com/

It contains my four winning entries from the IOCCC,
and three previously-unreleased chess programs:

  o Toledo Nanochess, a chess program in C that
    occupies only 1274 non-blank characters, still
    being smaller, it beats Micromax v1.6.
  o Toledo Picochess, a chess program in C that
    fits in 1K of source, but cannot play empassant,
    castling or promotion to minor pieces.
  o Toledo Javascript Chess, same as Toledo Nanochess
    but in Javascript, 2258 bytes.

The three are the current world's smallest chess
programs, of course, until someone does it better.

I'm interested in knowing about any other small
chess programs in C or Javascript, particularly if
them are smaller than mine.

After running your program through the preprocessor, we get this:


char *l = "ustvrtsuqqqqqqqqyyyyyyyy}{|~z|{}"
" + BAW~abcddcba .pknbrq PKNBRQ\n?A6J57IKJT576,+-48HLSU";
B, i, y, u, b, I[120], G;
main(f, w, c, h, e, S, s)
{
int t,
o,
L,
E,
d,
O = f,
N = -1e9,
p,
*g,
n,
*m = I,
H,
A,
q = 100,
r,
x = 10,
z = 15,
C,
a = y ? -x : x;
if (*I) {
y ^= 8;
d = !s || 1e5 > main(21, 0, 0, 0, 0, 1, 0);
H = G;
do {
;
if (o = I[p = O]) {
q
= o & z ^ y;
if (q < 7) {
A = q-- & 2 ? 8 : 4;
C = o - 9 & z ? q["& .$ "] : 42;
do {
r = I[p += C[l] - 64];
if (!w | p == w && q |
A > 2 | !r) {
g = q | p + a - e ? 0 : I + e;
if (!r & (q | A < 3 || g) | (r + 1 & z ^
y) > 9) {
m = 0;
if (!(r - 2 & 7))
return y ^= 8, G = O, 1e6 - 1e3 *
h;
n = o & z;
t = q | p > 28 & p < 91 ? n + 1 : (n
+= 2, 7 ^ y);
while (n - t) {
p = n, E = O = m ? *g = *m,
*m = 0 : g ? *g = 0 :
0;
L = (1 - q ? l[p / x + 5] - l[O /
x + 5] + l[p % x + 6] - l[O % x + 6] + o / 16 * 8 : !!m * 9) + (!q ? l
[p % x + 6] - 98 + !(I[p - 1] ^ n) + !(I[p + 1] ^ n) + l[n & 7] * 9 -
387 + !!g * 99 + (1 == A && (E = p)) : 0) + (r ? l[r & 7] * 9 - 288 -
h - q : 0)
+ !(I[p - a] & z ^ y ^ 9);
L -= s > h || s == h & (L > z & 1
< s | !d) ? main(H, s > h | !d ? 0 : p, L, h + 1, E, N, s) : 0;
if (!(
B - O | i - n | h | p - b |
S | L < -1e5))
return u = E;
O = o;
p = r;
m ? *m = *g, *g = 0 : g ? *g = 9 ^
y : 0;
if (L > N) {
N = L;
G = O;
if (!h & S && s)
i = n, B = O, b = p;
if (h && c - L < S)
return y ^= 8, L;
}
q == 1 & A > 6 & !m && (g = I + p,
m = p < O ? g - 3 : g + 2, o - y + *m > 32 & !r & !I[p += p - O] & !m
[p < O ? 1 : -1] & !!s & d & L > -1e5) ? 0 : n++;
}
}
}
}
while (!r & q > 2 || (p = O, q | A > 2 | (o & 16
&& !r) && ++C && --A));
}
}
} while (++O > 98 ? O = 20 : f - O);
return y ^= 8, N + 1e9 ? N < -998100 + 1e3 * h & d ? 0 : N :
0;
}
while (B++ < 120)
*m++ = B % x ? B / x % x < 2 | B % x < 2 ? z : B / x & 4 ? 0 :
*l++ & 31 : 7;
while (p = 19) {
while (++p < q)
putchar(l[p | 16]);
if (x - (B = getchar() % 16)) {
i = I[B += q - getchar() % 16 * x] & z;
b = getchar() % 16;
b += q - getchar() % 16 * x;
while (x - (p = getchar() % 16))
i = p ^ 8 ^ y;
} else
p = main(21, 0, 0, 0, u, 1, 5);
main(21, 0, 0, 0, u, 0, 1);
}
}

It isn't a legal C program, despite the fact that some compilers will
compile and execute the code.

 

[The unknown warrior]

Hi, I've recently published my personal web site
at http://nanochess.110mb.com/

It contains my four winning entries from the IOCCC,
and three previously-unreleased chess programs:

o Toledo Nanochess, a chess program in C that
occupies only 1274 non-blank characters, still
being smaller, it beats Micromax v1.6.
o Toledo Picochess, a chess program in C that
fits in 1K of source, but cannot play empassant,
castling or promotion to minor pieces.
o Toledo Javascript Chess, same as Toledo Nanochess
but in Javascript, 2258 bytes.

The three are the current world's smallest chess
programs, of course, until someone does it better.

I'm interested in knowing about any other small
chess programs in C or Javascript, particularly if
them are smaller than mine.

Enjoy it!

Regards,
Oscar Toledo G.

main() {
printf("I resign");
}

 

[Peter Nilsson]

This can only play white, as playing black it has
no way of knowing if white's first move was legal.
(you could add a table of the 20 legal first moves,
or something similar to allow it to play black).
Thw question of what qualifies as the "world's smallest
chess program" clearly depends on the definition
of "chess program".

Indeed. The judging from the code cited elsethread, the
program does not 'play' chess itself, rather it allows
two humans to play chess, restricted to legal moves.
[Although I doubt it handles draw by tripple repitition.]

By that measure, Eric's program is not a Chess program
because it assumes that a game of Chess is simply the
act of White resigning.

There is also issue of 'smallest'. Whilst the OP is
using character count as the measure, I'd use the count
of non white-space tokens after translation phase 3.

 

[Bertrand Mollinier Toublet]

Indeed. The judging from the code cited elsethread, the
program does not 'play' chess itself,

Actually, it does.

 

[James Kuyper]

user923005 wrote:
....

After running your program through the preprocessor, we get this: ....
It isn't a legal C program, despite the fact that some compilers will
compile and execute the code.

It would have been more useful to identify at least one of the ways in
which that code is defective.

The C standard doesn't talk about legal or illegal code. It talks about
"conforming" and "strictly conforming" code, but those categories are
nearly useless: the first because it includes just about anything (the
script for the play "Hamlet", for instance, is conforming C code); the
second because it excludes just about every useful program.

The useful terms that the C standard provides for describing problems
with C code are, roughly in order of increasing seriousness:
"implementation-defined behavior", "unspecified behavior", "constraint
violation", "syntax error", and "undefined behavior". Could you use one
of these terms to describe the worst problem you see in that code?

 

[Antoninus Twink]

o Toledo Nanochess, a chess program in C that occupies only 1274
non-blank characters, still being smaller, it beats Micromax v1.6.

Well, I for one would like to congratulate you on a remarkable
achievement.

Even by the standards of clc, the responses in this thread have been
amazingly churlish. Of course it's no surprise that Heathfield, Sossman
and their ilk couldn't resist jumping in with their saracastic replies,
only ever able to knock other people.

But it is disappointing that even generally sensible people like Dan
Corbet aren't able to see past their fixation with the "correct"
signature of main(), and as a result only see undefined behavior where
any reasonable person would see (and warmly admire) an extraordinarily
ingenious response to a difficult programming challenge.

Sad, very sad.

 

[Harald van Dijk]

Anthony Fremont said:

Richard Heathfield wrote: [...]

Your program lacks ambition. Here is a program of equivalent length,
which has three advantages over your program:

1) it doesn't invoke undefined behaviour;

I don't know about that, but your example didn't return an int, nor did
it
#include <stdio.h>. Shouldn't it?

Good observations, but I intend to weasel them away anyway. We can get
away without stdio.h, I think, because puts returns an int, which is
what the compiler will assume in the absence of a dec. [...]

The implicit declaration of puts is valid, but it gives puts type int(),
not int(const char *), so there will be no automatic conversion if the
argument doesn't have the proper type. Your argument doesn't. It has type
char *. This is very likely to work, but strictly speaking it's not valid
C90.

And it's a bad idea to rely on implicit function declarations for other
reasons anyway, of course.

 

[Keith Thompson]

Good observations, but I intend to weasel them away anyway. We can
get away without stdio.h, I think, because puts returns an int,
which is what the compiler will assume in the absence of a dec.

laration

In C90, not in C99.

Furthermore, although the /return status/ of the program is
undefined because of the absence of a return value, the behaviour
of the program itself is not.

In C99, not in C90 (in C99, falling off the end of main does an
implicit "return 0;").

[...]

 

[user923005]

user923005 wrote:

...


It would have been more useful to identify at least one of the ways in
which that code is defective.

The C standard doesn't talk about legal or illegal code. It talks about
"conforming" and "strictly conforming" code, but those categories are
nearly useless: the first because it includes just about anything (the
script for the play "Hamlet", for instance, is conforming C code); the
second because it excludes just about every useful program.

The useful terms that the C standard provides for describing problems
with C code are, roughly in order of increasing seriousness:
"implementation-defined behavior", "unspecified behavior", "constraint
violation",  "syntax error", and "undefined behavior". Could you use one
of these terms to describe the worst problem you see in that code?

main(f, w, c, h, e, S, s)

 

[user923005]

Well, I for one would like to congratulate you on a remarkable
achievement.

Even by the standards of clc, the responses in this thread have been
amazingly churlish. Of course it's no surprise that Heathfield, Sossman
and their ilk couldn't resist jumping in with their saracastic replies,
only ever able to knock other people.

But it is disappointing that even generally sensible people like Dan
Corbet aren't able to see past their fixation with the "correct"
signature of main(), and as a result only see undefined behavior where
any reasonable person would see (and warmly admire) an extraordinarily
ingenious response to a difficult programming challenge.

Sad, very sad.

This is called a straw man, because I never said any of those things.
Unless there is someone with a name that sounds similar to mine, named
'Dan Corbet' who did say them.

 

[jameskuyper]

main(f, w, c, h, e, S, s)

Yes, I see a problem - probably the same one you do - but would it
cost you so much effort to add some words saying what the problem is?
Anybody likely to actually perpetrate such code is unlikely to be
aware of the fact that it is defective. It may even do what they
expect it to do on the system where they're using it.

This particular problem is merely a portability issue; there are two
ways of defining main() that an implementation is required to accept,
but it is implementation-defined whether or not an implementation
supports other ways of defining it. This code can only be used on a
C90 implementation that supports a version of main() that takes 7 int
arguments. I'm not aware of any such implementation, but if one does
exist it could be fully conforming.

 

[user923005]

Yes, I see a problem - probably the same one you do - but would it
cost you so much effort to add some words saying what the problem is?

I guess I thought it was obvious.

Anybody likely to actually perpetrate such code is unlikely to be
aware of the fact that it is defective. It may even do what they
expect it to do on the system where they're using it.

This particular problem is merely a portability issue; there are two
ways of defining main() that an implementation is required to accept,
but it is implementation-defined whether or not an implementation
supports other ways of defining it. This code can only be used on a
C90 implementation that supports a version of main() that takes 7 int
arguments. I'm not aware of any such implementation, but if one does
exist it could be fully conforming.

I would argue that this is not a C program on any system that lacks
the special compiler which accepts 7 int arguments.
Further, I guess that there is no such compiler anywhere in the world
and his program works by accident.
It's not hard to repair, of course (just declare m
(int,int,int,int,int,int,int) and call that from main()).

I do recognize the difficulty of writing a chess program in general,
and a tiny one in particular.
I also appreciate the aesthetics of IOCCC entries.

 

[user923005]

[...]> Good observations, but I intend to weasel them away anyway. We can

get away without stdio.h, I think, because puts returns an int,
which is what the compiler will assume in the absence of a dec.

laration

In C90, not in C99.

Furthermore, although the /return status/ of the program is
undefined because of the absence of a return value, the behaviour
of the program itself is not.

In C99, not in C90 (in C99, falling off the end of main does an
implicit "return 0;").

[...]

Of course, if the code is assumed to be C99 compliant we have this
difficulty:

From WG14/N1256 Committee Draft — Septermber 7, 2007 ISO/IEC 9899:TC3,
xii Foreword

"5 This second edition cancels and replaces the first edition, ISO/IEC
9899:1990, as amended and corrected by ISO/IEC 9899/COR1:1994, ISO/IEC
9899/AMD1:1995, and ISO/IEC 9899/COR2:1996. Major changes from the
previous edition include:
[snip]
— remove implicit int
[snip]
— remove implicit function declaration"

 

[Keith Thompson]

user923005 wrote: [...]

main(f, w, c, h, e, S, s)

[...]

This particular problem is merely a portability issue; there are two
ways of defining main() that an implementation is required to accept,
but it is implementation-defined whether or not an implementation
supports other ways of defining it. This code can only be used on a
C90 implementation that supports a version of main() that takes 7 int
arguments. I'm not aware of any such implementation, but if one does
exist it could be fully conforming.

It depends on what you mean by "supports" and/or "accepts". I doubt
that any real-world C compiler actually documents that it accepts a
form of main that takes 7 int arguments, but the compilers I've used
don't actually check. I compiled and ran a small program with the
above declaration for main. It compiled without complaint, and the 7
parameters appeared to contain the values of argc, argc, envp (the
last two reinterpreted as int values) and four ints worth of
unidentified garbage.

 

[The unknown warrior]

Hi, I've recently published my personal web site
at http://nanochess.110mb.com/

I'd like to look at your program, but am I the only find to find the
pictures which move over the screen (probably javascript) *really*
annoying.

From what I can gather, you must be a pretty decent C programmer if you
can write a real chess program in 1274 characters, but your web design
skills leave a lot to be desired. People generally want to get at the
content that interests them, and not have to fight the browser to hide
things that are forced upon them.

Perhaps you can post the C source here. I'll compile it on my Sun
workstation (SPARC based) and on my laptop (running Solaris x86). I'll
let you know what happens. (I have both gcc and Sun's Studio Compiler
Suite). But I cant be bothered to fight a web sight that pushes pictures
down my throat the way your site does.

 

[user923005]

I'd like to look at your program, but am I the only find to find the
pictures which move over the screen (probably javascript) *really*
annoying.

 From what I can gather, you must be a pretty decent C programmer if you
can write a real chess program in 1274 characters, but your web design
skills leave a lot to be desired. People generally want to get at the
content that interests them, and not have to fight the browser to hide
things that are forced upon them.

Perhaps you can post the C source here. I'll compile it on my Sun
workstation (SPARC based) and on my laptop (running Solaris x86). I'll
let you know what happens. (I have both gcc and Sun's Studio Compiler
Suite). But I cant be bothered to fight a web sight that pushes pictures
down my throat the way your site does.

It plays against itself, in a game only a computer could love.
For instance, here is one of his nesting places:
r1b1k1nr/pp2nppp/2p5/q2PP3/4P3/2N5/PP3KPP/R1BQ1BNR w kq -

#include <stdio.h>
char *l = "ustvrtsuqqqqqqqqyyyyyyyy}{|~z|{}"
" + BAW~abcddcba .pknbrq PKNBRQ\n?A6J57IKJT576,+-48HLSU";
int B, i, y, u, b, I[120], G;
int M(int f, int w, int c, int h, int e, int S, int s)
{
int t,
o,
L,
E,
d,
O = f,
N = -1e9,
p,
*g,
n,
*m = I,
H,
A,
q = 100,
r,
x = 10,
z = 15,
C,
a = y ? -x : x;
if (*I) {
y ^= 8;
d = !s || 1e5 > M(21, 0, 0, 0, 0, 1, 0);
H = G;
do {
;
if (o = I[p = O]) {
q = o & z ^ y;
if (q < 7) {
A = q-- & 2 ? 8 : 4;
C = o - 9 & z ? q["& .$ "] : 42;
do {
r = I[p += C[l] - 64];
if (!w | p == w && q |
A > 2 | !r) {
g = q | p + a - e ? 0 : I + e;
if (!r & (q | A < 3 || g) | (r + 1 & z ^
y) > 9) {
m = 0;
if (!(r - 2 & 7))
return y ^= 8, G = O, 1e6 - 1e3 *
h;
n = o & z;
t = q | p > 28 & p < 91 ? n + 1 : (n
+= 2, 7 ^ y);
while (n - t) {
p = n, E = O = m ? *g = *m,
*m = 0 : g ? *g = 0 : 0;
L = (1 - q ? l[p / x + 5] - l[O /
x + 5] + l[p % x + 6] - l[O % x + 6] + o / 16 * 8 : !!m * 9) + (!q ? l
[p % x + 6] - 98 + !(I[p - 1] ^ n) + !(I[p + 1] ^ n) + l[n & 7] * 9 -
387 + !!g * 99 + (1 == A && (E = p)) : 0) + (r ? l[r & 7] * 9 - 288 -
h - q : 0) + !(I[p - a] & z ^ y ^ 9);
L -= s > h || s == h & (L > z & 1
< s | !d) ? M(H, s > h | !d ? 0 : p, L, h + 1, E, N, s) : 0;
if (!(B - O | i - n | h | p - b |
S | L < -1e5))
return u = E;
O = o;
p = r;
m ? *m = *g, *g = 0 : g ? *g = 9 ^
y : 0;
if (L > N) {
N = L;
G = O;
if (!h & S && s)
i = n, B = O, b = p;
if (h && c - L < S)
return y ^= 8, L;
}
q == 1 & A > 6 & !m && (g = I + p,
m = p < O ? g - 3 : g + 2, o - y + *m > 32 & !r & !I[p += p - O] & !m
[p < O ? 1 : -1] & !!s & d & L > -1e5) ? 0 : n++;
}
}
}
} while (!r & q > 2 || (p = O, q | A > 2 | (o & 16
&& !r) && ++C && --A));
}
}
} while (++O > 98 ? O = 20 : f - O);
return y ^= 8, N + 1e9 ? N < -998100 + 1e3 * h & d ? 0 : N :
0;
} while (B++ < 120)
*m++ = B % x ? B / x % x < 2 | B % x < 2 ? z : B / x & 4 ? 0 :
*l++ & 31 : 7;
while (p = 19) {
while (++p < q)
putchar(l[p | 16]);
if (x - (B = getchar() % 16)) {
i = I[B += q - getchar() % 16 * x] & z;
b = getchar() % 16;
b += q - getchar() % 16 * x;
while (x - (p = getchar() % 16))
i = p ^ 8 ^ y;
} else
p = M(21, 0, 0, 0, u, 1, 5);
M(21, 0, 0, 0, u, 0, 1);
}
return 0;
}
int main(void)
{
/* The board I[] is uninitialized: */
return M(0,0,0,0,0,0,0);
}

 

[Keith Thompson]

Keith Thompson said:

It is clear, however, from the original (on which my code was based)
that C90 is being used (main() rather than int main()).

Agreed, but I thought it was worth pointing out anyway.

Um, wrong. I mean, yes, what you say about C99 is correct - but what
I said about C89 is nevertheless correct. C&V: 2.1.2.2: "If the
main function executes a return that specifies no value, the
termination status returned to the host environment is undefined."

Note: the program's behaviour is /not/ undefined because of "falling
off" main. Only the termination status is undefined, as I pointed
out earlier.

Whoops, I meant to write "In C90, not in C99 ...", the point being
that in C99 the program's behavior and return value are both
well-defined (ignoring other issues). With that correction I think
we're in agreement.

[...]

 

[Harald van Dijk]

I might as well deal here with Harald's point about puts():

I will include my point about puts here:

>> Anthony Fremont said:

>>> Richard Heathfield wrote: > [...]
>>>> Your program lacks ambition. Here is a program of equivalent
>>>> length, which has three advantages over your program:
>>>>
>>>> 1) it doesn't invoke undefined behaviour;
>>>
>>> I don't know about that, but your example didn't return an int, nor
>>> did it
>>> #include <stdio.h>. Shouldn't it?

>>
>> Good observations, but I intend to weasel them away anyway. We can
>> get away without stdio.h, I think, because puts returns an int, which
>> is what the compiler will assume in the absence of a dec. > [...]

>>>> main() {
>>>> puts("YOU resign");
>>>> }

>
> The implicit declaration of puts is valid, but it gives puts type
> int(), not int(const char *), so there will be no automatic conversion
> if the argument doesn't have the proper type. Your argument doesn't.
> It has type char *. This is very likely to work, but strictly speaking
> it's not valid C90.
>
> And it's a bad idea to rely on implicit function declarations for
> other reasons anyway, of course.

[snip explanation that arguments and parameters have to match]
The number of arguments agrees. The type of a string literal is
certainly compatible with const char * (because otherwise you couldn't,
say, send "foo" to strlen()).

You can send "foo" to strlen() because there is an implicit conversion
from char * (the type of the string literal after array-to-pointer
conversion) to const char *.

So I'm not sure on what grounds Harald bases his complaint.

The fact that const char * and char * are not compatible. Compatible in C
does not mean implicitly convertible, it means roughly they can be the
same type.

This is valid:

extern int a[];
extern int a[3];

because int[] and int[3] are compatible.

This is invalid:

extern const char *p;
extern char *p;

because const char * and char * are not compatible.

What happens if you calculate sqrt(2)? If a function prototype is in
scope, 2 is implicitly converted from int to double. If a function
prototype is not in scope, the type of the argument does not match the
type of the parameter, so the behaviour is undefined.

What happens if you call puts("YOU resign")? If a function prototype is in
scope, "YOU resign" is implicitly converted from char * to const char *.
If a function prototype is not in scope, the type of the argument does not
match the type of the parameter, so the behaviour is undefined.

Do you believe that sqrt(2) is valid, if sqrt is declared as
double sqrt(); ? If not, in what ways does it significantly differ from
your example?