Chess - what is syntax and what is semantics?

G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

Hi!

I wonder what syntax and semantics is in the game of chess?

Perhaps a stupid question but I just saw an explanation of the syntax
and semantics of chess, it was as follows:

"In chess, syntax is knowing the legal moves, semantics knowing how to
play."

Is this true in the _exact_ sense of the words syntax and semantics?

IMHO, there is a formal language governing the game of chess. In formal
languages the syntax is unambigous. For instance: a rook being taken by
a bishop cannot duck or lie to save itself. It is taken. In
programming, by typing something with proper syntax semantic is
created, eg in C:

printf("hello world\n");

The semantic is that hello world is printed followed by a newline. But
semantics has nothing to do with knowledge. I could well be an idiot
who thought that printf means 'print to file', but what I believe does
not change the semantic.

Any suggestions?
/Sune
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

Thanks Dave,

is it then fair to say that both syntax and semantics of Algebraic
Notation are very basic, compared with, say, a programming language of
a type like C++ and Java?
I get that impression after looking into it...

/Sune
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

Sune <sune_ahlgren@hotmail.com> wrote:
> I wonder what syntax and semantics is in the game of chess?

Chess doesn't have syntax or semantics because it isn't a language.
Algebraic notation has syntax (rules that govern which strings of
characters are valid move descriptions) and semantics (rules that
tell you which move is described by a valid move description) but
chess doesn't.


Dave.

--
David Richerby Poetic Tool (TM): it's like a handy
www.chiark.greenend.org.uk/~davidr/ household tool but it's in verse!
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

My statement was based on the assumption what David said was correct
"...semantics (rules that tell you which move is described by a valid
move description).". I.e. a valid move doesn't need to be a clever
move, which means that as long as I adhere to the rules of piece
movements I don't have to read 1 page of chess literature.

Do you say that David is wrong? I'm curious.

BRs
/Sune
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

Sune wrote:

>is it then fair to say that both syntax and semantics of Algebraic
>Notation are very basic, compared with, say, a programming language of
>a type like C++ and Java?

That would *not* be fair to say. The syntax of Algebraic Notation (or
ant other popular chess notation) is quite simple - the syntax tells
you how to record the moves. The semantics is the game of Chess itself,
which is far from basic and has thousands of books written about it.
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

Sune wrote:

>My statement was based on the assumption what David said was correct
>"...semantics (rules that tell you which move is described by a valid
>move description).". I.e. a valid move doesn't need to be a clever
>move, which means that as long as I adhere to the rules of piece
>movements I don't have to read 1 page of chess literature.
>
>Do you say that David is wrong? I'm curious.

When applying a concept from language to a board game, it is
difficult to say that one application is right and annother wrong.
David explained what he means by "semantics" and so did I, so the
error was in applying David's definition to my post.
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

Guy Macon <_see.web.page_@_www.guymacon.com_> wrote:
> Sune wrote:
>> is it then fair to say that both syntax and semantics of Algebraic
>> Notation are very basic, compared with, say, a programming language of
>> a type like C++ and Java?
>
> That would *not* be fair to say. The syntax of Algebraic Notation (or
> ant other popular chess notation) is quite simple - the syntax tells
> you how to record the moves. The semantics is the game of Chess itself,
> which is far from basic and has thousands of books written about it.

No, the semantics is the move described by the string. To say that the
semantics of the notation is the game of chess is to make an error on a
similar as saying that the semantics of the phrase ``insert the disc and
press play'' is the entirety of music theory and composition.


Dave.

--
David Richerby Technicolor Pants (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ well-tailored pair of trousers but
it's in realistic colour!
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

Sune <sune_ahlgren@hotmail.com> wrote:
> is it then fair to say that both syntax and semantics of Algebraic
> Notation are very basic, compared with, say, a programming language of
> a type like C++ and Java?
> I get that impression after looking into it...

Pretty much, yes. Any algorithm can be expressed in C++ or Java; the same
is not true of algebraic notation.


Dave.

--
David Richerby Carnivorous Transparent Clock (TM):
www.chiark.greenend.org.uk/~davidr/ it's like a clock but you can see
right through it and it eats flesh!
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

David Richerby wrote:

>Any algorithm can be expressed in C++ or Java;

When did they upgrade C++ and Java to be universal turing machines?
My versions must be out of date - they lack the infinite amount of
storage that is required to express all algorithms. The infinite
address space is bad enough, but the infinite number of bits used
for addressing each location in that infinite address space is the
real killer...
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

Hi again David,

your explanations make sense, so here's another one for you:

It would seem that a game of chess has a fixed set of semantics between
every piece move(?). So in a sense of programming, this would imply
that for every piece move a chess player makes, he is rewriting his
program and plug it in the brain of his opponant for him to understand?

(I'm a programmer with no knowledge of game theory, I just try to
understand which is what in a board game.)

BRs
/Sune
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

Guy Macon a écrit :
> David Richerby wrote:
>
>
>>Any algorithm can be expressed in C++ or Java;
>
>
> When did they upgrade C++ and Java to be universal turing machines?
> My versions must be out of date - they lack the infinite amount of
> storage that is required to express all algorithms. The infinite
> address space is bad enough, but the infinite number of bits used
> for addressing each location in that infinite address space is the
> real killer...

In standard C++ (not in Java), as far as I know, there is no upper
limits for the amount of storage or the number of bits used to address a
location, only lower limits. So writing any algorithm is probably
feasible, although it is practically impossible to compile and run it,
but the same problem exists with a universal turing machine.

--
Richard
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

Guy Macon <_see.web.page_@_www.guymacon.com_> wrote:
> David Richerby wrote:
>> Any algorithm can be expressed in C++ or Java;
>
> When did they upgrade C++ and Java to be universal turing machines?
> My versions must be out of date - they lack the infinite amount of
> storage that is required to express all algorithms.

Not at all. The program can write to removable media and request that the
disc be changed as necessary. The discs can be labelled with the natural
numbers (integers if you want a two-way infinite tape) and the operator
can be instructed to load the ``next'' or ``previous'' disc. No Turing
machine needs an infinite amount of storage: an unbounded amount will do
just fine.


> The infinite address space is bad enough, but the infinite number of
> bits used for addressing each location in that infinite address space is
> the real killer...

You don't need an infinite number of bits to address the memory cells in
use because, at any stage, an algorithm can only have used up a finite
amount of memory. And Turing machines don't have addressing anyway.


Dave.

--
David Richerby Addictive Pointy-Haired Chair (TM):
www.chiark.greenend.org.uk/~davidr/ it's like a chair that's completely
clueless but you can never put
it down!
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

In article <jxp*trfYq@news.chiark.greenend.org.uk>,
David Richerby <davidr@chiark.greenend.org.uk> wrote:
> [...] The discs can be labelled with the natural
>numbers (integers if you want a two-way infinite tape)

No they can't; at least, not unless the discs are going to
get bigger with the labels. But, ...

> and the operator
>can be instructed to load the ``next'' or ``previous'' disc. [...]

... you don't need them to be, as long as they are ordered
[and the "current" disc -- or the place where it was before it was
mounted -- marked].

>You don't need an infinite number of bits to address the memory cells in
>use because, at any stage, an algorithm can only have used up a finite
>amount of memory.

True, but [again] not really the reason. The basic "moves"
in a UTM are "left" and "right". Anything else is just an efficiency
hack.

Positions in some forms of generalised chess [played on a
partially-unbounded board, eg one on which the "K-side" just keeps
going, with more and more files added as needed] can fairly easily
to be set up to emulate [in some sense] any computation, so are
universal. There are some [slightly] interesting chess problems
on such boards as well, eg how to mate with KRvK if the board has
only one corner. On a board with unboundedly-many rows, K&P endings
are mostly either draws or black wins, as white pawns can never
promote. But endings such as KPPvKR are interesting to analyse.

So, a generalised chess syntax is [surely] a perfectly good
general-purpose programming language, tho' not an easy one to write
programs in. As to the distinction between syntax and semantics, as
has already been said, this is a blurred-enough problem in "proper"
CS, much more a matter of convenience than of regulation; it's no
easier in chess.

--
Andy Walker, School of MathSci., Univ. of Nott'm, UK.
anw@maths.nott.ac.uk
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

Dr A. N. Walker <anw@maths.nott.ac.uk> wrote:
> David Richerby <davidr@chiark.greenend.org.uk> wrote:
>> [...] The discs can be labelled with the natural numbers (integers if
>> you want a two-way infinite tape)
>
> No they can't; at least, not unless the discs are going to get bigger
> with the labels. But, ...

Er, yes. Obviously I was thinking of the natural numbers in some sort of
platonic way. :) But the standard simulation of a tape with two stacks
will do nicely.


>> You don't need an infinite number of bits to address the memory cells
>> in use because, at any stage, an algorithm can only have used up a
>> finite amount of memory.
>
> True, but [again] not really the reason. The basic "moves" in a UTM are
> "left" and "right". Anything else is just an efficiency hack.

At that point, I was addressing (for want of a better word) the
misconception that, with a (countably) infinite amount of memory, one
would need an infinite number of bits to write down each address.


> Positions in some forms of generalised chess [played on a partially-
> unbounded board, eg one on which the "K-side" just keeps going, with
> more and more files added as needed] can fairly easily to be set up to
> emulate [in some sense] any computation, so are universal.

Positions can be set up to represent data structures but that's not the
same thing as computation. A 2-by-omega board with two rooks allows you
to represent the two registers of a register machine (see below for a
description) and two registers suffices for any computation.


> So, a generalised chess syntax is [surely] a perfectly good general-
> purpose programming language

No, because chess notation has no looping construct and the class of
loop-free programs is not universal.


Dave.

A quick description of register machines for anyone who's interested. The
machine consists of a finite number of registers R0, ..., Rn, each of
which holds a natural number. A program consists of a series of
instructions labelled with natural numbers. There are three kinds of
instruction:

Halt end the computation
Ri+ --> j Add 1 to Ri and jump to instruction j
Ri- --> j, k If Ri=0, jump to j; else, decrement Ri and jump to k

Jumps to non-existent instructions, by convention, halt the machine. The
machines are due to Marvin Minsky and can be shown to be Turing-complete.
It can also be shown that a machine with two registers can simulate any
other machine by using one register to code the simulated registers and
the other as workspace.

--
David Richerby Perforated Gerbil (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ children's pet but it's full of holes!
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

In article <yNz*0ugYq@news.chiark.greenend.org.uk>,
David Richerby <davidr@chiark.greenend.org.uk> wrote:
>> Positions in some forms of generalised chess [played on a partially-
>> unbounded board, eg one on which the "K-side" just keeps going, with
>> more and more files added as needed] can fairly easily to be set up to
>> emulate [in some sense] any computation, so are universal.
>Positions can be set up to represent data structures but that's not the
>same thing as computation. A 2-by-omega board with two rooks allows you
>to represent the two registers of a register machine (see below for a
>description) and two registers suffices for any computation.

That gives you a mechanism by which [eg] White can mess around
and emulate a computation [presumably while Black snoozes around by
shuffling his king and watching for 3-fold repetition -- we have to zap
the 50-move rule for this purpose!]. I was thinking rather of the
chess moves representing state changes in a TM. The standard proof
that chess is "exptime complete" shows some of the available mechanisms.
The idea would then be that for any given computation, more specifically
any decision problem, we can set up a starting position such that White
can force a win if and only if the decision problem returns "true".
Or, probably easier, such that this position is "legal" only if the
DP returns true. Generalising to other problems left as an exercise.

>> So, a generalised chess syntax is [surely] a perfectly good general-
>> purpose programming language
>No, because chess notation has no looping construct and the class of
>loop-free programs is not universal.

The description of a chess position has no loops, but the
record of a game may have. I'm thinking of those chess problems in
which, to win, White has to execute some complicated manoeuvre in
order to force [eg] Black to move a pawn, after which White has to
"reset" and then re-execute the manoevre to force another pawn move,
"repeat until" no more pawn moves, then Black must instead play a
weakening move allowing a new phase of the game.

Some of this might be easier as retro-analysis, because this
enables you to "uncapture" and hence create pieces. So a configuration
could creep along the board creating pawn chains that represent the
tape of the calculation. Note that there are non-erasing UTMs, in
which each square on the tape can switch only from 0 to 1.

--
Andy Walker, School of MathSci., Univ. of Nott'm, UK.
anw@maths.nott.ac.uk
 
G

Guest

Guest
Archived from groups: rec.games.chess.computer (More info?)

David Richerby wrote:
>
>Guy Macon <http://www.guymacon.com/> wrote:
>
>> David Richerby wrote:
>>> Any algorithm can be expressed in C++ or Java;
>>
>> When did they upgrade C++ and Java to be universal turing machines?
>> My versions must be out of date - they lack the infinite amount of
>> storage that is required to express all algorithms.
>
>Not at all. The program can write to removable media and request that the
>disc be changed as necessary. The discs can be labelled with the natural
>numbers (integers if you want a two-way infinite tape)

Bah! We don' need no steenkin two way tape!! A tape that is constrained
to be unerasable (write once, read many), and unbounded in one direction
only satisfies the the Church-Turing thesis.

>and the operator
>can be instructed to load the ``next'' or ``previous'' disc. No Turing
>machine needs an infinite amount of storage: an unbounded amount will do
>just fine.
>
>> The infinite address space is bad enough, but the infinite number of
>> bits used for addressing each location in that infinite address space is
>> the real killer...
>
>You don't need an infinite number of bits to address the memory cells in
>use because, at any stage, an algorithm can only have used up a finite
>amount of memory. And Turing machines don't have addressing anyway.

Point well taken. C does have addressing, but there is no reason why
a universal turing machine written in C would have to have addressing.
That was a silly mistake on my part. Thanks for the correction.

BTW, I don't think that labeling those disks/tapes will work - any
label with a finite amount of space on it would fill up - but I don't
think a label is required; just a row of unlabelled disks with an
empty space where the one currently in the drive goes.

It's nice to find out that my Commodore 128 is a universal turing
machine... Thanks!