Website for micro-Max

[H.G.Muller]

As an exercise in HTML I have now built a web site for my 2000-character chess program micro-Max. It can be found at:

http://home.hccnet.nl/h.g.muller/max-src2.html

I hope to host more chess pages on that site in the future.

[YvesLejeail]

Hi,
Your site has lot of valuable infos concerning all aspects of chess programming, thanks for the link !!! A mega site for a micro chess programme

[Dann Corbit]

As an exercise in HTML I have now built a web site for my 2000-character chess program micro-Max. It can be found at:

http://home.hccnet.nl/h.g.muller/max-src2.html

I hope to host more chess pages on that site in the future.

That is a very nice web site. I enjoy your tiny program.

[Naum]

You are telling me those couple lines of code can actually play chess?

Woa, I am impressed

[H.G.Muller]

Amazing, isn't it?

And it does not even play so bad, it probably has the highest numbr of ELO points per code-line of any program in existence. Even in the non-castling 62-line version some lines are devoted to improve the quality of play. (In particular the piece-square points, the pawn structure and the KQK mating incentive.) Without that it would technically still be a chess program, since it would do moves according to the (slightly simplified) rules, and would try to avoid tactical combination that lost material. But positionally it would play so poorly then that I would be reluctant to call it a chess program...

The 2000-character version is tactically not bad at all, it searches quite efficiently due to the iterative deepening, best-first sorting, and the simple but big hash table. It plays KPK (W:Ke1,Pe2; B:Ke8) like a pro, announcing queening-in-17 after a few seconds of search (at 24 ply).

[L?szl? G?sp]

Hi H.G.,

Congratulations for this nice work! Your little program is really amazing! (Though I have to learn to compile C programs at last...since I use Java.)

Best regards,

L?szl?

[David Weller]

Simply amazing!

Few functions _WITHIN_ my chess programs are that small!!!

I first 'learned' _some_ programming on a Commodore VIC20 and had to concentrate a lot on SIZE. So I can appreciate your work

Good ole 6502 assembly too!

I had a scrolling river like in river raid working once ...

[Uri Blass]

I wonder if the program was tested to see what is it's level relative to other engines.

Of course it cannot be very strong with little number of lines but considering the fact that tscp does not use hash I will not be surprised if it is better than tscp and even at the level of Gerbil.

Did somebody try to change it to be winboard program and test it?

Uri

[Dann Corbit]

I wonder if the program was tested to see what is it's level relative to other engines.

Of course it cannot be very strong with little number of lines but considering the fact that tscp does not use hash I will not be surprised if it is better than tscp and even at the level of Gerbil.

I disagree. Small line count programs can be very, very strong.
Consider Thinker. I guess that it is about the number of lines of TSCP.
If his program can play Winboard capable, I guess it will be tested before long.

Did somebody try to change it to be winboard program and test it?

Uri

[Dann Corbit]

Code: Select all

/***************************************************************************/
/*                               micro-Max,                                */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller  */
/***************************************************************************/
/* version 3.2 (2000 characters) features:                                 */
/* - recursive negamax search                                              */
/* - quiescence search with recaptures                                     */
/* - recapture extensions                                                  */
/* - (internal) iterative deepening                                        */
/* - best-move-first 'sorting'                                             */
/* - a hash table storing score and best move                              */
/* - full FIDE rules (expt minor ptomotion) and move-legality checking     */

/* hash table, 16M+8 entries*/
static struct hash {
    int             K,
                    V;
    char            X,
                    Y,
                    D;
}   A[16777224];

static int      V = 112, /* V=0x70=rank mask, M=0x88 */
                M = 136,
                S = 128,
                I = 8e3,
                C = 799,
                Q,
                N,
                i;

static char     O,
                K,
                L,
                /* relative piece values */
                w[] = {0, 1, 1, 3, -1, 3, 5, 9},
                /* step-vector lists 1st dir. in o[] per piece initial piece setup      */
                o[] = {-16, -15, -17, 0, 1, 16, 0, 1, 16, 15, 17, 0, 14, 18, 31, 33, 0, 7, -1, 11, 6, 8, 3, 6, 6, 3, 5, 7, 4, 5, 3, 6},
                /* board: half of 16x8+dummy*/
                b[129],
                /* hash translation table   */
                T[1035],
                /* piece symbols on printout*/
                n[] = ".?+nkbrq?*?NKBRQ";

/* recursive minimax search, k=moving side, n=depth */
/* (q,l)=window, e=current eval. score, E=e.p. sqr. */
/* e=score, z=prev.dest; J,Z=hashkeys; return score */
static int      D(int k, int q, int l, int e, int J, int Z, int E, int z, int n)
{
    int             j,
                    r,
                    m,
                    v,
                    d,
                    h,
                    i = 9,
                    F,
                    G;
    char            t,
                    p,
                    u,
                    x,
                    y,
                    X,
                    Y,
                    H,
                    B;
    struct hash    *a = A;
    j = (k * E ^ J) & 16777224 - 9;
    while ((h = A[++j].K) && h - Z && --i);
    a += i ? j : 0;
    if (a->K) {
        d = a->D;
        v = a->V;
        X = a->X;
        if (d >= n) {
            if (v >= l | X & S && v <= q | X & 8)
                return v;
            d = n - 1;
        }
        X &= ~M;
        Y = a->Y;
        Y = d ? Y : 0;
    } else
        d = X = Y = 0;
    N++;
    while (d++ < n | z == 8 & N < 1e7 & d < 98) {
        x = B = X;
        Y |= 8 & Y >> 4;
        m = d > 1 ? -I : e;
        do {
            u = b[x];
            if (u & k) {
                r = p = u & 7;
                j = o[p + 16];
                while (r = p > 2 & r < 0 ? -r : -o[++j]) {
            A:
                    y = x;
                    F = G = S;
                    do {
                        H = y += r;
                        if (Y & 8)
                            H = y = Y & ~M;
                        if (y & M)
                            break;
                        if (p < 3 & y == E)
                            H = y ^ 16;
                        t = b[H];
                        if (t & k | p < 3 & !(r & 7) != !t)
                            break;
                        i = 99 * w[t & 7];
                        if (i < 0 || E - S && b[E] && y - E < 2 & E - y < 2)
                            m = I;
                        if (m >= l)
                            goto C;
                        if (h = d - (y != z)) {
                            v = p < 6 ? b[x + 8] - b[y + 8] : 0;
                            b[G] = b[H] = b[x] = 0;
                            b[y] = u & 31;
                            if (!(G & M)) {
                                b[F] = k + 6;
                                v += 30;
                            }
                            if (p < 3) {
                                v -= 9 * (((x - 2) & M || b[x - 2] != u) +
                                        ((x + 2) & M || b[x + 2] != u) - 1);
                                if (y + r + 1 & S) {
                                    b[y] |= 7;
                                    i += C;
                                }
                            }
                            v = -D(24 - k,                                                    // int k=moving side
                                   -l - (l > e),                                              // int q,  (q,l)=window
                                   m > q ? -m : -q,                                           // int l,
                                   -e - v - i,                                                // int e=current eval
                                   J + *(int *) (T + y + 0 + (b[y] & 8) + S * (b[y] & 7))
                                       - *(int *) (T + x + 0 + (u & 8) + S * (u & 7))
                                       - *(int *) (T + H + 0 + (t & 8) + S * (t & 7)),        // int J, hashkey
                                   Z + *(int *) (T + y + 8 + (b[y] & 8) + S * (b[y] & 7))
                                       - *(int *) (T + x + 8 + (u & 8) + S * (u & 7))
                                       - *(int *) (T + H + 8 + (t & 8) + S * (t & 7)) + G - S,// int Z, hashkey 
                                   F,                                                         // int E, E=e.p. sqr.
                                   y,                                                         // int z=prev.dest
                                   h                                                          // int n=depth
                           );

                            v -= v > e;
                            if (z == 9) {
                                if (v != -I & x == K & y == L) {
                                    Q = -e - i;
                                    O = F;
                                    return l;
                                }
                                v = m;
                            }
                            b[G] = k + 38;
                            b[F] = b[y] = 0;
                            b[x] = u;
                            b[H] = t;
                            if (Y & 8) {
                                m = v;
                                Y &= ~8;
                                goto A;
                            }
                            if (v > m) {
                                m = v;
                                X = x;
                                Y = y | S & G;
                            }
                        }
                        t += p < 5;
                        if (p < 3 & 6 * k + (y & V) == S
                            || (u & ~24) == 36 & j == 7 &&
                            G & M && b[G = (x | 7) - (r >> 1 & 7)] & 32
                            && !(b[G ^ 1] | b[G ^ 2])
                            ) {
                            F = y;
                            t--;
                        }
                    } while (!t);
                }
            }
        } while ((x = x + 9 & ~M) - B);
C:
        if (m > I / 4 | m < -I / 4)
            d = 99;
        m = m + I ? m : -D(24 - k, -I, I, 0, J, Z, S, z, 1) / 2;
        if (!a->K | (a->X & M) != M | a->D <= d) {
            a->K = Z;
            a->V = m;
            a->D = d;
            A->K = 0;
            a->X = X | 8 * (m > q) | S * (m < l);
            a->Y = Y;
        }
    }
    if (z & 8) {
        K = X;
        L = Y & ~M;
    }
    return m;
}

int             main(void)
{
    int             j,
                    k = 8,
                   *p,
                    c[9];
    for (i = 0; i < 8; i++) {
        b[i] = (b[i + V] = o[i + 24] + 40) + 8;
        b[i + 16] = 18;
        b[i + 96] = 9;
        for (j = 0; j < 8; j++)
            b[16 * j + i + 8] = (i - 4) * (i - 4) + (j - 3.5) * (j - 3.5);
    }
    for (i = M; i < 1035; i++)
        T[i] = random() >> 9;
    while (1) {
        for (i = 0; i < 121; i++)
            printf(" %c", i & 8 && (i += 7) ? 10 : n[b[i] & 15]);
        p = c;
        while ((*p++ = getchar()) > 10);
        N = 0;
        if (*c - 10) {
            K = c[0] - 16 * c[1] + C;
            L = c[2] - 16 * c[3] + C;
        } else
            D(k, -I, I, Q, 1, 1, O, 8, 0);
        for (i = 0; i < 16777224; i++)
            A[i].K = 0;
        if (D(k, -I, I, Q, 1, 1, O, 9, 2) == I)
            k ^= 24;
    }
    return 0;
}


[Dann Corbit]

SamChess promoted through 2 leagues in G.L.'s touraments:
http://www.geocities.com/lyapko/lg200601.htm

If you look at SamChess, I think it is incredibly tiny for a functional Winboard program.

And yet it is clearly not the weakest program.

I think that we all toil in vain here, though. Lance Perkins, who wrote Thinker, is the master of the tiny-tiny grenade with a great big KABOOM.

[Uri Blass]

I wonder if the program was tested to see what is it's level relative to other engines.

Of course it cannot be very strong with little number of lines but considering the fact that tscp does not use hash I will not be surprised if it is better than tscp and even at the level of Gerbil.

I disagree. Small line count programs can be very, very strong.
Consider Thinker. I guess that it is about the number of lines of TSCP.
If his program can play Winboard capable, I guess it will be tested before long.

Did somebody try to change it to be winboard program and test it?

Uri

I do not understand what you disagree about.
I never claimed that bigger has to be better.

Some facts:

1)Thinker is clearly bigger than Micro-Max and I asked about the level of Micro-Max.

I said that I will not be surprised if Micro-Max is better than tscp.

2)Bigger has the potential to be better and I am almost sure that it is possible to write a better program with more lines.

Thinker is weaker than Rybka and I do not see the point of comparing thinker with tscp.

The target of tscp was not to write a small good program(otherwise it could be better to implement hash tables instead of lot of evaluation code that is not very important like evaluating backward pawns).

Uri

[Uri Blass]

SamChess promoted through 2 leagues in G.L.'s touraments:
http://www.geocities.com/lyapko/lg200601.htm

If you look at SamChess, I think it is incredibly tiny for a functional Winboard program.

And yet it is clearly not the weakest program.

I think that we all toil in vain here, though. Lance Perkins, who wrote Thinker, is the master of the tiny-tiny grenade with a great big KABOOM.

I think that thinker is not a tiny program.

We are talking here about source of less than 2 kbytes and I am going to be surprised if thinker(not including winboard code) is less than 4 kbytes of source(even if we replace all names of variables by names of one digit like done by MicroMax).

Source of thinker is not free so we can only guess.

Uri

[Dann Corbit]

Thinker's source code must be very, very small or it would compile to a large binary.

Now, you can compress a binary and make it smaller. But when it loads into memory it must be expanded. Thinker does not expand appreciably upon loading into memory.

We have seen some source from Thinker (Lance posts snippets from time to time) and it is clear that it is also well written [I would say even "pretty"] code.

It may be possible to write the world's strongest chess program in 5000 lines.

I think that the point I hoped to make (but phrased badly) is that there is no strong correlation between source code size {or binary size} and program strength. We can find absurdly tiny programs that are incredibly powerful [e.g. Thinker] or stupendously huge systems that are weak sisters [e.g. Alice].

I am not sure that I was trying to contradict you. I was just trying to point out that size != strength {even to the point that I doubt there is any correlation}. Other than the fact that you cannot possibly write a world class program with a 2 byte executable {so there are clearly some limits on program size} it is not necessarily complexity that leads to strength. It can even be simplicity.

IMO-YMMV

[H.G.Muller]

I guess that in the compactness vs complexity issue there is an automatic stabilizing effect: less code usually means faster execution, and more nodes per second, if the codes are not unduly wastefull. So the fact that the evaluation is very simplistic (something that is unavoidable in a project like this) is partly compensated by a seach-speed increas of perhaps a factor 3 compared to a more elaborate evaluation (such as counting mobility). The move generator of micro-Max might waste a factor 2-3 in search speed by scanning the board to find his own pieces, in stead of having a piece-list data structure besides the board array (but TSCP seems to do this too).

Evaluation clearly is the weakest point in micro-Max, compared to other engines. Making the search efficient was much more important, the move sorting affects the branching ratio and affects the performance exponentially, while move-generator speed only affects the pre-factor. The current move sorting does not seem so bad, despite the fact that only a single move is lifted from the essentially random move-generator-dictated order to try first. In a test it seemed to search only twice the number of nodes that was theoretically necessary, and that included the overhead due to the iterative deepening. I considered this pretty good, although the positon I tested this on (the initial position) might not be representative, and I should repeat it on a tacticly highly complicated middle-game position once.

I would love to learn how to make an engine Winboard compatible. What would be the best approach to this? Should I study GNUchess to figure out the interface definition? In what source file of GNUchess should I look?

[Rémi Coulom]

I would love to learn how to make an engine Winboard compatible. What would be the best approach to this? Should I study GNUchess to figure out the interface definition? In what source file of GNUchess should I look?

http://www.tim-mann.org/xboard/engine-intf.html

R?mi

[Uri Blass]

I guess that in the compactness vs complexity issue there is an automatic stabilizing effect: less code usually means faster execution, and more nodes per second, if the codes are not unduly wastefull. So the fact that the evaluation is very simplistic (something that is unavoidable in a project like this) is partly compensated by a seach-speed increas of perhaps a factor 3 compared to a more elaborate evaluation (such as counting mobility). The move generator of micro-Max might waste a factor 2-3 in search speed by scanning the board to find his own pieces, in stead of having a piece-list data structure besides the board array (but TSCP seems to do this too).

Evaluation clearly is the weakest point in micro-Max, compared to other engines. Making the search efficient was much more important, the move sorting affects the branching ratio and affects the performance exponentially, while move-generator speed only affects the pre-factor. The current move sorting does not seem so bad, despite the fact that only a single move is lifted from the essentially random move-generator-dictated order to try first. In a test it seemed to search only twice the number of nodes that was theoretically necessary, and that included the overhead due to the iterative deepening. I considered this pretty good, although the positon I tested this on (the initial position) might not be representative, and I should repeat it on a tacticly highly complicated middle-game position once.

I would love to learn how to make an engine Winboard compatible. What would be the best approach to this? Should I study GNUchess to figure out the interface definition? In what source file of GNUchess should I look?

I do not think that less code usually mean faster execution.
As you admit micromax has no piece list and it makes it slower in nodes per seconds.

more code can make the program faster in nodes per seconds and can make the program slower in nodes per second and the main question is what code you add.

Uri

[H.G.Muller]

I agree. But adding the piece list does not add all that much code, perhaps 100 characters, or so (which probably would have been more wisely spent on other improvements). And this is really the only such major inefficiency in micro-Max that should be repaired that way. I am thinking more of adding tens of KB. All that code can not go into accelerating the nodes per second, which is already close to the theoretical maximum. So if it is going to be executed significantly, the nodes per second must drop.

That doesn't mean of course, that it can not make better use of the nodes that it does look at: code that reduces your branching ratio by clever choice of extensions / reductions can be very complex and still worth it.

[H.G.Muller]

Well, I did some tests after making micro-Max quasi Winboard compatible, (thanks, R?mi...), but it is clearly weaker then TSCP. What seems to break it is the complete neglect of King safety in the positional evaluation. In combination with the lack of check extensions and check detection in end leaves, this is quite fatal.

If playing strength is the main concern, threat detection and threat-evasion extensions would probably be a much more valuable investment than a hash table. The latter does not buy all that much advantage in the middle game. I already found earlier that the recapture extension is also a bad idea; a version of micro-Max that only searches recaptures in QS, rather than alwas giving an extension for them, beats the version on my web-site by 65-35 when given equal number of nodes to search.

But micro-Max is meant more as a show case of important concepts in chess programming than as an attempt to play the best possible chess. In that respect it seemed interesting to also have an extension in it (and I could get this one for free). This is why I left it in.

[Uri Blass]

I decided to try to compile the program as first step before learning it and the program from the post of Dann Corbit does not compile correctly

I get 3 errors and 18 warning

Copying it directly from the site is even worse and I get more errors

Here are the errors that I got(first errors from copying the post of Dann Corbit .

Compiling...
main.cpp
c:\simple chess program\main.cpp(26) : warning C4244: 'initializing' : conversion from 'const double' to 'int', possible loss of data
c:\simple chess program\main.cpp(78) : warning C4554: '|' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(78) : warning C4554: '|' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(88) : warning C4554: '&' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(88) : warning C4554: '&' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(88) : warning C4554: '|' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(97) : warning C4554: '&' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(107) : warning C4554: '&' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(110) : warning C4554: '&' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(113) : warning C4554: '&' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(150) : warning C4554: '&' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(150) : warning C4554: '&' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(174) : warning C4554: '&' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(174) : warning C4554: '&' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(186) : warning C4554: '|' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(189) : warning C4554: '|' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(189) : warning C4554: '|' : check operator precedence for possible error; use parentheses to clarify precedence
c:\simple chess program\main.cpp(216) : warning C4244: '=' : conversion from 'double' to 'char', possible loss of data
c:\simple chess program\main.cpp(219) : error C2065: 'random' : undeclared identifier
c:\simple chess program\main.cpp(222) : error C2065: 'printf' : undeclared identifier
c:\simple chess program\main.cpp(224) : error C2065: 'getchar' : undeclared identifier
Error executing cl.exe.

main.obj - 3 error(s), 18 warning(s)


Compiling...
main.cpp
C:\simple chess program\main.cpp(22) : warning C4244: 'initializing' : conversion from 'const double' to 'int', possible loss of data
C:\simple chess program\main.cpp(34) : error C2065: 'k' : undeclared identifier
C:\simple chess program\main.cpp(34) : error C2065: 'q' : undeclared identifier
C:\simple chess program\main.cpp(34) : error C2065: 'l' : undeclared identifier
C:\simple chess program\main.cpp(34) : error C2065: 'e' : undeclared identifier
C:\simple chess program\main.cpp(34) : error C2065: 'J' : undeclared identifier
C:\simple chess program\main.cpp(34) : error C2065: 'Z' : undeclared identifier
C:\simple chess program\main.cpp(34) : error C2065: 'E' : undeclared identifier
C:\simple chess program\main.cpp(34) : error C2065: 'z' : undeclared identifier
C:\simple chess program\main.cpp(35) : error C2448: '<Unknown>' : function-style initializer appears to be a function definition
C:\simple chess program\main.cpp(35) : fatal error C1004: unexpected end of file found
Error executing cl.exe.

main.obj - 10 error(s), 1 warning(s)