Current world's smallest chess program

[Tim Rentsch]

I've never received a satisfactory answer to my question concerning what
"the ISO Standard itself" means precisely when referring to the
topicality of comp.std.c and why this newsgroup, comp.lang.c, isn't
a duplicate of comp.std.c. Certainly routine questions about the
use of ISO functions are discussed all the time on comp.std.c. Yet
people on this newsgroup toss out the vague "about the ISO Standard
itself" and hope that the reader assumes that means talk about
the Standard's typography and purchasing details and whatnot.

I don't know how other people might answer this question, but for
myself I usually distinguish based on the following criteria.

For comp.lang.c, my default presumption is that people are asking
about (or discussing) C as it is; they enter with some level of
existing "outside knowledge" (meaning, outside the Standard), so
there is some preconception about what C is like, and these
preconceptions color their perceptions (usually differently for
different people). People asking questions in comp.lang.c are
looking for operational answers, not theoretical answers. In
comp.lang.c, the language is fixed (or at least that's the most
common presumption).

For comp.std.c, my default presumption is that people want to
discuss C as it is, or as it might be, under a different set of
rules. More specifically, in comp.std.c the participants usually
adopt the stance that only the Standard itself (or sometimes other
outputs of the ISO effort, but in any case no non-ISO documents)
may be referenced. They may want to discuss changes to the text
for the purpose of clarification, they may want to discuss changes
to the text for the purpose of changing the language in some way,
or they may want to discuss how to interpret text in the Standard
without the usual operational preconceptions that are almost
always present in comp.lang.c. The discussion in comp.std.c is
more theoretical than operational. A perspective that may be
helpful is, comp.std.c can be seen as a forum that is helpful
to people who are interested in writing standards documents.

Of course, since these are just my personal guidelines, there
are plenty of exceptions, for both newsgroups. Despite that,
I find them useful, both for deciding in which newsgroup to
pursue an inquiry, and for understanding what expectations
participants bring into the discussions in the two cases.

 

[CBFalconer]

I don't know how other people might answer this question, but for
myself I usually distinguish based on the following criteria.

.... snip Tim Rentsch's answer ...

Even though this originated with that gross troll, Han, it deserves
a response. The point is 'what is the C language'. This is
defined by the ISO standard, and anything defined therein should be
accepted and executable by any system (with minor allowances for
C90 vs C99 differences, and larger allowances for K&R C
differences). That includes writing functions and using them. The
point is that those functions should be writable in the approved C
language. If they use features that do not exist in the standard,
they cannot be written for portable use.

c.l.c has heavy traffic, even after plonking trolls. We don't want
to waste our time pointing out that things are undefined, and
off-topic. The ideal situation is one where users are intelligent,
and need only one indication that they are on the wrong newsgroup.
The ugly nuisance situation is where too many users are stupid and
insist on cluttering the newsgroup with nonsense.

If someone wants to call functions not listed in the C standard,
the source of those functions should either be included, or be
easily available. A further possibility is a reasonable
description of the function, for the purposes of the query. For
example "frabble(char *foo)" might return an integer describing
some characteristic of *foo. If used, we can't check that, but we
can accept the fact provided it is clearly stated. Of course if
the source code for frabble is included there is no problem.

 

[Tim Rentsch]

... snip Tim Rentsch's answer ...

Even though this originated with that gross troll, Han, it deserves
a response. The point is 'what is the C language'. This is
defined by the ISO standard, and anything defined therein should be
accepted and executable by any system (with minor allowances for
C90 vs C99 differences, and larger allowances for K&R C
differences). That includes writing functions and using them. The
point is that those functions should be writable in the approved C
language. If they use features that do not exist in the standard,
they cannot be written for portable use.

c.l.c has heavy traffic, even after plonking trolls. We don't want
to waste our time pointing out that things are undefined, and
off-topic. The ideal situation is one where users are intelligent,
and need only one indication that they are on the wrong newsgroup.
The ugly nuisance situation is where too many users are stupid and
insist on cluttering the newsgroup with nonsense.

If someone wants to call functions not listed in the C standard,
the source of those functions should either be included, or be
easily available. A further possibility is a reasonable
description of the function, for the purposes of the query. For
example "frabble(char *foo)" might return an integer describing
some characteristic of *foo. If used, we can't check that, but we
can accept the fact provided it is clearly stated. Of course if
the source code for frabble is included there is no problem.

Apparently you missed the point. The question I was responding
to was about the difference between comp.lang.c and comp.std.c.
There was never any question that the general area of both groups
is ISO C; certainly not in my answer, nor in the question I was
responding to, at least not as I read it. And I think that was
made clear in my comments, essentially all of which you snipped,
so you could give a polemic on a topic unrelated to the question
being asked.

Whatever your beliefs are about topicality, S/N ratio on the
newsgroup, which people display inappropriate behavior here, etc,
you might want to reevaluate your behavior as to how those
beliefs should be acted on. Because right now, at least IMO, the
behavior displayed seems to belong more to the problem space than
it does to the solution space.

 

[Tim Rentsch]

Exactly! And if people are asking about C issues that are outside of
the ISO standard, they're looking for operational, practical answers,
not theoretical answers and admonitions based on someone's topicality
opinion. Everyone has a right to have a topicality opinion, and I
believe a happy coexistence is possible where people simply ignore
those threads they themselves consider off-topic, instead of imposing
their own topicality opinions on others and refusing to provide
rational reasons for doing so or to engage in a proper debate. I've
been posting my topicality guidelines for quite a while now, and
I've yet to see the contradictions mentioned therein resolved.

Please don't make my answer into something it isn't. You asked
what I thought was a reasonable question. I took it to be asking
a question outside the arena of topicality wars, and that's the
way I answered it. I take it as given that the topic of both
newsgroups is the C language, more specifically C as defined by
ISO documents. That doesn't mean I think the set of conversations
should be limited to those dealing with ISO sophistry (although
those too have their place, but so also do others), as I think
my postings have shown. So, again, please don't take my comments
into the domain of topicality warfare; that domain just isn't
productive.

That's the stance on comp.lang.c as well. ;-) See Chuck Falconer's
inane reply to your thoughtful post.

I saw it. If you'll forgive my saying so, as long as you keep
fanning the flames under the people on the other side, they are
going to keep firing back. It would be better for everyone if
both sides would stop trying to advance their own agenda about
topicality and just engage in discussion of what different people
are here to discuss. If the other side won't stop of their own
volition, that's an opportunity for you to be the bigger man and
do so first.

Fair enough. I agree that such discussions belong on comp.std.c.

I agree that the distinction is useful in differentiating the two
newsgroups. And just in case, I also would like to repeat that
my comments are not meant as a statement about how people should
behave, but as an observation that seems to be useful in guiding
my own behavior and understanding. If other people also find
that view useful, that's great; but if someone has a different
perspective, that's cool too -- I believe in not trying to impose
my views on other people, as long as they grant the same attitude
to other people in return.

 

[Antoninus Twink]

We don't want to waste our time pointing out that things are
undefined, and off-topic.

You can thank me later, but in a moment of brilliance I've found the
perfect solution: simply stop pointing out that things are "undefined"
and "off topic".

 

[Flash Gordon]

The French have a language academy that is supposed to define what is
and what is not French. So "brinksmanship" is supposedly "strategie du
bord de l'abime". We have some native French speakers here who will tell
you better than I, but the Academy's policy is doomed to fail.

Basically the idea is a hangover from the French revolution, when
everything was rationalised. In England we have never had such an
Academy. The English languge is defined by usage. Foreign words and
phrases are incorporated as they catch on, in an ad hoc fashion.

Spoken languages are very different to computer languages. French
speakers often know some English and can understand it, when is the last
time you found a C compiler that could correctly understand ML?

By saying "C is defined by the ISO standard" you are making the same
mistake as the Academie Francais. It is simply not possible to legislate
over what people (including even French people ) release into the
programing environment.

It does not legislate, but the compiler vendors generally make a
conscious effort to conform to the C standard and they are so
successfull that this that you *can* take code written for one target
and compile it on a completely different target and find that it still
works correctly. You can't always do this with the entire program, since
some things cannot be done in standard C, but I have ported over 90% of
an embedded application to a hosted system using a different processor,
debugged it on the hosted system, then put that 90% of the code back on
the embedded system with no further change.

 

[Phil Carmody]

Spoken languages are very different to computer languages. French
speakers often know some English and can understand it, when is the
last time you found a C compiler that could correctly understand ML?

Stupid analogy. French and English are, vocabulary-wise, very closely
related (and grammar-wise are very similar too). C and ML have no such
relation. Change your question to "When was the last time I found a
C++ compiler that could understand some bits of C?" and the answer
would be "Today".

Phil

 

[Walter Banks]

Then we've had the strange situation of almost no support for
the official current standard.

This statement just isn't backed by the facts. There is a lot of support
for the current standard. Complete implementation varies but significant
portions are in essentially every current C compiler. Validated versions
for C99 exist.

The situation in practise is that most C code
is not strictly conforming. I am not saying that this is desireable, but it
is the reality. Lots of dialects rather than a single centrally imposed
tongue.

ISO WG14 documents current practices. Changes and growth in
the language features and functions come from the dialect
elements that become mainstream.

Regards,

 

[CBFalconer]

.... snip ...

Apparently you missed the point. The question I was responding
to was about the difference between comp.lang.c and comp.std.c.

Apparently you missed the 'snip Tim' portion. I was replying to
your quote of Han, whose raw output never reaches me.

 

[CBFalconer]

.... snip ...

Compiler writers make a conscious effort to support conforming
programs. However they often encourage the use of extensions.
Sometimes they even deprecate standard library functions by
default and suggest the use of an alternative. Then we've had the
strange situation of almost no support for the official current
standard. The situation in practise is that most C code is not
strictly conforming. I am not saying that this is desireable, but
it is the reality. Lots of dialects rather than a single
centrally imposed tongue.

As far as I know the only major 'compiler writer' to take that
attitude is Microsoft, who are fouling the standard library with
attempts to install their 'safe' replacements. Notice that they
are also failing to implement the C99 standard in any way.

 

[Richard Bos]

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

It isn't required to. Draw by triple repetition isn't automatic; one of
the players must claim it. If you claim this draw, you can end the
program. If it never claims that draw itself, it is allowed not to.

I suspect, but haven't bothered to check, that it doesn't automatically
end the game in a draw when a position occurs from which neither player
can possibly win. If so, that is an aspect in which it might be said not
to play chess completely correctly. It would be even more pedantically
correct to say that it doesn't _arbitrate_ chess correctly; after all,
if a human player fails to end a game under those circumstances, you
don't say that he doesn't play chess, either.

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.

That is also a correct program; any player may choose to resign at any
point, and if so, the game ends at that point. AFAICT there is nothing
in the rules which say that you're not allowed to resign during your
opponent's move (and they do say something similar about draw offers and
claims), so it plays black as well (or rather, as badly, but as
correctly) as white.

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.

Normally, so would I, but the OP originally wrote his programs for the
IOCCC, which do use a modified character count.

Richard

 

[Richard Bos]

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.

Normally, yes. But this was originally an IOCCC entry.

Richard

 

[Richard Bos]

Richard Heathfield wrote:

Interesting, I personally find this to be an unwanted "feature" of puts().
When I want a newline, I prefer to specify them.

Normally, so do I, but when you're trying to squeeze every character out
of a program...

I was going to complain that this doesn't play chess, because you can
only resign for yourself, but I took the precaution of looking up the
literal wording, and in fact rule 5.1b of the FIDE laws of chess says:

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

Note that the referent of "he" is not made clear. It could grammatically
be either the player in question, or the opponent. Do also note, though,
that in either case, the result of the game is the same: the player
whose opponent makes the declaration, however he phrases it, wins. So
both by declaring "I resign" _and_ by declaring "You resign", these two
programs always lose.

Richard

 

[user923005]

Normally, so do I, but when you're trying to squeeze every character out
of a program...


I was going to complain that this doesn't play chess, because you can
only resign for yourself, but I took the precaution of looking up the
literal wording, and in fact rule 5.1b of the FIDE laws of chess says:

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

Note that the referent of "he" is not made clear. It could grammatically
be either the player in question, or the opponent. Do also note, though,
that in either case, the result of the game is the same: the player
whose opponent makes the declaration, however he phrases it, wins. So
both by declaring "I resign" _and_ by declaring "You resign", these two
programs always lose.

What if the player is female?

About the ambiguity... we can shorten it to:
#include <stdio.h>
int main(void)
{return puts("resign");}

 

[Kaz Kylheku]

I was going to complain that this doesn't play chess, because you can
only resign for yourself, but I took the precaution of looking up the
literal wording, and in fact rule 5.1b of the FIDE laws of chess says:

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

Note that the referent of "he" is not made clear. It could grammatically
be either the player in question, or the opponent.

Such chess implementations are broken.

Proof: pit two such programs against each other.

One of them has to go first, and its move is that it resigns. Thereby, the game
ends.

The other program fails to recognize that the game has ended, and also resigns.

The way I see it, a minimal chess playing program must meet these requirements:

1. It must be aware, via some input parameter, whether whether it has the
first move.

2. If it doesn't have the first move, it must be capable of accepting
input representing the opponent's move.

3. It must be capable of recognizing, from the input representing the
opponent's move, that the game has ended (the opponent has resigned).

 

[user923005]

Such chess implementations are broken.

Proof: pit two such programs against each other.  

One of them has to go first, and its move is that it resigns. Thereby, the game
ends.

The other program fails to recognize that the game has ended, and also resigns.

The way I see it, a minimal chess playing program must meet these requirements:

1. It must be aware, via some input parameter, whether whether it has the
   first move.

2. If it doesn't have the first move, it must be capable of accepting
   input representing the opponent's move.

3. It must be capable of recognizing, from the input representing the
   opponent's move, that the game has ended (the opponent has resigned).

Normally, chess programs have a supervisor program that controls both
programs (such as Winboard, Arena, ChessGui, etc.).
http://tim-mann.org/xboard.html
http://www.playwitharena.com/
http://biglion.110mb.com/

This supervisor program will end the game when any program sends a
resignation message, not even sending additional input to the second
program.

 

[Tim Rentsch]

Apparently you missed the 'snip Tim' portion. I was replying to
your quote of Han, whose raw output never reaches me.

No, I saw it, as the part of my posting that was silently
snipped clearly showed.

Which ever posting you were responding to, the response was
off point, because the question concerned differences between
comp.lang.c and comp.std.c, and the response didn't address
that key element.

I have no desire to be in the middle of a feud. If you're
going to continue your policy of not reading Han's postings
but then responding to them indirectly, I kindly ask that you
add me to the set of people whose postings you don't read.
Don't force me to deal with something that's really your
concern and not mine.

 

[Tim Rentsch]

I apologize for that. I actually was cognizant of the danger of
putting more into your answer than what you had given -- my original
reply started off "Exactly! If people..." and I stuck that "And"
in there in an attempt to make it clear I was building my own
opinion from yours. But in doing so, it's clear I have suggested
that your opinion has some kind of logical progression to my
opinion, which it doesn't, and for that I apologize.

I appreciate the apology.

If the other side is willing to do the same, I'm happy to cease
all attacks on this newsgroup. There's actually evidence that,
with a single exception, everyone I attack has attacked me first.

When I attack people, I generally provide evidence supporting my
attacks (quotes, references to threads, etc.). If not, there's always
the implied willingness to provide evidence. If someone asks me,
I will definitely provide evidence. The others, when asked for evidence
to support their attacks, refuse to do so.

But it's hard to ignore the other side when their attacks consist
of telling OPs that my posts receive no critique and are therefore
flawed in some way (as Nick Keighley, with no sense of irony, did
recently). I asked for evidence of ever making a wrong statement
that didn't go corrected, and Keighley didn't provide any such
evidence. Nor did Flash Gordon. Nor did Phil Carmody. Nor did
Mark McInture. Nor did Chuck when Kaz asked him to do the same.

That's what I perceive as the fundamental difference between me
and the others -- a willingness to provide evidence. My last
post of my "topicality guidelines" started out with the comment
that I will provide evidence to support all statements made,
if asked to do so.

But anyway, since you're a fair and neutral guy, if ever you want
to play the role of mediator, I'm willing to make an agreement
on this newsgroup that all my attacks will stop if the others
agree to do the same. Then, in your impartial role, you can
see who attacks first.

I know the last thing you want is to be dragged into this mess,
but since you appear to be respected by both sides, if you start a
thread with a small paragraph saying something like "In the
interests of this newsgroup, Han from China has agreed to cease
all attacks if the other party does the same", I will reply and
agree to that treaty, and we can mark it down as a starting point
of peace and see who starts trouble first from that point on. I
suspect many people on this newsgroup will be surprised.

I appreciate the compliment implied by the request. However, let
me make a counter-suggestion. Simply change unilaterally, and
wait for other people to catch up. Some will notice and change
their tone fairly quickly. Others will take longer, and (sadly)
a few may seem never to notice at all. Just ignore the negative
comments; if someone can't recognize that you're making an
effort to be more reasonable, that's their problem, not yours,
and eventually other people will see that too. Pick some
postings that you think provide clear and informative answers,
and consciously try to imitate their style. The point of doing
that is not to mimic other people but as a learning experience to
see what kinds of answers work and which ones don't, and to
develop and strengthen your own style. I don't want to say much
more about that, except that it's more difficult than it looks --
I've worked over a long time on my own writing style, both in and
out of comp.lang.c, and although I think it's not too bad now, I
know it could be better, and I'm still working on it.

One final comment about making a unilateral change - it may sound
ridiculous but it can be very powerful. Ghandi said it nicely:
"You must be the change you want to see in the world." I think
an independent change is more likely to have a big effect than
a mediated one; my suggestion is, give it a try.

 

[Doug Miller]

The way I see it, a minimal chess playing program must meet these requirements:

1. It must be aware, via some input parameter, whether whether it has the
first move.

1.1 And if so, play a legal move, offer a draw, or resign.

2. If it doesn't have the first move, it must be capable of accepting
input representing the opponent's move.

2.1 and determine if that move is legal
2.2 and if not, complain in some fashion and await a legal move

3. It must be capable of recognizing, from the input representing the
opponent's move, that the game has ended (the opponent has resigned).

This is incorrect. The game may be ended by the *program's* move, in at least
four ways:
a) the program's move checkmates the opponent
b) the program's move stalemates the opponent
c) the program's move makes it impossible for either player to win (e.g. the
program has a king and one bishop, the opponent has a king and one pawn, and
the program's move is to capture the opponent's pawn)
d) the program resigns.

The game may also be ended by the opponent's move in the same ways, by mutual
agreement of a draw, by a verified claim of threefold repetition of position*,
or by a verified claim of fifty consecutive moves having been played with
neither a capture nor a pawn move.

A better statement of rule 3 would be simply that the program must be capable
of recognizing when the game has ended, stop playing, and declare the outcome.

* A position is considered to have been repeated if and only if all the
following are true:
- it is the same player's turn to move each time
- each piece is on the same square (e.g. a position in which the king's and
queen's knights have traded places is a *different* position)
- each player has the same possible moves each time (e.g. if a rook has moved,
and then returned to its original square, that player may no longer castle
with that rook, and thus it's not the same position)

 

[Kaz Kylheku]

1.1 And if so, play a legal move, offer a draw, or resign.

2.1 and determine if that move is legal
2.2 and if not, complain in some fashion and await a legal move

That's no longer minimal. Minimal programs don't have to be robust.

You can make a program smaller by trimming its ability to cope with bad input,
but you cannot legitimately make a program smaller by trimming its ability to
deal with correct input. I.e. we can negotiate robustness against size.

Example: I once wrote assembly language using an assembler that crashed when
faced with an invalid opcode. The assembler worked fine as a back end for a
compiler.

This is incorrect. The game may be ended by the *program's* move, in at least
four ways:
a) the program's move checkmates the opponent
b) the program's move stalemates the opponent
c) the program's move makes it impossible for either player to win (e.g. the

How can any of these events happen, when our minimal program is contrived to
resign at the first opportunity?

Can the opponent checkmate or stalemate us with its one and only opening move?

I agree that these would be requirements for a minimal chess program (but one
that still resigns at first opportunity), if there is the additional
requirement that the program be able to play from any board configuration.