Current world's smallest chess program

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
nanochess
Posts: 64
Joined: Thu Feb 19, 2009 5:34 pm
Location: Mexico, Mexico

Current world's smallest chess program

Post 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!
User avatar
hgm
Posts: 27788
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Current world's smallest chess program

Post 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.
User avatar
Bill Rogers
Posts: 3562
Joined: Thu Mar 09, 2006 3:54 am
Location: San Jose, California

Re: Current world's smallest chess program

Post 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
Dann Corbit
Posts: 12538
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Current world's smallest chess program

Post 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;
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: Current world's smallest chess program

Post 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.
User avatar
hgm
Posts: 27788
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Current world's smallest chess program

Post 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.
User avatar
hgm
Posts: 27788
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Current world's smallest chess program

Post 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;
User avatar
Jim Ablett
Posts: 1383
Joined: Fri Jul 14, 2006 7:56 am
Location: London, England
Full name: Jim Ablett

Re: Current world's smallest chess program

Post 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.
User avatar
hgm
Posts: 27788
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Current world's smallest chess program

Post 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;
User avatar
Jim Ablett
Posts: 1383
Joined: Fri Jul 14, 2006 7:56 am
Location: London, England
Full name: Jim Ablett

Re: Current world's smallest chess program

Post 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.