Page 1 of 6

Current world's smallest chess program

Posted: Fri Feb 20, 2009 5:07 pm
by nanochess
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:
  • Toledo Nanochess, a chess program in C that occupies only 1274 non-blank characters, still being smaller, it beats Micromax v1.6.
    Toledo Picochess, a chess program in C that fits in 1K of source, but cannot play empassant, castling or promotion to minor pieces.
    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!

Re: Current world's smallest chess program

Posted: Fri Feb 20, 2009 5:36 pm
by hgm
Congratulations!

Seems I've got work to do... :wink:

One question: what are your exact rules for counting characters? I noticed that the IOCCC rules are a bit strange, not countng { } and ; at the end of a line. I always count all characters that cannot be deleted without wrecking the program. E.g., when the program contains the statement goto L; I do count the space between goto and L, as it canot be deleted without causing an error message for the undeclared identifier gotoL.

Re: Current world's smallest chess program

Posted: Fri Feb 20, 2009 8:52 pm
by Bill Rogers
I logged onto his site but found that the source is not avaliable for downloading. I would love to see his Jave script source.
As most of you know I do not program in either "c" or "javescript", I only program in "Basic'. I do own the worlds smallest chess program written in Basic. It was not written by me but as a collector I came across it legally.
The enire program in only 4k long.
Bill

Re: Current world's smallest chess program

Posted: Fri Feb 20, 2009 10:47 pm
by Dann Corbit
Strictly speaking, his program is not a legal C program because it does not use one of the variants of main() that are allowed by the language.

Here is the program de-obfuscated:

Code: Select all

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 &#40;q < 7&#41; &#123;
                    A = q-- & 2 ? 8 &#58; 4;
                    C = o - 9 & z ? q&#91;"& .$  "&#93; &#58; 42;
                    do &#123;
                        r = I&#91;p += C&#91;l&#93; - 64&#93;;
                        if (!w | p == w && q |
                            A > 2 | !r&#41; &#123;
                            g = q | p + a - e ? 0 &#58; I + e;
                            if (!r & &#40;q | A < 3 || g&#41; | &#40;r + 1 & z ^ y&#41; > 9&#41; &#123;
                                m = 0;
                                if (!&#40;r - 2 & 7&#41;)
                                    return y ^= 8, G = O, 1e6 - 1e3 * h;
                                n = o & z;
                                t = q | p > 28 & p < 91 ? n + 1 &#58; &#40;n += 2, 7 ^ y&#41;;
                                while &#40;n - t&#41; &#123;
                                    p&#91;I&#93; = n, E = O&#91;I&#93; = m ? *g = *m, *m = 0 &#58; g ? *g = 0 &#58; 0;
                                    L = &#40;1 - q ? l&#91;p / x + 5&#93; - l&#91;O / x + 5&#93; + l&#91;p % x + 6&#93; - l&#91;O % x + 6&#93; + o / 16 * 8 &#58; !!m * 9&#41; + (!q ? l&#91;p % x + 6&#93; - 98 + !&#40;I&#91;p - 1&#93; ^ n&#41; + !&#40;I&#91;p + 1&#93; ^ n&#41; + l&#91;n & 7&#93; * 9 - 387 + !!g * 99 + &#40;1 == A && &#40;E = p&#41;) &#58; 0&#41; + &#40;r ? l&#91;r & 7&#93; * 9 - 288 - h - q &#58; 0&#41; + !&#40;I&#91;p - a&#93; & z ^ y ^ 9&#41;;
                                    L -= s > h || s == h & &#40;L > z & 1 < s | !d&#41; ? main&#40;H, s > h | !d ? 0 &#58; p, L, h + 1, E, N, s&#41; &#58; 0;
                                    if (!&#40;B - O | i - n | h | p - b | S | L < -1e5&#41;)
                                        return u = E;
                                    O&#91;I&#93; = o;
                                    p&#91;I&#93; = r;
                                    m ? *m = *g, *g = 0 &#58; g ? *g = 9 ^ y &#58; 0;
                                    if &#40;L > N&#41; &#123;
                                        N = L;
                                        G = O;
                                        if (!h & S && s&#41;
                                            i = n, B = O, b = p;
                                        if &#40;h && c - L < S&#41;
                                            return y ^= 8, L;
                                    &#125;
                                    q == 1 & A > 6 & !m && &#40;g = I + p, m = p < O ? g - 3 &#58; g + 2, o - y + *m > 32 & !r & !I&#91;p += p - O&#93; & !m&#91;p < O ? 1 &#58; -1&#93; & !!s & d & L > -1e5&#41; ? 0 &#58; n++;
                                &#125;
                            &#125;
                        &#125;
                    &#125;
                    while (!r & q > 2 || &#40;p = O, q | A > 2 | &#40;o & 16 && !r&#41; && ++C && --A&#41;);
                &#125;
            &#125;
        &#125; while (++O > 98 ? O = 20 &#58; f - O&#41;;
        return y ^= 8, N + 1e9 ? N < -998100 + 1e3 * h & d ? 0 &#58; N &#58; 0;
    &#125; while &#40;B++ < 120&#41;
        *m++ = B % x ? B / x % x < 2 | B % x < 2 ? z &#58; B / x & 4 ? 0 &#58; *l++ & 31 &#58; 7;
    while &#40;p = 19&#41; &#123;
        while (++p < q&#41;
            putchar&#40;l&#91;p&#91;I&#93; | 16&#93;);
        if &#40;x - &#40;B = getchar&#40;) % 16&#41;) &#123;
            i = I&#91;B += q - getchar&#40;) % 16 * x&#93; & z;
            b = getchar&#40;) % 16;
            b += q - getchar&#40;) % 16 * x;
            while &#40;x - &#40;p = getchar&#40;) % 16&#41;)
                i = p ^ 8 ^ y;
        &#125; else
            p = main&#40;21, 0, 0, 0, u, 1, 5&#41;;
        main&#40;21, 0, 0, 0, u, 0, 1&#41;;
    &#125;
&#125;

Re: Current world's smallest chess program

Posted: Fri Feb 20, 2009 11:12 pm
by sje
Back in its youthful and productive years (late 1970s), Byte magazine had an APL themed issue. One of the sample programs was a chessplayer written in APL and I believe it had under a thousand characters of source.

Jennings' original Microchess for the 6502 had only about a 1 KB memory footprint including variable storage.

However, to be called a chess program, an application should also know all the rules (castlings, en passant, all promotions, repetition, etc.) and to be able to play either color.

Re: Current world's smallest chess program

Posted: Fri Feb 20, 2009 11:14 pm
by hgm
It seems there is something wrong with this toledo_nanochess. When I run it to play a game against uMax, I see in the task manager that its memory usage blows up indefinitely. When it reaches 256MB it suddenly jumps back to ~17MB, but this is most likely because my OS decides to swap most of it out: suddenly the disk becomes very active, and the entire system becomes suddenly extremely sluggish. Only killing the toledo process (with great difficulty) cures the system.

Re: Current world's smallest chess program

Posted: Fri Feb 20, 2009 11:31 pm
by hgm
Btw, I write a Max2WB adapter to be able to play the stand-alone versions of uMax and Toledo_Nanochess under WinBoard! This is possible, because they essentially use the same protocol now (producing a move when you enter an empty line, and relaying it by printing a new board.)

The only catch is that to make it work, the engine should not buffer its output. So in the Toledo sprogram I had to replace the putchar(l[...]); by write(1,l+(...),1); to achieve that. (That is 3 extra characters.) In uMax 1.6 I added an fflush(stdout); for now.

This makes them play automatically under Windows+Cygwin (and I guess also under Linux), but the adapter is dependent on the cygwin1.dll. To use the adapter, start WB with

-fcp "./Max2WB ./uMax1_6" -scp "./Max2WB ./Toledo"

This works, but, as I said, after some 15 moves Toledo crashes my system. (Of course they ignore the WinBoard TC settings; be sure to play without auto flag.)

Code: Select all

/**************************************************/
/*     Minimal Max2QH adapter by H.G. Muller      */
/**************************************************/

#include <stdio.h>
#include <signal.h>

char before&#91;80&#93;, after&#91;80&#93;;
FILE *f;

void ReadBoard&#40;int inp, char *board&#41;
&#123;       // read 64 non-blank characters
        int i;
        char c, *oldBoard = board;

        for&#40;i=0; i<64; i++) &#123;
            do&#123; read&#40;inp, &c, 1&#41;;
            &#125; while&#40;c == '\n' || c == ' ' || c == '\t' || c == '\r');
            *board++ = c;
        &#125;
        fprintf&#40;f, "E< '%s'\n", oldBoard&#41;; fflush&#40;f&#41;;
&#125;

void ProduceMove&#40;int from, int to&#41;
&#123;
        int ifrom=-1, ito=-1, i;
        write&#40;to, "\n", 1&#41;;      // send thinking command &#40;empty line&#41;
        ReadBoard&#40;from, after&#41;;  // should respond with board;
        for&#40;i=0; i<64; i++) &#123;
            if&#40;before&#91;i&#93; == after&#91;i&#93;) continue;
            if&#40;after&#91;i&#93; == '.') &#123;
                // from-square
                if&#40;ifrom <= 0 || ifrom == 7 || ifrom == 070 || ifrom == 077&#41;
                     ifrom = i;  // first one, or overwrite corner Rook
                else if&#40;ifrom != 4 && ifrom != 074&#41;
                     ifrom = 65; // must be e.p.
            &#125; else &#123;
                // if not empty after move, must be to-square
                if&#40;ito < 0 || ito != 4 && ito != 074&#41;
                     ito = i; // first one, or write King over Rook
            &#125;
            if&#40;ifrom == 65&#41; ifrom = ito ^ 010;
        &#125;
        printf&#40;"move %c%c%c%c\n", 'a'+&#40;ifrom&7&#41;, '8'-&#40;ifrom>>3&#41;,
                                  'a'+&#40;ito&7&#41;,   '8'-&#40;ito>>3&#41;);
        fflush&#40;stdout&#41;;
&#125;

main&#40;int argc, char **argv&#41;
&#123;
        int toPipe&#91;2&#93;, fromPipe&#91;2&#93;, from_prog, to_prog, pid, pid2, i, j;
        char c, buf&#91;256&#93;, command&#91;256&#93;, *name;

        if&#40;argc < 2&#41;
            exit&#40;0&#41;;   // first arg must be engine

        name = argv&#91;1&#93;; while&#40;*name&#41; name++;
        while&#40;name-argv&#91;1&#93; > 0 && name&#91;-1&#93; != '\\' && name&#91;-1&#93; != '/') name--;

        /* OK, so we now send through to_prog, receive through from_prog */
        
        f = fopen&#40;"log", "w");

        &#123;   /* cmain loop ommunicates to WinBoard */
            int ponderStateWB = 0;
            int ponderStateQH = 2;
            int forceMode = 0;

            setbuf&#40;stdin, NULL&#41;;
            i = 0;
            while&#40;&#40;c=getchar&#40;)) != EOF&#41; &#123;
                if&#40;c == '\r') continue;
                if&#40;c != '\n') &#123; buf&#91;i++&#93; = c; continue; &#125;
                buf&#91;i&#93; = 0;
                fprintf&#40;f, "WB> %s\n", buf&#41;; fflush&#40;f&#41;;

                sscanf&#40;buf, "%s", command&#41;;
                if&#40;!strcmp&#40;command, "quit"))       // pass on & kill
                    close&#40;to_prog&#41;,
                    close&#40;from_prog&#41;,
                    kill&#40;pid,  SIGKILL&#41;,
                    fclose&#40;f&#41;,
                    exit&#40;0&#41;;
                else if&#40;!strcmp&#40;command, "result")) // pass on & kill
                    close&#40;to_prog&#41;,
                    close&#40;from_prog&#41;,
                    kill&#40;pid,  SIGKILL&#41;;
                else if&#40;!strcmp&#40;command, "protover"))
                    printf&#40;"feature myname=\"%s\" done=1\n", name&#41;,
                    fflush&#40;stdout&#41;;
                else if&#40;!strcmp&#40;command, "go"))    // end force mode & think
                    forceMode=0,
                    ProduceMove&#40;from_prog, to_prog&#41;;
                else if&#40;!strcmp&#40;command, "hard"))
                    ponderStateWB = 1;
                else if&#40;!strcmp&#40;command, "easy"))
                    ponderStateWB = 0;
                else if&#40;!strcmp&#40;command, "force")) // remember
                    forceMode = 1;
                else if&#40;!strcmp&#40;command, "new")) &#123; // start new engine proc
                    /* close old pipes */
                    if&#40;from_prog&#41;close&#40;from_prog&#41;;
                    if&#40;to_prog&#41;close&#40;to_prog&#41;;
                    /* set up pipes */
                    pipe&#40;toPipe&#41;;
                    pipe&#40;fromPipe&#41;;
                    /* create engine */
                    if&#40;&#40;pid = fork&#40;)) == 0&#41;
                    &#123;   /* child */
                        fclose&#40;stderr&#41;;
                        close&#40;toPipe&#91;1&#93;);
                        close&#40;fromPipe&#91;0&#93;);
                        dup2&#40;toPipe&#91;0&#93;, 0&#41;;
                        dup2&#40;fromPipe&#91;1&#93;, 1&#41;;
                        if&#40;toPipe&#91;0&#93; >= 2&#41; close&#40;toPipe&#91;0&#93;);
                        close&#40;fromPipe&#91;1&#93;);
                        execv&#40;argv&#91;1&#93;, argv+1&#41;;
                        perror&#40;argv&#91;1&#93;);
                        exit&#40;1&#41;;
                    &#125;
                    /* parent */
                    close&#40;toPipe&#91;0&#93;);
                    close&#40;fromPipe&#91;1&#93;);
                    from_prog = fromPipe&#91;0&#93;;
                    to_prog   = toPipe&#91;1&#93;;
                    forceMode = 0;
                    ReadBoard&#40;from_prog, before&#41;;
                &#125; else if&#40;&#40;buf&#91;4&#93; == 0 || buf&#91;5&#93; == 0&#41; &&
                        command&#91;0&#93; >= 'a' && command&#91;0&#93; <= 'h' &&
                        command&#91;2&#93; >= 'a' && command&#91;2&#93; <= 'h' &&
                        command&#91;1&#93; >= '1' && command&#91;1&#93; <= '8' &&
                        command&#91;3&#93; >= '1' && command&#91;3&#93; <= '8'   ) // pass on
                &#123; /* move */
                    sprintf&#40;command, "%c%c%c%c\n",
                                buf&#91;0&#93;, buf&#91;1&#93;, buf&#91;2&#93;, buf&#91;3&#93;);
                    write&#40;to_prog, command, 5&#41;;
                    ReadBoard&#40;from_prog, before&#41;; // read board after forced move
                    if&#40;!forceMode&#41;     // go thinking if not in force mode
                        ProduceMove&#40;from_prog, to_prog&#41;;
                &#125;
                i = 0;
            &#125;
        &#125;
&#125;

Re: Current world's smallest chess program

Posted: Sat Feb 21, 2009 11:03 am
by Jim Ablett
Here's some windows compiles (Toledo NanoChess + Max2WB):

http://www.mediafire.com/?nyy0jxzt2ww

I added >

Code: Select all

  /* No buffering, please... */
  setbuf&#40;stdout, NULL&#41;;
  setbuf&#40;stdin, NULL&#41;;
  /* and I *really* mean it, too! */
  setvbuf&#40;stdout, NULL, _IONBF, 0&#41;;
  setvbuf&#40;stdin, NULL, _IONBF, 0&#41;;    
 
to Toledo which seems to fix the memory problem.

Jim.

Re: Current world's smallest chess program

Posted: Sat Feb 21, 2009 8:42 pm
by hgm
I am very sorry, but now that I can test it without Toledo crashing my system, it turns out that the max2wb source above contains a bad bug, preventing it to correctly handle long castling. The line

Code: Select all

                if&#40;ito < 0 || ito != 4 && ito != 074&#41;
should be changed into:

Code: Select all

                if&#40;ito < 0 || ito != 2 && ito != 072&#41;

Re: Current world's smallest chess program

Posted: Sat Feb 21, 2009 9:39 pm
by Jim Ablett
hgm wrote:I am very sorry, but now that I can test it without Toledo crashing my system, it turns out that the max2wb source above contains a bad bug, preventing it to correctly handle long castling. The line

Code: Select all

                if&#40;ito < 0 || ito != 4 && ito != 074&#41;
should be changed into:

Code: Select all

                if&#40;ito < 0 || ito != 2 && ito != 072&#41;

Recompiled:
Download:
http://www.mediafire.com/?t0zmkzeywjm

Max2WB+Toledo combo also works in Arena if you run it from a bat file.
Toledo thinks for about one and a half minutes per move on my Athlon XP/M 3000+

Jim.